A multithreaded and single threaded string interner that allows strings to be cached with a minimal memory footprint,
associating them with a unique key that can be used to retrieve them at any time. A Rodeo allows O(1)
internment and resolution and can be turned into a RodeoReader to allow for contention-free resolutions
with both key to str and str to key operations. It can also be turned into a RodeoResolver with only
key to str operations for the lowest possible memory usage.
Which interner do I use?
For single-threaded workloads Rodeo is encouraged, while multi-threaded applications should use ThreadedRodeo.
Both of these are the only way to intern strings, but most applications will hit a stage where they are done interning
strings, and at that point is where the choice between RodeoReader and RodeoResolver. If the user needs to get
keys for strings still, then they must use the RodeoReader (although they can still transfer into a RodeoResolver)
at this point. For users who just need key to string resolution, the RodeoResolver gives contention-free access at the
minimum possible memory usage. Note that to gain access to ThreadedRodeo the multi-threaded feature is required.
Interner
Thread-safe
Intern String
str to key
key to str
Contention Free
Memory Usage
Rodeo
❌
✅
✅
✅
N/A
Medium
ThreadedRodeo
✅
✅
✅
✅
❌
Most
RodeoReader
✅
❌
✅
✅
✅
Medium
RodeoResolver
✅
❌
❌
✅
✅
Least
Cargo Features
By default lasso has one dependency, hashbrown, and only Rodeo is exposed. Hashbrown is used since the raw_entry api is currently unstable in the standard library's hashmap.
The raw hashmap API is used for custom hashing within the hashmaps, which works to dramatically reduce memory usage
To make use of ThreadedRodeo, you must enable the multi-threaded feature.
multi-threaded - Enables ThreadedRodeo, the interner for multi-threaded tasks
ahasher - Use ahash's RandomState as the default hasher
no-std - Enables no_std + alloc support for Rodeo and ThreadedRodeo
Automatically enables the following required features:
ahasher - no_std hashing function
serialize - Implements Serialize and Deserialize for all Spur types and all interners
inline-more - Annotate external apis with #[inline]
Example: Using Rodeo
use lasso::Rodeo;letmut rodeo = Rodeo::default();let key = rodeo.get_or_intern("Hello, world!");// Easily retrieve the value of a key and find the key for valuesassert_eq!("Hello, world!", rodeo.resolve(&key));assert_eq!(Some(key), rodeo.get("Hello, world!"));// Interning the same string again will yield the same keylet key2 = rodeo.get_or_intern("Hello, world!");assert_eq!(key, key2);
Example: Using ThreadedRodeo
use lasso::ThreadedRodeo;use std::{thread, sync::Arc};let rodeo = Arc::new(ThreadedRodeo::default());let key = rodeo.get_or_intern("Hello, world!");// Easily retrieve the value of a key and find the key for valuesassert_eq!("Hello, world!", rodeo.resolve(&key));assert_eq!(Some(key), rodeo.get("Hello, world!"));// Interning the same string again will yield the same keylet key2 = rodeo.get_or_intern("Hello, world!");assert_eq!(key, key2);// ThreadedRodeo can be shared across threadslet moved = Arc::clone(&rodeo);let hello = thread::spawn(move || {assert_eq!("Hello, world!", moved.resolve(&key));
moved.get_or_intern("Hello from the thread!")}).join().unwrap();assert_eq!("Hello, world!", rodeo.resolve(&key));assert_eq!("Hello from the thread!", rodeo.resolve(&hello));
Example: Creating a RodeoReader
use lasso::Rodeo;// Rodeo and ThreadedRodeo are interchangeable hereletmut rodeo = Rodeo::default();let key = rodeo.get_or_intern("Hello, world!");assert_eq!("Hello, world!", rodeo.resolve(&key));let reader = rodeo.into_reader();// Reader keeps all the strings from the parentassert_eq!("Hello, world!", reader.resolve(&key));assert_eq!(Some(key), reader.get("Hello, world!"));// The Reader can now be shared across threads, no matter what kind of Rodeo created it
Example: Creating a RodeoResolver
use lasso::Rodeo;// Rodeo and ThreadedRodeo are interchangeable hereletmut rodeo = Rodeo::default();let key = rodeo.get_or_intern("Hello, world!");assert_eq!("Hello, world!", rodeo.resolve(&key));let resolver = rodeo.into_resolver();// Resolver keeps all the strings from the parentassert_eq!("Hello, world!", resolver.resolve(&key));// The Resolver can now be shared across threads, no matter what kind of Rodeo created it
Example: Making a custom-ranged key
Sometimes you want your keys to only inhabit (or not inhabit) a certain range of values so that you can have custom niches.
This allows you to pack more data into what would otherwise be unused space, which can be critical for memory-sensitive applications.
use lasso::{Key,Rodeo};// First make our key type, this will be what we use as handles into our interner#[derive(Copy,Clone,PartialEq,Eq)]structNicheKey(u32);// This will reserve the upper 255 values for us to use as nichesconstNICHE:usize = 0xFF000000;// Implementing `Key` is unsafe and requires that anything given to `try_from_usize` must produce the// same `usize` when `into_usize` is later calledunsafeimplKeyforNicheKey{fninto_usize(self) -> usize{self.0asusize}fntry_from_usize(int:usize) -> Option<Self>{if int < NICHE{// The value isn't in our niche range, so we're good to goSome(Self(int asu32))}else{// The value interferes with our niche, so we return `None`None}}}// To make sure we're upholding `Key`'s safety contract, let's make two small tests#[test]fnvalue_in_range(){let key = NicheKey::try_from_usize(0).unwrap();assert_eq!(key.into_usize(),0);let key = NicheKey::try_from_usize(NICHE - 1).unwrap();assert_eq!(key.into_usize(),NICHE - 1);}#[test]fnvalue_out_of_range(){let key = NicheKey::try_from_usize(NICHE);assert!(key.is_none());let key = NicheKey::try_from_usize(u32::max_value()asusize);assert!(key.is_none());}// And now we're done and can make `Rodeo`s or `ThreadedRodeo`s that use our custom key!letmut rodeo:Rodeo<NicheKey> = Rodeo::new();let key = rodeo.get_or_intern("It works!");assert_eq!(rodeo.resolve(&key),"It works!");
Example: Creation using FromIterator
use lasso::Rodeo;use core::iter::FromIterator;// Works for both `Rodeo` and `ThreadedRodeo`let rodeo = Rodeo::from_iter(vec!["one string","two string","red string","blue string",]);assert!(rodeo.contains("one string"));assert!(rodeo.contains("two string"));assert!(rodeo.contains("red string"));assert!(rodeo.contains("blue string"));
use lasso::Rodeo;use core::iter::FromIterator;// Works for both `Rodeo` and `ThreadedRodeo`let rodeo:Rodeo = vec!["one string","two string","red string","blue string"].into_iter().collect();assert!(rodeo.contains("one string"));assert!(rodeo.contains("two string"));assert!(rodeo.contains("red string"));assert!(rodeo.contains("blue string"));
Benchmarks
Benchmarks were gathered with Criterion.rs
OS: Windows 10
CPU: Ryzen 9 3900X at 3800Mhz
RAM: 3200Mhz
Rustc: Stable 1.44.1
