|
From: Christoph B. <bar...@or...> - 2007-07-20 00:12:49
|
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. Christoph |