Re:I Wrote My Fastest Hashtable
by TorKlingberg on Monday February 27, 2017 @08:48AM
(#13744086)
This is fine if you are working with 32-bit numbers on a CPU with fast 64-but multiplication. What if you have 64-bit numbers?
[ Parent
| on HN ]
x86-64 has single instruction (MUL) that produces a 128-bit unsigned result by multiplying two unsigned 64-bit operands.
In addition to what jbapple said, if your hash map has more than 2^32 buckets, the latency of the division is the last of your problem.
Re:I Wrote My Fastest Hashtable
by TorKlingberg on Monday February 27, 2017 @10:22AM
(#13744854)
Sure N (number of buckets) shouldn't be too big, but x (the input value) could be.
Re:I Wrote My Fastest Hashtable
by 79d697i6fdif on Monday February 27, 2017 @10:10AM
(#13744752)
realistically any hash table bigger than the 32 bit boundary will be well outside any CPU caches and possibly even ram. At these sizes the memory latency will dwarf CPU speed