Combine element hiding selector matching with style sheet generation

[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.

Hints for testers

Make sure that element hiding works correctly.

For things to test specifically:

• Add a filter for example.com, for example example.com##h1, then load example.com and see that the filter is applied (the element should be hidden and the DevTools panel should show the filter hit)
• Remove the filter just added, then reload the page and see that the filer is no longer applied
• Try the previous two steps again, but this time with a generic filter ##h1 (with no domain)
• Add the generic filter ##h1, then see that the h1 element is hidden, then add an exception example.com#@#h1, then see that h1 element on example.com is not hidden (but should be hidden on any other domain), then remove the exception and see that the h1 element on example.com is hidden too
• Remove all filters, then add the filter com,~example.com##h1 and see that the h1 element on example.com is not hidden (but should be hidden on any other .com domain)
• Remove all filters, then add the filter ##h1 (no domain), then add the exception com,~example.com#@#h1 and see that the h1 element is hidden on example.com but not on any other .com domain (but should also be hidden on any other TLDs like .org, .net , and so on)
• Remove all filters, then add the filter ~example.com##h1 and see that the h1 element is hidden on all domains other than example.com

This should be enough.

Also see #6999.

[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.

[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?

[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.

[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.

[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.

[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.

[abpbot]

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

[abpbot]

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

[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.

[abpbot]

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

[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

[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.

[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).

[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)).

[abpbot]

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

[abpbot]

Some commits referencing this issue have landed:

• ​Issue 6957 - Add generateStyleSheetForDomain function to ElemHide module
• ​Issue 6957 - Return common style sheet for unknown domains
• ​Issue 6957 - Skip selector lookup for unknown domains
• ​Issue 6957 - Add rulesFromStyleSheet function to ElemHide module