Crate con_art_rust
source · [−]Expand description
A Rust implementation of ART-OLC concurrent adaptive radix tree. It implements the optimistic lock coupling with proper SIMD support.
The code is based on its C++ implementation, with many bug fixes.
It only supports (and is optimized for) 8 byte key; due to this specialization, this ART has great performance – basic operations are ~40% faster than flurry hash table, range scan is an order of magnitude faster.
The code is extensively tested with {address|leak} sanitizer as well as libfuzzer.
Why this library?
- Fast performance, faster than most hash tables.
- Concurrent, super scalable, it support 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 this library?
- Not for arbitrary key size. This library only supports 8 byte key.
- The value must be a valid, user-space, 64 bit pointer, aka non-null and zeros on 48-63 bits.
- Not for sparse keys. ART is optimized for dense keys, if your keys are sparse, you should consider a hashtable.
Example:
use con_art_rust::Art;
let art = Art::new();
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; 8];
let scan_result = art.range(&0, &10, &mut scan_buffer, &guard); // scan values
assert_eq!(scan_result.unwrap(), 1);Structs
Raw interface to the ART tree.
The Art is a wrapper around the RawArt that provides a safe interface.
Unlike Art, it support arbitrary Key types, see also RawKey.
Traits
A trait for Art-specific keys, don’t use it unless you know what you are doing.