βοΈ
Two-Clocks Measurement Model (Modeled vs. Measured)
This interactive DAG simulates the structural execution pipeline (active trie depth, algorithm branch paths, and theoretical instruction ceilings) derived from crates/expanse/src/mutate.rs. Exact cycle and instruction measurements in the Benchmark tab are recorded independently via Valgrind/Callgrind harnesses (crates/expanse/benches/instructions.rs) on dedicated quiet hardware. Modeled estimates guide structural understanding; Callgrind counts are deterministic empirical truth.
π² Structural Hierarchy & Component Routing DAG
Click any node for struct layout & code specs
Judy Array Pointer JAP
16-byte Edge: pointer/immediate + 3-bit type tag.
Root-Level Leaf Pop β€ 31
Flat sorted keys. Zero trie overhead, monotonic append.
JPM / Tree Root Pop β₯ 32
Total population + OCC sequence counter + top branch.
Top-Level Branch Level 8
256-ary digital trie router dispatching digit 8.
Branch L3/L7 Fanout 1..7
SWAR / SIMD 16-byte digit scan with packed JPs.
Bitmap Branch B Fanout 8..180
256-bit bitmap + 8 subarray pointers (POPCNT).
Branch U Fanout > 180
2048 B flat table. Direct O(1) array index.
Immediate Pop 1..7
0 B heap: payload inlined in pointer.
Linear Leaf Pop 2..25
128-bit SIMD vector scan (AVX2/NEON).
Bitmap Leaf Pop 26..256
256-bit bitmask + 8 value subarrays.
Full Expanse Pop = 256
Null child pointer, 256 full density (Set).
β‘ Active Execution Pipeline & Algorithm Trace
π² Digital Trie Level Hierarchy & 8-Way Subarray Architecture
Active Depth: 1 Level
A 64-bit key is partitioned into 8 8-bit digits (
d8..d1). Each level in the digital trie routes one digit via an adaptive node form.
64-Bit Key Digit Breakdown & Active Traversal Path:
Bitmap Subexpanse Architecture (256 bits β 8 Subarrays Γ 32 bits)
POPCNT Rank Acceleration
Each 256-ary branch/leaf splits 256 keys into 8 32-bit subexpanses. Hardware POPCNT computes the array slot index:
slot = _mm_popcnt_u64(sub_bitmap & mask).
Multi-Level Trie Scaling: 1K vs 10K vs 100K vs 1M vs 10M Keys
1,000 Keys
2 Levels (d8 β d7 β Leaf)
Root JPM dispatches Digit 8 to Level 7 Branch. Subarray edges directly point to terminal Bitmap/Linear Leaves.
10,000 Keys
3 Levels (d8 β d7 β d6 β Leaf)
Level 7 branch subarray pointers descend into Level 6 branches before terminating at leaves.
100,000 Keys
5 Levels (d8 β d7 β d6 β d5 β d4)
Cascading intermediate branches. Memory stays compact at 0.36 B/k (set) and 8.56 B/k (map).
1,000,000 Keys
8 Levels (Full 64-bit Depth)
Full 8-level trie depth. Sequential Run Bypass skips all 8 levels directly to LeafB1 on monotonic streams.
10,000,000 Keys
8 Levels (Dense Fanout / L3βDRAM Boundary)
Dense multi-million scale trie spanning 64-bit address space. L3 cache / DRAM boundary.
𧬠Polymorphic 64-Bit Value Slots (
ValueSlot)
In Judy arrays and classical trie designs, 64-bit integer maps (JudyL) store raw integers, requiring a separate heap pointer and heap allocation for any variable-length payload. Expanse modernizes value storage by introducing Polymorphic 64-bit Value Slots with transparent discriminants.
β‘ Inline Payload (0..7 Bytes)
[payload_byte_6..0 (56b) | tag (8b)]
Small strings and byte payloads (UUIDs, status codes, short IDs) are stored directly inside the 64-bit leaf slot with 0 heap allocation. Measured 7-byte-payload lookup: 5.68 ns vs 29.00 ns for
BTreeMap<u64, Vec<u8>> (5.10Γ) β docs/design/large-values.md Β§10.3.
ποΈ ArenaMeta (24-bit Hot Meta + 32-bit Locator)
[hot_meta (24b) | arena_locator (32b) | tag 0x10]
The sole arena encoding (
SlotTag::ArenaMeta, replacing the former ArenaShort/ArenaLong pair): a 32-bit 16-byte-granular locator plus 24-bit hot metadata (TTL, timestamp, partition ID), so a predicate can be evaluated without fetching cold payload cache lines.
π¦ Chunked Slab Arena (
BlobArena)BlobRecordHeader { len: u32, generation: u32 }
Bump-allocated slabs with 16-byte alignment and 8-byte generation headers, plus a single-pass in-place mark-compact GC that relocates live records and rewrites their trie value slots (compaction pause times: 72β371 Β΅s with BCa 95% CIs across 5kβ20k entries,
results/baseline_large_values.json).
π Multi-Writer Optimistic Lock Coupling (
SyncExpanseMap)Stage B Multi-Writer OLC + Zero-Sharing Path + EBR
Zero reader locking on uncontended paths, hand-over-hand optimistic lock coupling for concurrent writers on disjoint expanses (Phases 4A, 4D, 4C: in-place mutations, BranchB subarray growth, and concurrent leaf capacity expansion with speculative abort recycling), and Epoch-Based Memory Reclamation.
πͺΆ 32-Bit Microprocessor Layout (
Edge32)[word0_ptr (4B) | aux (3B) | tag (1B)] = 8 Bytes
50% edge memory reduction for embedded ARM Cortex-M and RISC-V RV32 microcontrollers, fitting comprehensive routing tables directly in tight internal SRAM.
ποΈ Drop-In C-Compat ABI Benchmark Matrix: libexpanse.so vs Stock libjudy (Legacy C)
Source:
crates/expanse-capi/benches/vs_stock.rs (docs/BENCHMARKING.md). Drop-in ABI comparison under Valgrind/Callgrind on identical key streams. Ratio = ours Γ· stock (Ratio < 1.00x means libexpanse retires fewer instructions).
These are instructions retired, not wall clock. Fewer instructions does not imply a lower latency: on the quiet reference host libexpanse measures 1.031Γ slower (BCa 95% CI [1.024, 1.038]) on random 1M lookup while winning sequential/clustered insert and lookup. An earlier ~11% (1.11Γ) figure published here predates the harness repair and is superseded, not adjusted. The wall-clock figures once published in this table (“45% faster than Stock Judy”, 26.8 ns vs 48.6 ns on
judyl_get/random_big) were never measured — they are these instruction counts rescaled by a single constant (~5.52 instr/ns fits both arms to 0.26%) — and are retracted. Instruction ratios are not timings: 0.55× instructions and a 1.031× wall-clock loss are simultaneously true. Why random costs more than sequential is unmeasured; a counter run on this arm records 0.042 LLC misses per probe against 2.74 branch mispredicts per probe, so the DRAM-latency-bound reading once given here is refuted β the open mechanism is tracked in #480. See docs/BENCHMARKING.md.
| Status | Operation | Flavor | Distribution / Scope | Population | libexpanse .so (v1) | libexpanse .so (v3 AVX2) | Stock libjudy | Ratio (.so) | v1 β v3 Delta |
|---|
π Callgrind Deterministic Benchmark Dataset (50,000 Operations per Test)
Source:
crates/expanse/benches/instructions.rs evaluated under Valgrind/Callgrind in CI. Exactly reproducible instruction counts with L1/LL/RAM cache simulation.
| Workload | Category | Flavor | Instructions (v1) | Instr / Op | x86-64-v3 (AVX2/BMI2) | Hardware Delta | L1 Hits | RAM Hits | Algorithm / Mechanism |
|---|
β‘ Standardized YCSB Workload Benchmark Suite (N = 100k, Zipfian ΞΈ = 0.99)
Standardized Yahoo! Cloud Serving Benchmark (YCSB) evaluation comparing
ExpanseBlobMap against BTreeMap<u64, Box<[u8]>> and RocksDB MemTable model (crossbeam_skiplist::SkipMap). Measured across 128-byte blob payloads.
| Workload | Workload Ratio | ExpanseBlobMap (Mops/s) | BTreeMap (Mops/s) | SkipMap MemTable (Mops/s) | Speedup vs BTree | Speedup vs SkipMap | p99 Latency (Expanse) | Memory / Key |
|---|
π Large-Value Inlining, Predicate Filtering & GC Compaction Benchmarks
Demonstrates polymorphic 64-bit value slot optimizations: inlined payload acceleration (0..7 bytes without heap allocation), metadata-predicate scan selectivity, and slab compaction times.
| Optimization / Payload Band | Expanse Latency | Baseline Latency | Speedup | Heap Allocations | Architectural Impact |
|---|
πΎ Deterministic Memory Budget Matrix (Bytes / Key)
All Under Budget Ceilings
Source:
crates/expanse/examples/bytes_per_key.rs. Every cell is mem_used() / len β deterministic allocator accounting, machine-independent β and is recomputed from the engine and asserted by tests/test_visualizer_sync.rs. Map includes the 8-byte value per key (u64). Budget ceilings are the committed regression guards in that example.
| Distribution | Set (1k) | Set (100k) | Set (1M) | Map (1k) | Map (100k) | Map (1M) | Budget Ceiling (1M, set / map) | Key Generator |
|---|
πͺΆ Embedded 32-Bit Microprocessor Memory Census
Deterministic allocator accounting
Source:
crates/expanse/examples/bytes_per_key_32.rs (docs/design/32-bit-embedded.md). Every cell is mem_used() / N on the real 32-bit trie β deterministic and machine-independent, and recomputed from the engine by tests/test_visualizer_sync.rs. No comparative baseline is published: none is measured.
| Embedded Workload | Structure | Keys (N) | Measured B/key | mem_used() | Key Generator |
|---|
π Node Capacity & Lifecycle Promotion Ladder
Source:
crates/expanse/src/types.rs, node.rs, leaf.rs. Lifecycle transitions between immediate, linear, bitmap, and uncompressed representations.
| Node Type | Capacity Band | Size / Alignment | Search Algorithm & SIMD | Promotion Rule | Demotion Rule (Hysteresis) |
|---|
βοΈ Under The Hood: Why 256-ary Digital Radix Tries Outperform Search Trees
AVX2 Bitmaps β’ POPCNT β’ In-Pointer Immediate Leaves
1. Zero Heap Overhead for Small Populations (0 B)
For 1β7 keys in Map (or 1β15 keys in Set), Expanse encodes key bytes and values directly inside the 16-byte Edge pointer (tagged pointer). Zero allocations, zero heap indirection, and 100% cache-resident.
2. Single-Cycle Bitmask Rank (POPCNT / BMI2)
Bitmap leaves compress 256 key positions into eight 32-bit subexpanses. Value slot offsets are computed in 1 single CPU instruction (
POPCNT) by counting set bits below the query digit, eliminating binary search tree pointer chasing.
3. SIMD 128-bit Vectorized Linear Scan
In
LEAF_LINEAR (8β25 keys), keys are scanned using 128-bit vector instructions (_mm_cmplt_epi8 / vdupq_n_u8) in 2 instructions without branches, outperforming binary search at small scales.
ISA guarantees for these kernels (SSE2/NEON/POPCNT/Zbb), the 64-byte cache-line and 57-bit VA assumptions, and missed-opportunity analysis are cited against primary-source manuals in docs/HARDWARE.md.