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 _______________________________________________ es-discuss mailing list [email protected] https://mail.mozilla.org/listinfo/es-discuss
