|
From: Christoph B. <bar...@gm...> - 2007-07-11 22:19:23
|
Hi, I've looked into the profile after the first fix, that I sent earlier this day, and have seen that the method vgPlain_HT_remove took lots of runtime in my testcase program. The cause is a too small hashtable and chains of up to 99 elements. Therefore I have changed the m_hashtable.c implementation to automatically expand itself if the density of the hash reaches 75% (or 60% in a test). The implementation has at least the following flaws: - The primes are from http://planetmath.org/encyclopedia/GoodHashTablePrimes.html and stop at 31 bits. - One has to call VG_(HT_destruct)(VgHashTable table) because there are two allocations for each table. - There is an additional indirection for the chains array. One could get rid of it but would have to change the HT_add_node interface. Here are the runtimes on an Opteron 2.6GHz machine for the testcase from an earlier post: Native: 25 s Revision 6765 - tool=none: 59 s Revision 6765 - tool=memcheck: 7711 s Superblock fix - none 58 s Superblock fix - memcheck: 903 s Superblock + Hashtable 75% - none: 59 s Superblock + Hashtable 75% - memcheck: 423 s Superblock + Hashtable 60% - none: 59 s Superblock + Hashtable 60% - memcheck: 392 s Greetings Christoph |