1407246 - stylo: skip CustomPropertiesMap comparisons when we can

Status: RESOLVED FIXED

(Core :: CSS Parsing and Computation, enhancement, P2)

Description

[Cameron McCormack (:heycam)]

Comparing CustomPropertiesMap objects for equality during CalcStyleDifference can be expensive when there are many custom properties.  In lieu of making that process quicker, we could cache the results of the equality check (keyed off the pointer values of the CustomPropertiesMap objects).  We would make good use of the cached results in cases where we have many elements in a subtree that point to the same ComputedPropertiesMap object (which after https://github.com/servo/servo/pull/18803 is more likely).

This drops the total time spent under compute_style_difference in the YouTube page load from 405 ms to 151 ms, and the long style flush times towards the end of the page load down from 190 ms to 160 ms.

Comment 1

[Cameron McCormack (:heycam)]

Attachment: Bug 1407246 - Split out Variables struct difference calculation.

Review commit: https://reviewboard.mozilla.org/r/188022/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/188022/

Comment 2

[Cameron McCormack (:heycam)]

Attachment: style: Skip custom properties comparison if other inherited properties changed.

Review commit: https://reviewboard.mozilla.org/r/188024/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/188024/

Comment 3

[Cameron McCormack (:heycam)]

Basically, f? on these patches.  It's not super nice passing this RuleCache object all the way down into compute_style_difference, and really I should probably break it out into a separate object instead of hanging off RuleCache.

Comment 4

[Emilio Cobos Álvarez (:emilio)]

(In reply to Cameron McCormack (:heycam) from comment #0)
> Comparing CustomPropertiesMap objects for equality during
> CalcStyleDifference can be expensive when there are many custom properties. 
> In lieu of making that process quicker, we could cache the results of the
> equality check (keyed off the pointer values of the CustomPropertiesMap
> objects).  We would make good use of the cached results in cases where we
> have many elements in a subtree that point to the same ComputedPropertiesMap
> object (which after https://github.com/servo/servo/pull/18803 is more
> likely).

This is only true in the case they're (almost) equal, right? I suspect the first patch in https://github.com/servo/servo/pull/18803, plus https://github.com/servo/servo/pull/18793 (which I guess you should land eventually? :P) should make this not matter enough for the youtube case.

In particular, I profiled today with my patches plus yours, and with the diagnostic hashmap stuff removed, and the overhead from style::custom_properties::* was reduced immensely.

> This drops the total time spent under compute_style_difference in the
> YouTube page load from 405 ms to 151 ms, and the long style flush times
> towards the end of the page load down from 190 ms to 160 ms.

Is it more due to the first one (for anon boxes?) or the second one? Is this with your other patches applied?

(In reply to Cameron McCormack (:heycam) from comment #3)
> Basically, f? on these patches.  It's not super nice passing this RuleCache
> object all the way down into compute_style_difference, and really I should
> probably break it out into a separate object instead of hanging off
> RuleCache.

The first patch looks fine to me I guess, but the second one doesn't look great, and I'd be somewhat hesitant to merge it. If we don't have other ideas, I guess it's ok, but it looks somewhat out of band. Not sure if you agree with me, but I'd like to avoid as many out-of-band caches as possible...

It occurs to me that we can optimize this in a more self-contained way, too. In particular, right now comparing an OrderedMap requires comparing both the index and the values, but assuming the invariants hold, comparing only the values should be ok.

Also, there's no need to compare custom properties if the inherited style has already changed, which is a one-line change to your first patch.

ni? for the multiple questions around

Comment 5

[Emilio Cobos Álvarez (:emilio)]

(In reply to Emilio Cobos Álvarez [:emilio] from comment #4)
> It occurs to me that we can optimize this in a more self-contained way, too.
> In particular, right now comparing an OrderedMap requires comparing both the
> index and the values, but assuming the invariants hold, comparing only the
> values should be ok.

After a bit more thought I think this should be observable (I suspect it wouldn't go against the spec though), since HashMap order is unpredictable, but we could compare the index _after_ the values, at least.

But also we could add a fast path to a data-structure like https://github.com/bluss/ordermap/. The semantics of that OrderMap::eq are "same keys and values", but if we also care "same order", we can add an optimized method to do that that doesn't even need to do any hashing, and it'd remove pretty much all the overhead of the hashmap comparison. wdyt?

Comment 6

[Emilio Cobos Álvarez (:emilio)]

Of course that one needs to wait for the diagnostic stuff to go away and such, but...

Comment 7

[Emilio Cobos Álvarez (:emilio)]

In particular, this is a profile on current nightly (without the diagnostic stuff removed), on the new design of Youtube in: https://www.youtube.com/feed/subscriptions, for an account with 138 subscriptions:

  https://perfht.ml/2xx5PcS

You're getting rid of all the CustomPropertiesEqual on the post-traversal with the first patch, and in this profile the pageload doesn't look slower than Chromium, nor unresponsive, so I'd be hesitant to land that extra cache...

Comment 8

[Cameron McCormack (:heycam)]

(In reply to Emilio Cobos Álvarez [:emilio] from comment #4)
> This is only true in the case they're (almost) equal, right? I suspect the
> first patch in https://github.com/servo/servo/pull/18803, plus
> https://github.com/servo/servo/pull/18793 (which I guess you should land
> eventually? :P) should make this not matter enough for the youtube case.

That's right that this helps when they're almost equal.  That does seem to be a pattern that the page is using, i.e. changing one out of the ~150 custom properties that are set on an element.  I had both of those PRs applied when doing my measurements with this patch.

> In particular, I profiled today with my patches plus yours, and with the
> diagnostic hashmap stuff removed, and the overhead from
> style::custom_properties::* was reduced immensely.

Yeah, I did notice that the amount of work corresponding to custom properties stuff was greatly reduced, even before this patch.

> > This drops the total time spent under compute_style_difference in the
> > YouTube page load from 405 ms to 151 ms, and the long style flush times
> > towards the end of the page load down from 190 ms to 160 ms.
> 
> Is it more due to the first one (for anon boxes?) or the second one? Is this
> with your other patches applied?

I only measured with the two patches in this bug applied together.

> (In reply to Cameron McCormack (:heycam) from comment #3)
> > Basically, f? on these patches.  It's not super nice passing this RuleCache
> > object all the way down into compute_style_difference, and really I should
> > probably break it out into a separate object instead of hanging off
> > RuleCache.
> 
> The first patch looks fine to me I guess, but the second one doesn't look
> great, and I'd be somewhat hesitant to merge it. If we don't have other
> ideas, I guess it's ok, but it looks somewhat out of band. Not sure if you
> agree with me, but I'd like to avoid as many out-of-band caches as
> possible...

Yeah, I didn't really like it either. :-)

> It occurs to me that we can optimize this in a more self-contained way, too.
> In particular, right now comparing an OrderedMap requires comparing both the
> index and the values, but assuming the invariants hold, comparing only the
> values should be ok.

Hmm, I guess you are right that the order in the map doesn't really matter.

> Also, there's no need to compare custom properties if the inherited style
> has already changed, which is a one-line change to your first patch.

Good point. :-)

Comment 9

[Cameron McCormack (:heycam)]

Comment on attachment 8916990 [details]
Bug 1407246 - Split out Variables struct difference calculation.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/188022/diff/1-2/

Comment 10

[Cameron McCormack (:heycam)]

Comment on attachment 8916991 [details]
style: Skip custom properties comparison if other inherited properties changed.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/188024/diff/1-2/

Comment 11

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8916990 [details]
Bug 1407246 - Split out Variables struct difference calculation.

https://reviewboard.mozilla.org/r/188022/#review193828

::: layout/style/ServoBindings.cpp:404
(Diff revision 2)
>    nsChangeHint result = const_cast<ServoStyleContext*>(aOldStyle)->
>      CalcStyleDifference(
>        const_cast<ServoStyleContext*>(aNewStyle),
>        &equalStructs,
>        &samePointerStructs,
> -      NS_STYLE_INHERIT_MASK);
> +      /* aIgnoreVariables = */ true);

This patch should have something comparing the variables on the caller or similar. But you'd need to split it anyway, soo...

Comment 12

[Emilio Cobos Álvarez (:emilio)]

Comment on attachment 8916991 [details]
style: Skip custom properties comparison if other inherited properties changed.

https://reviewboard.mozilla.org/r/188024/#review193826

::: servo/components/style/gecko/restyle_damage.rs:60
(Diff revision 2)
>                  new_style,
>                  &mut any_style_changed,
>                  &mut reset_only,
>              )
>          };
> +        if reset_only {

feel free to merge these two conditions if you want in the same `if` condition, I don't think it affects the intent of the comment that much.

Comment 13

[Cameron McCormack (:heycam)]

Comment on attachment 8916990 [details]
Bug 1407246 - Split out Variables struct difference calculation.

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/188022/diff/2-3/

Comment 14

[Cameron McCormack (:heycam)]

Attachment: Servo PR

Comment 15

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/4cc45d7c8caf
Split out Variables struct difference calculation. r=emilio

Comment 16

[Sebastian Hengst [:aryx] (needinfo me if it's about an intermittent or backout)]

https://hg.mozilla.org/mozilla-central/rev/4cc45d7c8caf

Comment 17

[Ryan VanderMeulen [:RyanVM]]

Marking this 57:wontfix based on bug 1405411 comment 56.