Fast and Simple Rust Interner

This post describes a simple technique for writing interners in Rust which I haven't seen documented before.

This post describes a simple technique for writing interners in Rust which I haven’t seen documented before. String interning is a classical optimization when you have to deal with many equal strings. The canonical example would be a compiler: most identifiers in a program are repeated several times. Interning works by ensuring that there’s only one canonical copy of each distinct string in memory. It can give the following benefits: Less memory allocated to hold strings. If all strings are canonicalized, comparison can be done in O(1) (instead of O(n) ) by using pointer equality. Interned str

related reading

• Interning (computer science) - Wikipediaen.wikipedia.org
• (Re)writing an interpreter in Rust – Danny van Kootendannyvankooten.com
• abseil / Performance Hintsabseil.io
• What is Ownership? - The Rust Programming Languagedoc.rust-lang.org
• Working with strings in Rustfasterthanli.me
• A half-hour to learn Rustfasterthanli.me
• Rust Optimization.md · GitHubgist.github.com
• Rust Language Cheat Sheetcheats.rs
• HashMap in std::collections - Rustdoc.rust-lang.org
• Storing UTF-8 Encoded Text with Strings - The Rust Programming Languagedoc.rust-lang.org
• The Slice Type - The Rust Programming Languagedoc.rust-lang.org
• Adrian Sampson: Flattening ASTs (and Other Compiler Data Structures)cs.cornell.edu