A Rust implementation of ART-OLC concurrent adaptive radix tree. It implements the optimistic lock coupling with proper SIMD support.
It only supports (and is optimized for) fixed sized 8 byte key; due to this specialization, congee has great performance -- basic operations are faster than most hash tables, range scan is an order of magnitude faster.
The codebase is extensively tested with {address|leak} sanitizer as well as libfuzzer. Congee's performance is continuously tracked here.
- Fast performance, faster than most hash tables.
- Concurrent, super scalable, it reaches 150Mop/s on 32 cores.
- Super low memory consumption. Hash tables often have exponential bucket size growth, which often lead to low load factors. ART is more space efficient.
- Not for arbitrary key size. This library only supports 8 byte key.
Congee aims to be a simple and reliable primitive for building database systems.
use congee::Congee;
let art = Congee::default();
let guard = art.pin(); // enter an epoch
art.insert(0, 42, &guard); // insert a value
let val = art.get(&0, &guard).unwrap(); // read the value
assert_eq!(val, 42);
let mut scan_buffer = vec![(0, 0); 8];
let scan_result = art.range(&0, &10, &mut scan_buffer, &guard); // scan values
assert_eq!(scan_result, 1);
assert_eq!(scan_buffer[0], (0, 42));Benchmarked with the conc-map-bench
