internity 0.1.0

Blazingly fast string interning with compact handles, compact storage, and concurrent fill support
Documentation

Internity

crate.io docs.rs MSRV CI Coverage License

Compact string interning with local and concurrent engines.

String interning is a common technique to reduce memory use and improve performance when code handles the same strings over and over (identifiers in a compiler, tags/labels in telemetry, keys in a parser). The benefits of interning include:

  • Strings are stored once and reused which saves memory and CPU cycles

  • Strings are referenced with a 4-byte handle instead of an 8- or 16-byte reference. This can save considerable memory.

  • Hashing and comparison of interned strings is faster since it doesn’t require hashing or comparing whole strings, merely their 4-byte handle.

To intern a string, you supply it to the interning engine and it hands back a handle. No matter how many times you try to intern a given string, it gets deduplicated and gets added only once to the data store, and you get back the same handle. Later, you can use the handle to retrieve the actual string.

Handles

Interning yields a Sym — a 4-byte, Copy handle. It’s cheap to store and pass, Option<Sym> is also 4 bytes, and within one interner equal strings always produce equal handles, so == on handles is an O(1) stand in for string equality and a Sym works directly as a HashMap key.

Choosing an interner

internity supports two different string interners for different scenarios:

  • LocalLexicon. This engine interns strings from one thread and avoids synchronization during the fill phase. Shared readers can resolve strings concurrently.

  • ThreadedLexicon. This engine allows multiple threads to intern words concurrently and uses synchronization to coordinate inserts.

Both engines can be used through the Lexicon trait, allowing generic code to intern strings without selecting a concrete engine.

The intern → freeze → read pattern

Interning and resolving have different needs, so the typical lifecycle is to intern during a build phase, then freeze into a Reader for the read phase. A Reader is immutable, Send + Sync, and its lookups are lock-free — ideal for sharing across threads.

use internity::{LocalLexicon, Reader};

// Build phase.
let mut lexicon = LocalLexicon::new();
let hello = lexicon.intern("hello");
let world = lexicon.intern("world");
assert_eq!(lexicon.intern("hello"), hello); // deduplicated

// Read phase: freeze once, then resolve (here you could share `reader`
// across threads).
let reader = lexicon.freeze();
assert_eq!(reader.resolve(hello), "hello");
assert_eq!(reader.resolve(world), "world");

Custom hashers

Both interners default to a fast, non-cryptographic hasher and are generic over the BuildHasher, like HashMap. Use with_hasher to supply your own — for example a DoS-resistant hasher when interning untrusted input.

Production guidance

  • A Sym is local to the interner that created it. A foreign handle is range-checked, but an in-range numeric value can resolve to an unrelated string. Persist or transmit handles together with the matching interner.
  • The default Fx hasher is fast but not collision-attack resistant. Supply a defensive BuildHasher when strings can be selected by an attacker.
  • Interners do not remove individual strings. Memory grows during the fill phase until the interner is dropped or frozen.
  • A Sym does not implement serde::Serialize/Deserialize on its own: a bare handle is a meaningless integer without its interner. Serialize handles with the reader-aware se::SerializeIn derive (which resolves each handle to its string) and read them back with the de::DeserializeIn derive, so a value round-trips through a self-describing encoding. Serialize a whole corpus by freezing the interner and wrapping the Reader in se::SerializeReader.
  • Exceeding the documented byte or handle limits panics. Applications that accept untrusted strings should enforce count and byte quotas before interning.

Capacity

A single LocalLexicon holds up to approximately 4 GiB of string bytes; a ThreadedLexicon up to approximately 256 GiB (across its shards). Either way the number of distinct strings is bounded by the 4-byte handle (approximately 4.29 billion). Exceeding these limits panics rather than corrupting data.

Cargo features