|
From: Josef W. <Jos...@gm...> - 2007-07-20 11:03:12
|
On Friday 20 July 2007, Christoph Bartoschek wrote: > Am Freitag, 20. Juli 2007 schrieb Nicholas Nethercote: > > On Thu, 19 Jul 2007, Christoph Bartoschek wrote: > > > I've looked at some tracebacks and I see that the current hashtable with > > > 30011 entries is too small for the program. > > > > A general comment: there's a module m_oset.c which defines the OSet type. > > It implements an AVL tree. When I added it, it was intended to replace the > > Vg_HashTable type, the idea being that it would scale better as it had no > > fixed limits. But it turned out to have noticeable worse constant factors, > > and most people aren't running programs nearly as large as the ones you > > are, so the Vg_HashTable is still used. It might be worth trying the OSet > > instead of the Vg_HashTable for some of these structures. The interfaces > > are pretty similar. > > My experience shows that a dynamically resizing hashtable performs better than > an AVL tree. As long as one does not guaranteed access times and sorted > iteration over the set there is no reason to use an AVL tree. That is my understanding, too. I pretty much would like a general resizable hash table in Valgrind core; something like the one you posted (in topic "Long valgrind runtimes"). I use them a lot in callgrind for different structures, but have my own implementation(s). However, Vg_HashTable uses a simply key for entry comparision, which is not enough in some cases. What about an optional comparision callback? Josef |