Perfect Hashing

choice nodes need to match input against a fixed set of string alternatives. A naive linear scan costs O(k × n) for k options of length n. Instead, PackedParselets searches for a perfect hash at compile time: when one is found, it maps input to a candidate in O(1), reducing matching to a single verification step.

Candidate discovery

A "candidate" is a byte window (1, 2, 4, or 8 bytes) at some position within the options that uniquely distinguishes all of them when loaded as an unsigned integer.

options: ["alpha/", "beta/", "gamma/"]

1-byte window at position 0: ['a', 'b', 'g'] → unique ✓
1-byte window at position 4: ['a', '/', 'a'] → not unique ✗

With casefolding, bytes are OR-masked with 0x20 before comparison.

Hash families

Each candidate's distinct values are fed through hash functions, searching for one that produces unique outputs in a small range. In order of preference:

-Identity :: the loaded value directly. This is the simplest, and it's injective: a bounds check alone confirms the match (see below). -Mod :: v mod m + 1. -Shift-mod :: (v >> k) mod m + 1. -Multiply-shift-mod :: (v × c) >> k mod m + 1 with well-chosen constants.

The search is cost-ranked across all candidates and hash families, keeping the lowest-cost result. The hash-to-index mapping is classified as direct (hash values are consecutive, so the index is a single subtraction) or table (a compile-time tuple maps hash values to option indices). Direct mappings cost less, and the search stops early when an optimal (zero-cost) hash is found.

Verification

A perfect hash identifies which option the input might be, but unrecognised input could still produce a valid-looking index. Verification confirms the match using word-sized comparisons against a precomputed table of expected byte values.

For variable-length options, the minimum-length prefix is verified by word-sized comparison, and tail bytes beyond the minimum are verified separately: word-sized when all tails share a length, byte-by-byte otherwise. When variable-length options share trailing bytes (aligned from the end), those bytes are checked as a constant using pos + optlen addressing, potentially eliminating per-option tail verification entirely.

When enough already-parsed bytes precede pos, a single register load wider than the option length can verify all bytes at once, with the overflow masked to 0x00.

Injective optimisation

When the hash comes from the identity family, the loaded bytes are the hash value. A successful bounds check already guarantees they match a known option. The optimiser determines which verification bytes overlap with the hash window and skips them, reducing or eliminating verification loads.

Bucketed fallback

With many options, a collision-free hash into a small table becomes unlikely even when every option has a distinct window value (e.g. the 39 two-letter arXiv cs.* classes). For enough options, the search is then repeated accepting hashes that send up to two options to a slot, with second candidates in a parallel table. Matching verifies the first candidate and, only if that fails, the second: one hash and at most two verifications, instead of a scan. With fewer options the unrolled linear matcher (which LLVM often compiles to a switch) measured as fast or faster on varied input, so bucketing needs 8 options of equal length, or 16 of mixed lengths: the hash path must then also look up the matched option's length and check its tail bytewise. Window values stay distinct, so at most one option in a slot can match.

Linear scan fallback

When no hash applies, options are tried longest-first (so a failed longer option falls through to one of its prefixes) as an unrolled chain of length checks and register-sized comparisons.