Expanse

A clean-room, pure-Rust implementation of Judy arrays, modernized for modern 64-bit and 32-bit embedded microarchitectures, with libexpanse — a high-performance, drop-in C ABI replacement for libjudy.

Judy arrays (invented by Doug Baskins at Hewlett-Packard, ~2002) are sparse, dynamic associative structures built as 256-ary digital tries partitioned by expanse (decoding keys byte by byte over fixed digit ranges) rather than by population like comparison-based trees. Their speed comes from adaptive node compression — linear, bitmap, and uncompressed branches; linear and bitmap leaves; keys stored immediately inside pointers — tuned to keep every node traversal within a few cache-line fills.

Why "Expanse"?

Expanse is the Judy design's own defining term — so central that the published descriptions stop to define it before anything else, and use it as the precise contrast with population-partitioned trees (B-trees, binary trees):

"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 […]"
— Doug Baskins, A 10-Minute Description of How Judy Arrays Work and Why They Are So Fast (2002)

"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."
— Alan Silverstein, Judy IV Shop Manual (2002), "Digital Trees"

Naming the project after the mechanism honors the algorithm itself without inheriting the legacy Judy package namespace. Crate: expanse-trie (bare expanse is squatted on crates.io by an abandoned unrelated crate). C library: libexpanse, with a libjudy-compat shim for drop-in use.

Key Features

• Pure Rust & Memory Safe: #![no_std] core with zero unsafe memory leaks, zero external runtime dependencies, verified under Miri & Loom.
• Strictly Faster than Stock Judy: Outperforms original libjudy across 100% of benchmark workloads (inserts, lookups, deletions, and churn).
• 100% Drop-In C ABI Compatibility: Swap -lJudy for -lexpanse with zero code changes (Judy1, JudyL, JudySL, JudyHS). Passes php-judy test suite (221/221) and differential oracle.
• Multi-Architecture Vectorization & Embedded: Hardware-accelerated with dynamic glibc-hwcaps packaging (x86-64-v1..v4), ARM64 NEON, 64-bit RISC-V (RV64GC), and bare-metal 32-bit embedded (RV32IMAC, Cortex-M4/M7).
• Lock-Free OCC Concurrency: Multi-core optimistic concurrency control (SyncExpanseMap / SyncExpanseSet) with zero read locks, scaling read-only throughput to 265.8 M ops/s on 16 threads (12.0×) (measured: reference host — Intel i9-12900F, 24 threads, 30 MiB L3, commit 695b98d). Write-mixed workloads are currently seqlock-bound and do not scale past ~4 threads (see the concurrency scaling table below).
• Ultra-Dense Memory Packing: Down to 0.07–0.36 bytes/key on 64-bit sets (measured: Apple M1, bytes_per_key example, commit 6c63826a) and ~0.67 bytes/key on clustered 32-bit embedded sets (measured: bytes_per_key_32, commit 6c63826a).

Visual Performance Comparison

API Surfaces

Legacy ↔ modern naming:

Modernization Thesis

Full architectural specifications: docs/ARCHITECTURE.md · Embedded 32-Bit design: docs/design/32-bit-embedded.md · Large-Value design: docs/design/large-values.md · Database engine patterns: docs/DATABASE.md · CI/CD: docs/CI.md.

Database Engine Subsystems & Architecture

Expanse provides modern, hardware-vectorized digital trie primitives tailored for core database engine subsystems:

• Inverted Indexes & Posting Lists (ExpanseSet): Ultra-dense doc-ID tracking at 0.07–0.36 bytes/docID on clustered/dense sets (outperforming Roaring Bitmaps) with bitwise set algebra directly over compressed trie edges and $O(\text{depth})$ skip-scan acceleration.
• MVCC Visibility Maps & Active Transaction Tracking (SyncExpanseSet): Lock-free active transaction (xid) tracking with zero reader-writer locks, single-digit nanosecond visibility checks, and safe epoch reclamation under continuous OLTP churn.
• Columnar String & Symbol Dictionaries (ExpanseStrMap): High-cardinality string deduplication and symbol tables using 8-byte cross-chunk path folding, preserving lexicographical order with 70%+ memory reduction on shared URL/path prefixes.
• Secondary Indexes & MemTables (ExpanseMap / ExpanseMemTableRep): Rebalance-free ordered key indexing with fast point/prefix lookups (2.9×–14.5× faster point lookups than std::collections::BTreeMap at 1M keys; full ordered iter() now faster than BTreeMap::iter() for dense keys (sparse-key iteration still slower) — see docs/DATABASE.md §7.1), and official RocksDB Pluggable MemTable (integrations/rocksdb) integration.
• Zero-Copy Shared-Memory Analytics (roadmap): Position-independent base-relative layouts for cross-worker IPC and parallel query execution with zero serialization — a design target; not yet implemented (see docs/DATABASE.md §6).

See docs/DATABASE.md and integrations/rocksdb/README.md for full architectural specifications, integration blueprints, and code examples.

Comparative Performance vs Industry Primitives

Expanse is benchmarked against standard Rust and industry collections (crates/expanse/benches/comparative.rs). The speedup multipliers below are load-sensitive wall-clock figures not tagged to a specific host/commit; they await a clean-host re-measurement (deferred). Memory-footprint figures are deterministic.

1. ExpanseSet vs RoaringBitmap

• Sparse / clustered (<0.1% density): Expanse point lookups (contains) are ~2.2×–2.8× faster than Roaring Bitmaps due to direct tagged-pointer immediate storage (measured: reference host, commit 695b98d, benches/comparative.rs). On dense sets Roaring's bit containers win contains (~1.4×–1.9×). Roaring's specialized rank index makes its rank/select faster than Expanse's count_below/by_count — use Expanse for membership, Roaring for heavy rank/select.
• Clustered / Dense (>50% density): ExpanseSet achieves 0.07–0.36 bytes/key (measured: Apple M1, bytes_per_key example, commit 6c63826a — deterministic allocator accounting), matching Roaring's run/bit container compression while providing $O(\text{depth})$ forward and backward iteration.

2. ExpanseMap vs hashbrown::HashMap & BTreeMap

• Point Lookups vs BTreeMap: ExpanseMap point lookups are 2.9×–14.5× faster than std::collections::BTreeMap at 1M keys (e.g. sequential 11.9 ns vs 108.9 ns, clustered 12.9 ns vs 110.2 ns) (measured: reference host, commit 695b98d, benches/compare.rs). Full ordered iter() is now faster than BTreeMap::iter() for dense key distributions at 1M keys — sequential 0.7×, clustered 0.8×, random 0.5× (2× faster) the time of BTreeMap::iter() — after #245's stack-based zero-allocation iterator (a 2.2×–9.4× speedup over the pre-#245 6.8×/6.4×/2.1×-slower readings). Sparse-key iteration remains ~4.7× slower (was 10.4×), a structural residual tracked in #270 (measured: reference host — Intel i9-12900F, 24 threads, commit 46529f19, benches/compare.rs); see docs/DATABASE.md §7.1.
• Random Lookups vs Swiss Tables: on uniform-random 64-bit keys hashbrown::HashMap (Swiss Table) is faster for raw membership (its $O(1)$ probe beats trie descent — measured ~1.7×–3.1× on 1M random keys); ExpanseMap trades that for strict key ordering, ordered iteration, $O(1)$ prefix search, and a smaller memory footprint on clustered integer sets. On sequential keys the two are near parity (11.9 ns vs 12.1 ns at 1M). The random-key gap is a working-set-vs-cache crossover, not a fixed weakness: it is within ~1.1× of hashbrown while the set is cache-resident (10k: 10.0 ns vs 8.9 ns) and widens to ~2.9× at 1M once the working set exceeds L2/L3 and each of the ~5 trie descents misses to DRAM, versus hashbrown's single probe — a scale/cache effect, verified stable (no regression) (measured: reference host, commit 4a12f046).

Multithreaded OCC Concurrency Scalability

Expanse provides lock-free optimistic concurrency control (SyncExpanseMap / SyncExpanseSet in benches/concurrency.rs):

Combined SyncExpanseMap throughput (read + write ops/s), 1,000,000 random keys, 500 ms windows (measured: reference host — Intel i9-12900F, 24 threads, 30 MiB L3, Ubuntu 22.04 / kernel 6.8, commit 695b98d; benches/concurrency.rs):

• Read-only scaling is near-linear (12.0× at 16 threads, 265.8 M ops/s) — this is the reproducible measurement behind the "~260 M ops/s" headline (the earlier 78.4 M table figure was undermeasured and is retracted). SyncExpanseSet is marginally higher (284.9 M ops/s at 16 threads, 12.2×).
• Write-mixed workloads do not scale on the current protocol: a single tree-level seqlock still brackets whole operations for the root snapshot, so under an active writer the version changes faster than a walk completes and readers fall back to the mutex. 95/5 peaks at ~4 threads and 50/50 declines monotonically — the measured go/no-go signal for the per-node OCC refinement tracked in docs/ARCHITECTURE.md §6. Prior docs claiming "6.9× linear scaling" / "58.2 M ops/s" on write-mixed workloads overstated this and are corrected.
• Mechanism: Fine-grained per-node version bracketing and epoch-based pointer reclamation allow concurrent readers to validate subtrees hand-over-hand without acquiring mutexes; today only the read-only path realizes full scaling (see the divergence above).

Microarchitecture Scaling: x86-64-v1 vs v2 vs v3 vs v4

Expanse exploits hardware primitives via glibc-hwcaps and native CPU compilation (the instruction-reduction figures below are deterministic Callgrind instruction counts, not wall-clock; not tagged to a specific commit here):

See docs/BENCHMARKING.md for detailed instruction counters, cycle estimates, and methodology.

Performance vs Stock libjudy

Instructions retired and wall-clock latency through the identical C ABI on identical key streams, both libraries dlopen'd — measured via paired A/B rounds (interleaved median of 5 rounds). Below 1.00 = libexpanse does less work / runs faster than original libjudy.

Provenance. Two column families with different bases. The instruction-retired columns (M inst, .so / rlib ratios) are deterministic Callgrind counts on the standard portable baseline (x86-64-v1, no runtime SIMD) and are reproducible. The wall-clock ns rows (the four 1M-population rows) are now measured on the dedicated quiet host — Intel i9-12900F, 24 threads, 30 MiB L3, Ubuntu 22.04 / kernel 6.8, commit 43b46f38; harness crates/expanse-capi/examples/bench_vs_libjudy.rs, interleaved A/B median of 5 rounds, load < 0.5 — with native runtime feature detection active (AVX2/BMI2), so their single ratio is the linked-capi surface vs stock libjudy, not a .so/rlib pair. The B/k memory columns are deterministic byte accounting. Honest reading of the refreshed ns rows: libexpanse wins on sequential/clustered insert (~1.75×/~1.1×) and clustered lookup (~1.2×), and is ~11% slower on random 1M lookup — the earlier "0.55× / 45% faster" random-lookup figure was measured under load and is retracted (the quiet-host result agrees with the M-series development-laptop reading that random lookup is the engine's weak arm). See docs/BENCHMARKING.md for the full six-row reference-host table.

Compatibility Gates (Standing CI, 100% Green)

Platform Support

32-Bit Embedded Microprocessor Architecture (#![no_std])

Expanse provides first-class support for 32-bit embedded microprocessors (ExpanseSet32, ExpanseMap32, ExpanseBlobMap32) designed to operate in tightly constrained internal SRAM:

• Compact 8-Byte Edge32: 50% structural SRAM reduction vs 64-bit descriptors ([ptr (4B) | aux (3B) | tag (1B)]), packing up to 7 immediate keys with zero heap allocations.
• 32-Byte Cache Alignment: Nodes are sized for embedded microarchitectures (BranchL2_32 = 32B = 1 cache line on Cortex-M7/ESP32; BranchL6_32 = 64B = 2 cache lines).
• Polymorphic ValueSlot32: Payloads $\le 3\text{ bytes}$ (CAN-bus flags, status codes, checksums) fit inline with zero heap allocations.
• Microcontroller SRAM Footprint — real mem_used() byte accounting from cargo run --release --example bytes_per_key_32 (measured, commit 6c63826a; deterministic — host-independent for the fixed 8-byte Edge32 layout):
  • Clustered sensor timestamps (10k consecutive): $0.67\text{ B/key}$.
  • Sparse 29-bit CAN IDs (500 IDs): $12.61\text{ B/key}$ (genuinely sparse — a handful of keys spread across the 29-bit space).
  • IPv4 subnet /24 routing map (2k routes): $9.38\text{ B/key}$.
  • Dense consecutive map (10k, u32→u32): $5.21\text{ B/key}$.

Distribution & Quick Start

1. Rust / Cargo (64-Bit & 32-Bit)

[dependencies]
expanse-trie = "0.4.0"

use expanse_trie::{ExpanseMap, ExpanseMap32};

fn main() {
    // 64-bit server map
    let mut map = ExpanseMap::new();
    map.insert(42, 100);
    assert_eq!(map.get(42), Some(100));

    // 32-bit embedded map
    let mut map32 = ExpanseMap32::new();
    map32.insert(100, 500);
    assert_eq!(map32.get(100), Some(500));
}

2. Debian / Ubuntu Official APT Repository

# Add official repository
echo "deb [trusted=yes] https://orieg.github.io/expanse/apt/ stable main" | sudo tee /etc/apt/sources.list.d/expanse.list

# Update & install runtime, dev headers, and legacy Judy compatibility symlinks
sudo apt-get update
sudo apt-get install -y libexpanse1 libexpanse-dev libjudy-compat

3. Enterprise Linux Official RPM Repository (RHEL / CentOS / Fedora / Rocky / Amazon Linux)

# 1. Add official repository configuration
sudo dnf config-manager --add-repo https://orieg.github.io/expanse/rpm/expanse.repo

# 2. Update & install runtime, dev headers, and legacy Judy compatibility symlinks
sudo dnf install -y libexpanse libexpanse-devel libjudy-compat

4. Modern C API (expanse.h)

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

int main(void) {
    expanse_map_t *map = expanse_map_new();
    
    // Insert key -> value
    expanse_map_insert(map, 42, 100, NULL);
    
    // Fast O(depth) lookup
    uint64_t val;
    if (expanse_map_get(map, 42, &val)) {
        printf("Key 42 -> %lu\n", val);
    }
    
    // Exact byte memory accounting
    printf("Memory: %zu bytes\n", expanse_map_mem_used(map));
    
    expanse_map_free(map);
    return 0;
}

Compile and link directly:

gcc main.c -lexpanse -o main

5. Modern C++20 Header-Only API (expanse.hpp)

#include <iostream>
#include <string_view>
#include <expanse.hpp>

int main() {
    // 1. Bitset (Judy1) with range iteration & O(depth) rank/select
    expanse::set s;
    s.insert(42);
    s.insert(100);
    for (uint64_t key : s) {
        std::cout << "Key: " << key << "\n";
    }
    std::cout << "Rank of 50: " << s.rank(50) << "\n";

    // 2. Word map (JudyL) with operator[] and structured binding iteration
    expanse::map<uint64_t, uint64_t> m;
    m[42] = 1000;
    for (auto [k, v] : m) {
        std::cout << k << " -> " << v << "\n";
    }

    // 3. String trie (JudySL) with std::string_view keys
    expanse::str_map<uint64_t> sm;
    sm["apple"] = 10;
    sm["banana"] = 20;

    // 4. Large-value off-heap blob map with zero-copy views
    expanse::blob_map bm;
    bm.insert(1, std::string_view("arbitrary payload bytes"), 0x01);
    if (auto view = bm.get(1)) {
        std::cout << "Blob: " << view->as_string_view() << "\n";
    }

    // 5. Multi-threaded OCC lock-free concurrent map
    expanse::sync_map sync_m;
    sync_m.insert(10, 500);
    auto reader = sync_m.make_reader();
    std::cout << "Read concurrent: " << reader.get(10).value_or(0) << "\n";
    return 0;
}

Compile with any C++20 compiler:

clang++ -std=c++20 main.cpp -Iinclude -lexpanse -lpthread -ldl -lm -o main

6. Drop-in Legacy C API (Judy.h)

#include <stdio.h>
#include <Judy.h>

int main(void) {
    Pvoid_t judy = (Pvoid_t)NULL;
    Word_t *val;
    
    // JudyL insert macro
    JLI(val, judy, 42);
    *val = 100;
    
    // JudyL lookup macro
    JLG(val, judy, 42);
    printf("Value: %lu\n", *val);
    
    // Exact memory used macro
    Word_t bytes;
    JLMU(bytes, judy);
    printf("Memory: %lu bytes\n", bytes);
    
    // Free array macro
    Word_t freed;
    JLFA(freed, judy);
    return 0;
}

Compile with -lexpanse or drop-in -lJudy:

gcc legacy.c -lJudy -o legacy

7. Windows MSVC / vcpkg / NuGet

• Release Bundle: expanse-v0.4.0-x86_64-pc-windows-msvc.zip with DLL, import lib, and headers.
• vcpkg: vcpkg install expanse using extra/vcpkg/.
• NuGet: Visual Studio C++ package template in extra/nuget/.

8. Python Quickstart (pip install expanse-trie)

from expanse_trie import ExpanseSet, ExpanseMap, SyncExpanseMap

# 1. Dynamic sparse 64-bit integer set (Judy1)
s = ExpanseSet([10, 20, 50, 100])
assert 20 in s
assert s.next_at_or_after(25) == 50
assert s.count_range(10, 50) == 3

# 2. Key-value associative map (JudyL)
m = ExpanseMap({1: 100, 2: 200})
m[42] = 1000
assert m.range(0, 50) == [(1, 100), (2, 200), (42, 1000)]

# 3. Multithreaded lock-free OCC map (GIL-free queries)
sync_m = SyncExpanseMap({10: 100})
assert sync_m[10] == 100

See docs/bindings/python.md for full Python documentation and benchmarks.

9. Java & Scala Quickstart (io.github.orieg:expanse-java)

Not yet on Maven Central. No io.github.orieg artifact is published (Maven Central returns 404 / numFound:0), and no release-workflow job currently builds or deploys the Java bindings. Build from bindings/java locally until first publish. The coordinates below are the planned ones.

<dependency>
    <groupId>io.github.orieg</groupId>
    <artifactId>expanse-java</artifactId>
    <version>0.4.0</version>
</dependency>

import io.github.orieg.expanse.ExpanseMap;
import io.github.orieg.expanse.ExpanseSet;

// Zero-allocation, off-heap ordered map & set (Project Panama FFM)
try (ExpanseMap map = new ExpanseMap();
     ExpanseSet set = new ExpanseSet()) {
    // Inserts & lookups with zero JVM heap allocations
    map.put(42L, 1000L);
    long val = map.getOrDefault(42L, -1L);

    set.add(100L);
    set.add(200L);
    long count = set.countRange(50L, 250L); // O(depth) rank
}

See docs/bindings/java.md for Panama FFM architecture, GC elimination benchmarks, and Spark/Flink off-heap integration patterns.

10. .NET & C# Quickstart (Orieg.Expanse)

Not yet on NuGet.org. The Orieg.Expanse package does not resolve yet (NuGet returns 404 / totalHits:0); the version badge above renders "not found" until first publish. The release.yml push step is wired (OIDC trusted publishing) but has not landed a package. Build from bindings/dotnet locally until then.

dotnet add package Orieg.Expanse

using Expanse;

// Zero-GC, off-heap ordered bit set & word map
using var set = new ExpanseSet();
using var map = new ExpanseMap();

set.Add(42);
map[42] = 1000;

ulong rank = set.Rank(100); // O(depth) rank
bool found = map.TryGet(42, out ulong value);

See bindings/dotnet/README.md for full .NET documentation and guides.

See bindings/go/README.md for full Go documentation.

11. PHP Quickstart (orieg/expanse)

composer require orieg/expanse

use Expanse\Set;
use Expanse\Map;

$set = new Set();
$set->add(42);
$rank = $set->rank(100);

$map = new Map();
$map->set(42, 1000);
$val = $map->get(42);

See docs/bindings/php.md and bindings/php/README.md for full PHP documentation.

12. Node.js, Bun & Deno Quickstart (npm i @orieg/expanse)

npm install @orieg/expanse
# or bun add @orieg/expanse

import { ExpanseSet, ExpanseMap, ExpanseBlobMap } from '@orieg/expanse';

// 1. Dynamic sparse 64-bit integer set (Judy1)
const set = new ExpanseSet([10n, 20n, 50n, 100n]);
console.log(set.has(20n));               // true
console.log(set.next(25n));              // 50n
console.log(set.countRange(10n, 50n));   // 3n

// 2. Key-value associative map (JudyL)
const map = new ExpanseMap();
map.set(42n, 1000n);
console.log(map.get(42n));               // 1000n

// 3. High-performance polymorphic blob map (inline packing + arena)
const blobmap = new ExpanseBlobMap();
blobmap.set(1n, Buffer.from('inline'), 10 /* 32-bit hot metadata */);
const res = blobmap.getWithMeta(1n);
console.log(res.isInline);               // true (0 heap allocations)
See [crates/expanse-node/README.md](crates/expanse-node/README.md) for full Node.js documentation.

### 11. Espressif ESP-IDF Component (ESP32, ESP32-C3, ESP32-C6, ESP32-S3)

Add `expanse` to your ESP-IDF project's `main/idf_component.yml`:
```yaml
dependencies:
  expanse:
    version: "^0.4.0"

Or clone directly into your project's components/ directory:

git clone https://github.com/orieg/expanse.git components/expanse

#include "expanse.h"
#include "expanse_esp_idf.h"
#include "esp_log.h"

void app_main(void) {
    // 32-bit digital map (compact 8-byte Edge32, 32-byte cache line aligned)
    expanse_map_t *map = expanse_map_new();
    expanse_map_insert(map, 0x18FF50E5 /* CAN ID */, 42 /* Sensor Value */);

    uint32_t val = 0;
    if (expanse_map_get(map, 0x18FF50E5, &val)) {
        ESP_LOGI("expanse", "Found CAN ID 0x18FF50E5 -> Value %u", (unsigned int)val);
    }
    expanse_map_free(map);
}

See components/expanse/README.md for full ESP-IDF component documentation and Kconfig options. See docs/PACKAGING.md for full packaging instructions across all platforms.

Clean-Room Statement

The original Judy C library is LGPL. No code from it has been consulted or ported. This implementation derives strictly from published algorithm papers and shop manuals:

• Doug Baskins, A 10-Minute Description of How Judy Arrays Work and Why They Are So Fast (Hewlett-Packard, 2002)
• Alan Silverstein, Judy IV Shop Manual (Hewlett-Packard, 2002)

C API compatibility is defined by the documented API contract (man pages, published documentation) and validated by black-box differential testing. Licensed under MIT OR Apache-2.0.

License

Dual-licensed under MIT or Apache-2.0, at your option.