artmap 0.1.0

A concurrent in-memory Adaptive Radix Tree (ART) featuring optimistic lock coupling.
Documentation

artmap is a high-performance, concurrent in-memory associative map backed by an Adaptive Radix Tree (ART), featuring Optimistic Lock Coupling (OLC) and Epoch-Based Memory Reclamation (EBR).

It combines the $O(k)$ key-length lookup time and prefix compression of adaptive radix trees with the multi-core write scalability of fine-grained node latching and non-blocking optimistic readers. It is designed as a drop-in replacement for concurrent skip lists (crossbeam-skiplist::SkipMap) and concurrent B-trees in high-throughput transactional database engines and in-memory stores.

Performance

Benchmarked on bare metal (AMD Ryzen Threadripper 9970X 32-Core / 64-Thread Processor @ 5.48 GHz, 128 GB DDR5 RAM, Linux 6.8):

Data Structure Point Read (Random Hit) Point Insert Range Scan (100 items) Allocations / Insert
artmap::ArtMap (Slice Lookup) 19.4 ns(51.5M/s) — — 0 allocs
artmap::ArtMap (Standard Key)  15.0 ns(66.8M/s)  36.1 ns(27.7M/s)  1.51 µs(66.1M/s) 1.0 allocs
crossbeam_skiplist::SkipMap 145.2 ns(6.9M/s) 96.9 ns(10.3M/s) 2.20 µs(45.5M/s) ~1.0 allocs
imbl::OrdMap 40.6 ns(24.6M/s) 72.1 ns(13.9M/s) 319 ns(314M/s) ~0.14 allocs
std::collections::BTreeMap 58.6 ns(17.1M/s) 38.1 ns(26.2M/s) 184 ns(542M/s) ~0.16 allocs
std::collections::HashMap* 13.1 ns(76.3M/s) 29.0 ns(34.4M/s) N/A ~0 allocs

* Rocket badge denotes the fastest implementation among ordered, concurrent range-scannable maps. std::collections::HashMap is included as an unordered $O(1)$ reference baseline and does not support range queries, sorted scans, or concurrent multi-writer scaling.

Multi-Threaded Concurrent Performance

When running multi-threaded workloads with concurrent writers, non-concurrent data structures (BTreeMap, HashMap, imbl::OrdMap) require synchronization via parking_lot::RwLock. Under write contention, exclusive lock acquisition serializes all threads, causing severe lock convoying and throughput collapse.

Benchmarked on bare metal (AMD Ryzen Threadripper 9970X 32-Core / 64-Thread Processor @ 5.48 GHz, 128 GB DDR5 RAM, Linux 6.8):

Data Structure Concurrent Writes(8 Threads) Mixed Workload(4 Readers + 4 Writers) Concurrency Model
artmap::ArtMap  548 µs(14.6M/s)  857 µs(18.7M/s) Non-Blocking Reads + OLC Writes
crossbeam_skiplist::SkipMap 885 µs(9.04M/s) 1.52 ms(10.5M/s) Lock-Free Atomic CAS
parking_lot::RwLock<BTreeMap> 5.77 ms(1.39M/s) 5.53 ms(2.89M/s) Coarse Exclusive Lock
parking_lot::RwLock<HashMap>* 7.78 ms(1.03M/s) 7.45 ms(2.15M/s) Coarse Exclusive Lock
parking_lot::RwLock<imbl::OrdMap> 7.05 ms(1.13M/s) 8.33 ms(1.92M/s) Coarse Exclusive Lock
  • Outperforming SkipMap on Writes & Mixed Loads: artmap is 1.62× faster on concurrent writes (548 µs vs. 885 µs) and 1.77× faster on mixed read/write workloads (857 µs vs. 1.52 ms) by eliminating parent-node contention and leveraging lock-free atomic CAS for wide nodes.
  • 9.7× Faster Point Reads: artmap resolves random point lookups in 15.0 ns (66.8M ops/sec), compared to 145.2 ns for crossbeam-skiplist::SkipMap and 58.6 ns for standard BTreeMap.
  • 1.45× Faster Range Scans: artmap traverses 100 contiguous items in 1.51 µs (66.1M items/sec) with zero heap allocations during iteration, outperforming crossbeam-skiplist::SkipMap (2.20 µs).
  • Coarse Lock Bottleneck: Non-concurrent collections (RwLock<BTreeMap>, RwLock<HashMap>, RwLock<imbl::OrdMap>) run 6.5× to 9.7× slower on mixed workloads and up to 14× slower on concurrent writes because exclusive write acquisitions serialize all threads.
  • True Multi-Writer Scaling: Writers in artmap acquire fine-grained node locks only at the specific leaf or inner node being modified, allowing concurrent updates across disjoint prefixes to proceed in parallel.
  • Epoch-Based Memory Safety: Replaced or unlinked nodes are retired safely via crossbeam-epoch without reference-counting overhead on read traversal.

Features

  • Adaptive Radix Tree Architecture: Dynamically resizes inner nodes across 4 compact layouts (Node4 $\leftrightarrow$ Node16 $\leftrightarrow$ Node48 $\leftrightarrow$ Node256) to maximize CPU L1/L2 cache locality.
  • SIMD-Accelerated Lookups: Vectorized child key comparisons on Node16 using SSE2 on x86_64 and NEON on ARM64.
  • Prefix Compression: Collapses single-child paths into shared byte prefixes, dramatically reducing memory usage for structured database keys.
  • Optimistic Lock Coupling (OLC / ROWEX): Readers validate version counters optimistically, operating with zero locks and zero atomic writes.
  • Zero-Allocation Slice Queries: Query entries directly with raw byte slices (&[u8]) or string slices (&str) without allocating wrapper objects.
  • Bidirectional Range Iterators: Full DoubleEndedIterator support for ordered forward and reverse scans (map.range(A..B) and map.range(A..B).rev()).
  • Thread Safety Guaranteed: Compile-time static assertions ensure ArtMap<K, V> implements Send + Sync when K: Send + Sync and V: Send + Sync.
  • Deterministic Simulation Tested (DST): Validated continuously by a seeded PRNG fuzzer against an in-memory BTreeMap reference oracle with comprehensive structural invariant checking.

Quick Start

Add artmap to your Cargo.toml:

[dependencies]
artmap = "0.1"
use artmap::ArtMap;
use std::sync::Arc;
use std::thread;

fn main() {
    let map = Arc::new(ArtMap::<String, i32>::new());

    // Spawn concurrent writers
    let handles: Vec<_> = (0..4).map(|t| {
        let map = Arc::clone(&map);
        thread::spawn(move || {
            for i in 0..1000 {
                map.insert(format!("users:{:04}", t * 1000 + i), i);
            }
        })
    }).collect();

    for h in handles {
        h.join().unwrap();
    }

    assert_eq!(map.len(), 4000);

    // Non-blocking point lookup
    assert_eq!(map.get(&"users:0500".to_string()), Some(500));

    // Zero-allocation lookup by raw byte slice
    assert!(map.contains_key_slice(b"users:0500"));

    // Range scanning
    let start = "users:0100".to_string();
    let end = "users:0200".to_string();
    for (key, val) in map.range(&start..&end) {
        println!("{}: {}", key, val);
    }
}

Core Operations

Zero-Allocation Slice Lookups

Query the map using raw byte slices without allocating key objects:

use artmap::ArtMap;

let map = ArtMap::<String, i32>::new();
map.insert("tenant:100:profile".to_string(), 42);

// Check existence and retrieve without creating a String
if map.contains_key_slice(b"tenant:100:profile") {
    let value = map.get_by_slice(b"tenant:100:profile");
    assert_eq!(value, Some(42));
}

Concurrent Write & Read Access

Readers and writers execute concurrently without blocking one another:

use artmap::ArtMap;
use std::sync::Arc;

let map = Arc::new(ArtMap::<String, i32>::new());
map.insert("key:1".into(), 100);

let reader_map = Arc::clone(&map);
let writer_map = Arc::clone(&map);

// Readers proceed optimistically without locks
let reader = std::thread::spawn(move || {
    reader_map.get(&"key:1".to_string())
});

// Writers lock only the affected node
let writer = std::thread::spawn(move || {
    writer_map.insert("key:2".into(), 200);
});

assert_eq!(reader.join().unwrap(), Some(100));
writer.join().unwrap();

Bidirectional Range Scanning

Iterators traverse keys in sorted lexicographical order:

let start = "prefix:001".to_string();
let end = "prefix:100".to_string();

// Forward iteration
for (k, v) in map.range(&start..&end) {
    // ...
}

// Reverse iteration
for (k, v) in map.range(&start..&end).rev() {
    // ...
}

Deterministic Simulation Testing (DST)

artmap includes a deterministic simulation testing harness inspired by FoundationDB, TigerBeetle, and vart:

  • Seeded PRNG: Every simulation run is parameterized by a 64-bit seed (ARTMAP_SIM_SEED=<seed>) to reproduce any failure down to the byte.
  • Reference Oracle: Runs state transitions in lockstep against a canonical BTreeMap reference oracle.
  • Continuous Invariant Checking: Validates prefix compression, node capacity boundaries, child bitmaps, and latch states after every simulated step via map.validate_invariants().

To run the simulation suite:

# Run with a random seed
cargo test --test sim -- --nocapture

# Run with an exact reproducible seed
ARTMAP_SIM_SEED=20202 cargo test --test sim -- --nocapture

Benchmarks

Benchmarks compare artmap against crossbeam-skiplist::SkipMap, std::collections::BTreeMap, imbl::OrdMap, and std::collections::HashMap:

# Run comparison benchmarks locally
cargo bench --bench comparison_bench

# Run allocation and memory benchmarks locally
cargo bench --bench alloc_comparison

# Run on remote dedicated hardware (AMD Threadripper)
./scripts/bench-remote.sh --all

License

This project is licensed under the Apache License, Version 2.0.