Deterministic hash table benchmarks

David Bruant bruant.d at gmail.com
Fri Feb 24 12:16:29 PST 2012


Hi Jason,

Thanks for sharing this work.

Le 24/02/2012 19:43, Jason Orendorff a écrit :
> I wrote a benchmark and tested an implementation of Tyler Close's
> deterministic hash table against some conventional, non-deterministic
> ones.
>
> Tyler Close's table is faster, but it uses more memory.
"For any large enough number of entries N, a CloseTable with N entries
allocates either 1.0625x or 2.125x as much memory"
=> Based on your diagram, it seems that it's more often 1.0625 than 2.125.
However, I'm not sure I understand any of these number. As you point
out, "CloseTable entries are 50% larger", so I would expect that for a
large number of entries, CloseTables would be 1.5x bigger than
OpenTables (maybe more due to the additional pointer table).
What explains the 1.0625?


> Details and graphs:
>   https://wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
One missing benchmark is on enumerating the elements.


> Source code:
>   https://github.com/jorendorff/dht
A few comments:
table.cpp lines 274 and 299, you're calling the 2-arguments version of
lookup. I think it's the only place where it's the case. I'm not sure
changing this will affect performance since the lookup functions are
declared to be inlined.


> These results are very raw. Take a look at the code. See if there are
> simple ways to improve the performance of either hash table. Or
> explain to me why CloseTable is faster even though it's doing more
> work.
Ideas en vrac:

* As you point out for the last benchmark, locality could be one
explanation.
* You're compiling with -O3. Maybe there is some optimization the
compiler does with the CloseTable it doesn't do with OpenTable.
* Specifically for the lookups:
"i = (i + (h | 1)) & mask;" looks to be more work than "e = e->chain".

> Or why the DeleteTest results are so weird.
No clue on this one :-s

David


More information about the es-discuss mailing list