Am Samstag, 8. Dezember 2007 schrieb Julian Seward: > > Yes. The relation established by the comparison function has to be > > transitive. This is not the case here. Therefore the function should not > > be used. > > > > I've shown how this affects the AVL tree in theory and implementation. > > This also fits one fact that Tom gives: There have to be additional > > additions and deletions to the tree till the values are not found. > > Below is a test program which compares comparison functions through > exhaustive testing. It shows immediately that the slow (reference) > and fast versions produce different results. > > We can fix Memcheck by falling back to the reference version, but I'd > like to see if there is a way to get the correct behaviour without > the extra conditionals.
I would propose that you use a hashtable for the entries with one of the already used hashfunctions. You would get the following two benefits: - An amortized O(1) access time instead of O(log(n)) for all operations. - For some big programs (the ones I run) more than 70% of the memory consumption of memcheck is for the entries of secVBitTable2. Using a hashtable (preferably with a memory pool for the entries or a space efficient memory manager) would save about 16-24 bytes per entry. Christoph ------------------------------------------------------------------------- SF.Net email is sponsored by: Check out the new SourceForge.net Marketplace. It's the best place to buy or sell services for just about anything Open Source. http://sourceforge.net/services/buy/index.php _______________________________________________ Valgrind-developers mailing list Valgrind-developers@lists.sourceforge.net https://lists.sourceforge.net/lists/listinfo/valgrind-developers
