Sarlacc

Some say that it takes 1000 years for your data to be freed...

Sarlacc is a crate for easy interning of data in Rust. Interning is the process of deduplicating equal values in memory, allowing them to be hashed and checked for equality through quick and efficient pointer comparison.

This crate aims to have feature parity with the popular internment crate, however interning is implemented using a Ctrie, which is a lock-free hash set that synchronizes using atomics. The internment crate simply hides everything behind a global mutex.

Now you may be wondering... Why would you want to leak your entire memory stick BLAZINGLY FAST 🚀🚀🚀???

• This crate supports interning inside of arenas, which can be dropped when no longer needed
• Interning values that you expect to already be interned or checking whether a value is already interned does not involve a global lock and the operation does not leak memory
• Locks always have the issue that a thread could be pre-empted while holding the lock, leading to all other threads stalling
• Locks often involve OS syscalls

Todos:

• Better optimize the Ctrie implementation for memory efficiency and fewer pointer indirections
• Handle hash collisions with separate chaining instead of panicking (Note that the entire 64 bit hash has to collide for there to be an issue)
• Implement deletion from the Ctrie and ArcIntern functionality

Example

let a = Intern::from_ref("Hello");
let b = Intern::from_ref("world");
assert_ne!(a, b);
println!("{a}, {b}");

let also_a = Intern::from_ref("Hello");
assert_eq!(a, also_a);
assert!(ptr::eq(&*a, &*also_a));