1339572 - uBlockOrigin's domWatcher can be too slow

Status: RESOLVED WONTFIX

(WebExtensions :: General, defect)

Description

[(no longer active)]

See this profile for example: <https://perfht.ml/2lh4cO3>

uBlockOrigin's contentscript.js has a domWather API that registers a mutation observer that watches the entire DOM.  This performs really badly with pages with heavy DOM operations.  For example the profile above is with the SpeedoMeter benchmark <http://browserbench.org/Speedometer/> which modifies the DOM heavily.

Comment 1

[u287251]

From what I can see in the profiling, this appears to be a duplicate of bug 1334263.

I filed performance bug 1338942 this week-end, which has been marked as duplicate of the above bug.

I've been reading the Firefox documentation on sandboxes and xray vision to see if I could muster a workaround until the root issue is fixed, but I found nothing so far. Suggestions welcomed.

Comment 2

[(no longer active)]

Yeah, our expando performance seems abysmal.  But it seems to me that we can also improve stuff in uBlockOrigin.  Unfortunately I don't know much about what your code does, I'm assuming that it's used when you want to replace something in the page as a fixup when an ad gets blocked?  A couple of suggestions that immediately come to my mind, assuming my understanding there is correct:

* Can we somehow restrict the part of the DOM tree that we need to watch?  For example, can we have a selector that describes the subtree where we expect to see the node in question?

* Can we coalesce the reactions to DOM changes?  For example by accumulating what we need to look at in an array and setting a timer to help process things with a bit of a delay.  That way if the page adds a node and quickly removes it from the page before the timer fires, we'd save the cost of looking at it.

It may also be a good idea to profile this on some more realistic pages since Speedometer is hardly a realistic use case.  I've been doing a lot of profiling these days and would be happy to report back in case something from uBlock Origin shows up on another page...

Comment 3

[u287251]

> But it seems to me that we can also improve stuff in uBlockOrigin.
> Unfortunately I don't know much about what your code does

The second sentence does not support the first one. It makes no sense to state that the performance can be improved without knowing how it works in the first place. What I had in mind when I asked for suggestions is if there was a way to use sandboxes without suffering the expando issues, but with my current understanding, it does not look possible.

That part of uBlock Origin has been developed with performance in mind since forever. I have often revisited (even re-factored) to micro-optimize whatever I thought can help and I do spend a good amount of time thinking about what could help. At this point, the only thing I manage to improve are micro-optimisations[1].

> Can we somehow restrict the part of the DOM tree that we need to watch?

No. uBO can't predict the future, it can't make any assumptions about which part of the DOM is going to change on any given web page.

In any case, the issue is not the MutationObserver, the issue is the survey code used to implement generic cosmetic filtering[2]. You can test for yourself by disabling generic cosmetic filters in the "3rd-party filters" pane and benchmarking again (you can also just toggle off cosmetic filtering from the popup). MutationObserver will still be used, and yet this remove the expando bottleneck.

One way to see this immediately is to benchmark page load speed of this page, as it contains lots of nodes with classes (using the tool linked in the footnotes): https://en.wikipedia.org/wiki/List_of_country_calling_codes

Try with and then without generic cosmetic filters, the difference is huge, and similarly the difference between of Chromium and Firefox *with* generic cosmetic filters enabled is also huge. Yet the MutationObserver is always present (it's also used to implement blocked element-collpasing).

> Can we coalesce the reactions to DOM changes?

It's already done this way since essentially the beginning. Coalescing is a common approach I have used throughout all of uBO, not just that one case.

As said, efficiency is priority in uBO, and there are other measures used to improve the handling of generic cosmetic filtering[3]. I do benchmark regularly what amount to "unfriendly" scenarios for uBO, and also including against other more popular blockers, and even with this expando issue, uBlock Origin performs pretty much always better than the other blockers.[4]

At this point, only fixing the expando issue is going to provide *significant* performance gains, and not only for uBO, but for the WebExtensions platform in general given that all content scripts will be executed from within sandboxes. I have squeezed uBO's content script code to the point where there is not really any performance "juice" left to extract.

The expando issue is not a small issue, this makes Firefox looks bad compared to Chromium when benchmarking the *exact* same content script code, which is more and more relevant given that developers are now able to import as-is most of their extension code to Firefox.

***

[1] For example, this recent commit to avoid using `Array.prototype.push` in favor of direct assignment: https://github.com/gorhill/uBlock/commit/28084e1dc9bbe4d615347c474aea64f8e2f1a193 The improvement is completely marginal, and will never be noticeable by users, but I still did it because it was not a risky change.

[2] Generic cosmetic filtering is disabled by default for Firefox for Android.

[3] For example, the generic cosmetic filtering surveyor code will toggle itself off for a web site if two conditions are met: 1) no new generic cosmetic filters have been found after repeatedly trying to find new ones AND 2) the cost of surveying for new generic cosmetic filters is beyond a specific threshold.

[4] Especially on Chromium-based browsers. Handy: http://www.raymondhill.net/ublock/pageloadspeed.html

Comment 4

[u287251]

> One way to see this immediately is to benchmark page load speed of this page, 
> as it contains lots of nodes with classes (using the tool linked in the footnotes): 
> https://en.wikipedia.org/wiki/List_of_country_calling_codes

I just ran a benchmark with generic cosmetic filtering enabled (the default) using Chrome 58 with and without uBO, and the difference is even smaller than I expected (~500ms vs ~460ms), which demonstrates that uBO's content script code is well optimized and does not add significant overhead to a web page -- keeping in mind that the benchmarked page is rather unfriendly to uBO because 1) large with many nodes with classes, 2) nothing to block hence nothing to gain back to offset cost.

Comment 5

[(no longer active)]

(In reply to R. Hill from comment #3)
> > But it seems to me that we can also improve stuff in uBlockOrigin.
> > Unfortunately I don't know much about what your code does
> 
> The second sentence does not support the first one. It makes no sense to
> state that the performance can be improved without knowing how it works in
> the first place. 

Sorry I didn't mean any disrespect, and also didn't mean to compare uBlock Origin's performance with any other extension.  I was merely trying to brainstorm.  I will refrain from doing that about uBlock Origin in the future.

> What I had in mind when I asked for suggestions is if there
> was a way to use sandboxes without suffering the expando issues, but with my
> current understanding, it does not look possible.

No that's not possible.  We should definitely make things faster on the Gecko side -- that will help with any extension that needs to access content nodes.

> That part of uBlock Origin has been developed with performance in mind since
> forever. I have often revisited (even re-factored) to micro-optimize
> whatever I thought can help and I do spend a good amount of time thinking
> about what could help. At this point, the only thing I manage to improve are
> micro-optimisations[1].

OK, makes sense.  Please ignore my suggestions.

> The expando issue is not a small issue, this makes Firefox looks bad
> compared to Chromium when benchmarking the *exact* same content script code,
> which is more and more relevant given that developers are now able to import
> as-is most of their extension code to Firefox.

Yes, I'm aware.  We're going to look into that soon I hope.

(In reply to R. Hill from comment #4)
> > One way to see this immediately is to benchmark page load speed of this page, 
> > as it contains lots of nodes with classes (using the tool linked in the footnotes): 
> > https://en.wikipedia.org/wiki/List_of_country_calling_codes

For the record, the page I noticed this on had a large amount of dynamic DOM mutations, not a lot of nodes at the same time which is a bit of a different performance profile.

Comment 6

[u287251]

> For the record, the page I noticed this on had a large amount of dynamic DOM mutations,
> not a lot of nodes at the same time which is a bit of a different performance profile.

Yes, agreed.

So I ran the <http://browserbench.org/Speedometer/> through various uBlock Origin configurations, and through Chromium 53 as a reference benchmark. Here are the results:

                             Ch    FF
                  Default:   65    28
    No cosmetic filtering:   72    32
              Whitelisted:   79    39
                   No uBO:   81    39

Ch: Chromium 53
FF: Firefox 51

uBO's configurations:
- "Default" means to use uBO with out-of-the-box settings.
- "No cosmetic filtering" is the disabling of cosmetic filtering for the site.
- "Whitelisted" is the disabling of uBO for the site.
- "No uBO" means the extension was disabled (and browser restarted to be sure).

uBO's configurations and what it entails:
-               Default: content script, mutation observer, DOM scanning
- No cosmetic filtering: content script, mutation observer
-           Whitelisted: content script

Comment 7

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Hi Raymond,
I got to thinking about this bug when I noticed that uBlock's content script adds a lot of overhead to a site I run [1]. It seems like a shame that uBlock has to use a content script to find all the elements that need to be hidden. My assumption is that this is just a big list of CSS selectors. We're in the process of improving the performance of CSS selector matching in Firefox [2] and it would be great if we could take advantage of those improvements for uBlock.

I know that AdBlock Plus does this sort of filtering by injecting a big CSS style sheet into every page and then basing its cosmetic filtering on that. The way it figures out which nodes matched is pretty awful, but I think we could improve that part. There also used to be memory usage problems with this approach, but they have been fixed [3]. Do you think this sort of approach would be worth exploring for uBlock?

[1] To see an example of a big page: http://searchfox.org/mozilla-central/source/dom/base/nsGlobalWindow.cpp
[2] https://wiki.mozilla.org/Quantum/Stylo
[3] https://bugzilla.mozilla.org/show_bug.cgi?id=988266

Comment 8

[u287251]

> I got to thinking about this bug when I noticed that uBlock's content script 
> adds a lot of overhead to a site I run [1].

Out of curiosity, I benchmarked page load speed for that page[1]. Results:

Firefox 51:
uBO w/    cosmetic filtering: Average (valid): 8059.77 ms (11/12 iterations)
uBO w/out cosmetic filtering: Average (valid): 6306.58 ms (11/13 iterations)
ABP                         : Average (valid): 6377.89 ms (11/12 iterations)
No blocker                  : Average (valid): 6219.97 ms (11/12 iterations)

Chromium 53:
uBO w/    cosmetic filtering: Average (valid): 11100.26 ms (11/15 iterations)
uBO w/out cosmetic filtering: Average (valid): 10799.86 ms (11/12 iterations)
ABP                         : Average (valid): 11068.01 ms (11/17 iterations)
No blocker                  : Average (valid): 10558.31 ms (11/17 iterations)

Interesting results. Firefox does much better than Chromium for that page. The overhead added by uBO DOM survey code is more significant with Firefox than it is with Chromium -- and likely explanation here is the expandos performance issue I suppose.

> There also used to be memory usage problems with this approach, but they have
> been fixed [3].

Not what I am currently observing. I ran the same sort of benchmark as I ran elsewhere for Chromium recently[2], which consists to open Twitter and slowly page-down two days worth of tweets. Results:

ABP:
915.40 MB (100.0%) -- explicit
├──465.60 MB (50.86%) -- layout
│  ├──465.05 MB (50.80%) ── rule-processor-cache
│  └────0.55 MB (00.06%) ── style-sheet-cache
├──238.22 MB (26.02%) -- window-objects
│  ├──235.40 MB (25.72%) ++ top(https://twitter.com/, id=4294967297)/active
│  └────2.82 MB (00.31%) ++ top(none)/detached/window(https://twitter.com/i/videos/live_video/807361386695135233?embed_source=clientlib&player_id=0&rpc_init=1)
├───98.08 MB (10.71%) ++ js-non-window
├───71.08 MB (07.76%) ── heap-unclassified
├───19.82 MB (02.17%) ++ heap-overhead
├───12.11 MB (01.32%) ++ images
└───10.49 MB (01.15%) ++ (15 tiny)

uBO:
419.59 MB (100.0%) -- explicit
├──277.63 MB (66.17%) -- window-objects/top(https://twitter.com/, id=4294967297)
├───56.15 MB (13.38%) ── heap-unclassified
├───43.28 MB (10.32%) ++ js-non-window
├───20.18 MB (04.81%) ++ heap-overhead
├───12.27 MB (02.93%) ++ images
└───10.08 MB (02.40%) ++ (16 tiny)

Before measuring, I clicked the sequence [gc, cc, miminize] three times, and I waiting for each operation to complete.

> Do you think this sort of approach would be worth exploring for uBlock?

I am completely opened to do whatever it takes to make uBO more efficient overall -- efficiency is a primary feature of uBO, and the choices I make are what benefit efficiency most overall (while being aware that it's always possible to find edge cases).

My current assessment and what benchmarking shows is that uBO's approach it still beneficial overall, for both Chromium and Firefox, despite the edge cases.

If ever the global stylesheet approach become beneficial overall, this would have to be done though in a way which does not force me to forfeit current uBO features:

- It is currently possible to toggle off/on cosmetic filtering for any given site with immediate visual feedback when toggled off. Would it be possible to disable the global stylesheet on a per-site basis without having to reload the page?

- Ability to support exception cosmetic filters on a per-site basis: how would that work with a global stylesheet? How to disable specific rules ("punch" holes) in the global sheet on a per-site basis?

- How to find and report which specific rules in the global stylesheet affects the current page? (If the selector of the CSS rules can be obtained, then 1) these can be reported in the logger, 2) the specific nodes being affected can be found with a simple querySelectorAll).


***

[1] http://www.raymondhill.net/ublock/pageloadspeed.html

[2] https://twitter.com/gorhill/status/831882026999492609, link to full image: https://pbs.twimg.com/media/C4tv3iEWQAE1WH4.jpg:large

Comment 9

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Thanks for the careful analysis! There are a lot of discussions going on to figure out how to improve our Xray performance (the expando issue you mentioned is one part of that). It seems like that would give us the most immediate benefit, although it's a big project. I'll also try to follow up on why memory usage is still so high for ABP. I was under the impression that it should be much better.

Can you give me any more details on your benchmark? I'd like to try to reproduce it, but I'm not a twitter user. Would I need to follow a lot of people in order to get a big feed?

Comment 10

[u287251]

> Can you give me any more details on your benchmark? I'd like to try to reproduce it, but I'm not a twitter user.

Try this link instead:
http://metalelf0.github.io/VimColorSchemeTest-Ruby/python.html

Results on my side with Nightly:

ABP:
792.63 MB (100.0%) -- explicit
├──631.47 MB (79.67%) ++ layout
├───94.71 MB (11.95%) ++ window-objects/top(http://metalelf0.github.io/VimColorSchemeTest-Ruby/python.html, id=4294967297)
├───32.68 MB (04.12%) ── heap-unclassified
├───13.86 MB (01.75%) ++ js-non-window
├───13.07 MB (01.65%) ++ heap-overhead
└────6.84 MB (00.86%) ++ (16 tiny)

uBO:
uBO:
126.02 MB (100.0%) -- explicit
├───56.54 MB (44.87%) ++ window-objects/top(http://metalelf0.github.io/VimColorSchemeTest-Ruby/python.html, id=4294967297)
├───31.62 MB (25.10%) ++ js-non-window
├───17.80 MB (14.13%) ++ heap-overhead
├───13.61 MB (10.80%) ── heap-unclassified
├────3.82 MB (03.03%) ++ (16 tiny)
└────2.62 MB (02.08%) ++ xpconnect

Comment 11

[Bill McCloskey [inactive unless it's an emergency] (:billm)]

Thanks very much. I was able to reproduce. That appears to be a regression since ABP 2.8 (filed as bug 1320872). The memory usage on the vim page goes down quite a bit with version 2.7.3. I'll try to figure out what changed in AdBlock that caused such a huge regression.

I'll also talk to the add-on team and style system teams about exposing this sort of functionality in a way that's easy for extension developers to use in a WebExtension. It seems like the memory usage thing is a fixable issue.

> If ever the global stylesheet approach become beneficial overall, this
> would have to be done though in a way which does not force me to forfeit
> current uBO features:
> 
> - It is currently possible to toggle off/on cosmetic filtering for any
> given site with immediate visual feedback when toggled off. Would it be
> possible to disable the global stylesheet on a per-site basis without having
> to reload the page?

My hope was that we would provide a JS API to find all the nodes on the page that matched. Then you could do whatever your existing content script does.

> - Ability to support exception cosmetic filters on a per-site basis: how would
> that work with a global stylesheet? How to disable specific rules ("punch" holes)
> in the global sheet on a per-site basis?

ABP 2.7 uses an @-moz-document rule for this purpose. It seems like they moved away from this in 2.8, and that somehow lead to the memory regression.

> - How to find and report which specific rules in the global stylesheet affects
> the current page? (If the selector of the CSS rules can be obtained, then 1) these
> can be reported in the logger, 2) the specific nodes being affected can be found
> with a simple querySelectorAll).

This one seems more difficult. I'll have to talk to a style system person to figure out what our range of options are.

Comment 12

[u287251]

I decided to run the same benchmark I ran in comment 18, but for Nightly and Chrome 59 -- both being dev build and representative of what is coming to the users. So for whatever it's worth, results:

Nightly 55.0a1 (2017-03-21):
uBO w/    cosmetic filtering: Average (valid): 5457.20 ms (11/14 iterations)
uBO w/out cosmetic filtering: Average (valid): 4485.96 ms (11/15 iterations)
ABP                         : Average (valid): 4546.08 ms (11/14 iterations)
No blocker                  : Average (valid): 4457.16 ms (11/12 iterations)

Chrome 59.0.3043.0:
uBO w/    cosmetic filtering: Average (valid): 3077.42 ms (11/13 iterations)
uBO w/out cosmetic filtering: Average (valid): 2877.24 ms (11/12 iterations)
ABP                         : Average (valid): 19231.48 ms (11/15 iterations)
No blocker                  : Average (valid): 2901.97 ms (11/13 iterations)

Comment 13

[u287251]

Ugh, I meant comment 8, not comment 18.

Comment 14

[u287251]

The main issue is that the jQuery portion of the benchmark (and to a lesser extent, the VanillaJS portion) causes a whole lot of mutations events to be constantly fired, amounting to 1000s of added distinct nodes. This will cause performance issue for any extension installing a mutation handler listening to changes in childList/subtree.

With a single javascript line of code in uBO's mutation handler[1], suddenly performance with uBO looked much better, I got a score of ~58 with uBO vs. ~63 without uBO.

But the benefit of that single line of javascript code would be solely for that one specific benchmark, which seems a silly thing to do, to optimize just for the sake of one specific benchmark with no connection to real world[2].

More details on mozillazine: http://forums.mozillazine.org/viewtopic.php?p=14758155#p14758155

[1] if ( addedNode.parentNode !== null ) {
[2] what web page out there constantly create an iframe, dynamically fills it with many 1000s of new DOM elements then immediately removes them all?

Comment 15

[u287251]

> one specific benchmark with no connection to real world

Just to be clear, the benchmark itself is useful to measure DOM manipulation performance, but when the benchmark is executed with an extension which uses a mutation observer for childList/subtree, the benchmark no longer measure what it's actually designed to measure, it ends up spuriously measuring mutation handler code with what amount to be an unrealistic scenario from the mutation handler code's point of view.

Comment 16

[Jorge Villalobos [:jorgev] (he/him)]

Mass-closing bugs that relate to legacy versions of add-ons or are otherwise no longer worth tracking. Please comment if you think this bug should be reopened.

Sorry for the bugspam. Made you look, though!