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:
artmapis 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:
artmapresolves random point lookups in 15.0 ns (66.8M ops/sec), compared to 145.2 ns forcrossbeam-skiplist::SkipMapand 58.6 ns for standardBTreeMap. - 1.45× Faster Range Scans:
artmaptraverses 100 contiguous items in 1.51 µs (66.1M items/sec) with zero heap allocations during iteration, outperformingcrossbeam-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
artmapacquire 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-epochwithout 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
Node16using 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
DoubleEndedIteratorsupport for ordered forward and reverse scans (map.range(A..B)andmap.range(A..B).rev()). - Thread Safety Guaranteed: Compile-time static assertions ensure
ArtMap<K, V>implementsSend + SyncwhenK: Send + SyncandV: Send + Sync. - Deterministic Simulation Tested (DST): Validated continuously by a seeded PRNG fuzzer against an in-memory
BTreeMapreference oracle with comprehensive structural invariant checking.
Quick Start
Add artmap to your Cargo.toml:
[]
= "0.1"
use ArtMap;
use Arc;
use thread;
Core Operations
Zero-Allocation Slice Lookups
Query the map using raw byte slices without allocating key objects:
use ArtMap;
let map = new;
map.insert;
// Check existence and retrieve without creating a String
if map.contains_key_slice
Concurrent Write & Read Access
Readers and writers execute concurrently without blocking one another:
use ArtMap;
use Arc;
let map = new;
map.insert;
let reader_map = clone;
let writer_map = clone;
// Readers proceed optimistically without locks
let reader = spawn;
// Writers lock only the affected node
let writer = spawn;
assert_eq!;
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 in map.range
// Reverse iteration
for in map.range.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
BTreeMapreference 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
# Run with an exact reproducible seed
ARTMAP_SIM_SEED=20202
Benchmarks
Benchmarks compare artmap against crossbeam-skiplist::SkipMap, std::collections::BTreeMap, imbl::OrdMap, and std::collections::HashMap:
# Run comparison benchmarks locally
# Run allocation and memory benchmarks locally
# Run on remote dedicated hardware (AMD Threadripper)
License
This project is licensed under the Apache License, Version 2.0.