Eric Blake <e...@byu.net> writes:
> There might also be alternative implementations possible with
> better performance. For example, instead of malloc'ing free
> entries one at a time and tracking bucket overflows as pointers
> to malloc'd objects, we could instead malloc/realloc an array
> of overflows, with bucket overflows tracked as indices into
> that array.
An approach that is even better than allocating groups of entries
is to make the hash table's client allocate the entries as part
of the data items that it intends to put into the hash table.
Then you completely get rid of an allocation, instead of just
amortizing it.
GNU PSPP has a hash table library that supports this model. The
header file has a lot of details on how it works:
http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/hmap.h
http://git.savannah.gnu.org/cgit/pspp.git/tree/src/libpspp/hmap.c
http://git.savannah.gnu.org/cgit/pspp.git/tree/tests/libpspp/hmap-test.c
Of course, this would require an interface change, so I wouldn't
expect gnulib's hash table to switch to this model. But it might
be worth supporting as an alternative.
--
Only wimps use tape backup: _real_ men just upload their important stuff
on ftp, and let the rest of the world mirror it ;)
-- Linus Torvalds
