Stefan Sperling <stsp@stsp.name> wrote:
> We currently call malloc() to allocate a qid for every hash table insertion.
> This is necessary because each hash table slot contains a linked-list head
> which cannot store an element. The head can only point at the first element
> in the list.
> 
> If we instead store an object ID and a list head in our hash table array,
> the first element which hashes into a slot can be inserted by copying
> it directly into the slot. We only need to call malloc/free on insertion
> when a hash collision occurs.
> 
> The larger the table, the less likely collisions will be. So I hope this
> will help the object ID set scale better to very large sets for which
> the hash table will continue to grow (until it can no longer grow further
> due to memory limits).
> 
> Freeing the table becomes faster because all non-colliding hash table
> elements can be freed together during a single call to free().
> 
> One downside is that growing the table can now fail with a memory
> allocation failure. The workaround is to first copy collisions into the
> new table which should reduce memory used for those object IDs since the
> new table is larger and should be able to store more elements without
> collisions (unless we hit a theoretical worst case where all elements
> hash to more or less the same slot).
> 
> ok?

ok op@

> M  include/got_object.h  |    1+   0-
> M  lib/object_idset.c    |  223+  67-
> 
> 2 files changed, 224 insertions(+), 67 deletions(-)
> 
> commit - 4a2f8fe319b0c00f773ccf2db4b0b4ee2ef33dcc
> commit + 406637c13c3af719b1bf2a43b454491a98505cac