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.
d8..d1). Each level in the digital trie routes one digit via an adaptive node form.
slot = (sub_word & below).count_ones() (Bitmap256::subexpanse_rank; POPCNT where the target has it, a SWAR sequence otherwise).
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.
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.
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.
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.
BlobArena)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).
SyncExpanseMap)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.
Edge32)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).
cbbc762a, while every JudyLGet arm below retires fewer instructions than stock (workloads differ: capi_vs_stock vs capi_bench_vs_libjudy). Random 1M lookup, once a loss at 1.031ร (BCa 95% CI [1.024, 1.038], commit 4c4e852a, now superseded), measures 0.825ร [0.821, 0.827] and 0.828ร [0.825, 0.832] (results/baseline_vs_libjudy.json). 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. The cause of the sequential 100k loss is unmeasured. On the random arm, a counter run at 5f0dd3d5 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 |
|---|
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 |
|---|
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 |
|---|
| Optimization / Payload Band | Expanse Latency | Baseline Latency | Speedup | Heap Allocations | Architectural Impact |
|---|
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 |
|---|
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 |
|---|
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) |
|---|
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.
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.
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.