Changeset View
Changeset View
Standalone View
Standalone View
src/cuckoocache.h
Show First 20 Lines • Show All 225 Lines • ▼ Show 20 Lines | private: | ||||
* One option would be to implement the same trick the compiler uses and | * 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 | * 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. | * 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 | * Robison in 2005. But that code is somewhat complicated and the result is | ||||
* still slower than other options: | * still slower than other options: | ||||
* | * | ||||
* Instead we treat the 32-bit random number as a Q32 fixed-point number in | * 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 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 | * 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 | * non-uniformity the same as a mod, but it is much faster to compute. More | ||||
* about this technique can be found at | * about this technique can be found at | ||||
* http://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/ | * 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 | * The resulting non-uniformity is also more equally distributed which would | ||||
* be advantageous for something like linear probing, though it shouldn't | * be advantageous for something like linear probing, though it shouldn't | ||||
* matter one way or the other for a cuckoo table. | * matter one way or the other for a cuckoo table. | ||||
* | * | ||||
▲ Show 20 Lines • Show All 263 Lines • Show Last 20 Lines |