diff options
Diffstat (limited to 'src/cuckoocache.h')
| -rw-r--r-- | src/cuckoocache.h | 27 |
1 files changed, 12 insertions, 15 deletions
diff --git a/src/cuckoocache.h b/src/cuckoocache.h index 15cb55c3ce..d0dc61c7e6 100644 --- a/src/cuckoocache.h +++ b/src/cuckoocache.h @@ -5,6 +5,8 @@ #ifndef BITCOIN_CUCKOOCACHE_H #define BITCOIN_CUCKOOCACHE_H +#include <util/fastrange.h> + #include <algorithm> // std::find #include <array> #include <atomic> @@ -219,13 +221,8 @@ private: * One option would be to implement the same trick the compiler uses and compute the * constants for exact division based on the size, as described in "{N}-bit Unsigned * Division via {N}-bit Multiply-Add" by Arch D. Robison in 2005. But that code is - * somewhat complicated and the result is still slower than other options: - * - * Instead we treat the 32-bit random number as a Q32 fixed-point number in the range - * [0, 1) and simply multiply it by the size. Then we just shift the result down by - * 32-bits to get our bucket number. The result has non-uniformity the same as a - * mod, but it is much faster to compute. More about this technique can be found at - * https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ . + * somewhat complicated and the result is still slower than an even simpler option: + * see the FastRange32 function in util/fastrange.h. * * The resulting non-uniformity is also more equally distributed which would be * advantageous for something like linear probing, though it shouldn't matter @@ -241,14 +238,14 @@ private: */ inline std::array<uint32_t, 8> compute_hashes(const Element& e) const { - return {{(uint32_t)(((uint64_t)hash_function.template operator()<0>(e) * (uint64_t)size) >> 32), - (uint32_t)(((uint64_t)hash_function.template operator()<1>(e) * (uint64_t)size) >> 32), - (uint32_t)(((uint64_t)hash_function.template operator()<2>(e) * (uint64_t)size) >> 32), - (uint32_t)(((uint64_t)hash_function.template operator()<3>(e) * (uint64_t)size) >> 32), - (uint32_t)(((uint64_t)hash_function.template operator()<4>(e) * (uint64_t)size) >> 32), - (uint32_t)(((uint64_t)hash_function.template operator()<5>(e) * (uint64_t)size) >> 32), - (uint32_t)(((uint64_t)hash_function.template operator()<6>(e) * (uint64_t)size) >> 32), - (uint32_t)(((uint64_t)hash_function.template operator()<7>(e) * (uint64_t)size) >> 32)}}; + return {{FastRange32(hash_function.template operator()<0>(e), size), + FastRange32(hash_function.template operator()<1>(e), size), + FastRange32(hash_function.template operator()<2>(e), size), + FastRange32(hash_function.template operator()<3>(e), size), + FastRange32(hash_function.template operator()<4>(e), size), + FastRange32(hash_function.template operator()<5>(e), size), + FastRange32(hash_function.template operator()<6>(e), size), + FastRange32(hash_function.template operator()<7>(e), size)}}; } /** invalid returns a special index that can never be inserted to |