|
fc658755
|
2011-02-22T21:59:36
|
|
Rewrite git_hashtable internals
The old hash table with chained buckets has been replaced by a new one
using Cuckoo hashing, which offers guaranteed constant lookup times.
This should improve speeds on most use cases, since hash tables in
libgit2 are usually used as caches where the objects are stored once and
queried several times.
The Cuckoo hash implementation is based off the one in the Basekit
library [1] for the IO language, but rewritten to support an arbritrary
number of hashes. We currently use 3 to maximize the usage of the nodes pool.
[1]: https://github.com/stevedekorte/basekit/blob/master/source/CHash.c
Signed-off-by: Vicent Marti <tanoku@gmail.com>
|