commit c045958d36f0b59237d411014aebbe70818a6f0b
author Steinar H. Gunderson <sesse@chromium.org> Wed Aug 10 15:49:47 2022
committer Chromium LUCI CQ <chromium-scoped@luci-project-accounts.iam.gserviceaccount.com> Wed Aug 10 15:49:47 2022
tree 3aafe05253732e9453c844a50b2f3f17dd708349
parent dd1fed1d2f5c8ad01bee7e26233f512d6a02141b

Make RuleMap backed by a contiguous vector for all buckets.

Our current definition of RuleMap, HeapHashMap<AtomicString,
Member<HeapVector<RuleData>>>, is suboptimal for lookup performance:

 - First, we need to do the hash lookup. From there, we get a pointer
   (since HeapHashMap<>, unlike HeapVector<>, cannot take Oilpan-managed
   structs directly without Member<>).
 - We follow that pointer to get the vector metadata (base and size).
 - We follow the base pointer to get to the actual data.

The last two steps should really be only one step; either pointer is
unlikely to be in the L1 cache, causing undue performance cost.
Furthermore, this gives us extra per-allocation overhead, more
allocations to clean up in GC, and also heap fragmentation from all
the small vectors.

Instead, we make RuleMap a true class on its own, where the HeapHashMap
contains an index into a shared, contiguous vector (and a length).
This mean the vector metadata is shared between all buckets, and can
live in the same cache line as the HeapHashMap metadata (so we will
almost never miss it). Insertion should also be somewhat cheaper,
at the cost of a sorting/grouping step when we do compaction; however,
we can do that with counting sort, which seems to have low overhead.

Style microbenchmarks (Zen 3, LTO but no PGO):

  Initial style (µs)     Before     After    Perf      95% CI (BCa)
  =================== ========= ========= ======= =================
  ECommerce                8052      7940   +1.4%  [ +0.9%,  +1.9%]
  Encyclopedia            71293     69627   +2.4%  [ +1.8%,  +3.0%]
  Extension              165222    165434   -0.1%  [ -0.5%,  +0.2%]
  News                    31635     31323   +1.0%  [ +0.4%,  +1.5%]
  Search                   2133      1964   +8.6%  [ +7.9%,  +9.5%]
  Social1                 18438     17705   +4.1%  [ +3.7%,  +4.7%]
  Social2                   786       763   +3.0%  [ +2.4%,  +3.6%]
  Sports                  26244     25759   +1.9%  [ +1.5%,  +2.5%]
  Video                   31940     30849   +3.5%  [ +3.0%,  +4.1%]
  Geometric mean                            +2.8%  [ +2.6%,  +3.1%]

  Recalc style (µs)      Before     After    Perf      95% CI (BCa)
  =================== ========= ========= ======= =================
  ECommerce                9251      9098   +1.7%  [ +1.0%,  +2.3%]
  Encyclopedia            64104     62651   +2.3%  [ +1.6%,  +2.9%]
  Extension              164619    164016   +0.4%  [ -0.1%,  +0.8%]
  News                    23297     23003   +1.3%  [ +0.6%,  +1.9%]
  Search                    183       181   +1.0%  [ -0.1%,  +2.2%]
  Social1                 12952     12724   +1.8%  [ +1.2%,  +2.3%]
  Social2                   391       390   +0.3%  [ -0.5%,  +0.8%]
  Sports                  19382     19129   +1.3%  [ +0.8%,  +2.2%]
  Video                   19782     19525   +1.3%  [ +0.8%,  +1.9%]
  Geometric mean                            +1.3%  [ +0.9%,  +1.5%]

Change in Oilpan memory after running each benchmark:

  ECommerce       2565 kB ->  2399 kB  ( -6.5%)
  Encyclopedia   13483 kB -> 13481 kB  ( -0.0%)
  Extension      14200 kB -> 14107 kB  ( -0.7%)
  News            8469 kB ->  8399 kB  ( -0.8%)
  Search          3144 kB ->  2928 kB  ( -6.9%)
  Social1         6966 kB ->  6158 kB  (-11.6%)
  Social2         2113 kB ->  1948 kB  ( -7.8%)
  Sports         17347 kB -> 16565 kB  ( -4.5%)
  Video          22895 kB -> 21986 kB  ( -4.0%)

Note that these are closer to what Oilpan would refer to as “peak”
allocation; actually running a full GC afterwards would yield smaller
numbers on both sides. However, we are still uniformly down or neutral
in memory usage on the entire suite.

This being said, there may very well be isolated Pinpoint tests that
return negative results. We believe, however, that the results are
overall significantly positive.

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