Expanse

Expanse Engine Β· Architecture & Benchmark Intelligence Callgrind & Code Verified Rust 2024 / AVX2

Real-time mapping of digital trie architecture, SIMD vector execution flow, and deterministic Callgrind instruction measurements
βš–οΈ Expanse Modern vs Stock Judy Baseline
Sequential Run Bypass eliminates 8 levels of tree descent (~80 instructions saved).
1.7x Advantage
🌲 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).
Sub 0
Bits 0..31
Sub 1
Bits 32..63
Sub 2
Bits 64..95
Sub 3
Bits 96..127
Sub 4
Bits 128..159
Sub 5
Bits 160..191
Sub 6
Bits 192..223
Sub 7
Bits 224..255
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, delivering 13.4 ns lookups (4.34x faster).
πŸ›οΈ Arena Short (32-bit Hot Meta + 24-bit Offset)
[hot_meta (32b) | arena_offset (24b) | tag 0x10]
Combines 24-bit offset into 16 MiB slab arena with 32-bit hot metadata (TTL, timestamp, partition ID), enabling vectorized range filtering without fetching cold payload cache lines.
πŸ“¦ Chunked Slab Arena (BlobArena)
BlobRecordHeader { len: u32, generation: u32 }
Bump-allocated 2 MiB / 16 MiB slabs with 16-byte alignment and 8-byte generation headers. Includes in-place mark-compact GC consolidating live records in sub-millisecond pause times.
πŸ”’ Lock-Free OCC Concurrency (SyncExpanseMap)
Optimistic Version Bracketing + EBR
Zero reader locking, wait-free point gets, and Epoch-Based Memory Reclamation ensuring departed readers never stall concurrent writer progress.
πŸͺΆ 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 does less work).
Status Operation Flavor Distribution / Scope Population libexpanse .so (v1) libexpanse .so (v3 AVX2) Stock libjudy Ratio (.so) Ratio (rlib) Est. Cycles (.so) Hardware Delta Architectural Invariant & Win Rationale
πŸ“Š 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. Map includes 8-byte value per key (u64). All values measured under 64-bit architecture.
Distribution Set (1k) Set (100k) Set (1M) Map (1k) Map (100k) Map (1M) Budget Ceiling Dominant Node Form & Mechanism
πŸͺΆ Embedded 32-Bit Microprocessor Memory & Invariant Census SRAM Invariants 100% Passing
Source: crates/expanse/benches/embedded.rs & examples/bytes_per_key_32.rs (docs/RFC_32BIT_EMBEDDED.md). Evaluates 32-bit compact Edge32 layout (8B) and 32-byte cache alignment on ARM Cortex-M, ESP32, and RISC-V RV32 microcontrollers.
Embedded Workload Keys (N) Expanse 32-Bit std::collections BTree SRAM Advantage Microcontroller Architecture Impact
πŸ“š 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.