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..d834be198501e65b6d10e208614c5879d1fd9fea 100644
--- a/lib/elemHide.js
+++ b/lib/elemHide.js
@@ -40,17 +40,35 @@ 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 filtersBySelector = Object.create(null);
+
+/**
+ * Array of selectors which unconditionally apply to all domains.
+ */
+var unconditionalSelectors = [];
+
+/**
+ * Indicates that the unconditionalSelectors Array needs to be regenerated.
  */
-var usingFiltersByDomain = !("nsIStyleSheetService" in Ci);
+var unconditionalSelectorsDirty = false;
 
 /**
  * Object to be used instead when a filter has a blank domains property.
@@ -119,12 +137,32 @@ var ElemHide = exports.ElemHide =
     filterByKey = [];
     keyByFilter = Object.create(null);
     filtersByDomain = Object.create(null);
+    filtersBySelector = Object.create(null);
+    unconditionalSelectors = [];
+    unconditionalSelectorsDirty = false;
     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 +178,22 @@ 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];
+          unconditionalSelectorsDirty = true;
+        }
+      }
+
       knownExceptions[filter.text] = true;
     }
     else
@@ -150,19 +204,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)
+        if (!(filter.domains || filter.selector in exceptions))
         {
-          let filters = filtersByDomain[domain];
-          if (!filters)
-            filters = filtersByDomain[domain] = Object.create(null);
-
-          if (domains[domain])
-            filters[filter.text] = filter;
+          // The new filter's selector is unconditionally applied to all domains
+          let filters = filtersBySelector[filter.selector];
+          if (filters)
+          {
+            filters.push(filter);
+          }
           else
-            filters[filter.text] = false;
+          {
+            filtersBySelector[filter.selector] = [filter];
+            unconditionalSelectorsDirty = true;
+          }
+        }
+        else
+        {
+          // The new filter's selector only applies to some domains
+          this._addToFiltersByDomain(filter);
         }
       }
 
@@ -197,14 +258,31 @@ var ElemHide = exports.ElemHide =
       delete keyByFilter[filter.text];
       ElemHide.isDirty = true;
 
-      if (usingFiltersByDomain)
+      if (usingGetSelectorsForDomain)
       {
-        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];
+            unconditionalSelectorsDirty = true;
+          }
+        }
+        else
+        {
+          let domains = filter.domains || defaultDomains;
+          for (let domain in domains)
+          {
+            let filters = filtersByDomain[domain];
+            if (filters)
+              delete filters[key];
+          }
         }
       }
     }
@@ -416,14 +494,19 @@ 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 = [];
+    if (unconditionalSelectorsDirty)
+    {
+      unconditionalSelectors = Object.keys(filtersBySelector);
+      unconditionalSelectorsDirty = false;
+    }
+    let selectors = specificOnly ? [] : unconditionalSelectors.slice();

[Sebastian Noack, 2016/05/25 07:30:49]

You can skip the unconditionalSelectorsDirty logic in the specificOnly case:

let selectors;
if (specificOnly)
{
  selectors = [];
}
else
{
  if (unconditionalSelectorsDirty)
  {
     unconditionalSelectors = Object.keys(filtersBySelector);
     unconditionalSelectorsDirty = false;
  }
  selectors = unconditionalSelectors.slice();
}

[Sebastian Noack, 2016/05/25 07:30:49]

Also note that if you'd call Object.keys() unconditionally, you can avoid the
isDirty logic and don't have to copy the list. But that would still be notably
slower? Just want to make sure, since the way you did it initally, the array was
copied anyway by Array.concat().

[Sebastian Noack, 2016/05/25 07:40:26]

One more thing, if we need that is dirty logic, how about just setting
unconditionalSelectors to null instead adding yet another global variable? That
way the code is a little shorter, and we won't leak outdated data.

[kzar, 2016/05/25 08:05:19]

Done.

[kzar, 2016/05/25 08:05:19]

I know I could skip restoring unconditionalSelectors if specificOnly is true but
there's not much point.

[kzar, 2016/05/25 08:05:19]

Yep, just double checked and it's still quite a bit slower using Object.keys()
every time even without the concat.

[Sebastian Noack, 2016/05/25 08:11:56]

Besides a speedup in specificOnly case which might be negligible, it also
improves the code locality and makes the purpose of that logic slightly easier
to understand IMO. Also it will be even shorter now where you only have one
variable.

[kzar, 2016/05/25 08:29:04]

I disagree on this one, but I see your point. I'll leave it up to Wladimir to
decide.

[Wladimir Palant, 2016/05/25 10:43:03]

Frankly, while I can see the arguments towards only setting
unconditionalSelectors when needed, it's not really important enough to be
changed. The flow won't necessarily become more readable if we do, and it's
already fine as is.

 
     let seenFilters = Object.create(null);
     let currentDomain = domain ? domain.toUpperCase() : "";
@@ -435,13 +518,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);
         }