Deep Dive into Rust’s High‑Performance String Interning Library ustr

Introduction

Many applications repeatedly create identical strings as identifiers—symbols in trading systems, resource paths in game engines, variable names in compilers, or keys in configuration stores. Allocating new memory and performing byte‑wise comparisons for each occurrence wastes resources. String interning solves this by keeping a single copy of each distinct string and allowing pointer‑based equality checks.

What is ustr?

ustr

(Unique Str) is a lightweight handle representing a static, immutable entry in a global string cache. Its design is inspired by OpenImageIO’s ustring but adapted to Rust.

The library’s core advantages are summarized as fast, cheap, stable, and transparent:

Fast : Assignment and equality are pointer comparisons (O(1)); hash values are pre‑computed.

Cheap : Identical strings share a single stored copy, represented by a Ustr handle.

Stable : Interned strings are never freed, giving them a 'static lifetime and safe cross‑thread transfer.

Transparent : Strings are NUL‑terminated, so they can be passed directly to C FFI without converting to CString.

Quick Start

Add the dependency in Cargo.toml:

[dependencies]
ustr = { version = "1.1.0", features = ["serde"] }

Basic Usage

use ustr::{Ustr, ustr};

fn main() {
    // Two creation methods: Ustr::from and ustr()
    let u1 = Ustr::from("the quick brown fox");
    let u2 = ustr("the quick brown fox");
    // Same content shares one entry; equality is a pointer compare
    assert_eq!(u1, u2);
    // Copying is just copying a pointer, zero cost
    let u3 = u1;
    assert_eq!(u2, u3);
    // Convert to &str for normal string operations
    let words: Vec<&str> = u1.as_str().split_whitespace().collect();
    assert_eq!(words, ["the", "quick", "brown", "fox"]);
    // Inspect number of cached unique strings
    println!("Cache entries: {}", ustr::num_entries());
}

Passing Directly to C FFI

use ustr::ustr;

let u_fox = ustr("the quick brown fox");
// as_char_ptr() returns a C‑style NUL‑terminated pointer
let len = unsafe { libc::strlen(u_fox.as_char_ptr()) };
assert_eq!(len, 19);

This direct pointer capability distinguishes ustr from other interning libraries.

High‑Performance HashMap

UstrMap

and UstrSet use a hasher that accepts the pre‑computed hash, enabling fast lookups.

use ustr::{ustr, UstrMap};
let mut map: UstrMap<usize> = UstrMap::default();
let key = ustr("player_health");
map.insert(key, 100);
assert_eq!(*map.get(&key).unwrap(), 100);

Serde Serialization Support

Enabling the serde feature allows serializing individual Ustr values and the entire cache.

use ustr::{Ustr, ustr};
let u_ser = ustr("serde");
let json = serde_json::to_string(&u_ser).unwrap();
let u_de: Ustr = serde_json::from_str(&json).unwrap();
assert_eq!(u_ser, u_de);

// Serialize and restore the whole cache
use ustr::{ustr, Ustr};
ustr("Send me to JSON and back");
let json = serde_json::to_string(ustr::cache()).unwrap();
let _: ustr::DeserializedCache = serde_json::from_str(&json).unwrap();
assert_eq!(ustr::num_entries(), 1);

Internals

Core Data Structure: A Pointer to Everything

The Ustr struct is a transparent wrapper around a non‑null *const u8 pointer (8 bytes on 64‑bit systems). The pointer points to the string data, but just before the data lies a StringCacheEntry containing the string’s length and pre‑computed hash.

#[repr(transparent)]
pub struct Ustr {
    char_ptr: NonNull<u8>,
}

Accessing length or hash is a simple offset from the pointer:

fn as_string_cache_entry(&self) -> &StringCacheEntry {
    unsafe { &*(self.char_ptr.as_ptr().cast::<StringCacheEntry>().sub(1)) }
}

pub fn len(&self) -> usize { self.as_string_cache_entry().len }
pub fn precomputed_hash(&self) -> u64 { self.as_string_cache_entry().hash }

Sharded Concurrent Cache

The global cache is divided into NUM_BINS shards, each protected by its own parking_lot::Mutex. Insertion first hashes the string, selects a bin via the high bits of the hash, then locks only that bin, reducing contention.

pub struct Bins(pub (crate) [Mutex<StringCache>; NUM_BINS]);

fn whichbin(hash: u64) -> usize {
    ((hash >> TOP_SHIFT) % NUM_BINS as u64) as usize
}

String Creation Flow

Ustr::from

performs three steps: compute the hash with ahash, select and lock the appropriate bin, then insert or retrieve the existing entry. If the string already exists, insert returns the existing pointer without allocating new memory.

pub fn from(string: &str) -> Ustr {
    // 1. Compute hash
    let mut hasher = ahash::AHasher::default();
    hasher.write(string.as_bytes());
    let hash = hasher.finish();
    // 2. Choose bin and lock
    let mut sc = STRING_CACHE[whichbin(hash)].lock();
    // 3. Insert or get existing pointer
    Ustr { char_ptr: unsafe { NonNull::new_unchecked(sc.insert(string, hash) as *mut _) } }
}

Why Equality Is a Pointer Compare?

The PartialEq implementation derives equality by comparing the internal char_ptr. Because interning guarantees a unique address per distinct string, pointer equality is equivalent to content equality, yielding O(1) comparisons regardless of string length.

#[derive(Copy, Clone, PartialEq)]
#[repr(transparent)]
pub struct Ustr { char_ptr: NonNull<u8> }

Why Hashing Is Fast

The Hash trait for Ustr simply feeds the pre‑computed hash value into the hasher, avoiding any traversal of the string bytes.

impl Hash for Ustr {
    fn hash<H: Hasher>(&self, state: &mut H) {
        self.precomputed_hash().hash(state);
    }
}

Bump Allocator: Allocate‑Only Memory

The cache uses a bump allocator: allocation is a pointer bump, and memory is never reclaimed individually. When a bump region fills, a larger region is allocated and the old one is kept in old_allocs, ensuring all interned strings remain valid.

Thread Safety

Ustr

implements Send and Sync because the underlying string data is immutable and never freed, allowing safe sharing across threads without additional synchronization.

unsafe impl Send for Ustr {}
unsafe impl Sync for Ustr {}

Suitable Scenarios and Limitations

Ideal Use Cases

Environments with a small set of unique strings but massive repeated references—e.g., trading symbols, game resource IDs, compiler symbol tables, configuration keys, or log tags—benefit from ustr ’s pointer‑copy assignment, pointer‑compare equality, and O(1) hash reads.

Less Suitable Cases

Workloads that generate large numbers of short‑lived, distinct strings can cause unbounded memory growth, as interned strings are never released. If the primary operations involve string concatenation or slicing rather than lookup, a regular String may be preferable.

Performance Intuition

Compared with String, Ustr offers O(1) equality (pointer compare) versus O(n) byte‑wise comparison, O(1) hash retrieval versus O(n) traversal, and copying an 8‑byte pointer versus allocating and copying the entire string data. Ustr occupies 8 bytes, while String occupies 24 bytes (pointer, length, capacity).

Conclusion

ustr

is a cleverly designed interning library that combines a global cache, sharded locking, a bump allocator, and pre‑computed hashes to reduce string comparison, copying, and hashing to constant time. Its API integrates smoothly with Rust’s type system and FFI ecosystem, making it a strong candidate for projects with heavy repeated‑string workloads.