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) scaling linearly up to 260.9M ops/s on 16 cores with zero read locks.
• Ultra-Dense Memory Packing: Down to 0.07–0.36 bytes/key on 64-bit sets and 0.51 bytes/key on 32-bit embedded sets.

Visual Performance Comparison

API Surfaces

Legacy ↔ modern naming:

Modernization Thesis

Full architectural specifications: docs/ARCHITECTURE.md · Embedded 32-Bit RFC: docs/RFC_32BIT_EMBEDDED.md · Large-Value RFC: docs/RFC_LARGE_VALUES.md · Database engine patterns: docs/DATABASE.md · CI/CD Standards: docs/CI_CD_GUIDE.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 contiguous 64-byte SIMD leaf scans, achieving 2.1×–3.4× faster range scans than std::collections::BTreeMap, and official RocksDB Pluggable MemTable (integrations/rocksdb) integration.
• Zero-Copy Shared-Memory Analytics: Position-independent base-relative layouts for cross-worker IPC and parallel query execution with zero serialization.

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):

1. ExpanseSet vs RoaringBitmap

• Sparse (<0.1% density): Expanse point lookups (contains) and rank/select are 1.3×–1.8× faster than Roaring Bitmaps due to direct tagged pointer immediate storage.
• Clustered / Dense (>50% density): ExpanseSet achieves 0.07–0.36 bytes/key (deterministic memory budget), matching Roaring's run/bit container compression while providing $O(\text{depth})$ forward and backward iteration.

2. ExpanseMap vs hashbrown::HashMap & BTreeMap

• Ordered Range Scans (range(), iter_from()): ExpanseMap traverses sorted integer ranges 2.1×–3.4× faster than std::collections::BTreeMap by skipping empty branch expanses in cache lines.
• Random Lookups vs Swiss Tables: ExpanseMap point lookups run within 1.1× of hashbrown::HashMap (Swiss Table) on 64-bit integer keys while providing strict key ordering, $O(1)$ prefix search, and 40% lower memory footprint on clustered integer sets.

Multithreaded OCC Concurrency Scalability

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

• Mechanism: Fine-grained per-node version bracketing and epoch-based pointer reclamation allow concurrent readers to validate subtrees hand-over-hand without acquiring mutexes or stalling writers.

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

Expanse exploits hardware primitives via glibc-hwcaps and native CPU compilation:

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, main). Ratios below are measured on the standard portable baseline (x86-64-v1 on Linux, AArch64 on macOS) with runtime CPU feature detection. Below 1.00 = libexpanse does less work / runs faster than original libjudy.

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:
  • Clustered sensor timestamps: $0.51\text{ B/key}$ ($97.9%$ SRAM saved vs $24\text{ B/key}$ BTreeSet).
  • Sparse 29-bit CAN IDs: $0.63\text{ B/key}$ ($97.4%$ SRAM saved vs $24\text{ B/key}$ BTreeSet).
  • IPv4 subnet /24 routing: $8.03\text{ B/key}$ ($74.9%$ SRAM saved vs $32\text{ B/key}$ BTreeMap).
  • OTA firmware chunk metadata: $8.00\text{ B/key}$ ($83.3%$ SRAM saved vs $48\text{ B/key}$ BTreeMap).

Distribution & Quick Start

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

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

<dependency>
    <groupId>io.github.orieg</groupId>
    <artifactId>expanse-java</artifactId>
    <version>0.3.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.

8. .NET & C# Quickstart (Expanse.NET)

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.

9. 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 for full Node.js documentation. 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.