Opened on 03/31/2014 at 07:17:28 AM

Closed on 05/20/2016 at 03:14:18 PM

#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):

Description (last modified by kzar)


Migrating 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 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 would set ElemHide.filtersByDomain[""][""] to true. Adding ##foo would set ElemHide.filtersByDomain[""]["##foo"] to true. Adding would set ElemHide.filtersByDomain[""][] to false and ElemHide.filtersByDomain[""][] to true. Then ElemHide.getSelectorsByDomain() could go through ElemHide.filtersByDomain similarly to how ActiveFilter.isActiveOnDomain() does it with

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.

Attachments (0)

Change History (28)

comment:1 Changed on 04/01/2014 at 09:06:53 PM by mapx

  • Cc added

comment:2 Changed on 05/20/2014 at 06:09:07 AM by trev

  • Blocking 524 added

comment:3 Changed on 07/09/2014 at 12:38:11 PM by philll

  • Platform set to Firefox

comment:4 Changed on 07/09/2014 at 01:13:29 PM by philll

  • Platform changed from Firefox to Unknown

comment:5 Changed on 12/16/2014 at 11:54:57 AM by greiner

  • Cc greiner added

comment:6 Changed on 01/06/2015 at 09:59:04 AM by greiner

  • Owner set to greiner

comment:7 Changed on 01/06/2015 at 10:01:29 AM by mapx

  • Cc mapx added; removed

comment:8 Changed on 01/12/2015 at 09:31:44 PM 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.


comment:9 Changed on 01/22/2015 at 01:02:57 PM by greiner

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

comment:10 Changed on 04/27/2015 at 04:43:07 PM by greiner

  • Blocking 2392 added

comment:11 Changed on 07/24/2015 at 04:35:21 PM 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 on 07/24/2015 at 04:36:16 PM by greiner

comment:12 Changed on 11/30/2015 at 03:24:33 PM by greiner

  • Blocking 2392 removed

comment:13 Changed on 02/04/2016 at 11:39:39 AM by trev

  • Priority changed from P2 to P3

Not blocking anything, back to P3.

comment:14 Changed on 05/11/2016 at 10:18:04 PM by kzar

  • Owner changed from greiner to kzar

comment:15 Changed on 05/16/2016 at 08:29:53 PM by kzar

  • Review URL(s) modified (diff)

comment:16 Changed on 05/18/2016 at 04:00:26 PM by abpbot

A commit referencing this issue has landed:

comment:17 Changed on 05/18/2016 at 04:08:37 PM by kzar

  • Description modified (diff)

comment:18 Changed on 05/18/2016 at 04:09:15 PM by kzar

  • Description modified (diff)

comment:19 Changed on 05/18/2016 at 04:14:27 PM by kzar

  • Review URL(s) modified (diff)

comment:20 Changed on 05/18/2016 at 04:29:00 PM by abpbot

A commit referencing this issue has landed:

comment:21 Changed on 05/18/2016 at 04:32:07 PM 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 on 05/19/2016 at 02:24:02 PM 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 (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 ( After #235 ( 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)


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)

I got these (kind of surprising) results:

Before #235 ( After #235 ( 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 on 05/19/2016 at 03:19:16 PM by kzar

comment:23 Changed on 05/19/2016 at 03:32:31 PM by sebastian

I profiled following loop on Chrome 51:

for (var i = 0; i < 100; i++)

And with 3.6s are spent in getSelectorsByDomain() (total aggregated time), and with Object.keys() its 3.9s, implying that 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 on 05/19/2016 at 04:29:18 PM by sebastian

comment:24 Changed on 05/20/2016 at 05:57:28 AM by kzar

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

comment:25 Changed on 05/20/2016 at 05:57:44 AM by kzar

  • Status changed from reopened to reviewing

comment:26 Changed on 05/20/2016 at 06:01:04 AM 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)

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

Interested to hear what you guys think anyway.

comment:27 Changed on 05/20/2016 at 11:45:02 AM 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 on 05/20/2016 at 03:14:18 PM 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.

Add Comment

Modify Ticket

Change Properties
as closed .
The resolution will be deleted. Next status will be 'reopened'.
to The owner will be changed from kzar.
Note: See TracTickets for help on using tickets.