4 ms·
I'm only vaguely aware of how other people do perfect hashing (generators I've used always seem to produce arrays to load from), but dabbled in a purely-arithme
by o11c 1y ago
I'm only vaguely aware of how other people do perfect hashing (generators I've used always seem to produce arrays to load from), but dabbled in a purely-arithmetic toy problem recently.
As an exercise for the reader:
There are exactly 32 symbols in ASCII:
!"#$%&'()*+,-./:;<=>?@[\]^_`{|}~
Taking input in a register, uniquely hash them to the range 0-31.
Any other input values may return any number, but must not
trap or exhibit undefined behavior. The obvious approach of
"just make a 256-element array" isn't allowed.
This can be done in few enough cycles that you need to
carefully consider if there's any point to including:
loads (even hitting L1)
branches (even if it fully predicts when it is taken)
multiplication (unless just using lea/add/shift)
I found that out-of-order only helps a little; it's
difficult to scatter-gather very wide in so few cycles.
Writing C code mostly works if you can persuade the compiler
not to emit an unwanted branch.
- mananaysiempre 1y agoI’m tempted to emulate a conventional SIMD solution and go with a small lookup table: uint8_t classify(uint8_t c) { return c - (0x5F45452B2B210000ULL >> ((c & 0x70) >> 1)); } The AND-then-shift sequence on the right is annoying and it feels like one should be able to avoid it, but I don’t see how. Overall, this is more expensive than it looks—neither a full 64-bit constant nor a variable 64-bit shift are exactly free. So I’m probably missing something here.
- duskwuff 1y agoThis set of symbols has some interesting properties which allow for this solution: func symbolHash(c byte) byte { x := (c - 1) >> 5 y := int(c) + 0x1b150000>>(x<<3) return byte(y & 31) } But this doesn't generalize - it depends on the input consisting of a couple runs of consecutive characters which can be made continuous. (Extra credit: why is "c-1" necessary?)
- thomasmg 1y agoUsing a brute-force approach can quickly find a minimal perfect hash table. Eg. the RecSplit approach can be used for this case, to first split into 4 sections, and then use another one for each section. Or, in this case, the same one for each section: (hash(c + 4339104) & 7) * 4 + (hash(c + 201375) & 3) For a generic hash function (eg the Murmur hash, or the simple one here: long hash(long x) { x = ((x >>> 16) ^ x) * 0x45d9f3b; x = ((x >>> 16) ^ x) * 0x45d9f3b; x = (x >>> 16) ^ x; return x; } As described in the linked paper, the fastest way to find such a MPHF for larger sets is nowadays Consensus-RecSplit. [1] https://stackoverflow.com/questions/664014/what-integer-hash-function-are-good-that-accepts-an-integer-hash-key/12996028#12996028 https://stackoverflow.com/questions/664014/what-integer-hash...
- tmyklebu 1y agoTwo fast (today) instructions: unsigned h = _pext_u32(1264523 * x, 0x1020a01);
- tmyklebu 1y agoSame idea, but without BMI2: unsigned h = (1264523 * x & 0x1020a01) * 134746240 >> 27; Alternatively: unsigned h = (1639879 * x & 0x1038040) * 67375104L >> 32 & 31; The multiplication by 67375104L can be a usual 32x32 IMUL where the high half goes to edx, though I'm not sure that conveys a benefit over a 64x64 IMUL in serial code these days.
- mananaysiempre 1y agoWhere does the constant multiplier come from? Is it just bruteforced, or is there an idea behind it that I can’t see?
- tmyklebu 1y agoYeah, that was just a search. There are 2^32 multipliers; call them m. For a bit in m*x to be useful, it must be zero for 16 symbols and one for 16 symbols. Call those bits "useful bits." Try every multiplier; for each multiplier, compute all the useful bits (usually not many) and try all masks with 5 useful bits.
- mananaysiempre 1y ago> For a bit in m*x to be useful, it must be zero for 16 symbols and one for 16 symbols. Ahh brilliant, thanks!