1382319 - ABP causes us to spend 5x more time in selector matching on obama wikipedia page

Status: NEW

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

Description

[Bobby Holley (:bholley)]

I just noticed this. I know that ABP uses CSS to hide pages, but 5x seems like a bit much.

This is not specific to stylo, though stylo does improve the situation quite a bit.

URL: https://en.wikipedia.org/wiki/Barack_Obama

Profiles:
Gecko without ABP: https://perfht.ml/2vjUZat (637 ms)
Gecko with ABP: https://perfht.ml/2vkiGiU (2466 ms)
Stylo without ABP: https://perfht.ml/2vjOjcs (88 ms)
Stylo with ABP: https://perfht.ml/2vk3vWU (357 ms)

Note: styling time for stylo is time spent under Servo_TraverseSubtree. Styling time for gecko is time spent under ResolveStyleFor + WalkRuleTree + PseudoElementStyle. ResolveStyleFor corresponds to the bulk of selector matching, and that's the one we see blowing up - the second and third are unchanged with/without ABP.

The issue is exacerbated by the fact that we seem to style the entire document several times. I filed bug 1382311 for that.

Comment 1

[Bobby Holley (:bholley)]

bz pointed me to bug 988266#c20, so this is perhaps a known issue, but it does seem like the rulehash should be able to fast-reject all those id and class selectors, unless the hashmap is overloaded and performing badly, or unless some of them actually match on wikipedia.

Comment 2

[Boris Zbarsky [:bzbarsky]]

Attachment: Easylist (default filter) file as of today

Comment 3

[Boris Zbarsky [:bzbarsky]]

Attachment: Just the "slow" selectors from that file

I got this by doing:

grep "^##" easylist.txt | sed 's/^##//' | grep -v "^[.]" | grep -v "^#" > filtered.txt

Comment 4

[Boris Zbarsky [:bzbarsky]]

OK, so there are 18420 total CSS rules that apply to all sites (lines starting with "##").  Of those, 10038 start with a '.' and hence should be rejectable by either the rulehash or the bloom filter.  7957 start with '#' and should be rejectable for the same reason.

Note that if the bloom rejection fails some of these could be moderately slow to match.

Anyway, the remaining 425 rules are attached.  A bunch of them involve tag names, but those are mostly "a" or "div", which are common anyway.  And the Wikipedia page has a _lot_ of <a> elements.

In fact, 353 of the rules have the form:

  a[href.....]

with lots of "a[href^=whatever]" (339), a few "a[href*=whatever]" (13), and one "a[href$='/vghd.shtml']".  So at the very least, for every <a> on the page (4866 elements as of today on the Obama wikipedia page) we are going to match it against all those selectors.  Oh, and the style sharing cache won't help with that part, since these are all revalidation selectors.

Not surprisingly, the Gecko profile shows the GetAttr to get the href attribute, prefix matches, etc, etc, taking up quite a large chunk of the time in the "with abp" profile.

Comment 5

[Bobby Holley (:bholley)]

I believe there may not be too much more we can do here beyond "make styling even cheaper by continuing to optimize stylo". Boris, does that match your recollection, or was there any followup investigation required?

Comment 6

[Boris Zbarsky [:bzbarsky]]

That's pretty much correct, yes.  We could try to do things like [href^=foo] in-place instead of doing GetAttr.

I guess another thing we might be able to do for cases like this with tons of revalidation selectors is to stop matching revalidation selectors as soon as we detect a mismatch.  But given the caching of revalidation matching results we do, that's a bit annoying to implement...

Comment 7

[Daniel Holbert [:dholbert]]

(In reply to Bobby Holley (:bholley) (busy with Stylo) from comment #5)
> I believe there may not be too much more we can do here beyond "make styling
> even cheaper by continuing to optimize stylo".

Sounds like this shouldn't be qf:p1 then.  Bumping to p3.

Comment 8

[Daniel Holbert [:dholbert]]

Per comment 5 - comment 6, sounds like there's no specific low-risk-and-backportable fix that we could uplift to 57 for this -- so, let's call this wontfix for 57.

(Also: fortunately, the badness is limited as long as stylo is enabled, as shown by measurements in comment 0. So, this doesn't seem severe enough to worry about for 57.)