Issue 4057 - Further speedup ElemHide.getSelectorsforDomain

lib/elemHide.js

Index: lib/elemHide.js
diff --git a/lib/elemHide.js b/lib/elemHide.js
index 574ef91dff6340a1e9408571fef1b31726cec78c..e0d2c5e10b89334988094b84d7c06ea552b652dd 100644
--- a/lib/elemHide.js
+++ b/lib/elemHide.js
@@ -40,17 +40,30 @@ var filterByKey = [];
 var keyByFilter = Object.create(null);
 
 /**
- * Nested lookup table, filter (or false if inactive) by filter text by domain
+ * Indicates whether we are using the getSelectorsForDomain function and
+ * therefore mainting the required filtersByDomain, filtersBySelector and
+ * unconditionalSelectors lookups. (Will be false for Firefox)
+ * @type Boolean
+ */
+var usingGetSelectorsForDomain = !("nsIStyleSheetService" in Ci);
+
+/**
+ * Nested lookup table, filter (or false if inactive) by filter key by domain.
+ * (Only contains filters that aren't unconditionally matched for all domains.)
  * @type Object
  */
 var filtersByDomain = Object.create(null);
 
 /**
- * Indicates whether we are using (and maintaining) the filtersByDomain lookup.
- * (Will be false for Firefox)
- * @type Boolean
+ * Lookup table, filters by selector. (Only contains filters that have a
+ * selector that is unconditionally matched for all domains.)
  */
-var usingFiltersByDomain = !("nsIStyleSheetService" in Ci);
+var filtersBySelector = Object.create(null);
+
+/**
+ * Array of selectors which unconditionally apply to all domains.
+ */
+var unconditionalSelectors = [];
 
 /**
  * Object to be used instead when a filter has a blank domains property.
@@ -119,12 +132,31 @@ var ElemHide = exports.ElemHide =
     filterByKey = [];
     keyByFilter = Object.create(null);
     filtersByDomain = Object.create(null);
+    filtersBySelector = Object.create(null);
+    unconditionalSelectors = [];
     knownExceptions = Object.create(null);
     exceptions = Object.create(null);
     ElemHide.isDirty = false;
     ElemHide.unapply();
   },
 
+  _addToFiltersByDomain: function(filter)
+  {
+    let key = keyByFilter[filter.text];
+    let domains = filter.domains || defaultDomains;
+    for (let domain in domains)
+    {
+      let filters = filtersByDomain[domain];
+      if (!filters)
+        filters = filtersByDomain[domain] = Object.create(null);
+
+      if (domains[domain])
+        filters[key] = filter;
+      else
+        filters[key] = false;
+    }
+  },
+
   /**
    * Add a new element hiding filter
    * @param {ElemHideFilter} filter
@@ -140,6 +172,23 @@ var ElemHide = exports.ElemHide =
       if (!(selector in exceptions))
         exceptions[selector] = [];
       exceptions[selector].push(filter);
+
+      if (usingGetSelectorsForDomain)
+      {
+        // If this is the first exception for a previously unconditionally
+        // applied element hiding selector we need to take care to update the
+        // lookups.
+        let unconditionalFilters = filtersBySelector[selector];
+        if (unconditionalFilters)
+        {
+          for (let f of unconditionalFilters)
+            this._addToFiltersByDomain(f);
+          delete filtersBySelector[selector];
+          let index = unconditionalSelectors.indexOf(selector);
+          unconditionalSelectors.splice(index, 1);
+        }
+      }
+
       knownExceptions[filter.text] = true;
     }
     else
@@ -150,19 +199,26 @@ var ElemHide = exports.ElemHide =
       let key = filterByKey.push(filter) - 1;
       keyByFilter[filter.text] = key;
 
-      if (usingFiltersByDomain)
+      if (usingGetSelectorsForDomain)
       {
-        let domains = filter.domains || defaultDomains;
-        for (let domain in domains)
+        // The new filter's selector is unconditionally applied to all domains

[Wladimir Palant, 2016/05/24 15:16:18]

This comment belongs inside the if block since it only applies to one branch of
it.

[kzar, 2016/05/25 05:12:24]

Done.

+        if (!filter.domains && !exceptions[filter.selector])

[Wladimir Palant, 2016/05/24 15:16:19]

We don't really care about the value of exceptions[filter.selector] so I'd
prefer !(filter.selector in exceptions).

[kzar, 2016/05/25 05:12:24]

Done.

         {
-          let filters = filtersByDomain[domain];
-          if (!filters)
-            filters = filtersByDomain[domain] = Object.create(null);
-
-          if (domains[domain])
-            filters[filter.text] = filter;
+          let filters = filtersBySelector[filter.selector];
+          if (filters)
+          {
+            filters.push(filter);
+          }
           else
-            filters[filter.text] = false;
+          {
+            filtersBySelector[filter.selector] = [filter];
+            unconditionalSelectors.push(filter.selector);
+          }
+        }
+        // The new filter's selector only applies to some domains

[Wladimir Palant, 2016/05/24 15:16:18]

Same here, comment inside the block please.

[kzar, 2016/05/25 05:12:24]

Done.

+        else
+        {
+          this._addToFiltersByDomain(filter);
         }
       }
 
@@ -197,14 +253,32 @@ var ElemHide = exports.ElemHide =
       delete keyByFilter[filter.text];
       ElemHide.isDirty = true;
 
-      if (usingFiltersByDomain)
+      if (usingGetSelectorsForDomain)

[kzar, 2016/05/24 14:45:22]

I'm worried about the performance of ElemHide.remove now. There is a sometimes
noticeable pause when disabling EasyList. I've tried making
unconditioanlSelectors a lookup, which helps a bit but that slows down
getSelectorsForDomain lots as it then has to call
Object.keys(unconditioanlSelectors) every time.

Any ideas?

[Wladimir Palant, 2016/05/24 15:16:19]

A remove isn't a very common operation. Did you measure it, how long does it
take?

In theory, we could make unconditionalSelectors a sorted list which would allow
much faster searches. However, this will slow down insert operations
considerably (meaning that it makes ElemHide.add() slower).

[kzar, 2016/05/24 17:47:09]

Yea, it's pretty bad - something like 2325ms spent in elemHide.remove when
EasyList is disabled.

I guess you're right that this is kind of an usual operation. Also I realised
the speed is really not too important, the problem is that there is a visible
delay for the user. How about we wrap the subscription toggling code in
adblockplusui/messageResponder.js in a window.setTimeout of 0ms? Unless the user
clicks EasyList on and off repeatedly this fixes the sluggishness in the
interface when removing / disabling a big subscription.

[kzar, 2016/05/24 17:52:12]

Another idea, maybe crazy... removing is expensive but adding is much cheaper.
Perhaps in some situations we should remove everything and then add back in the
filters we need?

[kzar, 2016/05/25 04:57:16]

With Patch Set 5 ElemHide.remove is now down to about 330ms when disabling
EasyList. There is still a pause sometimes but it's far less noticeable.

       {
-        let domains = filter.domains || defaultDomains;
-        for (let domain in domains)
+        let filters = filtersBySelector[filter.selector];
+        if (filters)
         {
-          let filters = filtersByDomain[domain];
-          if (filters)
-            delete filters[filter.text];
+          if (filters.length > 1)
+          {
+            let index = filters.indexOf(filter);
+            filters.splice(index, 1);
+          }
+          else
+          {
+            delete filtersBySelector[filter.selector];
+            let index = unconditionalSelectors.indexOf(filter.selector);
+            unconditionalSelectors.splice(index, 1);
+          }
+        }
+        else
+        {
+          let domains = filter.domains || defaultDomains;
+          for (let domain in domains)
+          {
+            let filters = filtersByDomain[domain];
+            if (filters)
+              delete filters[key];
+          }
         }
       }
     }
@@ -416,11 +490,11 @@ var ElemHide = exports.ElemHide =
 
   /**
    * Returns a list of all selectors active on a particular domain, must not be
-   * used in Firefox (when usingFiltersByDomain is false).
+   * used in Firefox (when usingGetSelectorsForDomain is false).
    */
   getSelectorsForDomain: function(/**String*/ domain, /**Boolean*/ specificOnly)
   {
-    if (!usingFiltersByDomain)
+    if (!usingGetSelectorsForDomain)
       throw new Error("getSelectorsForDomain can not be used in Firefox!");
 
     let selectors = [];
@@ -435,13 +509,13 @@ var ElemHide = exports.ElemHide =
       let filters = filtersByDomain[currentDomain];
       if (filters)
       {
-        for (let filterText in filters)
+        for (let filterKey in filters)
         {
-          if (filterText in seenFilters)
+          if (filterKey in seenFilters)
             continue;
-          seenFilters[filterText] = true;
+          seenFilters[filterKey] = true;
 
-          let filter = filters[filterText];
+          let filter = filters[filterKey];
           if (filter && !this.getException(filter, domain))
             selectors.push(filter.selector);
         }
@@ -454,6 +528,9 @@ var ElemHide = exports.ElemHide =
       currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
 
-    return selectors;
+    if (specificOnly)

[Sebastian Noack, 2016/05/24 15:20:07]

Why do you still account for specificOnly inside the loop? As far as I
understand the logic, we can bail out now as soon as there is no next dot
regardless of specificOnly.

[Wladimir Palant, 2016/05/24 15:26:06]

Not all generic filters are in unconditionalSelectors - some have exception
rules applying to them, others exclude particular domains (like
~example.com##foo).

+      return selectors;
+    else

[Sebastian Noack, 2016/05/24 15:20:07]

Nit: extraneous else

[kzar, 2016/05/25 05:12:24]

Done.

+      return unconditionalSelectors.concat(selectors);

[Wladimir Palant, 2016/05/24 15:16:19]

I think we should avoid concatenating two arrays here, just initialize the
selectors array correctly.

  let selectors = specificOnly ? [] : unconditionalSelectors.slice();

[kzar, 2016/05/25 05:12:24]

Done.

   }
 };