artmap 0.6.0

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

artmap is a concurrent, ordered, in-memory map backed by an Adaptive Radix Tree (ART). It uses optimistic lock coupling (OLC): readers never block and never write to shared memory, and writers latch only the nodes they change. Memory is reclaimed with epoch-based reclamation (EBR), or, for the arena variants, all at once when the map is dropped.

There are four map types:

  • artmap::ArtMap: a key-value map. Removed and replaced entries are reclaimed through crossbeam-epoch.
  • artmap::VersionedArtMap: a map with a chain of 64-bit MVCC versions per key, snapshot reads (get_version_le, get_latest), tombstones (delete) and pruning (prune_key, prune_all).
  • artmap::ArenaArtMap: a key-value map allocated from a fixed-size bump arena with 32-bit offsets. Inserts make no heap allocations, and nothing is freed until the map is dropped.
  • artmap::ArenaVersionedArtMap: the versioned map on an arena, designed for LSM memtables.

Variant Selection Matrix

Memory Model Unversioned (General Purpose) Versioned / MVCC (Storage Engines)
EBR / Dynamic Heap(reclaimed via crossbeam-epoch) artmap::ArtMap<K, V>• Optimistic lock coupling (OLC)• Out-of-place replacement: handles stay valid• Dynamic heap growth and node resizing artmap::VersionedArtMap<K, V>• Snapshot reads (get_version_le)• Per-key chain latch for version writes• Tombstones and pruning
Arena / 32-Bit Offsets(fixed-size arena) artmap::ArenaArtMap<K, V>• Compact nodes with 32-bit child offsets• 0 heap allocations per insert• try_insert and max_insert_bytes for capacity planning artmap::ArenaVersionedArtMap<K, V>• 32-bit offset version chains• Sequential inserter cache (map.inserter())• Memtable-oriented: no pruning, freed on drop

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 Read(with standard key) Read(with slice key) Insert(sequential entries) Insert(random entries) Range scans(100 items)
artmap::ArtMap 24.8 ns(40.4M/s) 25.1 ns(39.9M/s) 32.5 ns(30.7M/s)  38.7 ns(25.9M/s) 718 ns(139M/s)
artmap::VersionedArtMap 21.9 ns(45.7M/s) 21.6 ns(46.2M/s) 48.2 ns(20.7M/s) 69.4 ns(14.4M/s) 807 ns(124M/s)
artmap::ArenaArtMap  13.4 ns(74.5M/s)  13.4 ns(74.8M/s)  27.1 ns(36.9M/s) 39.8 ns(25.1M/s) 574 ns(174M/s)
artmap::ArenaVersionedArtMap 14.7 ns(68.2M/s) 15.7 ns(63.6M/s) 41.3 ns(24.2M/s) 51.6 ns(19.4M/s) 616 ns(162M/s)
arenaskiplist::SkipList 181 ns(5.5M/s) 181 ns(5.5M/s) 39.5 ns(25.3M/s) 151 ns(6.6M/s) 809 ns(124M/s)
concread::bptree::BPTree 64.2 ns(15.6M/s) — 44.9 ns(22.3M/s) 128 ns(7.8M/s) 434 ns(231M/s)
crossbeam_skiplist::SkipMap 160 ns(6.2M/s) — 77.8 ns(12.9M/s) 174 ns(5.8M/s) 2.39 µs(41.9M/s)
imbl::OrdMap 41.8 ns(23.9M/s) — 52.6 ns(19.0M/s) 74.6 ns(13.4M/s) 343 ns(291M/s)
std::collections::BTreeMap 62.4 ns(16.0M/s) — 31.1 ns(32.1M/s) 65.7 ns(15.2M/s)  235 ns(426M/s)
vart::Tree 22.0 ns(45.5M/s) 20.6 ns(48.6M/s) 67.7 ns(14.8M/s) 69.6 ns(14.4M/s) 2.68 µs(37.3M/s)
dashmap::DashMap* 17.3 ns(58.0M/s) — 23.6 ns(42.4M/s) 29.1 ns(34.4M/s) N/A
papaya::HashMap* 21.7 ns(46.1M/s) — 52.2 ns(19.1M/s) 56.9 ns(17.6M/s) N/A
scc::HashIndex* 17.0 ns(58.7M/s) — 27.9 ns(35.9M/s) 31.1 ns(32.1M/s) N/A
std::collections::HashMap* 13.3 ns(74.9M/s) — 18.8 ns(53.3M/s) 21.1 ns(47.3M/s) N/A

* dashmap::DashMap, papaya::HashMap, scc::HashIndex, and std::collections::HashMap are marked with * as unordered $O(1)$ reference baselines and do not support range queries, sorted scans, or ordered traversals. The rocket icon marks the fastest ordered (range-scannable) map in each column. The sequential insert time for arenaskiplist::SkipList uses its sequential inserter cache (Inserter).

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, 100k Ops) Mixed Workload(4R + 4W, 100k Ops) Concurrency Model
artmap::ArtMap 2.00 ms(50.1M/s) 2.07 ms(48.2M/s) Non-Blocking Reads + OLC Node Latching
artmap::VersionedArtMap 2.34 ms(42.8M/s) 2.32 ms(43.1M/s) Non-Blocking Reads + OLC + Per-Key Chain Latch
artmap::ArenaArtMap  1.76 ms(56.8M/s)  2.02 ms(49.6M/s) OLC Node Latching + 32-Bit Offsets + Atomic Bump Allocation
artmap::ArenaVersionedArtMap 2.23 ms(44.9M/s) 2.23 ms(44.9M/s) OLC Node Latching + 32-Bit Offsets + Per-Key Chain Latch
arenaskiplist::SkipList 40.80 ms(2.5M/s) 28.81 ms(3.5M/s) Lock-Free Atomic CAS (Contiguous Arena)
concread::bptree::BPTree 8.86 ms(11.3M/s) 4.59 ms(21.8M/s) Lock-Free Reads + Single-Writer CoW (MVCC)
crossbeam_skiplist::SkipMap 10.10 ms(9.9M/s) 9.49 ms(10.5M/s) Lock-Free Atomic CAS
parking_lot::RwLock<BTreeMap> 66.53 ms(1.5M/s) 39.01 ms(2.6M/s) Coarse Exclusive Lock
parking_lot::RwLock<imbl::OrdMap> 78.35 ms(1.3M/s) 57.88 ms(1.7M/s) Coarse Exclusive Lock
parking_lot::RwLock<vart::Tree> 77.81 ms(1.3M/s) 51.67 ms(1.9M/s) Coarse Exclusive Lock (Persistent CoW)
dashmap::DashMap* 3.37 ms(29.6M/s) 3.60 ms(27.7M/s) Fine-Grained Sharded RwLock
papaya::HashMap* 7.69 ms(13.0M/s) 8.12 ms(12.3M/s) Lock-Free Reads + Fine-Grained Latching (EBR)
parking_lot::RwLock<HashMap>* 76.98 ms(1.3M/s) 44.66 ms(2.2M/s) Coarse Exclusive Lock
scc::HashIndex* 3.00 ms(33.3M/s) 3.14 ms(31.8M/s) Lock-Free Reads + Bucket Latching

Memory Footprint & Allocation Overhead

Benchmarked with 100,000 keys (64-bit integer keys and 64-bit values), measuring idle data structure size in memory when full, peak heap memory during continuous insertion, allocation frequency, and whole-structure teardown cost:

Data Structure Idle Memory(100k items) Peak Memory(during ingest) Allocations(per insert) Teardown / Reset(deallocation cost)
artmap::ArtMap 5.46 MB(54.6 B/item) 5.47 MB 1.32 $O(N)$ epoch-deferred reclamation
artmap::VersionedArtMap 10.25 MB(102.5 B/item) 10.25 MB 1.32 $O(N)$ epoch-deferred reclamation
artmap::ArenaArtMap 4.92 MB(49.2 B/item) 4.92 MB 0 $O(1)$ when K and V need no Drop
artmap::ArenaVersionedArtMap 6.52 MB(65.2 B/item) 6.52 MB 0 $O(1)$ when K and V need no Drop
arenaskiplist::SkipList 5.77 MB(57.7 B/item) 5.77 MB 0 $O(1)$ zero-cost reset
concread::bptree::BPTree 6.69 MB(66.9 B/item) 7.22 MB 0.52 $O(N)$ CoW heap drop
crossbeam_skiplist::SkipMap 4.00 MB(40.0 B/item) 4.00 MB 1.00 $O(N)$ epoch-deferred reclamation
imbl::OrdMap 2.81 MB(28.1 B/item) 2.81 MB 0.10 $O(N)$ recursive heap drop
std::collections::BTreeMap 2.71 MB(27.1 B/item) 2.71 MB 0.13 $O(N)$ recursive heap drop
vart::Tree 27.55 MB(275.5 B/item) 27.55 MB 1.31 $O(N)$ recursive Arc drop
dashmap::DashMap* 2.23 MB(22.3 B/item) 2.24 MB 0.02 $O(N)$ heap drop
papaya::HashMap* 3.96 MB(39.6 B/item) 3.96 MB 1.00 $O(N)$ epoch-deferred reclamation
scc::HashIndex* 2.40 MB(24.0 B/item) 3.59 MB 0.01 $O(N)$ epoch-deferred reclamation
std::collections::HashMap* 2.23 MB(22.3 B/item) 3.34 MB 0 $O(N)$ heap drop

* For sequential keys (e.g. monotonically increasing timestamps or auto-incrementing IDs), radix prefix compression reduces ArenaArtMap's net size to 3.11 MB (31.1 B/item) and ArenaVersionedArtMap to 4.71 MB (47.1 B/item).

  • Point reads: radix path resolution in ArenaArtMap completes random point lookups in 13.4 ns, against 181 ns for arenaskiplist and 160 ns for crossbeam-skiplist::SkipMap.
  • Concurrent writes: 8 threads insert 100,000 keys into ArenaArtMap in 1.76 ms (56.8M ops/s), against 3.00 ms for scc::HashIndex, 3.37 ms for dashmap and 10.1 ms for crossbeam-skiplist::SkipMap.
  • Range scans: bitmapped child navigation on Node48 and Node256 scans 100 contiguous items in 574 ns in ArenaArtMap, against 809 ns for arenaskiplist and 2.39 µs for crossbeam-skiplist::SkipMap. scan(range, callback) skips the per-entry handle.
  • No per-insert heap allocations in the arena maps, and an $O(1)$ drop when K and V need no Drop.

Features

  • Adaptive Radix Tree: inner nodes resize between four layouts (Node4, Node16, Node48 and Node256) for cache locality. Prefix compression collapses single-child paths.
  • Optimistic lock coupling: readers validate per-node version counters and retry on conflict. They never block and never write to shared memory.
  • MVCC: per-key chains of 64-bit versions with snapshot reads, tombstones and pruning.
  • SIMD Node16 search: SSE2 on x86_64 and NEON on aarch64.
  • Slice lookups: query with &[u8] or &str without building a key (get_by_slice, contains_key_slice).
  • Double-ended iterators: forward and reverse scans over any range (map.range(a..b).rev()).
  • Thread safety: every map is Send + Sync when K and V are Send + Sync. Compile-time assertions check this, and compile-fail tests check that handles and iterators are !Send.

Quick Start

Add artmap to your Cargo.toml:

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

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

// 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);

// A point lookup returns a handle that dereferences to the value.
assert_eq!(map.get("users:0500").as_deref(), Some(&500));

// Or copy the value out.
assert_eq!(map.get_value("users:0500"), Some(500));

// Lookup by raw bytes, without building a `String`.
assert!(map.contains_key_slice(b"users:0500"));

// Range scans, in key order.
let mut n = 0;
for entry in map.range("users:0100".."users:0200") {
    assert!(entry.key().as_str() >= "users:0100");
    n += 1;
}
assert_eq!(n, 100);

Core Operations

Handles and guards

get, insert, remove and the iterators return handles (EntryRef) that borrow the map and keep an epoch guard alive, so the entry stays valid even if another thread removes or replaces it:

use artmap::ArtMap;

let map = ArtMap::<String, String>::new();
map.insert("k".to_string(), "v1".to_string());

let old = map.get("k").unwrap();
// `insert` returns the displaced entry, if there was one.
let displaced = map.insert("k".to_string(), "v2".to_string()).unwrap();
assert_eq!(displaced.value(), "v1");

// The old handle still reads its own snapshot, and knows it was replaced.
assert_eq!(old.value(), "v1");
assert!(old.is_removed());
assert_eq!(map.get("k").unwrap().value(), "v2");

To amortise pinning over many operations, pin once and use the *_with_guard methods:

use artmap::ArtMap;

// Big-endian bytes keep integer keys in numeric order.
let map = ArtMap::<[u8; 8], u64>::new();
for i in 0..100u64 {
    map.insert(i.to_be_bytes(), i * 2);
}

let guard = map.pin();
let mut sum = 0;
for i in 0..100u64 {
    if let Some(v) = map.get_with_guard(&i.to_be_bytes(), &guard) {
        sum += *v;
    }
}
assert_eq!(sum, 9900);

Holding a handle, iterator or guard stalls memory reclamation process-wide, for every user of the default crossbeam-epoch collector, so do not hold one across I/O. Handles are !Send. Across an .await, use get_value, with_value, EntryRef::to_owned or EntryRef::value_cloned.

Concurrent reads and writes

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

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

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

// Readers never block.
let reader = std::thread::spawn(move || reader_map.get_value("key:1"));
// Writers latch only the nodes they change.
let writer = std::thread::spawn(move || {
    writer_map.insert("key:2".to_string(), 200);
});

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

Bidirectional range scans

use artmap::ArtMap;

let map = ArtMap::<String, u32>::new();
for i in 0..200u32 {
    map.insert(format!("prefix:{i:03}"), i);
}

let forward: Vec<u32> = map.range("prefix:001".."prefix:100").map(|e| *e).collect();
assert_eq!(forward.len(), 99);
assert_eq!(forward.first(), Some(&1));

let reverse: Vec<u32> = map.range("prefix:001".."prefix:100").rev().map(|e| *e).collect();
assert_eq!(reverse.first(), Some(&99));

Iterators guarantee that every key present for the whole scan is yielded exactly once, in order. Keys inserted or removed during the scan may or may not appear.

Versioned maps

use artmap::VersionedArtMap;

let map = VersionedArtMap::<String, u64>::new();
map.insert("account:1001".to_string(), 1, 500);
map.insert("account:1001".to_string(), 2, 750);

// Snapshot reads.
assert_eq!(map.get_version_le("account:1001", 1), Some((1, 500)));
assert_eq!(map.get_version_le("account:1001", 2), Some((2, 750)));

// A tombstone at version 3 hides the key from newer snapshots only.
map.delete("account:1001".to_string(), 3);
assert_eq!(map.get("account:1001"), None);
assert_eq!(map.get_version_le("account:1001", 2), Some((2, 750)));

// Drop versions that no snapshot at or above 3 can see.
map.prune_key("account:1001", 3, |_| false);
assert_eq!(map.version_count("account:1001"), 1);

Arena maps

The arena maps allocate every node, leaf and version from one fixed-size arena:

use artmap::{ArenaArtMap, ArenaVersionedArtMap};

let map = ArenaArtMap::<String, i32>::with_capacity(16 * 1024 * 1024);
map.insert("account:1001".to_string(), 500);
assert_eq!(map.get("account:1001"), Some(500));

// `try_insert` returns the key and value instead of panicking when full.
let tiny = ArenaArtMap::<String, i32>::with_capacity(64);
let full = tiny.try_insert("k".to_string(), 1).unwrap_err();
assert_eq!((full.key.as_str(), full.value), ("k", 1));

// The worst-case arena bytes one insert can consume, for capacity planning.
assert!(ArenaArtMap::<String, i32>::max_insert_bytes(16) > 0);

let vmap = ArenaVersionedArtMap::<String, i32>::with_capacity(16 * 1024 * 1024);
vmap.insert("account:1001".to_string(), 1, 500);
vmap.insert("account:1001".to_string(), 2, 750);
assert_eq!(vmap.get_version_le("account:1001", 1), Some((1, 500)));

for entry in vmap.range("account:1000".."account:2000") {
    assert_eq!((entry.version(), *entry.value()), (2, 750));
    // Every version of the key, newest first.
    let all: Vec<_> = entry.versions().map(|v| (v.version, v.value.copied())).collect();
    assert_eq!(all, vec![(2, Some(750)), (1, Some(500))]);
}

// Ordered bulk loads go faster through an inserter.
let mut ins = map.inserter();
for i in 0..1000 {
    ins.insert(format!("seq:{i:05}"), i);
}
assert_eq!(map.len(), 1001);

The arena's capacity is fixed. Updates and removes do not free arena memory: replaced leaves and versions stay in the arena until the map is dropped. When K and V need Drop, dropping the map runs their destructors; otherwise it is $O(1)$. Arena::reset needs exclusive access, so it can only run once no map is using the arena.

Memory retention

Removed and replaced entries are reclaimed: once no guard can still see them in the EBR maps, or when the map is dropped in the arena maps. Inner nodes are not yet reclaimed on delete. A node emptied by removes stays in the tree until clear() or drop, so a workload that keeps deleting and inserting keys under ever-new prefixes grows. Delete-side compaction is planned for a release after 0.6.

Verification

  • Miri, under Tree Borrows: the EBR suites, and the arena suites leak-checked with strict provenance and symbolic alignment checks, on x86_64 and aarch64.
  • loom models of the real latch and node protocol, with mutants that must fail: a missing writer fence, a missing validation fence, and missing lock coupling.
  • ThreadSanitizer and AddressSanitizer over the race and stress tests.
  • Model tests of every map and iterator against BTreeMap. Property tests over arbitrary byte keys, and a linearizability checker for point operations and clear.
  • Fault injection: panicking AsBytes, Clone and closures, and re-entrant user code, at every call site.
  • Compile-fail tests for handle lifetimes, variance, auto traits and the sealed internals.
  • Seeded sequential oracle fuzzing (tests/sim.rs and tests/versioned_simulation_tests.rs). Each run is reproducible with ARTMAP_SIM_SEED. This is not deterministic simulation of concurrent schedules: concurrency is covered by loom, the sanitizers and the stress tests.
ARTMAP_SIM_SEED=20202 cargo test --test sim -- --nocapture

Benchmarks

# Comparison against other ordered and unordered maps
cargo bench --bench comparison_bench

# Allocation and memory footprint
cargo bench --bench alloc_comparison

# Safety-plan benchmarks: guards, overwrites, churn, scans, versioned updates
cargo bench --bench safety_bench
cargo bench --bench memory_bench

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

License

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