boost::openmethod::policies::minimal_cover_hash

Map type ids to indexes by extracting a minimal cover of their bits.

Synopsis

Declared in <boost/openmethod/policies/minimal_cover_hash.hpp>

template<std::size_t MaxBits = 24>
struct minimal_cover_hash
    : type_hash

Description

minimal_cover_hash implements the type_hash policy as H(x) = pext(x, mask): the bits of x selected by mask, packed into the low popcount(mask) positions by BMI2's parallel bit extract, one instruction. The index range is [0, 2ˆpopcount(mask))].

mask is a minimal cover: a smallest‐found set of bit positions such that x & mask is still injective over the registered type ids. That is exactly the condition for pext to be injective, so the search never needs pext itself. Unlike fast_perfect_hash's randomized multiplier search it is deterministic, and it finishes in milliseconds on inputs where that search gives up:

the bits that vary at all are trivially a cover;
a greedy pass drops bits, lowest entropy first, while injectivity holds;
a second greedy pass builds a cover bottom‐up, adding the bit that resolves the most collisions each time, then trims it the same way;
the smaller of the two wins.

**Choose it when dispatch must not get slower but the default search is a problem.** One pext costs about what a multiply and a shift cost, so dispatch is as fast as with fast_perfect_hash; what this buys is a table found deterministically, in bounded time. Its footprint is comparable to fast_perfect_hash{empty}'s ‐ both widen when the type ids are sparse, and for the same reason ‐ so it is not the policy to pick for memory. minimal_perfect_hash is.

Type ids from different modules differ in many high bits, but those bits are perfectly correlated, since they all encode which module. The cover keeps about log2(modules) of them and the rest cost nothing, so a program that dlopen{empty}s modules pays one extra bit rather than an unusable table.

BMI2 is required, and that is not a portable requirement. pext requires a 64‐bit x86 target ‐ it is absent on ARM and on 32‐bit x86 altogether, absent on x86‐64 before Haswell and Excavator, and is microcoded on AMD Zen 1 and Zen 2 ‐ around 18 cycles rather than 3 ‐ where this policy will be slower than the default rather than faster. Because hash is inlined into every dispatch, ‐mbmi2 (or a ‐march= implying it) has to be set for every translation unit of the program, and of any module sharing the registry, not just one; a binary built with it executes an illegal instruction on the first dispatch on a CPU that lacks pext. MSVC is the exception: it emits the instruction from the intrinsic on any 64‐bit target, and takes no flag; clang‐cl is not MSVC here, and wants ‐mbmi2 or /arch:AVX2. Naming this policy in a registry where BOOST_OPENMETHOD_HAS_PEXT is 0 is a compile error. minimal_perfect_hash is the portable alternative, at a cost of a nanosecond or two per call.

After "Perfect Hashing in an Imperfect World", Joaquin M. Lopez Munoz.

Example

// Needs BMI2, for every translation unit of the program - hence the guard.
#if BOOST_OPENMETHOD_HAS_PEXT
struct cover_registry :
    default_registry::with<policies::minimal_cover_hash<>> {};
#endif