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 (1–15 keys) are stored immediately inside the 16-byte parent pointer itself, 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 in a single cnt instruction, and x86-64 does the same with POPCNT/TZCNT when built for x86-64-v2 or newer — with a portable SWAR fallback retained for base targets.

Inside Expanse: Architecture of a Modernized Digital Trie

When I sat down to design Expanse, my first instinct was to map Doug Baskins’s C structs into Rust types. That lasted about two hours. 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, paired with cached popcounts. 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 with zero lock acquisitions, validating generation version tags on descent. Under high read concurrency, reader throughput scales linearly across cores with zero read locks—reaching 260.9 million operations/second on 16 cores.

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 at 1M keys using deterministic allocator accounting (NodeAlloc / heap profiling) against standard library collections and specialized bitsets:

Because Expanse compresses key prefixes into edge descriptors and packs trailing bytes into bitmap leaves, dense and clustered integer sets use up to 7.7× less memory than Roaring Bitmaps and over 40× less memory than B-Trees.

2. Throughput Against Named Baselines

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

• Ordered Range Scans vs. BTreeMap (std::collections::BTreeMap): Expanse traverses sorted integer ranges 2.1× to 3.4× faster by skipping empty subexpanses whole cache lines at a time — while random point lookups stay within 1.1× of hashbrown’s Swiss Tables, with strict key ordering the hash map cannot offer.
• Point Lookups vs. Stock libJudy 1.0.5: Expanse delivers 18–35% lower latency on modern 64-bit microarchitectures by eliminating 128-byte cache line straddles and vectorizing byte scans.
• Sequential Range Scans vs. SkipMap (crossbeam-skiplist): Expanse achieves 4.1× higher range scan throughput in database MemTable benchmarks because adjacent keys share dense leaf nodes rather than scattered heap-allocated skip nodes.
• Instruction Count vs. Stock libJudy: In deterministic Callgrind profiling across all 14 standard benchmark arms (map_insert, set_insert, map_get, set_contains, map_churn), Expanse executes 2.3% to 17.0% fewer instructions to perform identical operations.

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 have terrible pointer overhead (each node has an array of forward pointers) and poor spatial cache locality.

By implementing RocksDB’s MemTableRep interface on top of Expanse:

• 8.8× higher key density in RAM: A 1 GB MemTable holds nearly an order of magnitude more active keys before triggering an L0 SSTable flush.
• Reduced Write Amplification: Fewer SSTable flushes translate directly to less background compaction I/O on SSDs.
• 4.1× faster sequential range queries: Prefix scans and range iterators pull sequential keys directly from packed 64-byte leaves.

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. Instead of evaluating hundreds of thousands of firewall rules sequentially or paying hash-table costs that degrade under collisions, Expanse performs Longest Prefix Match (LPM) in O(prefix depth):

• Matches incoming traffic across 500,000+ CIDR rules in bounded O(depth) hops (at most 4 hops for IPv4, 8 for 64-bit keys) without hash collisions or tree rotations.
• Zero heap allocations during routing table traversals.

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 allows background transactions to commit and register without acquiring write locks that stall concurrent readers checking row visibility.

Getting Started with Expanse

Expanse is open source under dual MIT / Apache-2.0 licensing.

Rust

Add expanse-trie to your Cargo.toml:

[dependencies]
expanse-trie = "0.3.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

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

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 are also 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: pecl install expanse or FFI
• Go / Ruby / WebAssembly

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!