diff options
Diffstat (limited to 'src/cuckoocache.h')
| -rw-r--r-- | src/cuckoocache.h | 43 |
1 files changed, 37 insertions, 6 deletions
diff --git a/src/cuckoocache.h b/src/cuckoocache.h index 5837549455..947e1a7185 100644 --- a/src/cuckoocache.h +++ b/src/cuckoocache.h @@ -2,8 +2,8 @@ // Distributed under the MIT software license, see the accompanying // file COPYING or http://www.opensource.org/licenses/mit-license.php. -#ifndef _BITCOIN_CUCKOOCACHE_H_ -#define _BITCOIN_CUCKOOCACHE_H_ +#ifndef BITCOIN_CUCKOOCACHE_H +#define BITCOIN_CUCKOOCACHE_H #include <array> #include <algorithm> @@ -58,7 +58,7 @@ public: * @post All calls to bit_is_set (without subsequent bit_unset) will return * true. */ - bit_packed_atomic_flags(uint32_t size) + explicit bit_packed_atomic_flags(uint32_t size) { // pad out the size if needed size = (size + 7) / 8; @@ -176,7 +176,7 @@ private: */ mutable std::vector<bool> epoch_flags; - /** epoch_heuristic_counter is used to determine when a epoch might be aged + /** epoch_heuristic_counter is used to determine when an epoch might be aged * & an expensive scan should be done. epoch_heuristic_counter is * decremented on insert and reset to the new number of inserts which would * cause the epoch to reach epoch_size when it reaches zero. @@ -184,7 +184,7 @@ private: uint32_t epoch_heuristic_counter; /** epoch_size is set to be the number of elements supposed to be in a - * epoch. When the number of non-erased elements in a epoch + * epoch. When the number of non-erased elements in an epoch * exceeds epoch_size, a new epoch should be started and all * current entries demoted. epoch_size is set to be 45% of size because * we want to keep load around 90%, and we support 3 epochs at once -- @@ -206,6 +206,37 @@ private: /** compute_hashes is convenience for not having to write out this * expression everywhere we use the hash values of an Element. * + * We need to map the 32-bit input hash onto a hash bucket in a range [0, size) in a + * manner which preserves as much of the hash's uniformity as possible. Ideally + * this would be done by bitmasking but the size is usually not a power of two. + * + * The naive approach would be to use a mod -- which isn't perfectly uniform but so + * long as the hash is much larger than size it is not that bad. Unfortunately, + * mod/division is fairly slow on ordinary microprocessors (e.g. 90-ish cycles on + * haswell, ARM doesn't even have an instruction for it.); when the divisor is a + * constant the compiler will do clever tricks to turn it into a multiply+add+shift, + * but size is a run-time value so the compiler can't do that here. + * + * 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 results has non-uniformity the same as a + * mod, but it is much faster to compute. More about this technique can be found at + * http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ + * + * The resulting non-uniformity is also more equally distributed which would be + * advantageous for something like linear probing, though it shouldn't matter + * one way or the other for a cuckoo table. + * + * The primary disadvantage of this approach is increased intermediate precision is + * required but for a 32-bit random number we only need the high 32 bits of a + * 32*32->64 multiply, which means the operation is reasonably fast even on a + * typical 32-bit processor. + * * @param e the element whose hashes will be returned * @returns std::array<uint32_t, 8> of deterministic hashes derived from e */ @@ -447,4 +478,4 @@ public: }; } // namespace CuckooCache -#endif +#endif // BITCOIN_CUCKOOCACHE_H |