โ๏ธ
Two-Clocks Measurement Model (Modeled vs. Measured)
This interactive DAG simulates the structural execution pipeline (node forms and algorithm branch paths from crates/expanse/src; branch levels and bytes per key only where the engine census and memory budget, both recomputed by test_visualizer_sync.rs, have the cell). 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 word + 7-byte aux + 8-bit type tag.
Root-Level Leaf Pop โค 31
Flat sorted keys. Zero trie overhead, monotonic append.
JPM / Tree Root Pop โฅ 32
Top edge + tree population; the Sync wrappers add a tree version word.
Top-Level Branch Level 8
256-ary digital trie router dispatching digit 8.
Branch L3/L7 Fanout 1..7
L3: 3 byte compares. L7: presence filter + 8-byte SSE2 / NEON compare.
Bitmap Branch B Fanout 8..192
256-bit bitmap + 8 subarray pointers (POPCNT).
Branch U Fanout > 192
4160 B flat table. Direct O(1) array index.
Immediate Pop 1..15
Keys inside the edge; a map with โฅ 2 keys allocates its values.
Linear Leaf Pop โค 25 / 32
Unrolled, SSE2 / NEON or binary search by key width and pop.
Bitmap Leaf Pop 21..256
256-bit bitmask; the map form adds 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. A population count over the digit's 32-bit subexpanse word gives the array slot index:
slot = (sub_word & below).count_ones() (Bitmap256::subexpanse_rank; POPCNT where the target has it, a SWAR sequence otherwise).
Branch Levels by Population and Distribution (engine census)
Depth depends on how keys spread, not on N alone: a branch exists only where an expanse holds more keys than a leaf takes (
LEAF_CAP = 32), and a narrow pointer skips every level whose digit all keys below it share. Each card lists the slot levels that hold a branch node in an ExpanseSet built from the memory-budget key generators (ExpanseStats::branch_depth_histogram); no lookup passes more branch nodes than that. Recomputed from the engine by test_visualizer_sync.rs.
1,000 Keys
10,000 Keys
100,000 Keys
1,000,000 Keys
๐งฌ 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.11ร) (workload: workload_large_values; measured: reference host i9-12900F, commit 695b98d; benches/large_values.rs inline_vs_heap_small_blobs, point estimates without an interval โ large_value_benchmarks.inlining_speedups in docs/visualizer_data.json; docs/design/large-values.md ยง10.3). Payloads of 8..14 bytes that fit a codec (integers below 256, 8โ9 alphanumerics, 8โ14 decimal digits) also stay in the slot under the Compressed* tags (codec.rs) when their hot metadata is 0.
๐๏ธ 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 two-phase copying compaction (
compact_with_index): every live record is first copied into a fresh arena with a bumped generation, and only once all copies succeed are the trie value slots rewritten, so a failed relocation leaves arena and index untouched (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
Blocking optimistic lock coupling, not lock-free: a reader samples the tree version (spinning while it is odd), then reads each branch under that node's own version word, validating hand over hand; after 64 failed attempts (
MAX_RETRIES) it takes the writer mutex. 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 (x86-64-v3 build) | 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 build | 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: How the 256-ary Digital Trie Resolves a Key
Bitmaps + POPCNT โข SSE2/NEON Byte Compares โข In-Edge Immediates
1. Immediates: Keys Inside the Edge
An immediate edge packs key bytes into the 16-byte Edge itself: up to 15 payload bytes, so
15 / kb keys of kb bytes in a set (ImmedType::max_count). A map keeps its keys in the 7-byte aux field, 7 / kb of them (map_immed_max): one key keeps its value in word 0 with no allocation, and two or more point word 0 at an allocated value array.
2. Bitmask Rank (POPCNT)
Bitmap nodes split 256 digit positions into eight 32-bit subexpanses. A value or child slot is the population count of the digit's subexpanse word masked below the digit (
Bitmap256::subexpanse_rank): one load, a mask and a POPCNT where the target has it. BMI2 PDEP is used only for select (the k-th set bit), behind a runtime CPUID check.
3. Linear-Leaf Search by Key Width and Population
leaf.rs picks the kernel from the key width and the population: up to 4 keys, unrolled scalar compares; an 8- or 16-byte SSE2 compare for 1-byte keys at 5..8 and 13..16 keys, 2-byte keys at 5..8 and 4-byte keys at 3..4; binary search everywhere else. On x86-64 every band is SSE2; on AArch64 NEON covers the 1-byte equality searches at exactly 8 and 16 keys, and the other bands run a short scalar loop. The 16-byte lower bound biases both operands by 0x80 and uses _mm_cmplt_epi8 + _mm_movemask_epi8 + a popcount.
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.