boost::openmethod::policies::minimal_perfect_hash

Map type ids to a dense index with a minimal perfect hash.

Synopsis

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

template<
    std::size_t Lambda = 4,
    std::size_t LoadPercent = 95,
    std::size_t MaxSeeds = 16>
struct minimal_perfect_hash
    : type_hash

Description

minimal_perfect_hash implements the type_hash policy by hash and displace, after Belazzougui, Botelho and Dietzfelbinger, without the compression step:

h = x * seed;                          // one multiply
p = pilots[h >> bucket_shift];         // this bucket's pilot
index = mulhi(h * p, slots);           // displace, then reduce

The type ids are split into n / Lambda buckets by the top bits of h. Buckets are placed largest first; each is given a 32‐bit odd pilot, found by trial, such that multiplying the key by it sends every id in the bucket to a slot that is still free. The final reduction is a multiply‐shift ‐ the top half of a 64x64 product ‐ which maps onto [0, slots)] for any slots without a division.

Choose it when the table size matters more than the last nanosecond. Unlike fast_perfect_hash, whose table is sized by the distribution of the type ids and whose randomized search can fail outright on a large, sparse set, this one spends 8 * n * 100 / LoadPercent bytes of v‐table vector plus 4 * n / Lambda bytes of pilots whatever the addresses are, and its search time depends only on how many type ids there are, not where they sit. That makes it the policy to reach for in a program that `dlopen`s modules registering classes of their own, where type ids from different modules are far apart and in unrelated ranges.

The price is on the dispatch path: the pilot must be loaded before the index can be formed, so the v‐table lookup becomes two dependent loads instead of one. Expect it to cost a nanosecond or two per call relative to fast_perfect_hash.

It needs no instruction‐set extension ‐ a 64‐bit multiply and a shift exist everywhere ‐ and makes no assumption about the layout of the type ids, so unlike minimal_cover_hash it is available on every target, and unlike a scheme keyed on address arithmetic it does not depend on std_rtti.

A type id of zero is outside this policy's domain. Zero is a fixed point of a multiply, so it lands in slot 0 for every seed and every pilot; it cannot be displaced, and the search fails whenever another bucket has taken that slot. Addresses are never zero, so std_rtti and static_rtti are unaffected; a custom rtti policy that hands out small integers must not use zero as one of them. When the registry has runtime_checks, initialize asserts that none of the registered type ids is zero.

LoadPercent = 100 asks for an exactly minimal table. It is reachable, but not in bounded time at a large Lambda: the last buckets have to hit the last few free slots, and the expected number of trials for a bucket of size s facing a fraction phi of free slots grows as phiˆ‐s. A few percent of slack removes that tail. Note also that an exactly minimal table is not the smallest total: reaching it needs the buckets halved, which doubles the pilot array, and that costs more than the slots it recovers.

Example

// One slot per type id, whatever the addresses are. Swapping the hash is all it
// takes: `with` replaces the policy of the same category, in place, so
// `vptr_vector` still comes after it.
struct compact_registry :
    default_registry::with<policies::minimal_perfect_hash<>> {};

Base Classes

Name

Description

type_hash

Policy for hashing type ids.

Types

Name

Description

search_error

No seed yielded a complete assignment.

no_checks

state layout when runtime checks are disabled.

with_checks

state layout when runtime checks are enabled: adds the table of registered type ids used to validate hashed types.

fn

A TypeHashFn metafunction.

Type Aliases

Name

errors

Template Parameters

Name

Description

Lambda

Average bucket size. Larger means a smaller pilot table and a longer search.

LoadPercent

Slots per 100 type ids, inverted: 100 is an exactly minimal table, 95 leaves one slot free in twenty.

MaxSeeds

How many multipliers to try before reporting search_error. Raising it rarely helps on its own ‐ a set that defeats one multiplier usually defeats them all at that Lambda and LoadPercent; lower Lambda or LoadPercent instead.

See Also

Registries and Policies

Created with MrDocs