Issue 4057 - Further speedup ElemHide.getSelectorsforDomain

lib/elemHide.js

Index: lib/elemHide.js
diff --git a/lib/elemHide.js b/lib/elemHide.js
index 6e2f1b56acbb6e67e79f779503b469f9d8829903..56f5919d98e2bedf001920374466a07ba3d4a443 100644
--- a/lib/elemHide.js
+++ b/lib/elemHide.js
@@ -40,17 +40,31 @@ var filterByKey = Object.create(null);
 var keyByFilter = Object.create(null);
 
 /**
- * Nested lookup table, filter (or false if inactive) by filter text by domain
- * @type Object
+ * Indicates whether we are using getSelectorsByDomain and maintaining the
+ * required lookup tables. (Will be false for Firefox)
+ * @type Boolean
  */
-var filtersByDomain = Object.create(null);
+var usingGetSelectorsByDomain = !("nsIStyleSheetService" in Ci);
 
 /**
- * Indicates whether we are using (and maintaining) the filtersByDomain lookup.
- * (Will be false for Firefox)
- * @type Boolean
+ * Lookup table, filter selector by filter ID.
+ */
+var selectorByFilterId = [];
+
+/**
+ * Lookup table, active filter IDs by domain.
+ */
+var activeFilterIdsByDomain = Object.create(null);
+
+/**
+ * Lookup table, inactive filter IDs by domain.
  */
-var usingFiltersByDomain = !("nsIStyleSheetService" in Ci);
+var inactiveFilterIdsByDomain = Object.create(null);
+
+/**
+ * Lookup table, filter ID by filter text.
+ */
+var filterIdByFilterText = Object.create(null);
 
 /**
  * Object to be used instead when a filter has a blank domains property.
@@ -118,7 +132,10 @@ var ElemHide = exports.ElemHide =
   {
     filterByKey = Object.create(null);
     keyByFilter = Object.create(null);
-    filtersByDomain = Object.create(null);
+    selectorByFilterId = [];
+    activeFilterIdsByDomain = Object.create(null);
+    inactiveFilterIdsByDomain = Object.create(null);
+    filterIdByFilterText = Object.create(null);
     knownExceptions = Object.create(null);
     exceptions = Object.create(null);
     ElemHide.isDirty = false;
@@ -155,19 +172,30 @@ var ElemHide = exports.ElemHide =
       filterByKey[key] = filter;
       keyByFilter[filter.text] = key;
 
-      if (usingFiltersByDomain)
+      if (usingGetSelectorsByDomain)
       {
+        let filterId = filterIdByFilterText[filter.text];
+        if (filterId == undefined)

[Wladimir Palant, 2016/05/20 12:33:27]

That's one of the few cases where you need ===, because null == undefined
evaluates to true.

[Sebastian Noack, 2016/05/20 13:03:04]

We always use typeof when checking for undefined.

[kzar, 2016/05/21 04:43:09]

Acknowledged.

+        {
+          filterId = selectorByFilterId.push(filter.selector) - 1;
+          filterIdByFilterText[filter.text] = filterId;
+        }
+
         let domainMatches = filter.domains || defaultDomains;
+

[Sebastian Noack, 2016/05/20 13:03:03]

Nit: It seems the code reads better without the blakn line here.

[kzar, 2016/05/21 04:43:09]

Done.

         for (let domain in domainMatches)
         {
-          let filters = filtersByDomain[domain];
-          if (!filters)
-            filters = filtersByDomain[domain] = Object.create(null);
-
+          let lookup;
           if (domainMatches[domain])
-            filters[filter.text] = filter;
+            lookup = activeFilterIdsByDomain;
           else
-            filters[filter.text] = false;
+            lookup = inactiveFilterIdsByDomain;
+
+          let filterIds = lookup[domain];
+          if (filterIds == undefined)
+            filterIds = lookup[domain] = [];
+
+          filterIds.push(filterId);
         }
       }
 
@@ -201,6 +229,33 @@ var ElemHide = exports.ElemHide =
       delete filterByKey[key];
       delete keyByFilter[filter.text];
       ElemHide.isDirty = true;
+
+      if (usingGetSelectorsByDomain)

[kzar, 2016/05/20 10:55:17]

I'm not too happy with this change it's kind of slow. When disabling large
subscriptions like EasyList that might be a problem.

(Come to think of it we also forgot to remove things from the lookup with the
earlier changes for this issue...)

+      {
+        let filterId = filterIdByFilterText[filter.text];
+        if (filterId)
+        {
+          delete filterIdByFilterText[filter.text];
+          delete selectorByFilterId[filterId];
+
+          let domains = Object.keys(filter.domains || defaultDomains);

[Wladimir Palant, 2016/05/20 12:33:27]

Why use Object.keys() here all the sudden rather than for..in loop?

[kzar, 2016/05/21 04:43:09]

Done.

+          let filterIdsByDomainLookups = [activeFilterIdsByDomain,
+                                          inactiveFilterIdsByDomain];
+          for (let domain of domains)
+          {
+            for (let filterIdsByDomain of filterIdsByDomainLookups)
+            {
+              let lookup = filterIdsByDomain[domain];
+              if (lookup)
+              {
+                let index = lookup.indexOf(filterId);
+                if (index != -1)
+                  lookup.splice(index, 1);
+              }
+            }
+          }
+        }
+      }
     }
   },
 
@@ -208,12 +263,12 @@ var ElemHide = exports.ElemHide =
    * Checks whether an exception rule is registered for a filter on a particular
    * domain.
    */
-  getException: function(/**Filter*/ filter, /**String*/ docDomain) /**ElemHideException*/
+  getException: function(/**String*/ selector, /**String*/ docDomain) /**ElemHideException*/
   {
-    if (!(filter.selector in exceptions))
+    if (!(selector in exceptions))
       return null;
 
-    let list = exceptions[filter.selector];
+    let list = exceptions[selector];
     for (let i = list.length - 1; i >= 0; i--)
       if (list[i].isActiveOnDomain(docDomain))
         return list[i];
@@ -410,30 +465,35 @@ var ElemHide = exports.ElemHide =
    */
   getSelectorsForDomain: function(/**String*/ domain, /**Boolean*/ specificOnly)
   {
-    if (!usingFiltersByDomain)
+    if (!usingGetSelectorsByDomain)
       throw new Error("getSelectorsForDomain can not be used in Firefox!");
 
     let selectors = [];
 
-    let seenFilters = Object.create(null);
+    let seenFilterIds = Object.create(null);
     let currentDomain = domain ? domain.toUpperCase() : "";
     while (true)
     {
       if (specificOnly && currentDomain == "")
         break;
 
-      let filters = filtersByDomain[currentDomain];
-      if (filters)
+      let inactiveFilterIds = inactiveFilterIdsByDomain[currentDomain];
+      if (inactiveFilterIds)
+        for (let filterId of inactiveFilterIds)
+          seenFilterIds[filterId] = true;
+
+      let activeFilterIds = activeFilterIdsByDomain[currentDomain];
+      if (activeFilterIds)
       {
-        for (let filterText in filters)
+        for (let filterId of activeFilterIds)
         {
-          if (filterText in seenFilters)
+          if (filterId in seenFilterIds)
             continue;
-          seenFilters[filterText] = true;
+          seenFilterIds[filterId] = true;
 
-          let filter = filters[filterText];
-          if (filter && !this.getException(filter, domain))
-            selectors.push(filter.selector);
+          let selector = selectorByFilterId[filterId];
+          if (!this.getException(selector, domain))
+            selectors.push(selector);
         }
       }