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/include/pub_tool_oset.h b/include/pub_tool_oset.h
index 687d34f..2e79448 100644
--- a/include/pub_tool_oset.h
+++ b/include/pub_tool_oset.h
@@ -72,9 +72,9 @@
typedef struct _OSet OSet;
-// - Cmp: returns -1, 0 or 1 if key is <, == or > elem.
+// - Cmp: returns -1, 0 or 1 if key is <, == or > elem.
// - Alloc: allocates a chunk of memory.
-// - Free: frees a chunk of memory allocated with Alloc.
+// - Free: frees a chunk of memory allocated with Alloc.
typedef Word (*OSetCmp_t) ( const void* key, const void* elem );
typedef void* (*OSetAlloc_t) ( HChar* ec, SizeT szB );
@@ -219,6 +219,11 @@
// * ResetIter: Each OSet has an iterator. This resets it to point to the
// first element in the OSet.
//
+// * ResetIterAt: Like ResetIter, but instead of resetting the iterator to the
+// smallest element, it resets the iterator to point to the smallest element
+// in the set whose key is greater-than-or-equal to the given key. (In many
+// cases this will be the element whose key equals that of the given key.)
+//
// * Next: Returns a pointer to the element pointed to by the OSet's
// iterator, and advances the iterator by one; the elements are visited
// in order. Or, returns NULL if the iterator has reached the OSet's end.
@@ -238,19 +243,15 @@
extern Word VG_(OSetGen_Size) ( const OSet* os );
extern void VG_(OSetGen_Insert) ( OSet* os, void* elem );
-extern Bool VG_(OSetGen_Contains) ( const OSet* os, const void* key );
-extern void* VG_(OSetGen_Lookup) ( const OSet* os, const void* key );
+extern Bool VG_(OSetGen_Contains) ( const OSet* os, const void* key );
+extern void* VG_(OSetGen_Lookup) ( const OSet* os, const void* key );
extern void* VG_(OSetGen_LookupWithCmp)( OSet* os,
const void* key, OSetCmp_t cmp );
-extern void* VG_(OSetGen_Remove) ( OSet* os, const void* key );
+extern void* VG_(OSetGen_Remove) ( OSet* os, const void* key );
extern void VG_(OSetGen_ResetIter) ( OSet* os );
+extern void VG_(OSetGen_ResetIterAt) ( OSet* os, const void* key );
extern void* VG_(OSetGen_Next) ( OSet* os );
-// set up 'oset' for iteration so that the first key subsequently
-// produced VG_(OSetGen_Next) is the smallest key in the map
-// >= start_at. Naturally ">=" is defined by the comparison
-// function supplied to VG_(OSetGen_Create).
-extern void VG_(OSetGen_ResetIterAt) ( OSet* oset, const void* key );
#endif // __PUB_TOOL_OSET_H