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 ~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 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 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.

Example:

```rust use congee::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).unwrap(); // read the value assert_eq!(val, 42);

let mut scanbuffer = vec![(0, 0); 8]; let scanresult = art.range(&0, &10, &mut artscanbuffer); // scan values asserteq!(scanresult, 1); asserteq!(scanbuffer[0], (0, 42)); ```

History

Congee was originally developed in the Alchemy project to fullfil its need for a concurrent, scalable, and low memory footprint range index.