Skip to main content

Expanse

CI Crates.io Version npm Version NuGet Version PyPI Version APT Repository RPM Repository Architectures MSRV License DOI

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.

Jump to: Install · Key features · Benchmarks · Quick starts by language · Platforms · Packaging guide


Install

The C library (libexpanse, headers, man pages, and the libJudy drop-in links):

# macOS, or Homebrew on Linux (formula ships from v0.7.0)
brew install orieg/tap/expanse
# The formula conflicts with Homebrew's stock `judy` (both install Judy.h and libJudy);
# if judy is installed, `brew unlink judy` first. The judy keg stays at `$(brew --prefix judy)`.

# 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 / Rocky / Amazon Linux
sudo dnf config-manager --add-repo https://orieg.github.io/expanse/rpm/expanse.repo
sudo dnf install -y libexpanse libexpanse-devel libjudy-compat

Prebuilt archives for Linux (glibc, musl), macOS and Windows, with SHA256SUMS, are on the Releases page; vcpkg, NuGet and MacPorts are covered in the packaging guide.

Language packages:

Language Install Quick start
Rust cargo add expanse-trie Rust
Python pip install expanse-trie Python
Node.js / Bun / Deno npm i @orieg/expanse Node.js
.NET dotnet add package Orieg.Expanse .NET
Java / Scala Maven io.github.orieg:expanse-java Java
PHP composer require orieg/expanse PHP
Ruby gem install expanse docs/bindings/ruby.md
Go go get github.com/orieg/expanse/bindings/go bindings/go
WebAssembly npm i @orieg/expanse-wasm crates/expanse-wasm
ESP-IDF component components/expanse ESP-IDF

Then link with -lexpanse (or keep -lJudy), or see the C, C++ and legacy Judy.h examples.


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

  • Verified drop-in for libJudy: swap -lJudy for -lexpanse, or LD_PRELOAD libexpanse.so, with no source change (Judy1, JudyL, JudySL, JudyHS; 64-bit builds). Four standing CI gates check it: a differential oracle against a dlopen'd stock libJudy on all four families, including zmap's JudyHS evict-and-reinsert window; the php-judy suite at 221/221 on Linux and macOS; the same suite built with Windows MSVC; and LD_PRELOAD transcripts identical to stock, among them a replay of MariaDB OQGraph's Judy1 colour map. Unmodified stress-ng, zmap and OQGraph have been run against it: Verified in real projects.
  • Faster than stock libJudy on most measured shapes, not all: through the identical C ABI at 1,000,000 keys, libexpanse takes 0.379–0.884× stock's time on sequential, random and clustered insert and lookup, every BCa 95% upper bound at or below 0.892 in two runs (measured: Intel Core i9-12900F reference host, commit cbbc762a; results/baseline_vs_libjudy.json, results/baseline_vs_libjudy_run2.json; workload: capi_bench_vs_libjudy). It is slower on sequential lookup at 100,000 keys, on stress-ng's 4 Mi-key inserts and deletes, on OQGraph's colour map, and by the widest margin on stress-ng's many-small-array hashjudy method (puts 0.105–0.157× stock's rate, 49–77× its peak memory); it also holds more memory on zmap's sparse window. Callgrind counts fewer instructions than stock on 24 of the 25 vs-stock operations and more on JudyHSIns with route keys (1.076×) (measured: same host and commit, results/baseline_vs_stock.json; workloads differ: capi_vs_stock vs capi_bench_vs_libjudy); an instruction count is not a timing. Wins · Losses.
  • Pure Rust: std by default on every target, and no_std + alloc with default-features = false (CI checks that build for riscv32imac, riscv32imc and thumbv7em-none-eabihf); zero external runtime dependencies. Checked under Miri and Loom in CI. The Sync* wrappers' two undefined-behaviour classes (an optimistic-read data race and &T/&mut aliasing over the engine, #1086) are closed on the 64-bit and 32-bit wrappers; a nightly Miri census runs each concurrent workload under the race detector and both aliasing models, and .github/miri-ub-sites.json records every entry clean, an observation at its seed range rather than a proof.
  • Hardware Acceleration & Portability: SSE2 leaf and branch kernels on every x86-64 build, with runtime CPUID dispatch to POPCNT and BMI2 PDEP on x86-64 only; NEON byte-equality kernels on ARM64 (compile-time baseline, no runtime dispatch). Every other target — 64-bit RISC-V (RV64GC) and bare-metal 32-bit embedded (RV32IMAC, Cortex-M4/M7) — runs the portable scalar paths. glibc-hwcaps variants (x86-64-v2/v3/v4) are a build recipe, not part of the released packages (docs/COMPAT.md).
  • Concurrent Readers and Writers: Every Sync* wrapper serves readers that take no lock on the common path and concurrent writers through optimistic lock coupling (a blocking protocol, not lock-free). SyncExpanseMap serves 322.8 M reads/s [322.1, 323.5] and 321.6 M reads/s [321.2, 322.1] at 16 threads in two independent runs, BCa 95% over 18 rounds (measured: reference host, commit f9853201; baseline_concurrent_mixed.json, baseline_concurrent_mixed_run2.json; workload: core_concurrency). Tables, losses and competitors.
  • Dense Memory Packing: Down to 0.07–0.36 bytes/key on dense and clustered 64-bit sets (ExpanseSet, key presence only) (measured: bytes_per_key example). A map stores an 8-byte value word per key, so it cannot go below 8 B/key: ExpanseMap measures 8.56–8.61 bytes/key on the same dense and clustered distributions at 1M keys (measured: deterministic mem_used() accounting, host-independent; bytes_per_key example, workload example_bytes_per_key; gated copy docs/visualizer_data.json → memory_budget) and ~0.31 bytes/key on clustered 32-bit embedded sets (measured: bytes_per_key_32 example). On uniform random keys per-key set cost is a sawtooth in key density, 7.08–21.02 bytes/key (measured: keyspace_density example; docs/ARCHITECTURE.md §3.5).

Visual Performance Comparison

Comparative Performance

OCC Concurrency Scalability

YCSB Workloads A–F: ExpanseMap / ExpanseBlobMap vs BTreeMap and SkipMap

Memory density across expanse occupancy: ExpanseSet bytes/key is a sawtooth in λ = N / 2¹⁶, with the LEAF_CAP cascade and both memory-budget cells marked


API Surfaces

Surface Crate / Package Deliverable
Native Rust API (64-Bit) crates/expanse (package expanse-trie) Pure-Rust library: ExpanseSet (bit set), ExpanseMap (word→word), ExpanseStrMap (string→word), ExpanseBytesMap (bytes→word), ExpanseBlobMap, plus iterators and the concurrent wrappers SyncExpanseSet, SyncExpanseMap, SyncExpanseStrMap, SyncExpanseBytesMap, SyncExpanseBlobMap (std feature)
Native Embedded Rust (32-Bit) crates/expanse (no_std with default-features = false) 32-bit microprocessor collections: ExpanseSet32 (bit set), ExpanseMap32 (u32→u32 map), ExpanseBlobMap32, and the concurrent SyncExpanseSet32 / SyncExpanseMap32, with compact 8-byte Edge32 layout and 32-byte cache line alignment
C ABI (libexpanse) crates/expanse-capi cdylib/staticlib exporting both the legacy Judy.h surface (Judy1*, JudyL*, JudySL*, JudyHS* — allowing consumers like php-judy to swap libJudy for libexpanse without source changes) and modern expanse.h
Modern C++20 Header include/expanse.hpp Modern header-only C++20 STL-compatible RAII wrapper (expanse::set, expanse::map, expanse::str_map, expanse::bytes_map, expanse::blob_map, expanse::sync_set, expanse::sync_map), std::span zero-copy access, std::forward_iterator ranges, and optimistic OCC readers
Java / Scala FFM API bindings/java (io.github.orieg:expanse-java) Java 22+ / 21 LTS Project Panama Foreign Function & Memory bindings: zero-GC off-heap collections (ExpanseMap, ExpanseSet, ExpanseStrMap, ExpanseBytesMap, ExpanseBlobMap, SyncExpanseMap, SyncExpanseSet), value slots, NavigableMap/NavigableSet adapters
.NET / C# API bindings/dotnet (Orieg.Expanse) .NET 8.0/9.0+ C# bindings & NuGet package via P/Invoke: zero-GC off-heap collections (ExpanseSet, ExpanseMap, ExpanseStrMap, ExpanseBytesMap, ExpanseBlobMap, ExpanseSyncMap, ExpanseSyncSet)
Go API bindings/go (github.com/orieg/expanse/bindings/go) Native Go bindings via CGO, or CGO-free via purego (CGO_ENABLED=0 or the expanse_purego build tag): zero-GC off-heap collections (Set, Map, StrMap, BytesMap, BlobMap, SyncSet, SyncMap)
PHP API bindings/php (orieg/expanse) Native PHP bindings via FFI & PIE: Expanse\Set, Expanse\Map, Expanse\StrMap, Expanse\BytesMap, Expanse\BlobMap, Expanse\SyncMap, Expanse\SyncSet
Python API bindings/python (pip install expanse-trie) High-performance Python extension via PyO3 (crates/expanse-py): ExpanseSet, ExpanseMap, ExpanseStrMap, ExpanseBytesMap, ExpanseBlobMap, SyncExpanseSet, SyncExpanseMap, SyncExpanseStrMap, SyncExpanseBytesMap, SyncExpanseOrderedBytesMap, SyncExpanseBlobMap, GIL-released queries
Node.js / Bun / Deno API crates/expanse-node (@orieg/expanse) Native high-performance N-API bindings via napi-rs: ExpanseSet, ExpanseMap, ExpanseStrMap, ExpanseBytesMap, ExpanseBlobMap, SyncExpanseMap, SyncExpanseSet
WebAssembly / Edge crates/expanse-wasm (@orieg/expanse-wasm) WebAssembly bindings for edge runtimes (Cloudflare Workers, Fastly) and browsers
Ruby API bindings/ruby (gem install expanse) Native Ruby extension via Fiddle / C ABI: Expanse::Set, Expanse::Map, Expanse::StrMap, Expanse::BytesMap, Expanse::BlobMap
RocksDB Pluggable MemTable integrations/rocksdb (rocksdb-expanse) Official RocksDB MemTableRep / MemTableRepFactory implementation. Against a fair variable-height skiplist baseline: 1.42× higher key density in RAM (13.2 vs 18.7 B/entry, deterministic accounting), point lookup 1.49× [1.4901, 1.5073], range seek 1.53× [1.5225, 1.5414], sequential scan 3.07×–3.14× [3.0480, 3.2269], batch scan 2.13× [2.0452, 2.3111] — each interval spans both runs (measured: reference host, two runs; baseline_rocksdb.json). Fewer L0 flushes is inferred (target). See docs/benchmarks/rocksdb_memtable/ and integrations/rocksdb/

Legacy ↔ modern naming:

Legacy C API Modern Rust Type Modern C Type Description
Judy1 ExpanseSet expanse_set_t Dynamic bit set / integer presence index
JudyL ExpanseMap expanse_map_t Word-to-word associative map
JudySL ExpanseStrMap expanse_strmap_t Null-terminated string-to-word map
JudyHS ExpanseBytesMap expanse_bytesmap_t Arbitrary byte array-to-word map

Modernization Thesis

Component Original Judy IV (2002) Expanse (2026)
Cache-line geometry Assumed 128-byte lines Nodes sized to 64-byte lines (1 or 2 cache lines per node)
Bit scan / rank SWAR bit hacks, unrolled loops Hardware POPCNT / TZCNT / LZCNT / ARM cnt (runtime CPUID dispatch on hot read paths; SWAR fallback on generic baseline builds; native in x86-64-v2/v3 packages)
Linear search Scalar unrolled byte compares Vectorized SIMD byte scans (SSE2 on x86-64, NEON on ARM64; AVX2/AVX-512 not yet implemented)
Allocation Custom 2001 chunk/buddy allocator High-performance slab page pooling + intrusive freelists
Pointer layout Full 16-byte JP per edge 16-byte Edge: word 0 is the raw untruncated 64-bit pointer, tag and metadata live in word 1 — zero upper-bit stealing, so it stays correct under 57-bit LA57 and 52-bit ARM64 LVA (encoding reference)
Concurrency Single-threaded, external locks Optimistic lock coupling: readers take no lock on the common path, and concurrent writers lock only the nodes they change (a blocking protocol, not lock-free)

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): Doc-ID tracking at 0.07–0.36 bytes/docID (presence only, no value) on clustered/dense sets — denser than Roaring Bitmaps on those distributions — with bitwise set algebra directly over compressed trie edges and $O(\text{depth})$ skip-scan acceleration.
  • MVCC Visibility Maps & Active Transaction Tracking (SyncExpanseSet): Optimistic active transaction (xid) tracking with no reader-side lock on the common path, and safe epoch reclamation under continuous OLTP churn.
  • Columnar String & Symbol Dictionaries (ExpanseStrMap): High-cardinality string deduplication and symbol tables using 8-byte chunk decomposition and tail collapse, preserving lexicographical order while sharing common prefix nodes.
  • Secondary Indexes & MemTables (ExpanseMap / ExpanseMemTableRep): Rebalance-free ordered key indexing, 2.7×–13.1× faster point lookups than std::collections::BTreeMap at 1M keys (workload: core_compare), and full ordered iter() faster than BTreeMap::iter() on sequential, clustered and random keys at 1M — sparse-key iteration, and iteration at 10k keys, are slower (measured: reference host, commit 82eb56af, two runs, results/baseline_compare.json and results/baseline_compare_run2.json; intervals in docs/BENCHMARKING.md); see docs/DATABASE.md §7.1. Ships an 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

Where Expanse wins, where it loses, and where to read the full tables. Losses are listed as plainly as wins; every suite publishes BCa 95% intervals per cell. Decision matrix: docs/DATABASE.md §7. Methodology: docs/BENCHMARKING.md. "Reference host" throughout is a quiet Intel Core i9-12900F; the commit, run and interval behind each figure are in the linked docs.

1. ExpanseSet vs RoaringBitmap

  • Sparse and clustered sets — Expanse. contains is 1.24×–2.09× faster: sparse 1.77× [1.76, 1.77] at 10k and 2.09× [2.08, 2.09] at 100k, clustered 1.59× [1.59, 1.60] and 1.24× [1.24, 1.24].
  • Dense sets and rank/select — Roaring. Its bit containers win dense contains by 7.86× [7.84, 7.89] at 10k and 3.11× [3.11, 3.13] at 100k, and its rank index beats count_below/by_count in every cell measured.
  • Memory — parity on dense data. ExpanseSet holds 0.07–0.36 bytes/key on clustered and dense sets (measured: bytes_per_key example, deterministic allocator accounting); that is key presence only — an ExpanseMap holding an 8-byte value per key measures 8.56–8.61 bytes/key on the same keys at 1M (same instrument), with ordered forward and backward iteration.

Rule of thumb: Expanse for membership on sparse and clustered sets, Roaring for dense sets and heavy rank/select (measured: reference host, 50% hit rate; results/baseline_comparative.json; workload: core_comparative).

2. ExpanseMap vs hashbrown::HashMap & BTreeMap

  • vs BTreeMap — Expanse on lookups. ExpanseMap point lookups are 2.7×–13.1× faster at 1M keys, from random keys (time ratio [0.367, 0.374]) to sparse ([0.076, 0.078]); sequential is [11.46, 11.91] ns vs [106.4, 107.4] ns (workload: core_compare). Ordered iter() at 1M keys is also faster on sequential, clustered and random keys ([0.558, 0.758]× the time of BTreeMap::iter()), but slower on sparse keys ([1.074, 1.088]×) and on every distribution at 10k keys (measured: reference host, commit 82eb56af, two runs, results/baseline_compare.json and results/baseline_compare_run2.json; intervals in docs/BENCHMARKING.md). Details: docs/DATABASE.md §7.1.
  • vs hashbrown — hashbrown on random keys. On 1M uniform-random keys std::collections::HashMap (a hashbrown Swiss table with std's default SipHash-1-3 hasher, RandomState) answers a lookup in [3.315, 3.375]× less time than ExpanseMap. The gap is small while the set is cache-resident ([1.142, 1.164]× at 10k). On sequential and sparse keys ExpanseMap is faster at both sizes, and on clustered keys it is faster at 10k and slower at 1M ([1.037, 1.050]×) (workload: core_compare) (measured: reference host, commit 82eb56af, two runs, results/baseline_compare.json and results/baseline_compare_run2.json; intervals in docs/BENCHMARKING.md). What Expanse offers in exchange: strict key ordering, ordered iteration, prefix search, and a smaller footprint on clustered integer keys.

Rule of thumb: a hash table for unordered point lookups on random or hashed keys — nothing in such a workload uses order or shared prefixes, which is what a trie is paid for; Expanse where order, prefix or range queries matter, or where keys are clustered. When a trie is the wrong tool: docs/DATABASE.md §7.3.

3. Trie competitors: ART, HOT and Masstree

Measured at 1M keys unless noted, ratios above 1 = Expanse faster. Full suites: ART · HOT · Masstree.

Competitor Point lookup Insert Ordered scan Memory
ART (integer keys) Expanse 1.54×–3.21× Expanse 4.84× (sequential) Expanse: k = 10 by 1.50×–1.53× on structured keys, 2.67× on random see suite
HOT (integer keys) Expanse in most cells; HOT on uniform-random map lookup, 0.946 [0.934, 0.960] mostly Expanse HOT: 0.39–0.52 on random keys at k = 1000 (100k keys) HOT flat 11.7–12.1 B/key (set); Expanse lower only for λ ∈ [8, 23]
HOT (string keys) Expanse on skewed 1.22×–2.00×; HOT on prefixed 0.80× Expanse on prefixed 1.34×–1.43× (ExpanseStrMap); HOT 0.74× (ExpanseBytesMap) HOT in 72 of 72 cells, 0.646 [0.643, 0.650] down to 0.050 [0.049, 0.050] HOT 36.2 vs 54.6 B/key (workload: hot_str_ptr)
Masstree (integer keys) Expanse 2.9×–13.5× Masstree 0.68×–0.75× on sorted random/sparse; Expanse 1.89× on shuffled random Expanse 1.08×–2.54× on structured keys and random at 1M; Masstree 0.49×–0.67× on random at 10k–100k Masstree flat 22.8 B/key; Expanse 17.6–20.0 for λ ∈ [8, 30], 23.8–24.7 past it
Masstree (string keys) Expanse on short 1.33×, skewed 1.47×, prefixed 1.12×; Masstree on counter 0.95× Masstree 0.43×–0.96× Masstree in 33 of 36 cells, 0.09×–0.83×; Expanse on prefixed k = 10, 1.53×–2.27× Masstree 33.9 vs 54.6 B/key (workload: masstree_str_map)

The two string-key Memory cells are deterministic allocator censuses at c1b604ad, after design B (#1586) moved ExpanseStrMap's node shells and suffix leaves into its allocator. Before it they read 36.2 vs 48.2 (HOT) and 33.9 vs 48.2 (Masstree), now superseded (two runs each, identical; hot_comparison §6, masstree_comparison §1).

Across the HOT integer suite, 112 of 144 latency cells go to Expanse, 31 to HOT (28 of them scans) and 1 to parity, identically in two runs.

  • Ordered scans are the systematic loss against HOT, on integer and string keys alike.
  • Insert verdicts are sorted-order verdicts. Ascending insertion is a B+-tree's best case; the Masstree random insert cell flips to Expanse on a shuffled permutation of the same keys.
  • Memory depends on density. Expanse's bytes/key is a sawtooth in expanse occupancy λ = N / 2¹⁶ (docs/ARCHITECTURE.md §3.5), while HOT and Masstree are flat, so the winner changes with λ.
  • Key-length limits. HOT and Masstree cap string keys at 255 bytes (HOT drops longer keys silently, Masstree refuses them); the Expanse arms are not restricted to match.
  • Concurrent arms (HOT-ROWEX, concurrent Masstree) are in the next section.

(measured: reference host, two runs per suite agreeing on every winner quoted; hosts, commits, intervals and per-cell artifacts are in the three suite READMEs linked above; workloads: art_scan, hot_latency, hot_memory_curve, hot_string_latency, hot_str_ptr, masstree_map_64bit, masstree_str_map. Memory figures are deterministic allocator censuses.)


Multithreaded OCC Concurrency Scalability

Every Sync* wrapper (SyncExpanseSet, SyncExpanseMap, SyncExpanseStrMap, SyncExpanseBytesMap, SyncExpanseBlobMap) serves concurrent readers and concurrent writers.

  • Readers take no lock on the common path. A reader samples a version, walks, and re-validates; retired memory is reclaimed through epochs.
  • Writers use optimistic lock coupling (Leis, Scheibner, Kemper & Neumann, DaMoN 2016): a writer locks only the node it changes, so writers on disjoint subexpanses proceed in parallel. After a bounded number of restarts, or for a structural change the lock-coupled path does not cover, an operation falls back to an exclusive section.
  • The protocol is blocking — not lock-free and not obstruction-free. A reader that takes no lock on the common path still spins while a writer's version bracket is open and falls back to the writer mutex after a bounded number of retries. Design, fallback paths and measured fallback rates: docs/ARCHITECTURE.md §4.1–4.2 and docs/benchmarks/concurrency/.

Throughput at 1 and 16 threads

Total operations per second (reads + writes), bounded keyspaces, two independent runs (measured: reference host, 16 hardware threads on 8 P-cores; intervals, commit and run links in concurrency §12 and docs/benchmarks/concurrency/results/baseline_concurrent_mixed.json; workload: core_concurrency).

arm keys → values 1 Thread 16 Threads, run 1 16 Threads, run 2 Scaling, run 1 / run 2
SyncExpanseMap (100% read) u64 → u64, 1M keys 35.4 M ops/s 323 M ops/s 322 M ops/s 9.12× / 9.15×
SyncExpanseSet (100% read) u64, 1M keys 76.4 M ops/s 523 M ops/s 529 M ops/s 6.84× / 6.93×
SyncExpanseMap (50R/50W mixed) u64 → u64, 1M keys 18.9 M ops/s 63.4 M ops/s 66.4 M ops/s 3.35× / 3.53×
SyncExpanseSet (50R/50W mixed) u64, 1M keys 34.5 M ops/s 127 M ops/s 129 M ops/s 3.67× / 3.73×
SyncExpanseBlobMap (100% read) u64 → 128-byte payload, 200k keys 28.9 M ops/s 267 M ops/s 267 M ops/s 9.23× / 9.24×
SkipMap (100% read) u64 → 128-byte payload, 200k keys 3.02 M ops/s 33.7 M ops/s 33.7 M ops/s 11.15× / 11.16×
SyncExpanseBlobMap (50R/50W mixed) u64 → 128-byte payload, 200k keys 11.9 M ops/s 13.2 M ops/s 13.4 M ops/s 1.11× / 1.13×
SkipMap (50R/50W mixed) u64 → 128-byte payload, 200k keys 2.15 M ops/s 17.8 M ops/s 17.6 M ops/s 8.25× / 8.23×
SyncExpanseBytesMap (100% read) 37-byte string → u64, 100k keys 10.5 M ops/s 117 M ops/s 116 M ops/s 11.09× / 11.10×
SyncExpanseStrMap (100% read) 37-byte string → u64, 100k keys 7.00 M ops/s 77.6 M ops/s 77.6 M ops/s 11.08× / 11.13×
DashMap<Vec<u8>, u64> (100% read) 37-byte string → u64, 100k keys 14.2 M ops/s 109 M ops/s 107 M ops/s 7.68× / 7.51×
SyncExpanseStrMap (50R/50W mixed) 37-byte string → u64, 100k keys 5.84 M ops/s 53.5 M ops/s 54.0 M ops/s 9.17× / 9.23×
SyncExpanseBytesMap (50R/50W mixed) 37-byte string → u64, 100k keys 4.85 M ops/s 40.0 M ops/s 38.9 M ops/s 8.26× / 8.17×
DashMap (50R/50W mixed) 37-byte string → u64, 100k keys 10.6 M ops/s 82.7 M ops/s 86.2 M ops/s 7.79× / 7.91×
Mutex<Expanse*> baselines (100% read) blob and string keys 8.67–35.3 M ops/s 2.65–5.76 M ops/s 2.70–5.65 M ops/s 0.16×–0.31× (collapse)

How to read it:

  • Compare rows only within a key type (u64 → u64, u64 → 128-byte payload, 37-byte string → u64). Populations and key widths differ between the three.
  • Read-only scaling holds to sixteen threads on every wrapper, where a Mutex around the same structure falls below its single-thread rate.
  • The 50R/50W rows are a mixed-operation rate, not read scaling: every thread picks a read or a write per operation. A write inserts or removes a uniform key, and half of each keyspace is present, so 0.25 of the writes remove a present key. The integer and string wrappers scale there; SyncExpanseStrMap reaches 53.5 M ops/s against 2.43 M for the same map behind one mutex, and SyncExpanseBytesMap 40.1 M against 2.65 M (workload: core_concurrency).
  • Known losses at 50R/50W: SyncExpanseBlobMap scales 1.11× / 1.13× to sixteen threads where SkipMap scales 8.2× on the same keys: its removals no longer serialise the writers (#1280), but it peaks at four threads, its in-window arena compactions take 0.15–0.28 of window time, and what limits it past four threads is unmeasured (concurrency §26–§27). DashMap serves 82.7 M ops/s on string keys against 53.5 M and 40.1 M for the two Expanse wrappers (workload: core_concurrency). Earlier blob 50R/50W figures timed an insert that failed once the arena reached its cap, and are withdrawn (#1280).

Against tries that admit concurrent writers

Competitor Writers only Eight readers alongside writers Details
HOT-ROWEX (integer keys) Expanse at one to eight writers, 1.11×–1.45× Expanse in every cell, 1.200–2.094 hot_comparison §7
Masstree (integer keys) Masstree in every cell, 0.921–0.936 at one writer and 0.689–0.723 at eight Expanse, 2.243–2.564 masstree_comparison §7
Masstree (short string keys) Masstree from one to eight writers, 0.803–0.816 at one; BOUNDARY_RESULT at sixteen Expanse, 1.241–1.337 masstree_comparison §7

Ratios are competitor-relative throughput, above 1 = Expanse faster; each range covers two runs of 15 interleaved rounds, with BCa 95% intervals per cell in the linked sections (measured: reference host; Masstree rows at c1b604ad, after design B; workloads: hot_rowex_set_63bit, hot_rowex_map_64bit, masstree_conc_map_64bit, masstree_conc_str). Neither arm carries hardware counters, so what sets these levels is unmeasured.


Microarchitecture Scaling: x86-64-v1 vs v3

Higher ISA tiers do not uniformly help. On the measured arch sweep — run 33030463060 on the idle reference host — clustered lookups gain 1.08×–1.14× over the portable baseline, random is flat to slightly worse (0.87×–0.95×), and sequential regresses, including an unexplained 0.34× x86-64-v2 cell at N = 10k (cause unknown; published as measurement, not finding). Full table and caveats: docs/BENCHMARKING.md.

Per-tier instruction counts are deterministic: docs/visualizer_data.json carries Callgrind counts for x86-64-v1 and x86-64-v3 on 22 arms of crates/expanse/benches/instructions.rs (which holds 93 #[library_benchmark] routines) — v1→v3 deltas on those 22 span −1.9% to −42.6% (largest on map_remove/random).


Compatibility Gates (Standing CI, 100% Green)

Gate Verification Target Status
G1: Differential Oracle Randomized operation sequences through libexpanse and a dlopen'd stock libjudy must agree identically, on all four families; includes zmap's JudyHS window pattern (evict the oldest key with JudyHSDel, re-insert evicted keys) 🟢 Passing
G2: php-judy Drop-in php-judy compiles unmodified against libexpanse; entire test suite passes (221/221 on Linux + macOS) 🟢 Passing
G3: Windows Parity php-judy compiles on Windows MSVC against expanse.dll / expanse.lib and passes full suite 🟢 Passing
G4: LD_PRELOAD Parity Unmodified binaries built against stock Judy run identically under LD_PRELOAD=libexpanse.so; a replay of MariaDB OQGraph's two-Judy1 colour map runs the same way preloaded, relinked and rebuilt on the shipped Judy.h 🟢 Passing

What each gate runs is in docs/COMPAT.md (drop-in gates) and docs/CI.md.

Verified in real projects

Each project ran unmodified, with only the library behind libJudy.so.1 (or the link line) changed. Ratios are libexpanse ÷ stock libJudy; for a rate, above 1 means libexpanse is faster, and for a time or a size, below 1 means it is. No independent, non-LLM review of these comparisons has been done.

Project What was checked Correctness libexpanse better libexpanse worse
stress-ng judy and sparsematrix --sparsematrix-method judy (suite) One stress-ng binary, its own per-phase rates and bogo-ops/s, 1 Ki, 256 Ki and 4 Mi keys at 1–8 workers; two runs of 12 rounds, two-sample BCa 95% Runs unmodified. The suite measures rates; it keeps no separate correctness record beyond stress-ng's own verified-get phase in sparsematrix bogo-ops/s 1.179–1.187× at 1 Ki keys (every lower bound ≥ 1.173) and 1.205–1.220× at 256 Ki (≥ 1.187), wall-clock time 0.847–0.851× and 0.822–0.832×; sparsematrix big 1.089–1.153× (≥ 1.088); sparsematrix default 1.003–1.006×, parity 4 Mi keys: inserts 0.951–0.993× (every upper bound ≤ 0.997), deletes 0.927–0.962× (≤ 0.966), bogo-ops/s 0.963–0.993× (#1679, #1680); sparsematrix default gets 0.936–0.937× (≤ 0.939)
stress-ng sparsematrix --sparsematrix-method hashjudy (many small arrays; suite) The same harness on the small-array shape: default is 500 JudyL arrays of about 20 keys, big 100,000 arrays of about 10, at 1 and 4 workers. A second set rebuilds stress-ng with JLFA added to hashjudy_destroy, which in stress-ng's own source frees no array, so every bogo op leaks its arrays with either library Runs unmodified. The suite measures rates and peak memory; it keeps no separate correctness record default gets 1.320–1.336× (every lower bound ≥ 1.314) The largest gap in the suite. puts/s 0.105–0.127× on big (every upper bound ≤ 0.128) and 0.147–0.157× on default (≤ 0.158); bogo-ops/s 0.174–0.240× (≤ 0.241) and 0.270–0.288× (≤ 0.290); big gets 0.418–0.488× (≤ 0.491); max-rss 77.08–77.21× on big and 49.40–49.49× on default. With the leak removed, default at 4 workers is still 0.326× [0.324, 0.328] and 0.324× [0.322, 0.327] on puts, 0.517× [0.515, 0.520] and 0.515× [0.512, 0.518] on bogo-ops/s, and 4.61× [4.54, 4.68] and 4.63× [4.58, 4.69] on max-rss; on big removing it changes neither puts nor max-rss. How the remaining gap splits between the small-array floor and other engine cost is unmeasured (#1738, #1742)
zmap response dedup, a 1,000,000-entry JudyHS window on 8-byte keys (§3.7; suite) The window's call pattern in CI, end-to-end scans, and the cachehash harness The window's evict-and-reinsert pattern matches stock in the differential oracle (G1). At 0.18.0, 0 dedup mismatches over 9,429,885 responses in 12 live runs (four configurations each on the stock build, the libexpanse build and the stock binary on libexpanse), and an identical churn differential (correctness record) Dense responders: peak RSS lower by 0.22–0.53 MB, every interval below zero. cachehash time per response (workloads: zmap_dedup_m1_miss, zmap_dedup_m2_dup50, zmap_dedup_m3_evict) 0.871 [0.867, 0.874] to 0.872 [0.869, 0.874], 0.884 [0.882, 0.886] in both runs, and 0.754 [0.729, 0.759] to 0.759 [0.758, 0.761] Sparse responders with the window full: peak RSS +10.05 [9.87, 10.11] and +10.09 [9.96, 10.28] MB, about 10% of stock's peak, and +13.06 and +13.27 MB through eviction, a characterised limitation (upper bounds: every target in the rig answers). cachehash RSS growth 1.196–1.206× stock's, every lower bound ≥ 1.194. End-to-end receive time per response 1.0045 [1.0028, 1.0065] and 1.0063 [1.0026, 1.0166] on zmap_e2e_e2_probes2; no difference detected on zmap_e2e_e1_probes1, 1.0026 [0.9996, 1.0093] and 1.0018 [0.9996, 1.0041]
MariaDB OQGraph, two Judy1 arrays as a breadth-first search's colour map (§3.2; suite) The colour-map call pattern in CI (G4) and Callgrind, top-down counters per call, the engine's mtr suite, and whole-query wall clock The colour-map replay is identical to stock in CI (G4). At 0.18.0 every timed query returned the same row count in every arm, round and run, over 40 cells (timed record). The mtr suite's results are identical, 26/26 tests and 1,428 SQL result comparisons (unsourced pending re-measurement: that record was not found with the timed record, #1682) 0.787× and 0.758× the instructions per search at 10k and 100k vertices (Judy1 colouring rows below) More cycles per Judy1 call despite fewer instructions: +6.34 [5.73, 6.97] and +7.56 [6.64, 8.29] at 10k vertices, +10.57 [9.81, 11.89] and +10.54 [9.57, 11.35] at 100k, from branch mispredicts and front-end stalls (topdown-bad-spec, topdown-fe-bound), a characterised limitation (#1728). Whole-query wall clock at 0.18.0 (82eb56af), two runs over 40 cells (workloads: oq_bfs_from, oq_bfs_path, oq_bfs_to, oq_dijkstra_from, oq_dijkstra_path, oq_leaves_from): the native expanse.h port 1.011–1.062× stock's time, slower in both runs on all 40 cells, every lower bound above 1 and every upper bound ≤ 1.078; the stock binary on libexpanse 0.998–1.060× (≤ 1.066), slower in both runs on 28; the Judy.h rebuild 0.991–1.040× (0.978 to 1.051 over every interval), slower in both runs on 16 and faster on 1. Not re-run since (#1682)
Small arrays (the per-array floor, COMPAT.md) Allocator accounting of a 20-key JudyL array, gated by the memory-budget CI job — — A 20-key array holds 20,864 B of slab pages (mem_held) for 384 B of live nodes; stock's resident cost is 399.3 B per such array, keys uniform on [0, 500), measured at 0.18.0 (evaluation record, #1666)

(stress-ng — measured: Intel Core i9-12900F reference host, P-cores pinned, libexpanse 5f4892932; diagnostic_delete_main_ref_run1.json, _run2, diagnostic_sm_main_ref_run1.json, _run2; workloads: sng_judy_1k, sng_judy_256k, sng_judy_4m, sng_sm_judy_default, sng_sm_judy_big. These main-branch figures are a diagnostic re-measure outside the suite's pre-registration, taken on the reference host only; the second host (AMD Zen 5) has not been re-run on main. stress-ng hashjudy — measured: same host and pin, libexpanse aacc1add4; diagnostic_hj_main_ref_run{1,2}.json (main against stock) and diagnostic_hj_leak_ref_run{1,2}.json (with and without the leak) under docs/benchmarks/stressng_comparison/results/, two-sample BCa 95%; workloads: sng_sm_hashjudy_default, sng_sm_hashjudy_big; also a re-measure outside the pre-registration. zmap memory — measured: 2× Xeon E5-2697 v4 (sparse) and the reference host (dense), libexpanse edee6bfa5, results/zmap_judyhs_rss_edee6bfa.json. zmap timing — measured: reference host, P-cores pinned one SMT sibling each, libexpanse edee6bfa5, two runs, two-sample BCa 95%, docs/benchmarks/zmap_comparison/results/rerun_edee6bfa/; zmap correctness — measured: reference host, libexpanse 82eb56af, docs/benchmarks/zmap_comparison/results/era_0_18_82eb56af/correctness/. Small-array stock RSS — measured: 2× Xeon E5-2697 v4, libexpanse 82eb56af, memprobe_small_arrays_82eb56af.json. OQGraph cycles — measured: reference host P-cores, commit 5e64fcf17, results/colour_topdown_5e64fcf17.json, two runs of 10 paired processes. OQGraph wall clock and timed row counts — measured: reference host, container on CPUs 0–15, mariadbd on 2,4,6,8 and the client on 10, libexpanse 82eb56af, MariaDB 8e291917, docs/benchmarks/oqgraph_comparison/results/era_0_18_82eb56af/, two runs of 10 rounds, paired BCa 95%, 0 void rounds; workloads: the six oq_* workloads on 40 cells. Small array — measured: deterministic bytes_per_key small-array rows, gated by the memory-budget CI job.)


Performance vs Stock libjudy

Wall-clock latency and instructions retired through the identical C ABI on identical key streams. Below 1.00 = libexpanse does less work / runs faster than original libjudy.

Provenance. Two runs of the harness at one commit (workload: capi_bench_vs_libjudy): 15 paired rounds per run, arms interleaved, 50% hit rate, value slot dereferenced, ratios expanse_dl / stock with BCa 95% intervals, expanse_dl being libexpanse.so dlopen'd exactly as stock is (measured: Intel Core i9-12900F reference host, commit cbbc762a, run 1 43689413621, run 2 43689749825; per-round data, load windows and byte counts in results/baseline_vs_libjudy.json and results/baseline_vs_libjudy_run2.json). The B/k columns are exact JudyLMemUsed accounting from the same runs, identical in every round, so they carry no interval. Every cell, 100,000 keys included, is in docs/BENCHMARKING.md.

Benchmark Workload (workload: capi_bench_vs_libjudy) Ratio, run 1 [BCa 95%] Ratio, run 2 [BCa 95%] Bytes/key (Expanse vs Stock) Status
Sequential 1,000,000 insert 0.379× [0.378, 0.380] 0.379× [0.378, 0.380] 8.56 B/k vs 8.32 B/k (1.03×) 🟢 0.38× stock's time; 3% more memory
Sequential 1,000,000 lookup 0.853× [0.850, 0.855] 0.849× [0.845, 0.853] 8.56 B/k vs 8.32 B/k (1.03×) 🟢 0.85× stock's time; 3% more memory
Random 1,000,000 insert 0.786× [0.783, 0.788] 0.785× [0.783, 0.787] 17.58 B/k vs 17.67 B/k (0.995×) 🟢 0.79× stock's time; memory at parity
Random 1,000,000 lookup 0.825× [0.821, 0.827] 0.828× [0.825, 0.832] 17.58 B/k vs 17.67 B/k (0.995×) 🟢 0.83× stock's time; memory at parity
Clustered 1,000,000 insert 0.794× [0.792, 0.796] 0.796× [0.793, 0.797] 8.61 B/k vs 9.32 B/k (0.92×) 🟢 0.80× stock's time; 8% less memory
Clustered 1,000,000 lookup 0.884× [0.881, 0.892] 0.879× [0.876, 0.882] 8.61 B/k vs 9.32 B/k (0.92×) 🟢 0.88× stock's time; 8% less memory
Sequential 100,000 lookup 1.102× [1.099, 1.107] 1.098× [1.097, 1.100] 8.57 B/k vs 8.41 B/k (1.02×) 🔴 1.10× stock's time, a loss in both runs

Instructions retired, in millions, through the same C ABI. .so is libexpanse.so dlopen'd exactly as stock is, and is the like-for-like arm; rlib is the Rust library linked into the harness with LTO, a shape no C consumer gets. Callgrind counts are exact integers, so they carry no interval, and they are not timings: the sequential 100,000-key lookup above is a wall-clock loss although every JudyLGet arm here retires fewer instructions than stock (measured: Intel Core i9-12900F reference host, commit cbbc762a, run 43689888414; results/baseline_vs_stock.json, 75 arms; harness crates/expanse-capi/benches/vs_stock.rs; workloads differ: capi_vs_stock vs capi_bench_vs_libjudy). The rows below are a subset; all 25 operations are in docs/BENCHMARKING.md.

Operation (workload: capi_vs_stock) Keys libexpanse .so libexpanse rlib stock libjudy .so / stock rlib / stock Instructions (.so)
JudyLIns, sequential 30,000 6.14 6.00 14.71 0.417× 0.408× 58% fewer
JudyLIns, random 30,000 17.11 16.67 18.98 0.901× 0.878× 10% fewer
JudyLIns, clustered 30,000 11.05 10.74 13.37 0.827× 0.804× 17% fewer
JudyLGet, sequential 30,000 4.20 4.35 6.69 0.628× 0.650× 37% fewer
JudyLGet, random 30,000 3.67 3.82 6.77 0.543× 0.565× 46% fewer
JudyLGet, clustered 30,000 3.48 3.63 5.86 0.594× 0.619× 41% fewer
JudyLGet, random 1,500,000 296.27 303.77 478.17 0.620× 0.635× 38% fewer
JudyL churn (upsert, insert neighbour, delete it), random 30,000 38.36 36.72 56.30 0.681× 0.652× 32% fewer
Judy1Set, random 30,000 14.18 14.27 17.26 0.822× 0.827× 18% fewer
Judy1Set, clustered 30,000 6.79 6.87 11.90 0.571× 0.577× 43% fewer
Judy1Test, random 30,000 3.88 3.88 5.77 0.673× 0.673× 33% fewer
Judy1 breadth-first colouring 10,000 vertices 22.19 22.30 28.19 0.787× 0.791× 21% fewer
Judy1 breadth-first colouring 100,000 vertices 254.77 255.23 336.28 0.758× 0.759× 24% fewer
JudyHSIns, fixed 8-byte keys 30,000 25.20 24.72 28.92 0.871× 0.855× 13% fewer
JudyHSIns, route keys 30,000 48.45 47.17 45.04 1.076× 1.047× 🔴 7.6% more

Where libexpanse is slower or larger than stock

Every loss measured so far, with its source:

  • Sequential lookup at 100,000 keys: 1.102× [1.099, 1.107] and 1.098× [1.097, 1.100] stock's time, a loss in both runs (workload: capi_bench_vs_libjudy, table above). At 1,000,000 keys the same lookup is a win.
  • JudyHSIns on route keys retires 1.076× stock's instructions through the .so and 1.047× through the rlib; every other vs-stock operation retires fewer (table above).
  • stress-ng at 4 Mi keys: inserts and deletes below stock's rate, and the sparsematrix default gets at 0.936–0.937× (Verified in real projects; #1679, #1680).
  • Many small arrays (stress-ng sparsematrix --sparsematrix-method hashjudy): puts 0.105–0.157× stock's rate and peak memory 49–77×, and with stress-ng's own leak removed still 0.32× on puts and 4.6× on memory at 4 workers (Verified in real projects; #1742).
  • Judy1 on a small key range (MariaDB OQGraph's colour map): more cycles per call than stock despite fewer instructions (docs/ARCHITECTURE.md §3.2, Known cost).
  • JudyHS peak memory on sparse 8-byte keys (zmap with a full window): about 10 MB more peak RSS (docs/ARCHITECTURE.md §3.7, Known cost).
  • Small arrays: a 20-key JudyL array holds 20,864 B of slab pages (docs/COMPAT.md).
  • Sequential keys' memory: 8.56 against 8.32 bytes/key at 1,000,000 keys, 1.03× (table above).

Platform Support

Platform Target Triple Distribution & Packaging
Linux x86-64 x86_64-unknown-linux-gnu libexpanse APT/RPM package, .tar.gz
Linux ARM64 aarch64-unknown-linux-gnu libexpanse APT/RPM package (Graviton, Raspberry Pi 4/5), .tar.gz
Linux RISC-V 64-bit riscv64gc-unknown-linux-gnu libexpanse APT/RPM package (RV64GC edge/server), .tar.gz
Linux x86-64 Static x86_64-unknown-linux-musl Static musl archives, Alpine Linux compatible .tar.gz
macOS Apple Silicon aarch64-apple-darwin Universal / Native AArch64 .tar.gz, Homebrew tap (orieg/tap/expanse), MacPorts Portfile
macOS Intel x86_64-apple-darwin x86-64 .tar.gz, Homebrew tap (orieg/tap/expanse), MacPorts Portfile
Windows x86-64 x86_64-pc-windows-msvc Precompiled expanse.dll / expanse.lib .zip, vcpkg, NuGet
RISC-V 32-Bit (RV32) riscv32imac-unknown-none-elf #![no_std] staticlib / embedded crate (design #109)
ARM Cortex-M (M4/M7) thumbv7em-none-eabihf #![no_std] staticlib / embedded crate (design #109); C ABI measured on-target on an STM32H747I-DISCO Cortex-M7 and Cortex-M4 (harness, results); executed on every PR on an emulated Cortex-M3 (thumbv7m-none-eabi, QEMU mps2-an385, smoke)
Espressif RISC-V (ESP-IDF) riscv32imc-unknown-none-elf (C2/C3 — RV32IMC, no A extension), riscv32imac-unknown-none-elf (C6/H2), riscv32imafc-unknown-none-elf (P4 — hard-float ilp32f, matching ESP-IDF) ESP-IDF Component (components/expanse/), #![no_std]. RISC-V parts only — the Xtensa ESP32/S2/S3 have no mainline rustc target. No Judy* symbols at 32-bit (docs). Per-part ISA, HP/LP core counts and CAS soundness are sourced to the Espressif datasheets/TRMs in docs/HARDWARE.md §4.3
WebAssembly (wasm32) wasm32-unknown-unknown npm @orieg/expanse-wasm (WasmExpanseMap32, WasmExpanseSet32)
WebAssembly Memory64 (wasm64) wasm64-unknown-unknown 64-bit engine (ExpanseMap, ExpanseSet), Node.js Memory64 (--experimental-wasm-memory64)

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; deterministic — host-independent for the fixed 8-byte Edge32 layout):
    • Clustered sensor timestamps (10k consecutive): $0.31\text{ B/key}$ (0.3120 B/key).
    • Sparse 29-bit CAN IDs (500 IDs): $9.86\text{ B/key}$ (9.8560 B/key — genuinely sparse, keys spread across 29-bit space).
    • IPv4 subnet /24 routing map (2k routes): $8.42\text{ B/key}$ (8.4160 B/key).
    • Dense consecutive map (10k, u32→u32): $4.42\text{ B/key}$ (4.4240 B/key).

Distribution & Quick Start

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

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

3b. macOS: Homebrew & MacPorts

brew install orieg/tap/expanse   # macOS, or Homebrew on Linux
brew test orieg/tap/expanse      # compiles and runs one program against expanse.h and one against Judy.h

Installs libexpanse (dylib and static), expanse.h / expanse.hpp / Judy.h, the manual pages, pkg-config files and the libJudy compatibility links; it also works under Homebrew on Linux. The formula declares conflicts_with "judy", since both install Judy.h and a libJudy library: if Homebrew's stock judy is installed, run brew unlink judy first. The judy keg stays in the Cellar and remains reachable at $(brew --prefix judy), which is where the oracle tests and bench_vs_libjudy look for stock libjudy on macOS. Upgrade with brew update && brew upgrade expanse. A MacPorts Portfile ships with every release — see docs/PACKAGING.md §2.15.

4. Modern C API (expanse.h)

#include <inttypes.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
    expanse_word_t val;
    if (expanse_map_get(map, 42, &val)) {
        printf("Key 42 -> %" PRIu64 "\n", (uint64_t)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 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);
    if (val != NULL) {
        printf("Value: %zu\n", (size_t)*val);
    }
    
    // Exact memory used macro
    Word_t bytes;
    JLMU(bytes, judy);
    printf("Memory: %zu bytes\n", (size_t)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.19.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 optimistic OCC map (GIL-free queries)
sync_m = SyncExpanseMap()
sync_m[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 yet (Maven Central returns 404 / numFound:0); publication is wired into .github/workflows/release.yml (package-maven) to deploy on release tags. 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.19.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, Java 22+)
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
}

JDK Baseline: Java 22+ (finalized Project Panama FFM - JEP 454). Requires --enable-native-access=ALL-UNNAMED. Java 21 LTS supported for source builds with --enable-preview. See docs/bindings/java.md for Panama FFM architecture, bundled multi-arch native platform matrix, GC elimination benchmarks, and Spark/Flink off-heap integration patterns.

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

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. Go (CGO or CGO-free purego): see bindings/go/README.md.

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 expanse from '@orieg/expanse'; // CommonJS package: named ESM imports are not exposed
const { ExpanseSet, ExpanseMap, ExpanseBlobMap } = 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'), 0 /* 24-bit hot metadata; 0 keeps a payload of <= 7 bytes inline */);
const res = blobmap.getWithMeta(1n);
console.log(res.isInline);               // true (0 heap allocations)
blobmap.set(2n, Buffer.from('tagged'), 10); // with metadata: an arena record that keeps it
console.log(blobmap.getWithMeta(2n).hotMeta); // 10

See crates/expanse-node/README.md for full Node.js documentation.

13. Espressif ESP-IDF Component (ESP32-C2/C3/C6/H2/P4, and ESP32/S2/S3 with the esp-rs toolchain)

Add expanse to your ESP-IDF project's main/idf_component.yml:

dependencies:
  expanse:
    version: "^0.19.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 aligned nodes).
    // Keys and values are expanse_word_t — one machine word, uint32_t here.
    expanse_map_t *map = expanse_map_new();
    expanse_map_insert(map, 0x18FF50E5 /* CAN ID */, 42 /* value */, NULL);

    expanse_word_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);
}

The 32-bit library exports the ordered expanse_set_* / expanse_map_* core and no Judy* symbols — the drop-in ABI is a 64-bit-only guarantee. See the surface matrix. 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:

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.


Citation

Expanse is archived on Zenodo. Machine-readable metadata is in CITATION.cff; GitHub renders it under Cite this repository.

Two DOIs are minted. Cite the concept DOI for the project as a whole — it always resolves to the latest release — or a version DOI to pin the exact release you used:

Scope DOI
Concept (all versions) 10.5281/zenodo.22152112
v0.11.1 10.5281/zenodo.23175906
v0.11.0 10.5281/zenodo.23143791
v0.10.2 10.5281/zenodo.23123969
v0.10.1 10.5281/zenodo.23096677
v0.10.0 10.5281/zenodo.23091733
v0.9.2 10.5281/zenodo.23043802
v0.9.1 10.5281/zenodo.23033289
v0.9.0 10.5281/zenodo.23005353
v0.8.2 10.5281/zenodo.22946275
v0.8.1 10.5281/zenodo.22930163
v0.8.0 10.5281/zenodo.22928508
v0.7.1 10.5281/zenodo.22901468
v0.7.0 10.5281/zenodo.22884696
v0.6.0 10.5281/zenodo.22569440
v0.5.0 10.5281/zenodo.22152113
@software{brousse_expanse,
  author  = {Brousse, Nicolas},
  title   = {{Expanse: clean-room Judy arrays in Rust with a
             drop-in libjudy C ABI}},
  year    = {2026},
  version = {0.19.0},
  doi     = {10.5281/zenodo.22152112},
  url     = {https://github.com/orieg/expanse}
}

If your claim depends on a measured number, cite the version DOI rather than the concept DOI: figures are re-measured between releases, and several changed in v0.5.0.


Contributing

CONTRIBUTING.md covers what a mergeable change looks like: the clean-room rule, scripts/gate.sh, the pull request flow, and the evidence standard any performance number has to meet. AGENTS.md is the full engineering guide behind it, for humans and coding agents alike. Bug, performance, and feature reports have issue forms that ask for the evidence triage needs; suspected vulnerabilities go through the private channel in SECURITY.md, never a public issue. Participation is covered by the Code of Conduct.


License

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

Metadata

Release files for expanse-trie 0.19.0

For a detailed explanation of source distributions (sdists) and built distributions (wheels), please see the package formats documentation.

Source distribution (sdist)

Source distribution for expanse-trie 0.19.0
File Size Uploaded Provenance Actions
expanse_trie-0.19.0.tar.gz 1.8 MB With provenance Details for expanse_trie-0.19.0.tar.gz

Built distributions (wheels)

Table of built distributions (wheels) for expanse-trie 0.19.0
File Actions
expanse_trie-0.19.0-cp310-abi3-win_amd64.whl CPython 3.10 abi3 Windows x86-64 Details for expanse_trie-0.19.0-cp310-abi3-win_amd64.whl
expanse_trie-0.19.0-cp310-abi3-manylinux2014_x86_64.manylinux_2_17_x86_64.whl CPython 3.10 abi3 Linux glibc 2.17+ x86-64 Details for expanse_trie-0.19.0-cp310-abi3-manylinux2014_x86_64.manylinux_2_17_x86_64.whl
expanse_trie-0.19.0-cp310-abi3-manylinux2014_aarch64.manylinux_2_17_aarch64.whl CPython 3.10 abi3 Linux glibc 2.17+ ARM64 Details for expanse_trie-0.19.0-cp310-abi3-manylinux2014_aarch64.manylinux_2_17_aarch64.whl
expanse_trie-0.19.0-cp310-abi3-macosx_11_0_arm64.whl CPython 3.10 abi3 macOS 11.0+ ARM64 Details for expanse_trie-0.19.0-cp310-abi3-macosx_11_0_arm64.whl
expanse_trie-0.19.0-cp310-abi3-macosx_10_12_x86_64.whl CPython 3.10 abi3 macOS 10.12+ x86-64 Details for expanse_trie-0.19.0-cp310-abi3-macosx_10_12_x86_64.whl

Total release size: 8.9 MB

Release files / expanse_trie-0.19.0.tar.gz

Download URL expanse_trie-0.19.0.tar.gz
Size 1.8 MB
Tags Source
SHA-256 checksum
How to use checksums
386f215600946a81b1a188b993136e1e0251aa827ca2f8ccaff5f311cf4d7b5b
BLAKE2b-256 checksum
How to use checksums
09e3a5331c7fdedabab2094130b8808dd0bda363a46d8db4f7dde93b30e0f502
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
Yes
Uploaded via twine/7.0.0 CPython/3.13.16

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

PyPI Publish Attestation

PyPI verified that this artifact, at this checksum, originated from the publisher listed below.

Signed by GitHub Actions, verified by PyPI on Nov 16, 2026.

Transparency log

Release files / expanse_trie-0.19.0-cp310-abi3-win_amd64.whl

Download URL expanse_trie-0.19.0-cp310-abi3-win_amd64.whl
Size 1.4 MB
Tags CPython 3.10 Windows x86-64 abi3
SHA-256 checksum
How to use checksums
685bf466671d6085001ac75bcb50054fe9dc901a13423e29122e508f7c721c0d
BLAKE2b-256 checksum
How to use checksums
6427f9c62c14559f2ae458a98a8f11d32cfc9c47ffdfa96e7e3d30d92f57d998
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
Yes
Uploaded via twine/7.0.0 CPython/3.13.16

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

PyPI Publish Attestation

PyPI verified that this artifact, at this checksum, originated from the publisher listed below.

Signed by GitHub Actions, verified by PyPI on Nov 16, 2026.

Transparency log

Release files / expanse_trie-0.19.0-cp310-abi3-manylinux2014_x86_64.manylinux_2_17_x86_64.whl

Download URL expanse_trie-0.19.0-cp310-abi3-manylinux2014_x86_64.manylinux_2_17_x86_64.whl
Size 1.5 MB
Tags CPython 3.10 Linux glibc 2.17+ x86-64 abi3
SHA-256 checksum
How to use checksums
3344027109d69771e6474c05e6926b3e273c3938be6c129fa8cc6f4c3bca659f
BLAKE2b-256 checksum
How to use checksums
294a3b4753f24a63b58459c80033730e56b130c3e8e60acf713167a7181af709
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
Yes
Uploaded via twine/7.0.0 CPython/3.13.16

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

PyPI Publish Attestation

PyPI verified that this artifact, at this checksum, originated from the publisher listed below.

Signed by GitHub Actions, verified by PyPI on Nov 16, 2026.

Transparency log

Release files / expanse_trie-0.19.0-cp310-abi3-manylinux2014_aarch64.manylinux_2_17_aarch64.whl

Download URL expanse_trie-0.19.0-cp310-abi3-manylinux2014_aarch64.manylinux_2_17_aarch64.whl
Size 1.4 MB
Tags CPython 3.10 Linux glibc 2.17+ ARM64 abi3
SHA-256 checksum
How to use checksums
11dd50b43735fb6dc01f32ab91f687bde064e425679b904bf00443d281677bf7
BLAKE2b-256 checksum
How to use checksums
05677a1527c532fb2adae464dd97ce6bd25ece54052b3b25cb5e1a6a9ed5a790
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
Yes
Uploaded via twine/7.0.0 CPython/3.13.16

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

PyPI Publish Attestation

PyPI verified that this artifact, at this checksum, originated from the publisher listed below.

Signed by GitHub Actions, verified by PyPI on Nov 16, 2026.

Transparency log

Release files / expanse_trie-0.19.0-cp310-abi3-macosx_11_0_arm64.whl

Download URL expanse_trie-0.19.0-cp310-abi3-macosx_11_0_arm64.whl
Size 1.3 MB
Tags CPython 3.10 abi3 macOS 11.0+ ARM64
SHA-256 checksum
How to use checksums
cc9eebc0bd82b21e18dea5b2e320fa96ff25a1862de8a78211b8ece78705e5ed
BLAKE2b-256 checksum
How to use checksums
a2e73151632a3e15b34f2908eaefd814087526ad5ac54f32f4c40ac79bb3a8d7
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
Yes
Uploaded via twine/7.0.0 CPython/3.13.16

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

PyPI Publish Attestation

PyPI verified that this artifact, at this checksum, originated from the publisher listed below.

Signed by GitHub Actions, verified by PyPI on Nov 16, 2026.

Transparency log

Release files / expanse_trie-0.19.0-cp310-abi3-macosx_10_12_x86_64.whl

Download URL expanse_trie-0.19.0-cp310-abi3-macosx_10_12_x86_64.whl
Size 1.5 MB
Tags CPython 3.10 abi3 macOS 10.12+ x86-64
SHA-256 checksum
How to use checksums
02ac97da0b116a29908b33be7ffc80b5d87924d6a12aecffd385011354d5f411
BLAKE2b-256 checksum
How to use checksums
d2790b22cbe145a892747e4952b64dc314142d1820abe4782b66a2231a30fc9c
Upload date
Uploaded using Trusted Publishing?
What is trusted publishing?
Yes
Uploaded via twine/7.0.0 CPython/3.13.16

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

PyPI Publish Attestation

PyPI verified that this artifact, at this checksum, originated from the publisher listed below.

Signed by GitHub Actions, verified by PyPI on Nov 16, 2026.

Transparency log

Security for expanse-trie 0.19.0

Provenance

Provenance describes where a file came from. On PyPI, provenance is shared via attestations, which provide a verifiable record of the build or publishing details. View details, limitations and caveats.

Full provenance

All 6 files in this release have been uploaded with provenance metadata.

Select from 6 files

Attestation for expanse_trie-0.19.0.tar.gz

PyPI Publish Attestation

PyPI verified that this artifact, at this checksum, originated from the publisher listed below.

Signed by GitHub Actions, verified by PyPI on Nov 16, 2026.

Transparency log

A note on package security

PyPI is a repository for distributing packages, not a service for auditing them. While third-party security researchers and our staff do their best to detect and remove malicious packages, PyPI cannot guarantee the quality, security or suitability of any given package.

To learn more about protecting yourself from malicious actors, visit our package security documentation.

Anthropic, PBC Visionary sponsor Bloomberg Visionary sponsor Hudson River Trading Visionary sponsor Meta Visionary sponsor NVIDIA Visionary sponsor Microsoft Sustainability sponsor Depot Continuous Integration AWS Cloud computing and Security Sponsor Datadog Monitoring Fastly CDN Google Download Analytics Sentry Error logging StatusPage Status page