commit 0a15e2dae34432cd3ba85b48822292e8509340d3
author Steinar H. Gunderson <sesse@chromium.org> Thu May 12 21:34:00 2022
committer Chromium LUCI CQ <chromium-scoped@luci-project-accounts.iam.gserviceaccount.com> Thu May 12 21:34:00 2022
tree 238f6c3e54af250bb8ae957e109e0ab058267886
parent d36e1f5a479479513c2731a5e0d9e1ede1e4bdb5

Aho-Corasick attribute selector pruning.

If a stylesheet has a lot of different rules bucketed on the same
attribute (some extensions inject user stylesheets that do this,
for one), we can do better than testing each and every one of them
individually. As an optimization, we can use SubstringSetMatcher
(an implementation of the Aho-Corasick string matching algorithm)
to rapidly test against all of them in linear time in the length of
the attribute value. This takes a bit of RAM for such stylesheets
(e.g. a 743-element tree from the Extension subtest takes ~153 kB),
but speeds up their matching significantly.

Style microbenchmarks (Zen 2, LTO but no PGO; only Extension,
News, Sports and Video actually get behavioral differences):

Parse (µs)             Before     After    Perf      95% CI (BCa)
=================== ========= ========= ======= =================
ECommerce                1693      1717   -1.4%  [ -1.5%,  -1.2%]
Encyclopedia             9170      9179   -0.1%  [ -0.2%,  -0.0%]
Extension                1637      1662   -1.5%  [ -1.6%,  -1.3%]
News                    10267     10288   -0.2%  [ -0.3%,  -0.1%]
Search                   6236      6260   -0.4%  [ -0.4%,  -0.3%]
Social1                 21045     21046   -0.0%  [ -0.1%,  +0.1%]
Social2                   722       737   -2.0%  [ -2.2%,  -1.9%]
Sports                  73974     74119   -0.2%  [ -0.3%,  -0.1%]
Video                   38936     39101   -0.4%  [ -0.5%,  -0.4%]
Geometric mean                            -0.7%  [ -0.8%,  -0.6%]

Initial style (µs)     Before     After    Perf      95% CI (BCa)
=================== ========= ========= ======= =================
ECommerce               11477     11419   +0.5%  [ +0.4%,  +0.6%]
Encyclopedia           110338    110068   +0.2%  [ +0.2%,  +0.3%]
Extension              261834    137113  +91.0%  [+90.8%, +91.1%]
News                    43919     43823   +0.2%  [ +0.1%,  +0.3%]
Search                   2775      2800   -0.9%  [ -1.0%,  -0.8%]
Social1                 26140     26114   +0.1%  [ +0.0%,  +0.2%]
Social2                  1087      1061   +2.4%  [ +2.2%,  +2.6%]
Sports                  37874     36289   +4.4%  [ +4.3%,  +4.4%]
Video                   41291     41292   -0.0%  [ -0.1%,  +0.1%]
Geometric mean                            +8.3%  [ +8.2%,  +8.3%]

Recalc style (µs)      Before     After    Perf      95% CI (BCa)
=================== ========= ========= ======= =================
ECommerce               14568     14544   +0.2%  [ +0.0%,  +0.3%]
Encyclopedia            98240     97627   +0.6%  [ +0.5%,  +0.8%]
Extension              257682    130824  +97.0%  [+96.8%, +97.2%]
News                    33016     33000   +0.0%  [ -0.1%,  +0.2%]
Search                    251       249   +0.6%  [ +0.4%,  +0.8%]
Social1                 17993     17884   +0.6%  [ +0.5%,  +0.7%]
Social2                   602       580   +3.8%  [ +3.4%,  +4.0%]
Sports                  29106     27465   +6.0%  [ +5.9%,  +6.1%]
Video                   29407     29343   +0.2%  [ +0.1%,  +0.5%]
Geometric mean                            +9.2%  [ +9.1%,  +9.3%]

Change-Id: I5fe9d74fae11c30e7dc5c2cd62f2944e2cba50eb
Bug: 1318773
Reviewed-on: https://chromium-review.googlesource.com/c/chromium/src/+/3581992
Reviewed-by: Philip Rogers <pdr@chromium.org>
Commit-Queue: Steinar H Gunderson <sesse@chromium.org>
Reviewed-by: Jeremy Roman <jbroman@chromium.org>
Cr-Commit-Position: refs/heads/main@{#1002855}