boost::openmethod::policies::two_level_hash

Map type ids to an index with two multiply‐shifts.

Synopsis

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

template<
    std::size_t Lambda = 4,
    std::size_t MaxDoublings = 3>
struct two_level_hash
    : type_hash

Description

two_level_hash implements the type_hash policy with a per‐bucket multiplier into a shared power‐of‐two table:

h     = m1 * x;                  // mix once
h1(x) = h >> s1;                 // which bucket, 2^b of them
h2(x) = (m2[h1(x)] * h) >> s2;   // the index, into 2^t slots

The first level is one imperfect multiply‐shift into a fixed number of buckets; the second is a per‐bucket multiplier, found by trial, that sends every id in its bucket to a slot that is still free.

It is minimal_perfect_hash with one thing changed: where that reduces with the top half of a product, onto a table of any size, this one shifts, onto a table whose size is a power of two. The shift is the cheaper of the two where the compiler hoists the shift amount out of the dispatch loop, which is worth about a nanosecond per call; where it reloads it on every call the two cost the same. Both are slower than fast_perfect_hash.

What the power‐of‐two table costs is a sawtooth: it holds 2ˆceil(log2(n)) slots, so between 1.0 and 2.0 per type id depending on where n falls relative to a power of two, against a flat 100 / LoadPercent for minimal_perfect_hash. Which of the two is smaller is decided by the class count, which a program does not usually control. Prefer minimal_perfect_hash when the footprint has to be predictable, and this one when the dispatch path matters more.

The second multiply has to be applied to h, not to x itself. Two type ids in one module are a few tens of bytes apart, so m2 * x differs between them by about m2 * 16; for a 32‐bit m2 that is below 2ˆ(64 ‐ t), the shift discards it, and the two land on the same slot for every multiplier the search can try. Multiplying the already‐mixed h costs nothing, since h is ready long before m2 arrives from the table.

Like minimal_perfect_hash this needs no instruction‐set extension and makes no assumption about the layout of the type ids.

A type id of zero is outside this policy's domain, exactly as it is for minimal_perfect_hash. Zero is a fixed point of both multiplies, so it lands in slot 0 whatever m1 and the per‐bucket multiplier are, and the search fails whenever another bucket has taken that slot. Addresses are never zero; a custom rtti policy handing out small integers must not use zero. When the registry has runtime_checks, initialize asserts that none of the registered type ids is zero.

Example

struct two_level_registry :
    default_registry::with<policies::two_level_hash<>> {};

Base Classes

Name

Description

type_hash

Policy for hashing type ids.

Types

Name

Description

search_error

No table within MaxDoublings doublings admitted 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.

MaxDoublings

How far the table may grow past the smallest power of two that could hold the type ids, before search_error is reported. The cap is relative to the class count deliberately: an absolute one lets a pathological input ask for a table orders of magnitude larger than the program needs.

See Also

Registries and Policies

Created with MrDocs