Lookup - CIB Guide — michael.caisse.io

The idea

A hash map spends its life hedging: it doesn’t know the keys, so it needs a hash that behaves well on anything, buckets that might collide, and a “not found” path on every query. When the keys are known at build time, all of that hedging is waste.

lookup takes the keys as data, picks a search strategy for those keys at compile time, and hands back a constexpr object with one operation. The hash it picks doesn’t have to be good in general — only collision-free for your keys and cheap to compute.

You write input

A default value and an array of key/value entries. Plain data, no types to implement.

The compiler picks strategy

Linear scan for a handful of entries; otherwise a hash built from the bits that actually distinguish your keys.

You get table[key]

A total function. Every key returns something; absent keys return the default.

The decision happens once, in the compiler, from your keys. What ships is a table and a few instructions.

Quick start

opcode → name

#include <lookup/lookup.hpp>
#include <stdx/utility.hpp>   // CX_VALUE

constexpr auto opcode_names = lookup::make(CX_VALUE(
    lookup::input<std::uint32_t, char const *, 3>{
        "unknown",                                   // the default value
        std::array{lookup::entry{0x10u, "read"},
                   lookup::entry{0x20u, "write"},
                   lookup::entry{0x30u, "erase"}}}));

opcode_names[0x20u];   // "write"
opcode_names[0x99u];   // "unknown" — every key returns something

Link cib_lookup; it depends only on stdx. No logging, no nexus, no fmt.

The API

Piece	What it is
`lookup::entry{k, v}`	One key/value pair
`lookup::input<K, V, N>{def, arr}`	The table as data: a default plus `N` entries. Deduces from `lookup::input(def, array)`
`lookup::make(CX_VALUE(in))`	Build, choosing a strategy
`table[key]`	The only operation. Returns `V`; never fails
`lookup::strategies<Ts...>`	Try strategies in order
`lookup::strategy_failed(t)`	Did that strategy decline?

lookup::make is simply:

include/lookup/lookup.hpp, in full

strategies<linear_search_lookup<4>, pseudo_pext_lookup<true, 2>>::make(input);

Four entries or fewer become a scan; anything larger goes to pseudo-pext. Verified: a 3-entry make yields exactly the type linear_search_lookup<4>::make produces. Name a strategy directly when you want a different trade-off.

Keys and values

Keys become raw bits via bit_cast, so they must be 8 bytes or smaller. Integers, enums and floats all work.
Float keys normalize signed zero: -0.0 and +0.0 hit the same entry (verified).
Values are anything trivially copyable — including stdx::bitset, which is how msg stores sets of eligible callbacks (verified), and function pointers, which turn a table into a dispatch table.
Sparse keys cost nothing extra. Keys from 1 to 4,000,000,000 in one table came to 80 bytes (verified); the table never spans the key range.
Duplicate keys aren’t rejected. The input is data, not a set; under linear search the last match wins (verified). Deduplicate before building.

Strategies

Strategy	How a query works	Reach for it when
`linear_search_lookup<MaxSize>`	Branchless select across every entry	Very few entries, or keys that resist hashing. Declines inputs larger than `MaxSize`
`pseudo_pext_lookup<false, …>`	Extract key bits, index the value table directly	Fewest instructions per query; largest table
`pseudo_pext_lookup<true, N>`	Extract key bits, index an index table, then the values	The default. `N` caps how long a search may get

What “pseudo-pext” means

Look at the keys as raw bits and find a mask of bit positions that tells them apart. Most bits are the same across all keys and carry no information.
Extract and compact those bits — a software stand-in for x86’s pext instruction, which is why the strategy is named after it.
Use the compacted value as an index. Because the keys are fixed, the compiler can check that this is collision-free for them, and try again with a different mask if it isn’t.

This is why “bad” hash functions are fine here: the only requirements are cheapness and collision-freedom on a known, finite key set.

Key-bits bench

Pick a key set and see which bits actually distinguish it. The selected bits are the ones a pseudo-pext hash extracts; the rest are dead weight that a general-purpose hash would still churn through.

which bits matter

The bench finds a small set of bit positions that separates every key — the same job the strategy does at compile time.

Key set

key bits

mask

index bits

direct table

keys → index

A general-purpose hash map would hash all 32 bits and then compare keys to resolve collisions. Here the compiler knows there are none.

When a strategy declines

A strategy that can’t handle an input doesn’t fail the build — it returns strategy_failed_t, which is what lets strategies<...> move on to the next candidate.

declining is a value, not an error

constexpr auto t = lookup::linear_search_lookup<2>::make(
    CX_VALUE(lookup::input<int, int, 3>{ /* three entries */ }));
static_assert(lookup::strategy_failed(t));   // it declined: too many entries

When building tables generically, branch on it:

generic table building

constexpr auto t = some_strategy::make(CX_VALUE(input));
if constexpr (not lookup::strategy_failed(t)) { /* use t */ }

Rest of cib

Library	Coupling	What passes between them
msg	the consumer	Indexed dispatch builds one table per indexed field, mapping a field value to a `stdx::bitset` of eligible callbacks. The default value is the bitset for “value not in the table”. Handling a message is a lookup per field plus a bitset intersection.
stdx	link	`CX_VALUE`, `bitset`, bit utilities. The only dependency.
benchmark/lookup	comparison	The same key sets through `std::map`, `std::unordered_map`, frozen and mph, with `tools/benchmark/gen_map_data.py` generating the data.

Use cases

Constant maps

Opcode to name, error code to message, register address to width. The default value carries the “unknown” case, so call sites have no miss path.

Dispatch tables

values can be function pointers

constexpr auto handlers = lookup::make(CX_VALUE(
    lookup::input<std::uint32_t, void (*)(), 3>{
        &unhandled,
        std::array{lookup::entry{0x10u, &on_read},
                   lookup::entry{0x20u, &on_write},
                   lookup::entry{0x30u, &on_erase}}}));

handlers[opcode]();   // always callable: unknown opcodes reach &unhandled

Sets of indices

Values needn’t be scalars. Map a key to a stdx::bitset and intersect the results of several tables — precisely msg’s indexed dispatch.

Sparse, wide key spaces

Hardware IDs scattered across a 32-bit space don’t need a 4-billion-entry array or a hash map: a handful of entries stays in tens of bytes.

Choosing deliberately

When a table is hot, benchmark it with your real keys rather than trusting the default. benchmark/lookup/ already has the harness and the competitors wired up.

Pitfalls

Symptom	Cause	Fix
`no matching function for call to 'make'`	Input not wrapped	`lookup::make(CX_VALUE(input))`
`strategy_failed_t does not provide a subscript operator`	Every strategy declined	Use `lookup::make`, or widen the bounds (§7)
`cannot form a reference to 'void'` inside `<array>`	Key type wider than 8 bytes	Use a smaller key, or hash it yourself first
An absent key silently returns a plausible value	Tables are total; the default is returned	Choose a default that reads as “absent”
Two entries with the same key, one ignored	Duplicates aren’t rejected	Deduplicate before building
The table seems to be rebuilt each call	It’s a local, not a `constexpr`	`constexpr static` inside the function, or a namespace-scope `constexpr`
Compile time climbs on a big table	The strategy is searching for a workable mask	Lower `MaxSearchLen`, or accept the direct form’s larger table