Opened 14 months ago

Last modified 9 months ago

#6957 closed change

Combine element hiding selector matching with style sheet generation — at Version 24

Reported by: mjethani Assignee: mjethani
Priority: P3 Milestone:
Module: Core Keywords:
Cc: jsonesen, hfiguiere, sebastian Blocked By: #6956
Blocking: #7000 Platform: Unknown / Cross platform
Ready: yes Confidential: no
Tester: Unknown Verified working: no
Review URL(s):

https://codereview.adblockplus.org/29886555/
https://codereview.adblockplus.org/29893618/
https://codereview.adblockplus.org/29893628/
https://codereview.adblockplus.org/29897558/

Description (last modified by mjethani)

Background

After #6956, it will be possible for core to generate the style sheet on its own. In order to optimize style sheet generation in practice, it could be combined with the code for looking up selectors for a domain. The "default" style sheet, based on the list of "unconditional" selectors, would have to be generated only once and cached. Then each call to the style sheet generation code would only have to generate a second style sheet, based on some ~1,000 selectors that don't apply to all domains, and concatenate it with the default style sheet.

This would make the combination of selector lookup and style sheet generation much faster. It might also have benefits for memory usage, though this may no longer be a concern after #6967.

What to change

In lib/elemHide.js, add a new generateStyleSheetForDomain function that performs the same task as getSelectorsForDomain but also returns a generated style sheet (CSS code to be injected directly into the document). This function should generate the default style sheet, based on the list of "unconditional" selectors, only once and then always use the cached value for subsequent calls.

The cached default style sheet should be invalidated when the set of filters is updated.

Change History (24)

comment:1 Changed 14 months ago by mjethani

  • Blocked By 6956 added
  • Cc jsonesen hfiguiere added
  • Description modified (diff)
  • Ready set
  • Review URL(s) modified (diff)
  • Summary changed from Return cached string object for unconditional style sheet to Combine element hiding selector matching with style sheet generation

comment:2 Changed 14 months ago by mjethani

  • Owner set to mjethani

comment:3 Changed 14 months ago by mjethani

  • Status changed from new to reviewing

comment:4 Changed 14 months ago by mjethani

  • Cc sebastian added

comment:5 Changed 14 months ago by mjethani

@sebastian what do you think about this idea?

The ElemHide module could return the style sheet along with the selectors. Internally it would have a cached "default" style sheet (see patch), based on the list of selectors that are applied unconditionally on all domains. This would slow down the selector lookup slightly, but this would be more than offset by the fact that the extension wouldn't have to generate the style sheet separately.

The only downside is that this would be a performance hit for platforms that don't support user style sheets, but the extension could just call the old getSelectorsForDomain instead on those platforms.

Last edited 14 months ago by mjethani (previous) (diff)

comment:6 follow-up: Changed 14 months ago by sebastian

In order to tell whether this is a good idea we should compare the complexity added, performance gain and memory usage after the change.

At the current point I don't see yet how it might improve the memory usage, but would rather assume that the caching will add up to the memory footprint?

How would that make things worse than it's now on platforms that don't support user stylesheets?

Can you specify the cache invalidation? I assume we'd regenerate the stylesheet text for the unconditional element hiding rules every time element hiding filters are added/removed/disabled/enabled. What performance implications do you expect this to have on filter changes?

comment:7 in reply to: ↑ 6 Changed 14 months ago by mjethani

Replying to sebastian:

At the current point I don't see yet how it might improve the memory usage, but would rather assume that the caching will add up to the memory footprint?

After #6967, it won't help with the memory usage. It should instead add ~600 KB to the footprint.

How would that make things worse than it's now on platforms that don't support user stylesheets?

The additional cost here would be the cost of generating the style sheet for about ~1,500 selectors.

On platforms that do support user style sheets, this is a net gain, because the extension doesn't have to generate the style sheet at all.

Can you specify the cache invalidation? I assume we'd regenerate the stylesheet text for the unconditional element hiding rules every time element hiding filters are added/removed/disabled/enabled. What performance implications do you expect this to have on filter changes?

Filters are added all in the beginning when the extension is loaded, before the style sheet is ever generated, or when a new copy of a subscription is downloaded. Invalidating the style sheet should be similar to the invalidation of the "unconditional" selectors, which also happens when the current set of filters is modified. We're setting one variable to null, now we have to set two variables to null. I don't expect this to have any impact on performance.

comment:8 Changed 14 months ago by mjethani

  • Priority changed from P2 to P3

comment:9 follow-up: Changed 14 months ago by sebastian

Microsoft Edge (the only WebExtension platform that doesn't support user stylesheets) doesn't support Shadow DOM v0 either (and never will since it has been superseded by Shadow DOM v1 which is useless for our purpose). That said we could now get rid of the whole logic injecting stylesheets in Shadow DOM altogether. Also this means the same CSS we inject as a user stylesheet on modern versions of Chrome and Firefox, could just be injected as-is into an author stylesheet in Microsoft Edge (and consequently older versions of Chrome and Firefox). Maybe I miss something, but otherwise it seems to me that browsers that don't support user stylesheets could benefit from this change in the same way.

comment:10 in reply to: ↑ 9 ; follow-up: Changed 14 months ago by mjethani

Replying to sebastian:

Microsoft Edge (the only WebExtension platform that doesn't support user stylesheets) doesn't support Shadow DOM v0 either (and never will since it has been superseded by Shadow DOM v1 which is useless for our purpose). That said we could now get rid of the whole logic injecting stylesheets in Shadow DOM altogether. Also this means the same CSS we inject as a user stylesheet on modern versions of Chrome and Firefox, could just be injected as-is into an author stylesheet in Microsoft Edge (and consequently older versions of Chrome and Firefox). Maybe I miss something, but otherwise it seems to me that browsers that don't support user stylesheets could benefit from this change in the same way.

Yes, the only question is the cost of transmitting a 660 KB style sheet from the background page to the content script. This would be in addition to the list of selectors (which is also needed).

If you mean that we should use tabs.insertCSS on Edge without the cssOrigin option, that's fine. In that case, I guess we get rid of all the style sheet logic in the content script. It sounds like a good idea to me.

Last edited 14 months ago by mjethani (previous) (diff)

comment:11 in reply to: ↑ 10 Changed 14 months ago by sebastian

Replying to mjethani:

If you mean that we should use tabs.insertCSS on Edge without the cssOrigin option, that's fine. In that case, I guess we get rid of all the style sheet logic in the content script. It sounds like a good idea to me.

Agreed, let's do that.

comment:12 Changed 14 months ago by abpbot

comment:13 Changed 14 months ago by mjethani

  • Review URL(s) modified (diff)

comment:14 Changed 14 months ago by mjethani

  • Review URL(s) modified (diff)

comment:15 Changed 14 months ago by abpbot

A commit referencing this issue has landed:
Issue 6957 - Return common style sheet for unknown domains

comment:16 follow-up: Changed 14 months ago by mjethani

To test out the performance of the last patch, I exported the ElemHide and Filter objects globally, reloaded the extension, and pasted the following into the background page console:

Promise.resolve().then(() =>
{
  let filters = [...Filter.knownFilters.values()]
                .filter(f => f.type == "elemhide" ||
                             f.type == "elemhideexception");
  let domains = new Set(filters.reduce(
    (a, f) => a.concat(f.domains ? [...f.domains.keys()].filter(d => !!d) : []),
    []
  ));

  console.log(`${domains.size} known domains`);

  let totalTime = 0;

  for (let domain of domains)
  {
    let startTime = performance.now();
    ElemHide.generateStyleSheetForDomain(domain, false);
    totalTime += performance.now() - startTime;
  }

  console.log("total time:", totalTime);

  console.log(`${domains.size} unknown domains`);

  let unknownDomain = "www." + Math.random().toString(36).substring(2) + ".com";

  totalTime = 0;

  for (let i = 0; i < domains.size; i++)
  {
    let startTime = performance.now();
    ElemHide.generateStyleSheetForDomain(unknownDomain, false);
    totalTime += performance.now() - startTime;
  }

  console.log("total time:", totalTime);
});

As I had expected, before applying the patch, the performance for both known and unknown domains is comparable; after applying the patch, while the performance for known domains is comparable to before, for unknown domains it is twice as fast.

comment:17 Changed 14 months ago by abpbot

A commit referencing this issue has landed:
Issue 6957 - Skip selector lookup for unknown domains

comment:18 in reply to: ↑ 16 ; follow-up: Changed 14 months ago by mjethani

Replying to mjethani:

To test out the performance of the last patch, I exported the ElemHide and Filter objects globally, reloaded the extension, and pasted the following into the background page [console:

[...]

I ran the test again after applying the third patch.

Before the third patch:

19847 known domains
total time: 19036.100001540035
19847 unknown domains
total time: 9504.100004211068

After the third patch:

19847 known domains
total time: 14159.499996807426
19847 unknown domains
total time: 24.69999808818102

comment:19 in reply to: ↑ 18 Changed 14 months ago by mjethani

Replying to mjethani:

[...]

After the third patch:

19847 known domains
total time: 14159.499996807426
19847 unknown domains
total time: 24.69999808818102

Now to compare this with the original ElemHide.getSelectorsForDomain followed by createStyleSheet:

19847 known domains
total time: 49213.59999803826
19847 unknown domains
total time: 29677.100003231317

In short, it's about thrice as fast for domains occurring in EasyList+AA (or whatever lists the user is subscribed to), and more than a thousand times as fast for any other random domain.

For EasyList+AA, we end up adding ~1.5 MB to the memory footprint.

comment:20 Changed 14 months ago by sebastian

Just in case which browsers / browser versions did you benchmark on? But assuming we get similar performance improvements on the current stable version of Firefox and Chrome (for a similar memory tradeoff), this looks good to me. Another 1.5M isn't much compared to our overall memory usage, but the performance improvement seems to be significant (considering that element hiding filters are applied for every single document).

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

comment:21 Changed 14 months ago by mjethani

I was developing against Google Chrome Canary, but the changes here are logical and not micro-optimizations targeting any specific VM. I would not expect much of a difference between the different browsers. If there are specific issues on other browsers, we can optimize for those separately (the logic would not change, only how we do things (#6989)).

comment:22 Changed 14 months ago by mjethani

  • Blocking 7000 added

comment:23 Changed 14 months ago by abpbot

A commit referencing this issue has landed:
Issue 6957 - Add rulesFromStyleSheet function to ElemHide module

comment:24 Changed 14 months ago by mjethani

  • Review URL(s) modified (diff)
Note: See TracTickets for help on using tickets.