Issue 6652 - Implement fast selector lookups for unknown domains

lib/elemHide.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-present eyeo GmbH
  *
  * Adblock Plus is free software: you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 3 as
  * published by the Free Software Foundation.
  *
  * Adblock Plus is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 "use strict";
 
 /**
  * @fileOverview Element hiding implementation.
  */
 
 const {ElemHideException} = require("./filterClasses");
 const {FilterNotifier} = require("./filterNotifier");
 
 /**
  * Lookup table, active flag, by filter by domain.
  * (Only contains filters that aren't unconditionally matched for all domains.)
- * @type {Map.<string,Map.<Filter,boolean>>}
+ * @type {Map.<string,?Map.<Filter,boolean>>}
  */
 let filtersByDomain = new Map();
 
 /**
  * Lookup table, filter by selector. (Only used for selectors that are
  * unconditionally matched for all domains.)
  * @type {Map.<string,Filter>}
  */
 let filterBySelector = new Map();
 
@@ skipping 14 matching lines @@
  * @type {Set.<ElemHideBase>}
  */
 let knownFilters = new Set();
 
 /**
  * Lookup table, lists of element hiding exceptions by selector
  * @type {Map.<string,Filter>}
  */
 let exceptions = new Map();
 
+/*
+ * Set containing selectors with generic exceptions
+ * @type {Set.<string>}
+ */
+let genericExceptionSelectors = new Set();
+
+/*
+ * Checks if a domain is known
+ * @param {string} domain
+ * @returns {boolean}
+ */
+function isDomainKnown(domain)
+{
+  while (domain)
+  {
+    // A domain is "known" if we have seen any filters that would apply to it.
+    // For example, given the filters "##foo" and "example.com#@#foo",
+    // example.com is a known domain, as is mail.example.com and any other
+    // subdomains of example.com.
+    if (filtersByDomain.has(domain))
+      return true;
+
+    let nextDot = domain.indexOf(".");
+    domain = nextDot == -1 ? null : domain.substring(nextDot + 1);
+  }
+
+  return false;
+}
+
+/*
+ * Returns a list of selectors that apply on any unknown domain
+ * @returns {string[]}
+ */
+function getConditionalGenericSelectors()
+{
+  let selectors = [];
+
+  let filters = filtersByDomain.get("");
+  if (!filters)
+    return selectors;
+
+  for (let {selector} of filters.keys())
+  {
+    if (genericExceptionSelectors.size == 0 ||

[Manish Jethani, 2018/05/07 16:15:08]

Right now some selectors are disabled on all domains if AA is enabled. There's
no other way to do this. But in case in the future the size comes down to 0, it
should help.

+        !genericExceptionSelectors.has(selector))
+    {
+      selectors.push(selector);
+    }
+  }
+
+  return selectors;
+}
+
 /**
  * Container for element hiding filters
  * @class
  */
 let ElemHide = exports.ElemHide = {
   /**
    * Removes all known filters
    */
   clear()
   {
     for (let collection of [filtersByDomain, filterBySelector,
-                            knownFilters, exceptions])
+                            knownFilters, exceptions,
+                            genericExceptionSelectors])
     {
       collection.clear();
     }
     unconditionalSelectors = null;
     FilterNotifier.emit("elemhideupdate");
   },
 
   _addToFiltersByDomain(filter)
   {
     let domains = filter.domains || defaultDomains;
-    for (let [domain, isIncluded] of domains)
+    if (filter instanceof ElemHideException)
     {
-      // There's no need to note that a filter is generically disabled.
-      if (!isIncluded && domain == "")
-        continue;
+      for (let domain of domains.keys())
+      {
+        // Add an entry for each domain, but without any filters. This makes
+        // the domain "known" and helps us avoid the optimized path (which
+        // would give incorrect results).
+        if (domain != "" && !filtersByDomain.has(domain))
+          filtersByDomain.set(domain, null);
+      }
+    }
+    else
+    {
+      for (let [domain, isIncluded] of domains)
+      {
+        // There's no need to note that a filter is generically disabled.
+        if (!isIncluded && domain == "")
+          continue;
 
-      let filters = filtersByDomain.get(domain);
-      if (!filters)
-        filtersByDomain.set(domain, filters = new Map());
-      filters.set(filter, isIncluded);
+        let filters = filtersByDomain.get(domain);
+        if (!filters)
+          filtersByDomain.set(domain, filters = new Map());
+        filters.set(filter, isIncluded);
+      }
     }
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideBase} filter
    */
   add(filter)
   {
     if (knownFilters.has(filter))
       return;
 
     if (filter instanceof ElemHideException)
     {
-      let {selector} = filter;
+      let {selector, domains} = filter;
+
       let list = exceptions.get(selector);
       if (list)
         list.push(filter);
       else
         exceptions.set(selector, [filter]);
 
+      if (domains)
+        this._addToFiltersByDomain(filter);
+
+      if (filter.isGeneric())
+        genericExceptionSelectors.add(filter.selector);
+
       // If this is the first exception for a previously unconditionally
       // applied element hiding selector we need to take care to update the
       // lookups.
       let unconditionalFilterForSelector = filterBySelector.get(selector);
       if (unconditionalFilterForSelector)
       {
         this._addToFiltersByDomain(unconditionalFilterForSelector);
         filterBySelector.delete(selector);
         unconditionalSelectors = null;
       }
@@ skipping 23 matching lines @@
     if (!knownFilters.has(filter))
       return;
 
     // Whitelisting filters
     if (filter instanceof ElemHideException)
     {
       let list = exceptions.get(filter.selector);
       let index = list.indexOf(filter);
       if (index >= 0)
         list.splice(index, 1);
+
+      if (filter.isGeneric())
+        genericExceptionSelectors.delete(filter.selector);
     }
     // Unconditially applied element hiding filters
     else if (filterBySelector.get(filter.selector) == filter)
     {
       filterBySelector.delete(filter.selector);
       unconditionalSelectors = null;
     }
     // Conditionally applied element hiding filters
     else
     {
@@ skipping 74 matching lines @@
   getSelectorsForDomain(domain, criteria)
   {
     let selectors = [];
 
     if (typeof criteria == "undefined")
       criteria = ElemHide.ALL_MATCHING;
     if (criteria < ElemHide.NO_UNCONDITIONAL)
       selectors = this.getUnconditionalSelectors();
 
     let specificOnly = (criteria >= ElemHide.SPECIFIC_ONLY);
-    let excluded = new Set();
     let currentDomain = domain ? domain.toUpperCase() : "";
 
-    // This code is a performance hot-spot, which is why we've made certain
-    // micro-optimisations. Please be careful before making changes.
-    while (true)
+    if (isDomainKnown(currentDomain))

[kzar, 2018/05/08 13:46:47]

I don't quite understand how your change speeds things up. Aren't we pretty much
doing the same check in isDomainKnown as we were before (checking if the domain
part is present in filtersByDomain)? 

If calling .has instead of .get or similar is helping couldn't we add that check
into this loop instead of having a duplicate loop out in the isDomainKnown
function?

[Manish Jethani, 2018/05/08 14:20:43]

Let me come back with an answer after investigating this a little more.

[Manish Jethani, 2018/05/08 15:49:00]

Alright, I checked.

Fifty percent of the speedup is owning to the fact that it's a separate
function. This means we could start by separating out the existing while loop
into its own function. I'll make a patch for that.

The remaining is mainly owing to the fact that we don't call this.getException
for unknown domains, because we already know that there are no domain-specific
exceptions; instead we just do a lookup in the genericExceptionSelectors set for
the filter's selector, which is much, much faster. Other minor things are that
we don't create a set object and access its size property and "potentially" (but
never in fact because it's an unknown domain, but the JS runtime doesn't know
this) its has method.

Another factor might be that we only get the keys of the filters map, whereas in
the case of known domains we also get the values (isIncluded), which might be
slower. I haven't checked specifically for this though.

So we might end up with two functions, for known and unknown domains
respectively:

  getConditionalSelectorsForDomain(domain, specificOnly)
  getConditionalGenericSelectors()

We might be able to combine these into one function (if there's no domain
specified then it's the same as the second case?), depending on how much cleaner
it is and how much it affects performance.

[kzar, 2018/05/08 17:13:43]

Interesting, I wonder why that is. Is something in this function causing it to
deoptimise?
I wonder why getException is slower than your new logic. In other words I wonder
if we could make use of your tweak to filtersByDomain (storing null for
exceptions) in the getException function instead.

[Manish Jethani, 2018/05/08 17:37:13]

Yes, I found out:

https://codereview.adblockplus.org/29774573/

See the first comment on that patch. It was that we were modifying the
unconditional selectors array. My suggestion is to use concatenation of two
arrays.
Let me look into that.

[Manish Jethani, 2018/05/08 17:49:30]

getException should really be called hasException and return boolean. If the
domain is unknown (has no entry in filtersByDomain), it should check
genericExceptionSelectors instead of doing the usual stuff.

Or the caller could take care of this, either way.

Anyway I have something in mind here so I'll update the patch tomorrow after
rebasing on #29774573. We should land that one first since the benefits are more
obvious.

     {
-      if (specificOnly && currentDomain == "")
-        break;
+      let excluded = new Set();
 
-      let filters = filtersByDomain.get(currentDomain);
-      if (filters)
+      // This code is a performance hot-spot, which is why we've made certain
+      // micro-optimisations. Please be careful before making changes.
+      while (true)
       {
-        for (let [filter, isIncluded] of filters)
+        if (specificOnly && currentDomain == "")
+          break;
+
+        let filters = filtersByDomain.get(currentDomain);
+        if (filters)
         {
-          if (!isIncluded)
+          for (let [filter, isIncluded] of filters)
           {
-            excluded.add(filter);
-          }
-          else if ((excluded.size == 0 || !excluded.has(filter)) &&
-                   !this.getException(filter, domain))
-          {
-            selectors.push(filter.selector);
+            if (!isIncluded)
+            {
+              excluded.add(filter);
+            }
+            else if ((excluded.size == 0 || !excluded.has(filter)) &&
+                     !this.getException(filter, domain))
+            {
+              selectors.push(filter.selector);
+            }
           }
         }
+
+        if (currentDomain == "")
+          break;
+
+        let nextDot = currentDomain.indexOf(".");
+        currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
       }
-
-      if (currentDomain == "")
-        break;
-
-      let nextDot = currentDomain.indexOf(".");
-      currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
+    }
+    else if (!specificOnly)
+    {
+      selectors = selectors.concat(getConditionalGenericSelectors());

[kzar, 2018/05/08 13:46:47]

Won't selectors always be [] here? I wonder why we concat the two lists together
instead of just returning getConditionalGenericSelectors().

[Manish Jethani, 2018/05/08 14:20:43]

No, the selectors array will contain the unconditional selectors, which is
actually most selectors.

I wrote previously: "To give you some numbers, there are 18,300 unconditional
selectors, 1,095 conditional generic selectors, and 16 generic exceptions in  in
EasyList+AA."

[kzar, 2018/05/08 17:13:44]

Ah yea, gotya.

     }
 
     return selectors;
   }
 };