Implement fast selector lookups for most domains

[mjethani]

Background

We can make some further optimizations to ElemHide.getSelectorsForDomain that would speed up lookups by ~20x for most domains.

1. ElemHide.getSelectorsForDomain first creates a copy of the unconditionalSelectors array and then pushes each conditional selector to it. This is too slow, because the newly created copy is modified. Instead, it can populate a separate array with conditional selectors and then concatenate the two and return the result. This makes the code perform twice as fast on Chrome and about the same on Firefox.

2. ElemHide.getSelectorsForDomain does filter matching for every domain. This is not necessary; instead, it can do filter matching only for known domains (i.e. those that have filters that would apply to them). For any random domain like x4aabd7c0ddcd.com or manishjethani.com the lookups can be much, much faster, because there are no domain-specific filters that apply and no exceptions to check against (except for generic exceptions like #@#foo, which would still apply to ##foo on x4aabd7c0ddcd.com or manishjethani.com).

3. The same optimization also works for known domains that have no domain-specific exceptions for any generic filters. In EasyList+AA, out of 10,899 domains, 9,419 fall in this category (as of 12 May 2018).

In other words, ElemHide.getSelectorsForDomain can do faster lookups for all but 1,480 known domains.

4. Since the list of generic selectors that apply on most domains is the same, ElemHide.getSelectorsForDomain can cache this list and, for most domains, return the cached list concatenated with the generated list of domain-specific selectors.

What to change

1. In lib/elemHide.js in the ElemHide.getSelectorsForDomain function, populate a separate array with conditional selectors, then concatenate it with the unconditionalSelectors array and return the result.

Make ElemHide.getUnconditionalSelectors private to the module so it doesn't have to return a copy of unconditionalSelectors, as ElemHide.getSelectorsForDomain will make a copy anyway.

2. In the same function, find out if a domain is "known".

If there are two filters like ##foo and example.com#@#foo, then example.com, mail.example.com, and any other subdomains of example.com should be considered as known.

In order to make this work for exceptions as well (as in the preceding example), exception domains should be added to the filtersByDomain map as well, but only the domains, without any filters.

Furthermore, if an exception has no domains (generic exception), it should be added to a new genericExceptions map.

Finally, in ElemHide.getSelectorsForDomain, if a domain is not known, straightaway look up generic filters in the filtersByDomain map, and for each filter check if the selector exists in the genericExceptions map before adding the selector. Cache the result of this loop (~1,100 selectors in EasyList+AA, as of 12 May 2018) as a new conditionalGenericSelectors array and use the cached result on subsequent calls.

3. In the same function, if a domain is known but is found not to have any domain-specific exceptions for any generic filters, add the domain to a new genericFriendlyDomains set.

If a domain is found to be in the genericFriendlyDomains set (~9,500 out of ~11,000 domains in EasyList+AA, as of 12 May 2018), use the value of the conditionalGenericSelectors array instead of generating the list of generic selectors for the domain.

4. In general, write the code in a way that some of the functionality and related optimizations can be reused by other modules like ElemHideEmulation (see #6665) and Snippets (see #6538).

Resolution

The ideas here got implemented as part of #6957, #6989, and #7244.

[mjethani]

I feel like we should make this a meta issue and file separate issues for the specific changes. I also have more changes in mind that I haven't mentioned here, like efficient caching of the selectors for a known domain.

[kzar]

Well I think a meta issue is kinda overkill here and we've already had some other issues about improving the performance of this code. I don't think we need to cache selectors, since this code is already much faster than it was and will be faster still with your upcoming changes.

[mjethani]

Regarding caching, we could obviously cache the result of getConditionalGenericSelectors (similar to unconditionalSelectors now) since it's always the same every time it's called. It's also only about ~1,100 selectors with EasyList+AA.

If we cache that we can also use the same cached value for known domains that have no domain-specific exceptions for generic selectors, which should be most known domains. For such domains then ElemHide.getSelectorsForDomain will have the same performance as criteria = ElemHide.SPECIFIC_ONLY.

[abpbot]

A commit referencing this issue has landed:
​Issue 6652 - Do not push to unconditional selectors array

[kzar]

Fair enough, sorry I thought you were talking about caching the results of getSelectorForDomain which is something we decided against in the past.

[mjethani]

Adding the circumvention tag for management and tracking purposes.

I just realized that the speedups here would be beneficial in fighting circumvention, especially for snippets filters where we need to inject the JavaScript before the HTML document has a chance to execute any of its own code (especially in the case of API wrappers), since we're using tabs.executeScript on the webNavigation.onCommitted event. I intend to call into ElemHide for looking up snippets filters eventually.

[jsonesen]

@mjethani do you mind setting this to reviewing? makes it easier when querying for new issues to work on.