Skip to content

Interning is quadratic for strings crafted to share a dynamic-set bucket #314

Open

Description

@tstreule

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:

Activity

  1. SimonSapin commented on Oct 29, 2026

    @SimonSapin
    Member

    To clarify: interning N different strings intentionally crafted to all have hash collisions takes O(N²) quadratic time overall, right? For an individual string the worst case is O(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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions