2062315 - PrecomputedHasher defeats hashbrown's control-byte filter on all 64-bit platforms

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect)

Description

[Mayank Bansal]

Attachment: reproducer.rs

I found the answer to that lead, and it's not what the note predicted. Here's the analysis, written so you can paste it into a bug.

---

Summary

PrecomputedHasher defeats hashbrown's control-byte filter on all 64-bit platforms. Every entry in every PrecomputedHashMap in the style system has control tag 0x00, so every lookup runs a full key comparison against ~8 candidate entries instead of ~1. This affects all five SelectorMap buckets (id_hash, class_hash, local_name_hash, attribute_hash, namespace_hash), the invalidation dependency maps, the cascade's custom-property maps, and the @property registry.

Where the lead came from

Profiling bug 2062076 left a note that the element path is the only place a measurable style win could come from: on a Windows SP3 profile (speedometer3-no-nv, 41.8 s, 2 ms sampling), the content main thread spends 331 samples ≈ 629 ms in SelectorMap::get_all_matching_rules — 17x the entire eager-pseudo path (match_pseudo, 19 samples) — and 263 of those 331 are under each_class → AtomIdent::with → hashbrown.

Decomposing that with the code (selector_map.rs:248, wrapper.rs:1278, snapshot_helpers.rs:206):

node	samples	note
get_all_matching_rules	331	≈ 629 ms
├ each_class	263	the per-class closure
│ ├ each_class_or_part	262	so get_class_attr + find_attr = 1 sample
│ └ AtomIdent::with	243	the wrapper is free; this is the callback
matches_complex_selector (whole thread)	80	all real selector matching

Two things fall out immediately. Enumerating the classes is free (1 sample), so "hoist the class walk out of the per-map loop" is dead on arrival. And real matching is only 80 samples thread-wide, so the bulk of the 263 is the class_hash probe plus get_matching_rules' per-rule bloom check — not matching.

The defect

selector_map.rs:83:

fn finish(&self) -> u64 {
    self.hash.expect("PrecomputedHasher wasn't fed?") as u64
}

A u32 atom hash, zero-extended into a u64. hashbrown takes the control tag from the top 7 bits (hashbrown/src/control/tag.rs:35):

const MIN_HASH_LEN: usize = if size_of::<usize>() < size_of::<u64>() { size_of::<usize>() } else { size_of::<u64>() };
let top7 = hash >> (MIN_HASH_LEN * 8 - 7);   // >> 57 on 64-bit

hash >> 57 of a zero-extended u32 is always 0. So every full slot's tag is 0x00 and every query looks for 0x00; Group::match_tag matches every occupied slot in the group and hashbrown falls back to comparing keys one by one. The SIMD filter — the entire point of SwissTable — is inert.

The MIN_HASH_LEN dance exists precisely to handle usize-width hashes on 32-bit, which means 32-bit builds are fine and only 64-bit is affected.

Evidence

Reproduced against std::collections::HashMap with a hasher identical to PrecomputedHasher (rustc 1.96), counting key comparisons directly:

n	today (h as u64)	(h << 32) | h
16, all miss	16.0 ns, 8.01 compares/lookup	1.7 ns, 0.00
256, all miss	16.3 ns, 7.88 compares/lookup	2.0 ns, 0.00
4096, all miss	22.2 ns, 8.05 compares/lookup	2.0 ns, 0.00
4096, 50% hit	13.3 ns, 4.72 compares/lookup	3.1 ns, 0.50

The compare count is the structural result; the timings understate Gecko. In the microbenchmark an extra candidate is an L1-resident 4-byte compare. In the style system each candidate is a ~56-byte (Atom, SmallVec<[Rule; 1]>) load, and for local_name_hash/attribute_hash — queried with &WeakAtom, so Borrow must deref each stored AtomIdent — it is an additional chase into the 40 KB gGkAtoms table. That shows up in the profile as gecko_string_cache::impl$3::deref carrying 11.5% self time under equivalent, with find_inner at 36.5% of the probe subtree. A healthy tag filter would make that ~1 deref per lookup.

Proposed fix

fn finish(&self) -> u64 {
    let hash = self.hash.expect("PrecomputedHasher wasn't fed?") as u64;
    (hash << 32) | hash
}

Duplicating into the high half rather than multiplying is deliberate: the bucket index is hash as usize & bucket_mask, so keeping the low 32 bits identical leaves bucket assignment, probe sequence and iteration order unchanged. Only the control byte changes. Atom hashes come from mozilla::HashString, which has good entropy in its high bits, so the tag is well distributed.

Sizing — deliberately not claiming a win yet

get_all_matching_rules is 629 ms of 26.16 s main-thread CPU across a 41.8 s run, and probes are only part of that; the profile as recorded does not separate the hashbrown probe from get_matching_rules' per-rule ancestor-hash check, which is the one measurement still missing. A first-order estimate lands in the few-tenths-of-a-percent range on Speedometer 3 — plausibly under the noise floor, which is the same trap the rest of this patch family fell into. What makes it worth pushing anyway: three lines, no new mechanism, no behaviour change, and it helps every atom-keyed map on every workload rather than one path.

Comment 1

[Mayank Bansal]

Emilio, does this sound plausible?

Comment 2

[Emilio Cobos Álvarez [:emilio]]

Sounds believable yeah, the fix sounds reasonable. But then again everything Claude proposes is pretty believable.

Comment 3

[Emilio Cobos Álvarez [:emilio]]

Attachment: Bug 2062315 - Improve PrecomputedHasher's output. r=#style

Make sure we don't output the upper 64 bits of hash as always zero.

Comment 4

[Mayank Bansal]

Attachment: Bug 2062315 - Widen PrecomputedHasher's output so hashbrown's control tag isn't always zero. r?#firefox-style-system-reviewers

finish() returned the u32 atom hash zero-extended to u64, but hashbrown derives its
7-bit control tag from the top 7 bits. Every entry in every PrecomputedHashMap
therefore had tag 0, so each lookup matched every occupied slot in the group and ran
a full key comparison on all of them. Duplicating the hash into the high half leaves
the low bits, and so the bucket index and iteration order, untouched.

Simulating hashbrown over Speedometer 3's class names (1081 atoms), key comparisons
per lookup drop from 1.70 to 1.01 on a hit and from 8.77 to 0.08 on a miss (14.30 at
a 0.78 load factor). Probe length is unchanged either way, so a full avalanche mix
would only churn iteration order.

Comment 5

[Pulsebot]

Pushed by [e-mail]:
https://github.com/mozilla-firefox/firefox/commit/9ac4086531fb
https://hg.mozilla.org/integration/autoland/rev/71e373401d84
Improve PrecomputedHasher's output. r=firefox-style-system-reviewers,dshin

Comment 6

[Serban Stanca [:SerbanS]]

https://hg.mozilla.org/mozilla-central/rev/71e373401d84

Comment 7

[Serban Stanca [:SerbanS]]

https://hg.mozilla.org/mozilla-central/rev/71e373401d84

Comment 8

[Performance Sheriff Bot]

Perfherder has detected a browsertime performance change from push 71e373401d8479b16296720166f28b6da2c8f3ce.

No action is required from the author; this comment is provided for informational purposes only.

Improvements	Test	Platform	Options	Absolute values [old vs new]	Performance Profiles
5%	stylebench Dynamic media queries/Resizing to 750px - 3/Sync (doc)	macosx1470-64-shippable	fission webrender	14.72 ms -> 14.04 ms	Before/After
5%	stylebench Dynamic media queries/Resizing to 750px - 1/Sync (doc)	macosx1470-64-shippable	fission webrender	14.70 ms -> 14.03 ms	Before/After
5%	stylebench Dynamic media queries/Resizing to 650px - 3/Sync (doc)	macosx1470-64-shippable	fission webrender	15.08 ms -> 14.39 ms	Before/After
4%	stylebench Dynamic media queries/Resizing to 450px - 4/Sync (doc)	macosx1470-64-shippable	fission webrender	15.32 ms -> 14.63 ms	Before/After
4%	stylebench Dynamic media queries/Resizing to 450px - 1/Sync (doc)	macosx1470-64-shippable	fission webrender	15.31 ms -> 14.62 ms	Before/After
...	...	...	...	...	...
2%	stylebench Dynamic media queries/Resizing to 300px - 1 (doc)	linux2404-64-shippable	fission webrender	15.95 ms -> 15.61 ms	Before/After

Need Help or Information?

If you have any questions, please reach out to [e-mail]. Alternatively, you can find help on Slack by joining #perf-help, and on Matrix you can find help by joining #perftest.

Details of the alert can be found in the alert summary, including links to graphs and comparisons for each of the affected tests.

Comment 9

[Performance Sheriff Bot]

Perfherder has detected a talos performance change from push 71e373401d8479b16296720166f28b6da2c8f3ce.

No action is required from the author; this comment is provided for informational purposes only.

Improvement	Test	Platform	Options	Absolute values [old vs new]
23%	perf_reftest_singletons many-custom-props.html (doc)	windows11-64-24h2-shippable	e10s fission stylo webrender	154.47 ms -> 119.26 ms
17%	perf_reftest_singletons many-custom-props.html (doc)	linux2404-64-shippable	e10s fission stylo webrender	266.85 ms -> 222.28 ms
15%	perf_reftest_singletons many-custom-props.html (doc)	macosx1470-64-shippable	e10s fission stylo webrender	274.96 ms -> 233.60 ms
12%	perf_reftest coalesce-2.html (doc)	linux2404-64-shippable	e10s fission stylo webrender	24.66 ms -> 21.68 ms

Need Help or Information?

If you have any questions, please reach out to [e-mail]. Alternatively, you can find help on Slack by joining #perf-help, and on Matrix you can find help by joining #perftest.

Details of the alert can be found in the alert summary, including links to graphs and comparisons for each of the affected tests.