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, hardware-vectorized digital trie engine in pure Rust, with every unsafe block carrying a documented safety argument and tested under Miri and AddressSanitizer in CI, 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. Sean Barrett saw the same mismatch from the 32-bit side in 2003: 16 words there are 64 bytes, and he noted that Judy was designed for 64-byte cache lines while running mostly on machines with 32-byte lines ( A Performance Comparison of Judy to Hash Tables).

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 optimistic 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. Optimistic Concurrency Control (OCC) with Epoch-Based Reclamation

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 across cores while keeping the ordered iteration a sharded hash map cannot offer: SyncExpanseMap serves 322.8 M reads/s at 16 threads (95% CI [322.1, 323.5]; a second run measured 321.6 [321.2, 322.1]), measured on a later build than v0.6.0 (commit f9853201), per the committed run 1 and run 2 results.

The honest limit, stated plainly: as released in v0.6.0, this is a single-writer design. Under a 50/50 read/write mix, writes serialize on one mutex, and the threads spend their time handing it off. Readers are optimistic and take no lock on the common path, but the protocol is blocking: a reader spins while a writer holds a node’s version open, and falls back to the writer mutex after 64 failed validations. This is optimistic lock coupling ( Leis et al., The ART of Practical Synchronization, DaMoN 2016) with epoch-based reclamation. DashMap and SkipMap win that regime outright.

Update: multi-writer support has since shipped. From v0.7.0, writers on disjoint subtrees run in parallel under per-node version locks, first on SyncExpanseSet and SyncExpanseMap; current releases use those locks for inserts and removals on every 64-bit wrapper, and keep the writer mutex for fallbacks, root-state changes and whole-tree operations ( architecture §4.2).

3. Pure Rust Core with a Drop-In libJudy C ABI

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

On 64-bit builds, these legacy Judy1/JudyL/JudySL/JudyHS symbols are a drop-in for libJudy, checked by black-box differential testing against stock libJudy: a C, C++, or PHP application linking against libJudy can replace -lJudy with -lexpanse without code changes. 32-bit builds do not export the legacy symbols. CI also runs the php-judy regression suite against libexpanse, with zero failures.

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 ( results)
Uniform random 64-bit	7.92	not part of the dense/clustered design target; density-dependent, see the sawtooth post ( results)
Sparse (i << 40)	16.31	one 16-byte edge per isolated key—the structural floor ( results)

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

The lookup chart comes from two runs of the same build (commit 82eb56af), committed as run 1 and run 2 with their tables in BENCHMARKING.md. The two runs agree on which container is faster in every cell, but their intervals do not overlap on many of the magnitudes, so the chart shows the ordering and the range both runs span rather than one ratio. Against BTreeMap and BTreeSet, Expanse is faster in every cell. Against the hash containers it depends on the keys: uniform-random keys lose at both sizes, and clustered keys lose to HashMap at a million keys. Sequential keys at a million entries against HashMap are shown as parity: both committed runs put Expanse slightly ahead (0.936–0.986×), too narrowly to claim an order.

Both charts are current measurements on later builds than v0.6.0, from committed result files: concurrency run 1 and run 2 (commit f9853201), and YCSB (commit 21a382f3).

Each YCSB badge compares ExpanseMap holding u64 values with BTreeMap holding 128-byte records, so the two arms do not carry the same payload. With the same 128-byte payload, ExpanseBlobMap against BTreeMap measures 1.278× on A (BCa 95% CI [1.252, 1.318]), 1.936× on B [1.918, 1.957], 2.008× on C [1.969, 2.030], 1.955× on D [1.937, 1.971] and 1.029× on F [1.025, 1.035], and loses Workload E at 0.442× [0.441, 0.443], from the same result file.

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

• 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. ( results)
• Small-Payload Inlining (ExpanseBlobMap): payloads of 7 bytes or less are stored directly inside the edge with zero heap allocations.

Isn’t a hash table just as good?

In 2003 Sean Barrett asked exactly this question in A Performance Comparison of Judy to Hash Tables. He benchmarked JudyL against a hash table he wrote himself with the same interface, 32-bit keys and values: about 200 lines of C, secondary hashing, doubling at 65% full, on a 700 MHz Pentium III laptop. What he found:

• On random keys the hash table won throughout, generally by about 2×.
• Below 10,000 entries the hash table won every hit-lookup test.
• On sequential keys Judy’s hit time stayed flat as the structure grew, and beat the hash table beyond about 20,000 entries.
• The hash table was always faster for insert/delete churn at a constant size.
• Judy was smaller: about 5 bytes per entry on sequential keys, 4 of them the value, against 12 to 24 for the hash table.

His conclusion was that Judy’s compactness does not buy it an enormous speed advantage, and that an hour or three spent on a standard 200-line hash table holds up against 20,000 lines of Judy. His method is the one I wanted to hold Expanse to: if performance is what matters, “the only thing to do is measure performance, not space.”

So I measured, and then measured again with the gaps he would have pointed at closed: lookups in random order, keys built to hurt a trie, every population from 16 keys to 4 million, and his churn test. The second round took back the one lookup win I had published.

Random keys: the hash table still wins, by about his factor of 2. Against hashbrown, the SwissTable implementation behind Rust’s HashMap, Expanse reaches 0.501× its lookup throughput on uniform random 64-bit keys at 500,000 entries, BCa 95% CI [0.495, 0.510], and 0.498× in a second run ( results). On lookups for keys that are not there it is 0.250×. Against std HashMap at a million random keys, an Expanse lookup takes 3.3 times as long; the two committed runs span [3.315, 3.375] ( table). std’s default hasher is SipHash, built to resist collision attacks and slower than hashbrown’s default, which is why the two ratios differ.

Modernizing the trie does not get around this. On random lookups at a million keys, Expanse takes 1.031× stock libJudy’s time [1.024, 1.038] ( results). Barrett also wrote that there were not many ways left to improve Judy, but a lot of room to improve hash tables.

Structured keys: the trie wins only when the lookups come in key order. An earlier version of this section said the trie wins on structured keys, at 1.740× hashbrown on dense sequential keys and 1.990× on clustered ones. Those lookups walked the keys in the order they were inserted. Shuffle the same lookups over the same build and the result flips ( results):

• On dense sequential keys Expanse reaches 0.602× hashbrown’s throughput [0.550, 0.673]; in insertion order it is ahead, at 1.384×.
• On sparse clustered keys it reaches 0.639× [0.623, 0.660]; in insertion order, 1.919×.

Both runs agree. In insertion order Expanse runs at 134.6 million lookups a second on sequential keys; shuffled, at 65.1 million, while hashbrown gets slightly faster. Consecutive lookups landing in the same trie leaf is the likely reason, but no cache counter was taken, so that is a hypothesis. The insertion-order ratio also moved between two pairs of runs on the same code (1.532× and 1.384×), and the shuffled one did not, so the shuffled figure is the one to quote. Sequential keys give you a trie that is fast when you read them back in order: a scan, a replay, a cursor. Looked up at random, they are just keys, and the hash table wins.

Keys built to hurt a trie, and small populations: the hash table wins those too. Barrett listed key patterns that should be bad for a digital tree. Against hashbrown at 500,000 keys, one ASCII character per byte runs at 0.187× and byte-swapped dense keys at 0.498× ( same table). He found the hash table winning below 10,000 entries. Measured at every population from 16 to 4,194,304 keys, hashbrown is faster on hit lookups at every one of them, on random, sequential and byte-swapped keys (a few sequential cells tie in one of the two runs) ( population sweep). There is no crossover to find.

Churn: his result again. Hold the population constant and replace the oldest keys in batches of 128, and hashbrown wins every cell: an insert plus a remove costs Expanse 9× hashbrown’s time on random keys at 100,000 (0.111×) and about 1.1× on sequential keys at 4 million (0.880×) ( results). Barrett found the same. Against Rust’s BTreeMap, the ordered structure Expanse actually competes with, Expanse wins every churn cell by 1.76× to 2.47×, and every lookup cell at 500,000 keys; its one lookup loss in the sweep is at 32 sequential keys, one past the size of its root leaf.

Memory: the one place structured keys still pay off. At 500,000 entries with 8-byte values, exact heap accounting identical in every run ( results):

• Dense sequential keys cost 8.7 bytes per key in Expanse, against 35.7 for hashbrown. That is about 0.7 bytes beyond the value itself, close to the byte or so Barrett measured for Judy.
• Uniform random keys cost 24.7 against 35.7.
• At 100,000 random keys the order inverts, 30.6 against 22.3. That is not Expanse getting worse so much as hashbrown sitting at its best: its table is nearly full there, just before it doubles.

The population sweep shows the whole curve. hashbrown saws between 19.6 and 35.7 bytes per key as its table fills and doubles. On sequential keys Expanse falls below it from about 5,600 keys up, reaching 8.6 bytes per key at 4 million. On random keys Expanse is smaller only near the tops of hashbrown’s sawtooth. And small maps are Expanse’s worst case: 1,296 bytes per key at 16 keys, the largest of the three structures by an order of magnitude below about 1,000 keys.

What Barrett didn’t measure is where Expanse earns its size.

• No rehash cliff. Grow both structures from empty to a million keys and hashbrown wins every percentile up to P99.99: its median insert is 0.355× Expanse’s [0.350, 0.360]. Its worst insert is about 11 ms in every round, because the whole table is reallocated and rehashed at once. Expanse’s worst insert across the 18 rounds of both runs was 4.5 to 154 µs, because a trie only ever grows locally ( results).
• Order. Range scans, floor and ceiling lookups and sorted iteration are native. A hash table has to dump and sort first, which is why hashbrown is disqualified from YCSB Workload E in the same suite. Barrett’s own advice was that if you need a sorted iterator, use Judy. For a storage engine it is the use that matters most.
• Concurrency. Optimistic readers alongside writers, with ordered iteration intact, as described above.

So the honest answer:

• If all you do is point lookups and point updates, whatever your keys look like, use a hash table. Barrett was right in 2003 and the margin has not closed.
• Expanse is for the other cases: ordered queries and scans, dense keys where memory matters, bounded worst-case inserts, and concurrent readers. Against the ordered structure you would otherwise reach for, BTreeMap, it wins every churn cell and every lookup cell at 500,000 keys.

The hashbrown lookup, population-sweep and churn figures are run 1 of two committed runs on the reference host (Intel i9-12900F, CPUs 0–15, performance governor), means of 9 rounds with BCa 95% intervals, measured at Expanse commits 4659016f, 0c2152c4 and cc70a809; run 2 is beside each in the same directory. The memory and tail-latency figures are from commit 2f82cd07 (powersave governor), and the 500,000- and 100,000-key memory figures reproduced byte for byte in the new runs. The std HashMap and libJudy figures are from commit 82eb56af.

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 ( results) — 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 ( results):

• Higher throughput than the SkipList arm across the read-heavy and read-modify-write workloads (B, C, D, F).
• Range scans are the honest loss: on the scan-heavy Workload E BTreeMap leads both the 128-byte arm and the word-keyed map. Earlier scan ratios I published were both in my favor and both wrong—the scan bound was a key-width window, so every arm walked one record instead of the range it asked for.

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 while concurrent readers check row visibility without taking a lock on the common path. In v0.6.0, writers still serialize against each other on one mutex; since v0.7.0, writers on disjoint subtrees run in parallel.

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.18.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 SIMD vectorization and optimistic 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!

Corrections (2026-11-08). Corrected: the concurrency protocol is blocking optimistic lock coupling, not lock-free; the single-writer description is scoped to v0.6.0, the version this post covers, with a note on the concurrent writers that shipped in v0.7.0; the C ABI claim is now scoped to the legacy symbols on 64-bit builds instead of “100%”; “memory-safe” is replaced by what is actually checked, since Expanse uses audited unsafe and has a published advisory ( GHSA-4wgg-rc8x-w9r2). Removed benchmark figures that were withdrawn or are not in a committed result file; the concurrency and YCSB charts are replaced with current measurements from committed result files, and the stdlib comparison chart, whose figures had none, is replaced by a lookup chart from two committed runs that shows only the orderings both runs agree on.