1363789 - stylo: Use a 1-entry SmallVec in the selector maps to reduce allocations

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, defect, P4)

Description

[Boris Zbarsky [:bzbarsky]]

Looking at a profile of stylist::update for the myspace-orig testcase from bug 1358806, I'm seeing about 20% of the time under find_push and about half of that is malloc/realloc bits.

find_push does this:

    map.entry(key).or_insert_with(Vec::new).push(value)

where "map" is FnvHashMap<Str, Vec<V>, and this is going to heap-allocate storage for the vec the first time we end up inserting.

For comparison, the equivalent Gecko data structure is:

  struct RuleHashTableEntry : public PLDHashEntryHdr {
    // Auto length 1, because we always have at least one entry in mRules.
    AutoTArray<RuleValue, 1> mRules;
  };

which avoids the extra allocation when there is only one rule targeting the id/class/tag involved.

Might be worth checking what the actual lengths of these vecs end up being in practice; if "1" is a common length it might be worth doing something with an inline buffer.

When I initially did the measurements in Gecko, back in 2011 or so, I got numbers along the lines of https://bugzilla.mozilla.org/show_bug.cgi?id=681755#c8 (the RuleHashTableEntry numbers are the ones relevant here).  At the time, after loading a bunch of websites, about 60% of the arrays had length 1.

Comment 1

[Boris Zbarsky [:bzbarsky]]

Oh, and per IRC discussion the allocs coming from the hashtable storage themselves are more or less unavoidable, and Gecko has those too.  The hashtable starts off with no storage, then allocates a reasonable chunk all at once, then does doubling, so not much to improve there.

Comment 2

[Bobby Holley (:bholley)]

Nice idea! I will measure.

Comment 3

[Boris Zbarsky [:bzbarsky]]

https://perf-html.io/public/87f8162a9d4d24e519628b481ff30bbbbf3345df/calltree/?callTreeFilters=prefix-01234567xEa9Ey1bcDYqD.ofKrxAexx3jDYo.qmL5xMrxMszMnzBazBbzBczD0zD1zLozL5zUtzUuzUvzV0zV1zV2zV3&thread=3 is the profile I'm looking at.

Comment 4

[Bobby Holley (:bholley)]

Have a patch, but the results on my usual testcases are inconclusive. 100x myspace doesn't benefit at all from this optimization, because every selector is duplicated.

Going to try constructing a best-case and worst-case testcase.

Comment 5

[Bobby Holley (:bholley)]

I measured this on amazon, looking at the interval between navigation start and first non-blank paint (what tp6 measures). The numbers are noisy, but I think it definitely improve things. Without this patch I get times in the range of 29-40, and with this patch I get times in the range of 23-32. It's simple enough, so I think it's worth getting it into the tree.

Comment 6

[Bobby Holley (:bholley)]

Attachment: Use a 1-entry smallvec in the selector maps. v1

MozReview-Commit-ID: 1JPkVxs3cdP

Comment 7

[Bobby Holley (:bholley)]

(In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #5)
> I measured this on amazon, looking at the interval between navigation start
> and first non-blank paint (what tp6 measures).

Specifically, looking at the work spent in Servo_StyleSet_* in this interval.

Comment 8

[Bobby Holley (:bholley)]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=c8c473154198a9d362613120b8a4363372bf8b80

Comment 9

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8894243 [details] [diff] [review]
Use a 1-entry smallvec in the selector maps. v1

Review of attachment 8894243 [details] [diff] [review]:
-----------------------------------------------------------------

r=me, with the comment.

I wonder if the invalidation stuff should also use them... Seems likely it'd also benefit from it.

::: servo/components/style/selector_map.rs
@@ +52,5 @@
>  /// TODO: Tune the initial capacity of the HashMap
>  #[derive(Debug)]
>  #[cfg_attr(feature = "servo", derive(HeapSizeOf))]
>  pub struct SelectorMap<T> {
>      /// A hash from an ID to rules which contain that ID selector.

Please point here to the measurements done on both this bug and bug 681755.

Comment 10

[Bobby Holley (:bholley)]

(In reply to Emilio Cobos Álvarez [:emilio] from comment #9)
> Comment on attachment 8894243 [details] [diff] [review]
> Use a 1-entry smallvec in the selector maps. v1
> 
> Review of attachment 8894243 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> r=me, with the comment.
> 
> I wonder if the invalidation stuff should also use them... Seems likely it'd
> also benefit from it.

Hm, don't those use SelectorMaps under the hood? I don't see any other HashMaps mapping to Vecs in style/.

> 
> ::: servo/components/style/selector_map.rs
> @@ +52,5 @@
> >  /// TODO: Tune the initial capacity of the HashMap
> >  #[derive(Debug)]
> >  #[cfg_attr(feature = "servo", derive(HeapSizeOf))]
> >  pub struct SelectorMap<T> {
> >      /// A hash from an ID to rules which contain that ID selector.
> 
> Please point here to the measurements done on both this bug and bug 681755.

Done.

Comment 11

[Bobby Holley (:bholley)]

https://github.com/servo/servo/pull/17988

Comment 12

[Emilio Cobos Álvarez (:emilio)]

Err, right, nvm, they use SelectorMap already.

Comment 13

[Bobby Holley (:bholley)]

https://hg.mozilla.org/integration/autoland/rev/179f972c8e053a35b3bc5cffc32523451658b3b0