4 ms·
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?
by TorKlingberg 10y ago
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?
- jbapple 10y agox86-64 has single instruction (MUL) that produces a 128-bit unsigned result by multiplying two unsigned 64-bit operands.
- gpderetta 10y agoIn 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.
- TorKlingberg 10y agoSure N (number of buckets) shouldn't be too big, but x (the input value) could be.
- 79d697i6fdif 10y agorealistically 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