Deterministic hash table benchmarks
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: wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
One missing benchmark is on enumerating the elements.
Source code: 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 :
On Fri, Feb 24, 2012 at 2:16 PM, David Bruant <bruant.d at gmail.com> wrote:
"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.
Yes, it's more often 1.0625.
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?
An OpenTable always allocates a single power-of-2-sized chunk of memory.
A CloseTable makes two allocations: a power-of-2-sized chunk for the data, and a smaller one (1/16 the size on 32-bit platforms, 1/8 the size on 64-bit platforms) for the hash table. So the Close table can be 1+1/16 as big as an OpenTable, and that's 1.0625 (or 1+1/8=1.125 on 32-bit platforms).
Both tables double in size as the number of entries increase. An OpenTable doubles each time the load factor reaches 0.75; a CloseTable doubles when it's completely full. It turns out this causes the CloseTable to double earlier, and that is why the factor is sometimes 2×1.0625=2.125 (or 2.25 on 64-bit platforms).
I hope this is clear.
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.
Details and graphs: wiki.mozilla.org/User:Jorend/Deterministic_hash_tables
Source code: jorendorff/dht
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. Or why the DeleteTest results are so weird.