Expanse: Modernized Judy Arrays

For the past few months, I have been deep in the weeds of sparse data structures. What started as a focused effort to cut worker memory in PHP with Judy arrays quickly turned into a major rabbit hole: vendorizing, fixing, and hardening libJudy itself after finding latent compiler bugs in the 20-year-old upstream C code.

Diving back into Doug Baskins’s original 20,000-line C codebase reminded me of the exact visceral reaction I had when I first read it twenty years ago: my eyes were bleeding.

It is a monument of early-2000s low-level wizardry—dense macros, custom chunk allocators, manual SWAR (SIMD Within A Register) bit-twiddling, and cryptic pointer tagging. The core algorithmic ideas behind Judy arrays were brilliant, but the implementation was so notoriously complex that almost the entire software engineering field eventually walked away from it.

Over the last two decades, when engineers needed high-performance ordered collections or bitsets, they reached for B-Trees, Adaptive Radix Trees (ART), or Roaring Bitmaps instead. Not because those structures were fundamentally more cache-efficient than Judy, but because nobody wanted to maintain, debug, or port 20,000 lines of arcane C macro soup to new CPU microarchitectures. The clearest proof: ART, the field’s go-to in-memory index since 2013, is itself an adaptive radix trie — its Node4/16/48/256 layouts revisit the same idea as Judy’s linear, bitmap, and uncompressed branches. The industry never refuted Judy’s design; it rebuilt a simpler subset of it and moved on.

With today’s AI agentic coding harnesses and formal verification tools, that cognitive barrier is largely gone. I found myself asking a question that had lingered in the back of my mind for years:

What would Judy arrays look like if designed from scratch for modern hardware?

The result of that exploration is Expanse: a clean-room, pure-Rust, memory-safe, hardware-vectorized digital trie engine, along with libexpanse—a drop-in C ABI replacement for libjudy.

Why “Expanse”?

In tree search literature, most data structures partition their keys by population (the number and distribution of keys currently stored). A B-Tree or Red-Black tree dynamically rebalances, splits, and merges nodes as keys are inserted, keeping the tree balanced relative to its population.

Judy arrays do something fundamentally different: they partition by expanse.

“Expanse, population, and density are not commonly used terms in tree search literature, so let’s define them here: Expanse is a range of possible keys […] A digital tree divides up the population (index set) uniformly by expanse (dividing and redividing the initial expanse evenly), while other methods, such as b-trees, divide up the population by the distribution of the population itself.”
— Doug Baskins & Alan Silverstein, Judy IV Shop Manual (2002)

The B-tree binary-searches stored pivot keys at every hop; the Expanse trie reads the key’s own bytes as positions, and byte 1 never even costs a hop — its single-child level is folded into the edge as a narrow-pointer skip.

An expanse-partitioned 256-ary digital tree decodes keys byte-by-byte, from the most significant to the least significant byte. Because the branching boundaries are fixed a priori by numerical byte ranges:

1. Tree structure is invariant to insertion order: Inserting keys in ascending, descending, or random order produces the same tree. There are zero tree rotations, zero cascading page splits, and zero rebalancing passes.
2. Keys are inferred by position: Full 64-bit integer keys do not need to be duplicated and stored inside index nodes. The path through the tree is the key prefix; only the trailing uncompressed bytes are stored at the leaves.
3. Predictable mutation latency: Writes affect only the local subexpanse, providing deterministic latency without write-stall spikes.

Here is that same decode again, level by level — each byte magnifies the slot it picked into the next level’s whole range:

The reason naive 256-ary tries are rarely used in practice is memory bloat: allocating 256 pointers (2 KB on 64-bit) at every branch node wastes 99% of memory when only a few keys are present.

Judy solved this with adaptive polymorphic compression: branches dynamically morph between packed linear arrays, 2-tier bitmap subexpanses, and uncompressed tables based on local density. Small populations are stored immediately inside the 16-byte parent pointer itself — up to 15 key-remainder bytes, so 15 keys at one byte each, or 2 at seven — bypassing heap allocations entirely.

The 2002 vs. 2026 Hardware Mismatch

When Doug Baskins designed Judy IV at HP around 2000–2002, the hardware assumptions were radically different from the CPUs powering our servers today:

Judy IV was tuned for the wide cache lines of its era’s HP enterprise hardware: its own design documents size nodes around 16-word cache line fills — 128 bytes on a 64-bit machine.

On modern 64-bit server microarchitectures (x86-64, ARM64, and 64-bit RISC-V), the standard L1 and L2 cache line size is 64 bytes. When data structures engineered around 128-byte boundaries are traversed without 64-byte alignment awareness, child pointers and node metadata frequently straddle two adjacent 64-byte cache lines. Every straddle forces a second cache line fetch, doubling the memory cost of that hop.

Furthermore, calculating popcounts and ranks in bitmap nodes in 2002 required multi-step SWAR math. Today ARM64 counts bits with a NEON cnt+addv pair, and x86-64 does it in one POPCNT at x86-64-v2 (TZCNT needs BMI1, so x86-64-v3) — with a portable SWAR fallback retained for base targets.

Inside Expanse: Architecture of a Modernized Digital Trie

Expanse is a clean-room build: published descriptions and black-box differential testing against a compiled stock binary, never the LGPL source. Transliterating Judy IV into Rust was never the interesting version of this project anyway. In 2002 C, Judy relied heavily on upper-bit pointer stealing, unaligned word reads, and bespoke chunk allocators that assumed an isolated, single-threaded world.

To build a data structure that survives modern server workloads, I had to rethink the engine around three modern hardware primitives: strict 64-byte cache lines, virtual address sanity (supporting 57-bit PML5 without corrupting pointers), and lock-free multi-core read scaling.

You can inspect the live tree structure, node transitions, and memory layouts interactively in the Expanse Architecture & Benchmark Visualizer.

1. 64-Byte Cache Line Node Geometry & Single-Line SWAR

Expanse re-engineers the digital trie geometry specifically around exact 64-byte and 128-byte cache-line multiples (with 32-byte alignment support for embedded profiles):

• Linear Branch (BranchL3 — 64 bytes): In BranchL3 (a 3-child linear branch), the entire node is packed into exactly one 64-byte line:

  • Header (16 bytes): Holds an OCC generation version tag (4 bytes), child count (1 byte), level (1 byte), presence filter (2 bytes), and an 8-byte packed sorted digit word storing the 3 child digit keys.
  • Edges (48 bytes): Holds exactly three 16-byte edge descriptors (3 × 16 = 48 bytes).
  • Total: 16 B header + 48 B edges = 64 bytes exactly.

  How Single-Line SWAR Works: SIMD Within A Register (SWAR) treats a standard 64-bit integer register as an 8-lane vector of 8-bit bytes, executing parallel byte searches on standard scalar integer ALUs without invoking vector registers:

  1. The needle byte (e.g. 0x8C) is broadcast across all 8 lanes via scalar multiplication (needle * 0x0101010101010101).
  2. XORing against the header’s packed digit word zeroes out matching byte lanes (diff = digit_word ^ needle_splat).
  3. The zero-byte lane is detected in parallel via Alan Mycroft’s classic bitmask: (diff - 0x0101010101010101) & ~diff & 0x8080808080808080.
  4. A single trailing-zeros count (trailing_zeros() / 8) returns the exact edge index (0, 1, or 2) with no comparison loop to mispredict.

  Because the header and all three 16-byte child edges reside in the exact same 64-byte line, the entire branch resolution and child edge read complete in a single memory fetch with zero cache-line boundary crossings. (A naive “8-byte header + 4 edges” one-line branch is arithmetically impossible: 8 + 4 × 16 = 72 > 64.)

• Larger Linear Branch (BranchL7 — 128 bytes): Exactly two cache lines holding a 16-byte header and 7 full 16-byte edges (16 + 7 × 16 = 128 B).

• Bitmap Branch (BranchB — 128 bytes): Exactly two cache lines. Line 0 holds a 256-bit bitmap split into eight 32-bit subexpanses plus the first four subarray pointers; line 1 holds the rest, the cached per-subexpanse popcounts, and the OCC version. Navigating a branch is a popcount-rank calculation that indexes directly into packed pointer arrays.

• Uncompressed Branch (BranchU — 4 KiB + 1 line): A flat array of 256 edges on dedicated slab pages, reserved exclusively for dense clusters where direct positional array indexing outperforms bit-scanning.

2. Lock-Free Optimistic Concurrency Control (OCC)

In multi-threaded server environments, traditional tree structures hit a hard concurrency wall. Coarse-grained mutexes bottleneck all cores, while read-write locks (RwLock) trigger massive cache-invalidation storms as readers contend for the lock word.

Expanse solves this with per-node versioned Optimistic Concurrency Control (SyncExpanseMap and SyncExpanseSet). Readers traverse the trie without taking a lock, validating generation version tags on descent. On 100%-read workloads, reader throughput scales near-linearly across cores—884.5 million ops/second for SyncExpanseSet and 424.1 million for SyncExpanseMap at 16 threads (11.4× scaling), ahead of DashMap (132.1 M, 8.5×) while keeping the ordered iteration a sharded hash map cannot offer.

The honest limit, stated plainly: this is a single-writer design. Under a 50/50 read/write mix every Expanse arm loses throughput as threads are added (0.12×–0.55×): writes serialize on one mutex, and the threads spend their time handing it off. Readers are not the bottleneck—the reader fallback never fires in these runs—so “lock-free” here means lock-free reads, precisely obstruction-free with a mutex fallback after 64 lost races. DashMap and SkipMap win that regime outright. Multi-writer support is the standing follow-up.

3. Pure Rust Core with 100% C ABI Drop-In Compatibility

The core engine is #![no_std] Rust, verified against memory leaks, data races, and undefined behavior using Miri and Loom.

At the same time, libexpanse exports the legacy C ABI:

• Judy1 → expanse_set_t / ExpanseSet
• JudyL → expanse_map_t / ExpanseMap
• JudySL → expanse_strmap_t / ExpanseStrMap
• JudyHS → expanse_bytesmap_t / ExpanseBytesMap

Any existing C, C++, or PHP application linking against libJudy can replace -lJudy with -lexpanse with zero code modifications. In fact, libexpanse passes the entire 221-test regression suite of php-judy without a single failure.

Performance & Memory Benchmarks

If there is one thing I learned while hardening libjudy, it is that benchmarking low-level data structures is full of traps. It is shockingly easy to measure test-harness teardown or memory-allocator recycling instead of algorithmic speed, or to compare an inlined static Rust library against a dynamically linked C library.

To ensure apples-to-apples comparisons, every benchmark in Expanse is evaluated against explicit baseline implementations across identical key distributions (uniform random, sequential runs, clustered 256-key bursts, and Zipfian distributions).

Full benchmark datasets and Callgrind profiles are documented on the Expanse Benchmarks page.

1. Memory Density (Bytes per Key)

I measured memory footprint with deterministic allocator accounting (NodeAlloc)—the one benchmark that is machine-independent and reproduces byte-for-byte:

Key Distribution (ExpanseSet, 1M keys)	Bytes / key	Note
Sequential integers	0.07	full-expanse + bitmap-leaf compression
Clustered (256-key runs)	0.36	was 1.34 before leaf-targeted narrow pointers
Clustered (4096-key runs)	0.12	was 0.19 before branch-targeted narrow pointers
Uniform random 64-bit	7.92	not part of the dense/clustered design target; density-dependent, see the sawtooth post
Sparse (i << 40)	16.31	one 16-byte edge per isolated key—the structural floor

Against stock libJudy through the identical C ABI, the map-flavor footprint is 0.92×–1.03× (smaller on random and clustered keys, 3% larger on sequential). On clustered and dense sets the 0.07–0.36 bytes/key matches Roaring Bitmaps’ run/bit-container compression while keeping ordered navigation; on genuinely sparse keys the trie’s floor is a 16-byte edge per isolated key, and other structures have regimes where they win.

2. Throughput Against Named Baselines

Across different access patterns, performance reflects the structural advantages of expanse partitioning:

• Point Lookups vs. BTreeMap: 2.9×–14.5× faster at 1M keys (sequential: 11.9 ns vs 108.9 ns)—no stored-key comparisons, just positional descent. Full ordered iteration is also now faster than BTreeMap::iter() on dense distributions (0.5×–0.8× its time); sparse-key iteration remains ~2.4× slower, the structural floor of one re-descent per isolated key.
• Lookups vs. hashbrown’s Swiss Tables: near parity on sequential keys, and within ~1.1× while the working set stays cache-resident—but a hash probe wins uniform-random lookups at 1M keys (~2.9×) once every trie descent misses to DRAM. What you buy for that trade is strict ordering, O(depth) prefix search, and the smaller clustered-set footprint.
• vs. Stock libJudy 1.0.5 (quiet host, SIMD paths active): at a million keys, inserts are faster on all three distributions (0.545×–0.933× of stock’s time) and lookups faster on sequential and clustered keys (0.872× / 0.904×). Three arms are measured losses, each with its CI lower bound above parity: random 1M lookup at 1.031×, BCa 95% CI [1.024, 1.038]; that same arm statically linked at 1.028×; and random 100k insert at 1.009×, CI [1.005, 1.013]. Why random lookup costs more than sequential is unmeasured—no counter run covers that arm.
• Instruction-Count A/B (Callgrind, deterministic): the three headline engine optimizations—hoisted OCC checks, stack-buffered immediates, width-monomorphized key access—remove 2.3% to 17.0% of retired instructions across all 14 benchmark arms, nothing regressed. Against stock libJudy, Expanse retires fewer instructions on every measured arm (0.49×–1.00×). Instruction counts and wall clock come from separate harnesses at different populations, so neither explains the other.
• Small-Payload Inlining (ExpanseBlobMap): payloads of 7 bytes or less are stored directly inside the edge with zero heap allocations; in the YCSB latency report the word-keyed map holds a 28 ns read-only p50 (bracket overhead included) with p99.9 under 80 ns.

Real-World Use Cases in Systems Engineering

Having spent years building high-throughput infrastructure at TubeMogul and Adobe—where a few nanoseconds of p99 latency or a 20% memory bloat cascades across thousands of servers—these are the specific patterns where digital tries shine:

1. RocksDB Pluggable MemTable (rocksdb-expanse)

Standard LSM-tree storage engines, such as RocksDB, use SkipLists for their in-memory MemTables because SkipLists allow lock-free concurrent inserts. But SkipLists pay a variable-height tower of forward pointers per node — ~18.7 bytes of indexing overhead per entry against Expanse’s 13.2, a 1.42× density edge — and have poor spatial cache locality.

By implementing RocksDB’s MemTableRep interface on top of Expanse, the standardized YCSB suite (100k keys, Zipfian θ=0.99, 128-byte records) measures:

• 8.1×–11.1× higher throughput than the SkipList arm across the read-heavy and read-modify-write workloads (B, C, D, F), with the skiplist carrying the highest steady-state latency of every engine tested (p50 ~200–330 ns vs ~40–140 ns).
• Range scans are the honest loss: on the scan-heavy Workload E BTreeMap leads the 128-byte arm 1.96× (1.289 vs 0.657 Mops/s), and still leads 1.55× against the word-keyed map. I published 4.33×, then 3.08×, both in my favor and both wrong—the scan bound was a key-width window, so every arm walked one record instead of the ~55 it asked for. Uniform-random keys pack ~1.43 records per leaf; a B-tree walks contiguous arrays. Clustered keys get ~322 per leaf and don’t show it.
• The honest tail: on the 50%-write blob workloads, arena slab growth shows p99 latency spikes (~39 µs)—flagged and tracked, not hidden.

2. CIDR Subnet Routing & Network Filtering

IPv4 and IPv6 subnets (e.g., 192.168.1.0/24 or /48 IPv6 blocks) are natural prefix paths in a 256-ary digital trie. Longest Prefix Match wants exactly the descent the trie already does: bounded at 4 hops for IPv4 and 8 for 64-bit keys, no hash collisions, no tree rotations, no allocation on the read path. I have not built the LPM layer yet, so take this one as a design fit rather than a benchmark.

3. Database MVCC Visibility Maps

In modern transactional engines (PostgreSQL, MySQL InnoDB, CockroachDB), tracking active transaction IDs (xid) for Multi-Version Concurrency Control (MVCC) requires a low-overhead, concurrent bitset. SyncExpanseSet lets background transactions commit and register without stalling concurrent readers checking row visibility. Writers still serialize against each other on one mutex; readers never wait on them.

Getting Started with Expanse

Expanse is open source under dual MIT / Apache-2.0 licensing. Each release is also archived on Zenodo; to cite the software, use the concept DOI 10.5281/zenodo.22152112, which always resolves to the latest release.

Rust

Add expanse-trie to your Cargo.toml:

[dependencies]
expanse-trie = "0.6.0"

use expanse_trie::ExpanseMap;

let mut map = ExpanseMap::new();
map.insert(1042, 500);

if let Some(val) = map.get(1042) {
    println!("Found value: {}", val);
}

// Ordered range navigation in O(depth)
for (key, val) in map.range(1000..=2000) {
    println!("{}: {}", key, val);
}

C / Linux Packages (Debian, Ubuntu, Fedora, RHEL)

Install prebuilt packages directly from the official repositories:

# Debian / Ubuntu
echo "deb [trusted=yes] https://orieg.github.io/expanse/apt/ stable main" | sudo tee /etc/apt/sources.list.d/expanse.list
sudo apt-get update
sudo apt-get install -y libexpanse1 libexpanse-dev libjudy-compat

# Fedora / RHEL / AlmaLinux
sudo dnf config-manager --add-repo https://orieg.github.io/expanse/rpm/expanse.repo
sudo dnf install -y libexpanse libexpanse-devel libjudy-compat

Compile against the modern C API (expanse.h) or drop-in legacy API (Judy.h):

#include <stdio.h>
#include <expanse.h>

int main() {
    expanse_map_t *map = expanse_map_new();
    expanse_map_insert(map, 1042, 500, NULL);

    uint64_t val = 0;
    if (expanse_map_get(map, 1042, &val)) {
        printf("Retrieved key 1042 -> %llu\n", (unsigned long long) val);
    }
    
    expanse_map_free(map);
    return 0;
}

gcc -O3 main.c -lexpanse -o main
./main

Language bindings and target platforms are available across the ecosystem:

• Python: pip install expanse-trie
• Node.js / Bun / Deno: npm install @orieg/expanse
• .NET / C#: dotnet add package Orieg.Expanse
• Java / Scala: io.github.orieg:expanse-java (via Project Panama FFM)
• PHP: orieg/expanse (via native Zend extension & FFI)
• Go: github.com/orieg/expanse/bindings/go
• Ruby: gem install expanse
• WebAssembly / Edge: @orieg/expanse-wasm
• C++20: include/expanse.hpp STL-compatible RAII wrapper
• 32-Bit Embedded (#![no_std]): ExpanseSet32, ExpanseMap32, ExpanseBlobMap32 (Cortex-M4/M7, RV32IMAC, and ESP-IDF ESP32-C3 component)

Looking Ahead

Building Expanse reminded me that good algorithmic ideas don’t expire—sometimes they just get trapped in the implementation constraints of the era in which they were born.

Doug Baskins’s insight that digital tries partitioned by expanse could outperform comparison-based trees was ahead of its time in 2002. Rebuilding that vision for modern 64-bit microarchitectures with memory safety, SIMD vectorization, and lock-free concurrency shows how much headroom remains when we design algorithms around the actual physics of modern silicon.

Check out the project on GitHub, explore the live Architecture Visualizer, and let me know your thoughts!