Opened 4 years ago

Closed 17 months ago

#235 closed change (fixed)

Performance of ElemHide.getSelectorsByDomain() needs to be improved

Reported by: trev Assignee: kzar
Priority: P3 Milestone: Adblock-Plus-1.12-for-Chrome-Opera-Safari
Module: Core Keywords:
Cc: greiner, mapx, Ross, scheer, sebastian Blocked By:
Blocking: #524 Platform: Unknown
Ready: yes Confidential: no
Tester: Unknown Verified working: no
Review URL(s):

http://codereview.adblockplus.org/4529242486341632/
https://codereview.adblockplus.org/29341426/
https://codereview.adblockplus.org/29342798/

Description (last modified by kzar)

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.

Change History (28)

comment:1 Changed 4 years ago by mapx

  • Cc smultron45@… added

comment:2 Changed 3 years ago by trev

  • Blocking 524 added

comment:3 Changed 3 years ago by philll

  • Platform set to Firefox

comment:4 Changed 3 years ago by philll

  • Platform changed from Firefox to Unknown

comment:5 Changed 3 years ago by greiner

  • Cc greiner added

comment:6 Changed 3 years ago by greiner

  • Owner set to greiner

comment:7 Changed 3 years ago by mapx

  • Cc mapx added; smultron45@… removed

comment:8 Changed 3 years ago by 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

comment:9 Changed 3 years ago by greiner

  • Review URL(s) modified (diff)
  • Status changed from new to reviewing

comment:10 Changed 2 years ago by greiner

  • Blocking 2392 added

comment:11 Changed 2 years ago by greiner

  • Priority changed from P3 to P2
  • Tester set to Unknown

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

Last edited 2 years ago by greiner (previous) (diff)

comment:12 Changed 23 months ago by greiner

  • Blocking 2392 removed

comment:13 Changed 21 months ago by trev

  • Priority changed from P2 to P3

Not blocking anything, back to P3.

comment:14 Changed 18 months ago by kzar

  • Owner changed from greiner to kzar

comment:15 Changed 17 months ago by kzar

  • Review URL(s) modified (diff)

comment:16 Changed 17 months ago by abpbot

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

comment:17 Changed 17 months ago by kzar

  • Description modified (diff)

comment:18 Changed 17 months ago by kzar

  • Description modified (diff)

comment:19 Changed 17 months ago by kzar

  • Review URL(s) modified (diff)

comment:20 Changed 17 months ago by abpbot

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

comment:21 Changed 17 months ago by kzar

  • Cc Ross scheer added
  • Description modified (diff)
  • Milestone set to Adblock-Plus-for-Chrome-Opera-Safari-next
  • Resolution set to fixed
  • Status changed from reviewing to closed

comment:22 Changed 17 months ago by kzar

  • Cc sebastian added

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)
Last edited 17 months ago by kzar (previous) (diff)

comment:23 Changed 17 months ago by 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.

Last edited 17 months ago by sebastian (previous) (diff)

comment:24 Changed 17 months ago by kzar

  • Resolution fixed deleted
  • Review URL(s) modified (diff)
  • Status changed from closed to reopened

comment:25 Changed 17 months ago by kzar

  • Status changed from reopened to reviewing

comment:26 Changed 17 months ago by 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.

comment:27 Changed 17 months ago by 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.

comment:28 Changed 17 months ago by kzar

  • Resolution set to fixed
  • Review URL(s) modified (diff)
  • Status changed from reviewing to closed

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

Note: See TracTickets for help on using tickets.