Performance of ElemHide.getSelectorsByDomain() needs to be improved

[trev]

Background

Migrating ​https://github.com/adblockplus/adblockplus/pull/2 to our issue tracker: when a page loads in Chrome ElemHide.getSelectorsByDomain() is currently by far the most significant operation in our background page. According to Chrome's profiler this call takes up ~130ms on my machine, with ~50ms being spent in ActiveFilter.isActiveOnDomain(). The next item on the list is our webRequest handler which needs 20-30ms. Hello1024 who created the GitHub pull request even measured 285ms for ElemHide.getSelectorsByDomain() on his hardware. This function is really just a quick hack and not optimized for performance.

What to change

We need to optimize ElemHide.getSelectorsByDomain() somehow. The GitHub pull request proposes caching responses per domain which I would only consider as a last resort. Here is something else that should work as an optimization:

Currently each filter has its own ActiveFilter.domains property (computed on demand) that indicates which domains it is active on. Consequently, ElemHide.getSelectorsByDomain() has to iterate over all filters and call ActiveFilter.isActiveOnDomain() for each of them.

Instead ElemHide could maintain its own ElemHide.filtersByDomain map. This can be organized in such a way that adding example.com##foo would set ElemHide.filtersByDomain["example.com"]["example.com##foo"] to true. Adding ##foo would set ElemHide.filtersByDomain[""]["##foo"] to true. Adding ~example.com##foo would set ElemHide.filtersByDomain["example.com"][~example.com##foo] to false and ElemHide.filtersByDomain[""][~example.com##foo] to true. Then ElemHide.getSelectorsByDomain() could go through ElemHide.filtersByDomain similarly to how ActiveFilter.isActiveOnDomain() does it with ActiveFilter.domains.

Note that this entire additional data structure is unnecessary on Firefox where ElemHide.getSelectorsByDomain() is unused - so it needs to be skipped there in an efficient way.

To include the improvement in adblockpluschrome the adblockpluscore dependency also needs to updated from 6deffadd2643 to 719f4b374d89. This will also include several other commits, mostly irrelevant except ​Issue 3998 - cssProperties.js content script shouldn't assume that messaging will automatically know the context which will require further changes to accommodate.

Hints for testers

Ensure element hiding still works in Adblock Plus for Chrome, Opera and Safari as before.

[scali]

Hi there. I believe this is negatively affecting the performance of Hangouts on the web pretty severely, which is increasing the latency of opening new chat windows by 300ms in the best case, and 4+ seconds in the worse case. It's quite easy to reproduce. Log into gmail, opt into hangouts if you're not using hangouts in gmail already, and open a chat window, either from the roster or by composing a new one.

You should see a drop-shadow appear around an empty box, then some time later it fills with the actual chat UI. The time between these 2 occurrences is where we're seeing significant slowdown that disappears when AdBlockPlus is disabled. I'd be happy to provide more information if needed.

Thanks!
-Chris

[greiner]

Changed priority based on fhd's suggestion since it's blocking a roadmap item.

[trev]

Not blocking anything, back to P3.

[abpbot]

A commit referencing this issue has landed:
​https://hg.adblockplus.org/adblockpluscore/rev/6deffadd2643

[abpbot]

A commit referencing this issue has landed:
​https://hg.adblockplus.org/adblockpluschrome/rev/b7884247c8ed

[kzar]

Since Sebastian was concerned about performance of for ... in ..., especially in older versions of Chrome, I did some further testing of ElemHide.getSelectorsForDomain. For each revision of the code I opened ​http://www.extremetech.com/ (a pretty heavy website) and compared the CPU usage (in Top down mode) of ElemHide.getSelectorsForDomain.

Note: that the Chrome 40 tests were performed on a testing machine where as Chrome 50 tests were performed on my laptop directly. So you cannot compare CPU time directly between them, instead look at the relative difference between code revisions.

​Before #235 (1.11.0.1602)	​After #235 (1.11.0.1603)	​Removed for ... in (kzar/235-object-keys)
Chrome 40
(Self: 32 ms, Total: 156 ms)	(Self: 52 ms, Total: 90 ms)	(Self: 42 ms, Total: 71 ms)
Chrome 50
(Self: 478 ms, Total: 1299 ms)	(Self: 449 ms, Total: 598 ms)	(Self: 448 ms, Total: 604 ms)

Edit:

Did another batch of tests since Sebastian pointed out it might be better to just call the function from the console in a loop. Running this code:

for (var i = 0; i < 1000; i += 1)
  ElemHide.getSelectorsForDomain("www.extremetech.com");
1;

I got these (kind of surprising) results:

​Before #235 (1.11.0.1602)	​After #235 (1.11.0.1603)	​Removed for ... in (kzar/235-object-keys)
Chrome 40
(Self: 4085ms, Total: 9758ms)	(Self: 10425ms, Total: 12820ms)	(Self: 10054ms, Total: 11966ms)
Chrome 50
(Self: 14085ms, Total: 34036ms)	(Self: 27722ms, Total: 34526ms)	(Self: 25592ms, Total: 31892ms)

[sebastian]

I profiled following loop on Chrome 51:

for (var i = 0; i < 100; i++)
  ElemHide.getSelectorsForDomain("wikipedia.com");

And with for..in 3.6s are spent in getSelectorsByDomain() (total aggregated time), and with Object.keys() its 3.9s, implying that for..in is actually faster on modern Chrome versions. That seems to be in contract to your latest benchmark on Chrome 50, however.

But even weirder, in your latest benchmark Chrome 50, even performs better before the optimization, which I have a hard time to believe. So all in all that benchmark seems to be fishy.

[kzar]

I've reopened this issue since I thought of a new approach for the algorithm. It's possible I'm missing something but it seems > 3x faster for my test on Chrome 50.

for (var i = 0; i < 1000; i += 1)
  ElemHide.getSelectorsForDomain("www.extremetech.com");
1;

Before: Self: 26952ms, Total: 33371ms
After: Self: 3110ms, Total: 8852ms

Interested to hear what you guys think anyway.

[kzar]

So it turns out my new approach slows down the removal of filters quite a bit. I'm looking into ways around that as it seems to give a large speedup to getSelectorsForDomain.

Also in the process of working on this I realised we forgot to remove filters from the filtersByDomain lookup earlier and so I have opened issue #4054 for that regression.

[kzar]

At Sebastian's request I have split out work on this faster approach into a new issue #4057.