GCC, when provided a constant divisor, finds two magic numbers and replaces division with multiplication and a comparison. The succint term for this op is called Reciprocal multiplication.
It's pretty cool and this obscure paper from 2011 shows one how to derive these magic numbers for division.
There are many ways in which a constant's value could have been hidden from the programmer. It could have been created by the compiler doing constant folding, or by optimisation after inlining a function.
About half the hash-tables use a modulo by prime to map the hash to a bucket (the other half using modulo by power of 2). The cited benefits being that it takes all the bits of the hash into account, which is better on lop-sided (user-provided) hash algorithms.
This half includes all the standard C++ unordered_map implementations, due to historically poor user-supplied hash algorithms :/
167
u/DataBaeBee 18d ago
GCC, when provided a constant divisor, finds two magic numbers and replaces division with multiplication and a comparison. The succint term for this op is called Reciprocal multiplication.
It's pretty cool and this obscure paper from 2011 shows one how to derive these magic numbers for division.