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.5M/s) | 30.2 ns(33.1M/s) | 578 ns(172.8M/s) | 1.0 allocs |
crossbeam_skiplist::SkipMap |
143.8 ns(7.0M/s) | 98.0 ns(10.2M/s) | 2.24 µs(44.6M/s) | ~1.0 allocs |
imbl::OrdMap |
40.4 ns(24.8M/s) | 71.9 ns(13.9M/s) | 332 ns(301M/s) | ~0.14 allocs |
std::collections::BTreeMap |
58.6 ns(17.1M/s) | 37.1 ns(27.0M/s) | 188 ns(530M/s) | ~0.16 allocs |
std::collections::HashMap* |
13.1 ns(76.1M/s) | 29.0 ns(34.5M/s) | N/A | ~0 allocs |
* 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. The rocket icon denotes the fastest implementation among ordered, concurrent range-scannable maps.
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 |
5.73 ms(17.4M/s) | 5.25 ms(19.1M/s) | Non-Blocking Reads + OLC Writes |
crossbeam_skiplist::SkipMap |
10.12 ms(9.88M/s) | 9.65 ms(10.4M/s) | Lock-Free Atomic CAS |
parking_lot::RwLock<BTreeMap> |
71.0 ms(1.41M/s) | 38.0 ms(2.63M/s) | Coarse Exclusive Lock |
parking_lot::RwLock<HashMap>* |
90.2 ms(1.11M/s) | 45.6 ms(2.19M/s) | Coarse Exclusive Lock |
parking_lot::RwLock<imbl::OrdMap> |
81.0 ms(1.24M/s) | 57.1 ms(1.75M/s) | Coarse Exclusive Lock |
- Outperforming SkipMap on Writes & Mixed Loads:
artmapis 1.77× faster on concurrent writes (5.73 ms vs. 10.12 ms) and 1.84× faster on mixed read/write workloads (5.25 ms vs. 9.65 ms) by eliminating parent-node contention and leveraging lock-free atomic CAS for wide nodes. - 9.6× Faster Point Reads:
artmapresolves random point lookups in 15.0 ns (66.5M ops/sec), compared to 143.8 ns forcrossbeam-skiplist::SkipMapand 58.6 ns for standardBTreeMap. - 3.87× Faster Range Scans:
artmaptraverses 100 contiguous items in 578 ns (172.8M items/sec) with zero heap allocations during iteration via cached cursor-stack descent, outperformingcrossbeam-skiplist::SkipMap(2.24 µs). - Coarse Lock Bottleneck: Non-concurrent collections (
RwLock<BTreeMap>,RwLock<HashMap>,RwLock<imbl::OrdMap>) run 7.2× to 10.9× slower on mixed workloads and up to 15.7× 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.4"
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.