commit 5e3b0aa36d05e39f840e2725fe9d9e9bc654c578
author Steinar H. Gunderson <sesse@chromium.org> Mon Sep 25 12:40:23 2023
committer Blink WPT Bot <blink-w3c-test-autoroller@chromium.org> Mon Sep 25 12:58:45 2023
tree 87401428bc0b829ffb3d0ee44c83564182dbe847
parent e053db4bf52bdf84cf2c38e8edc3245807c83c17

Switch RuleMap to a custom hash table.

A significant part of style (~6%) is doing lookups in RuleMaps,
specifically in AtomicString-indexed hash tables. These currently
use WTF::HashTable, but we can do better with a custom
hash table implementation. Thus, we implement RobinHoodMap,
a lookup-optimized variant with higher load factor and thus
tighter memory footprint.

One direct consequence of this is less RAM usage; e.g. Social1
reports ~460 kB less PartitionAlloc memory allocated (most subtests
have smaller hash tables, though, since they have fewer rules).
But we also get less cache pressure. The exact result depends
on the CPU; smaller/slower caches give more gains, less sophisticated
branch predictors give less gains. In general, most seem to be
around neutral, but Intel CPUs give a fairly good gain. Inserts
are slightly slower and lookups are faster, so repeated style
application should get larger gains. Of course, in the style
perftest, we have the cache all to ourselves, so it will tend to
underestimate these effects somewhat.

Style perftest (Alder Lake P-cores, LTO but no PGO):

Initial style (µs)     Before     After    Perf      95% CI (BCa)
=================== ========= ========= ======= =================
ECommerce                4491      4484   +0.1%  [ -0.6%,  +0.8%]
Encyclopedia            40679     39868   +2.0%  [ +1.1%,  +2.9%]
Extension               53970     53971   -0.0%  [ -0.8%,  +0.7%]
News                    19728     19325   +2.1%  [ +0.9%,  +3.2%]
Search                   6316      6176   +2.3%  [ +1.1%,  +3.4%]
Social1                 11547     11753   -1.8%  [ -2.8%,  -0.7%]
Social2                  7383      7281   +1.4%  [ +0.4%,  +2.3%]
Sports                  20644     20580   +0.3%  [ -0.8%,  +1.4%]
Video                   16020     16064   -0.3%  [ -1.1%,  +0.5%]
Geometric mean                            +0.7%  [ +0.1%,  +1.2%]

Recalc style (µs)      Before     After    Perf      95% CI (BCa)
=================== ========= ========= ======= =================
ECommerce                5011      4958   +1.1%  [ +0.3%,  +1.8%]
Encyclopedia            32407     31336   +3.4%  [ +2.6%,  +4.3%]
Extension               49217     48970   +0.5%  [ -0.3%,  +1.2%]
News                    15065     14569   +3.4%  [ +2.3%,  +4.4%]
Search                   2911      2771   +5.0%  [ +4.3%,  +5.9%]
Social1                  7417      7271   +2.0%  [ +0.8%,  +3.0%]
Social2                  5634      5548   +1.5%  [ +0.6%,  +2.4%]
Sports                  11345     11040   +2.8%  [ +1.9%,  +3.6%]
Video                   10659     10381   +2.7%  [ +1.8%,  +3.6%]
Geometric mean                            +2.5%  [ +1.9%,  +3.0%]

Change-Id: I3b25f24d0595b21ad5d5e354e2c03a390bddc5aa
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/4866725
Commit-Queue: Steinar H Gunderson <sesse@chromium.org>
Reviewed-by: Anders Hartvoll Ruud <andruud@chromium.org>
Cr-Commit-Position: refs/heads/main@{#1200933}