Repository navigation
Description
Interning strings that share a bucket of the dynamic set takes quadratic time. The set's bucket is chosen by a hash with a public key, so such strings are cheap to craft. Parsers that intern names from untrusted input, such as html5ever with attribute and tag names, inherit this.
Cause
dynamic_set::Set has a fixed NB_BUCKETS = 4096, each a linked list. insert walks the bucket's list to find an existing entry, and remove (on dropping the last reference) walks it again.
The bucket is the low 12 bits of the hash Atom::from already computed with phf_shared::hash and the static set's key. That reuse is deliberate (see #197): it saves hashing the string twice. But the key is compiled into the binary and the same for every user, so anyone can find strings that land in one bucket offline, at about 4096 tries per string.
Strings of 7 bytes or less are inline atoms and never reach the set.
Repro
string_cache = "=0.11.0", cargo run --release, Apple M1 Pro:
use string_cache::DefaultAtom as Atom;
use std::time::Instant;
// The dynamic set picks one of its 4096 buckets from the low 12 bits of the atom's hash.
const BUCKET_MASK: u64 = (1 << 12) - 1;
fn main() {
let target = Atom::from("collide-0").get_hash() & BUCKET_MASK;
let mut same_bucket = Vec::new();
let mut spread = Vec::new();
let mut i = 0u64;
while same_bucket.len() < 40_000 {
let s = format!("collide-{i}");
if Atom::from(s.as_str()).get_hash() & BUCKET_MASK == target {
same_bucket.push(s);
}
i += 1;
}
for i in 0..40_000 {
spread.push(format!("spread-{i}"));
}
for n in [5_000usize, 10_000, 20_000, 40_000] {
for (label, strings) in [("one bucket", &same_bucket), ("spread", &spread)] {
let start = Instant::now();
let atoms: Vec<Atom> = strings[..n].iter().map(|s| Atom::from(s.as_str())).collect();
drop(atoms);
println!("{n:>6} atoms, {label:<10}: {:.3?}", start.elapsed());
}
}
}| atoms | one bucket | spread |
|---|---|---|
| 5,000 | 41 ms | 0.36 ms |
| 10,000 | 170 ms | 0.79 ms |
| 20,000 | 710 ms | 2.1 ms |
| 40,000 | 2.84 s | 5.9 ms |
Through html5ever, one start tag with 80,000 such attribute names (about 1.4 MB) takes about 10 s to tokenize. That remains with servo/html5ever#796 fixed, because interning happens before its duplicate check.
Possible directions
I haven't designed either of these:
- Pick the dynamic set's bucket with a hash keyed per process, so colliding strings can't be precomputed. This gives up part of the hash reuse May we have a comment explaining why the library implements its own fixed length hashmap? #197 describes.
- Let the set grow with the number of live atoms, so a bucket's list stays short. On its own, this only raises the cost of crafting collisions.
Activity
SimonSapin commentedon Oct 29, 2026
To clarify: interning
Ndifferent strings intentionally crafted to all have hash collisions takesO(N²)quadratic time overall, right? For an individual string the worst case isO(number of previous strings in that bucket)linear time.I think to fix this we’ll probably need to give up on reusing the same hash for the static set and the dynamic set, so that interning a string that ends up in the dynamic set requires hashing it twice with different hashers.
Use a per-process hash for the dynamic set
Add Servo website to HTML parsing benchmarks (servo#813)
Add Servo website to HTML parsing benchmarks (#813)