4 ms·
Once we constrain the size of our integers - which most hashtable implementations do implicitly by only using numbers that are natively supported by hardware -
by scott_s 17y ago
Once we constrain the size of our integers - which most hashtable implementations do implicitly by only using numbers that are natively supported by hardware - number multiplication is once again a constant.
From the other direction, if a hashtable implementation uses arbitrarily sized numbers to compute hashes, it probably has bad design.
- lemire 17y agoPlease consider vectorization. Natively, modern processors can multiply several 16-bit integers in the time it takes to multiply one pair of 64-bit integers.
- scott_s 17y agoI am considering vectorization. There is always a maximum number of native values that can be operated on at one time by the processor. The maximum cycle costs are also known. Between the two of those, we have a maximum time spent on the computation, and it is a constant. Considering the size of numbers during algorithm analysis matters when the numbers are huge - that is, when the numbers are larger than the maximum values that can be represented natively by the processor. When that happens, "numbers" become a data structure unto themselves and must be analyzed as such.