artmap provides a concurrent, ordered, in-memory map and set 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 and a set type:
artmap::ArtMap: a key-value map. Removed and replaced entries are reclaimed throughcrossbeam-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.artmap::ArtSet: an ordered set of keys, a thin wrapper overArtMap<K, ()>.insertonly adds a key that is absent, andinsert,removeandcontainsreturn abool. It costs no more memory than the keys.
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
ArenaArtMapcompletes random point lookups in 13.4 ns, against 181 ns forarenaskiplistand 160 ns forcrossbeam-skiplist::SkipMap. - Concurrent writes: 8 threads insert 100,000 keys into
ArenaArtMapin 1.76 ms (56.8M ops/s), against 3.00 ms forscc::HashIndex, 3.37 ms fordashmapand 10.1 ms forcrossbeam-skiplist::SkipMap. - Range scans: bitmapped child navigation on
Node48andNode256scans 100 contiguous items in 574 ns inArenaArtMap, against 809 ns forarenaskiplistand 2.39 µs forcrossbeam-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
KandVneed noDrop.
Features
- Adaptive Radix Tree: inner nodes resize between four layouts (
Node4,Node16,Node48andNode256) 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
Node16search: SSE2 on x86_64 and NEON on aarch64. - Slice lookups: query with
&[u8]or&strwithout 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 and
ArtSetisSend + Syncwhen its key and value types are. Compile-time assertions check this, and compile-fail tests check that handles and iterators are!Send.
Quick Start
Add artmap to your Cargo.toml:
[]
= "0.7"
use ArtMap;
use Arc;
use thread;
let map = new;
// Concurrent writers.
let handles: =
.map
.collect;
for h in handles
assert_eq!;
// A point lookup returns a handle that dereferences to the value.
assert_eq!;
// Or copy the value out.
assert_eq!;
// Lookup by raw bytes, without building a `String`.
assert!;
// Range scans, in key order.
let mut n = 0;
for entry in map.range
assert_eq!;
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;
let map = new;
map.insert;
let old = map.get.unwrap;
// `insert` returns the displaced entry, if there was one.
let displaced = map.insert.unwrap;
assert_eq!;
// The old handle still reads its own snapshot, and knows it was replaced.
assert_eq!;
assert!;
assert_eq!;
To amortise pinning over many operations, pin once and use the *_with_guard methods:
use ArtMap;
// Big-endian bytes keep integer keys in numeric order.
let map = new;
for i in 0..100u64
let guard = map.pin;
let mut sum = 0;
for i in 0..100u64
assert_eq!;
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;
use Arc;
let map = new;
map.insert;
let reader_map = clone;
let writer_map = clone;
// Readers never block.
let reader = spawn;
// Writers latch only the nodes they change.
let writer = spawn;
assert_eq!;
writer.join.unwrap;
assert_eq!;
Bidirectional range scans
use ArtMap;
let map = new;
for i in 0..200u32
let forward: = map.range.map.collect;
assert_eq!;
assert_eq!;
let reverse: = map.range.rev.map.collect;
assert_eq!;
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.
Sets
ArtSet<K> is an ordered set. insert adds a key only if it is absent, and insert, remove and contains return a bool:
use ArtSet;
let set = new;
assert!;
assert!;
// A key that is already present is left alone.
assert!;
assert!;
assert!;
assert!;
// Keys come back in order, and ranges work as they do for the maps.
set.insert;
let keys: = set.range.map.collect;
assert_eq!;
Versioned maps
use VersionedArtMap;
let map = new;
map.insert;
map.insert;
// Snapshot reads.
assert_eq!;
assert_eq!;
// A tombstone at version 3 hides the key from newer snapshots only.
map.delete;
assert_eq!;
assert_eq!;
// Drop versions that no snapshot at or above 3 can see.
map.prune_key;
assert_eq!;
Arena maps
The arena maps allocate every node, leaf and version from one fixed-size arena:
use ;
let map = with_capacity;
map.insert;
assert_eq!;
// `try_insert` returns the key and value instead of panicking when full.
let tiny = with_capacity;
let full = tiny.try_insert.unwrap_err;
assert_eq!;
// The worst-case arena bytes one insert can consume, for capacity planning.
assert!;
let vmap = with_capacity;
vmap.insert;
vmap.insert;
assert_eq!;
for entry in vmap.range
// Ordered bulk loads go faster through an inserter.
let mut ins = map.inserter;
for i in 0..1000
assert_eq!;
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.7.
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 andclear. - Fault injection: panicking
AsBytes,Cloneand 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.rsandtests/versioned_simulation_tests.rs). Each run is reproducible withARTMAP_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
Benchmarks
# Comparison against other ordered and unordered maps
# Allocation and memory footprint
# Safety-plan benchmarks: guards, overwrites, churn, scans, versioned updates
# Run on remote dedicated hardware (AMD Threadripper)
License
This project is licensed under the Apache License, Version 2.0.