Fix bug #191182, where printing the leak checker results was really slow if
there were a lot of loss records.
The fix was:
- Avoid the O(m * n) looping over the chunks when creating the loss
records, by putting loss records into an OSet instead of a list, which
makes duplicate detection for each chunk an O(log n) operation instead of
an O(n) operation.
- Avoid the looping over loss records which was used to do a poor
man's sort, but was O(n^2). Instead copy pointers to the loss records
from the OSet into an array and sort it normally with VG_(ssort) (n log n,
usually) before printing.
This approach was similar to that used in the patch Philippe attached to the
bug report.
Other changes:
- Added Philippe's test programs in the new memcheck/perf directory. It
used to take 57s on my machine, now it takes 1.6s.
- Cleaned up massif/perf/Makefile.am to be consistent with other Makefiles.
- Improved some comments relating to VgHashTable and OSet.
- Avoided a redundant traversal of the hash table in VG_(HT_to_array), also
identified by Philippe..
- Made memcheck/tests/mempool's results independent of the pointer size, and
thus was able to remove its .stderr.exp64 file.
git-svn-id: svn://svn.valgrind.org/valgrind/trunk@9781 a5019735-40e9-0310-863c-91ae7b9d1cf9
diff --git a/memcheck/mc_include.h b/memcheck/mc_include.h
index 6d4cc07..74c36a7 100644
--- a/memcheck/mc_include.h
+++ b/memcheck/mc_include.h
@@ -230,13 +230,15 @@
typedef
enum {
- Unreached =0, // Not reached, ie. leaked.
- // (At best, only reachable from itself via a cycle.
- IndirectLeak =1, // Leaked, but reachable from another leaked block
- // (be it Unreached or IndirectLeak).
- Possible =2, // Possibly reachable from root-set; involves at
+ // Nb: the order is important -- it dictates the order of loss records
+ // of equal sizes.
+ Reachable =0, // Definitely reachable from root-set.
+ Possible =1, // Possibly reachable from root-set; involves at
// least one interior-pointer along the way.
- Reachable =3 // Definitely reachable from root-set.
+ IndirectLeak =2, // Leaked, but reachable from another leaked block
+ // (be it Unreached or IndirectLeak).
+ Unreached =3, // Not reached, ie. leaked.
+ // (At best, only reachable from itself via a cycle.)
}
Reachedness;
@@ -262,17 +264,23 @@
}
LeakCheckMode;
+/* When a LossRecord is put into an OSet, these elements represent the key. */
+typedef
+ struct _LossRecordKey {
+ Reachedness state; // LC_Extra.state value shared by all blocks.
+ ExeContext* allocated_at; // Where they were allocated.
+ }
+ LossRecordKey;
+
/* A loss record, used for generating err msgs. Multiple leaked blocks can be
* merged into a single loss record if they have the same state and similar
* enough allocation points (controlled by --leak-resolution). */
typedef
struct _LossRecord {
- struct _LossRecord* next;
- ExeContext* allocated_at; // Where they were allocated.
- Reachedness state; // LC_Extra.state value shared by all blocks.
- SizeT szB; // Sum of all MC_Chunk.szB values.
- SizeT indirect_szB; // Sum of all LC_Extra.indirect_szB values.
- UInt num_blocks; // Number of blocks represented by the record.
+ LossRecordKey key; // Key, when used in an OSet.
+ SizeT szB; // Sum of all MC_Chunk.szB values.
+ SizeT indirect_szB; // Sum of all LC_Extra.indirect_szB values.
+ UInt num_blocks; // Number of blocks represented by the record.
}
LossRecord;