News for hackers. Stuff that matters.
Re:Modern Minimal Perfect Hashing: A Survey by o11c on Tuesday June 10, 2025 @11:52PM (#44244045)
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.
Re:Modern Minimal Perfect Hashing: A Survey by mananaysiempre on Wednesday June 11, 2025 @01:43AM (#44244529)
I’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.
Re:Modern Minimal Perfect Hashing: A Survey by duskwuff on Wednesday June 11, 2025 @02:10AM (#44244661)
This 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?)
Re:Modern Minimal Perfect Hashing: A Survey by thomasmg on Wednesday June 11, 2025 @07:20AM (#44246393)
Using 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...

Re:Modern Minimal Perfect Hashing: A Survey by tmyklebu on Wednesday June 11, 2025 @09:07AM (#44247201)
Two fast (today) instructions:

  unsigned h = _pext_u32(1264523 * x, 0x1020a01);
Re:Modern Minimal Perfect Hashing: A Survey by tmyklebu on Wednesday June 11, 2025 @09:26AM (#44247401)
Same 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.
Re:Modern Minimal Perfect Hashing: A Survey by mananaysiempre on Wednesday June 11, 2025 @10:24PM (#44253751)
Where does the constant multiplier come from? Is it just bruteforced, or is there an idea behind it that I can’t see?
Re:Modern Minimal Perfect Hashing: A Survey by tmyklebu on Saturday June 14, 2025 @10:01PM (#44280072)
Yeah, 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.

Re:Modern Minimal Perfect Hashing: A Survey by mananaysiempre on Monday June 16, 2025 @04:56AM (#44287733)
> For a bit in m*x to be useful, it must be zero for 16 symbols and one for 16 symbols.

Ahh brilliant, thanks!