Congee
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) 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 code is extensively tested with {address|leak} sanitizer as well as libfuzzer.
Why Congee?
- 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.
Why not Congee?
- Not for arbitrary key size. This library only supports 8 byte key.
Design principles
Congee aims to be a simple and reliable primitive for building database systems.
Example:
use Art;
let art = default;
let guard = art.pin; // enter an epoch
art.insert; // insert a value
let val = art.get.unwrap; // read the value
assert_eq!;
let mut scan_buffer = vec!;
let scan_result = art.range; // scan values
assert_eq!;
assert_eq!;