Crate intern_arc

Interning library based on atomic reference counting

This library differs from arc-interner (which served as initial inspiration) in that

• it contains no static global state (interners must be created and can be dropped; you can use OnceCell or lazy_static! to manage global instances)
• it does not dispatch based on TypeId (each interner is for exactly one type)
• it offers both Hash-based and Ord-based storage
• it handles unsized types without overhead, so you should use Intern<str> instead of Intern<String>

Unfortunately, this combination of features makes it inevitable to use unsafe Rust. The handling of reference counting and constructing of unsized values has been adapted from the standard library’s Arc type. Additionally, the test suite passes also under miri to check against some classes of undefined behavior in the unsafe code (including memory leaks).

API flavors

The same API is provided in two flavors:

• InternHash uses hash-based storage, namely the standard HashSet
• InternOrd uses ord-based storage, namely the standard BTreeSet

Interning small values takes of the order of 100–200ns on a typical server CPU. The ord-based storage has an advantage when interning large values (like slices greater than 1kB). The hash-based storage has an advantage when keeping lots of values (many thousands and up) interned at the same time.

Nothing beats your own benchmarking, though.

Caveat emptor!

This crate’s Interned type does not optimise equality using pointer comparisons because there is a race condition between dropping a value and interning that same value that will lead to “orphaned” instances (meaning that interning that same value again later will yield a different storage location). All similarly constructed interning implementations share this caveat (e.g. internment or the above mentioned arc-interner).

Structs

InternHash
InternOrd
Interned