Module cardinality_pointer 

CardinalityPointer<T> - pointer with the cardinality of its target’s reachable set encoded in stolen high bits.

Layout: a single u64 where the top 8 bits hold log2(cardinality_of_target) and the low 56 bits hold the address (mask: 0x00FF_FFFF_FFFF_FFFF). 56 bits address 64 PiB of virtual memory which is well above any current process.

The architectural win

Database query planners, ECS world walkers, and graph databases all want a quick estimate of “how big is the thing this points to” BEFORE deciding the algorithm:

• Tiny set (<= 8 elements) -> linear scan
• Medium (<= 1024) -> sort-merge
• Large (> 1M) -> hash join

Without CardinalityPointer you either keep cardinality in a parallel metadata table (extra cache line per lookup) or dereference the pointer just to read the size field (full cache miss when the target is cold). Embedding log2(cardinality) in the pointer itself eliminates both costs - the planner branches directly on the high byte of the pointer with no dereference.

Bit budget

• 8 bits in the high byte: log2(cardinality) ranges 0..=255, so cardinalities up to 2^255 are encodable. (Realistic cardinalities cap around 2^40, so 6-7 of those bits will always be zero in practice; remaining bits are reserved for future use.)
• 56 bits of address: enough for any single process on x86_64 (current canonical addresses are 48 bits) and Apple Silicon (Top Byte Ignored hardware accepts 56-bit pointers natively).

Portability

On AArch64 with Top Byte Ignored enabled (Apple Silicon, modern Linux on ARM), the hardware automatically masks the top byte on every dereference, so no explicit masking is needed. On x86_64 the CardinalityPointer::as_raw accessor explicitly masks the address before exposing it. This module ships the portable masked variant; a hardware-TBI fast path can be added when cross-platform cfg blocks are available.

Structs

CardinalityPointer

8-byte pointer with log2(cardinality) packed into the high byte.

Enums

SizeTier

Coarse cardinality tier for branching decisions.

Constants

ADDR_MASK

Top byte of the u64 is the cardinality encoding; low 56 bits are the address.

CARD_SHIFT