Issue 4057 - Further speedup ElemHide.getSelectorsforDomain

lib/elemHide.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-2016 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
@@ skipping 22 matching lines @@
  */
 var filterByKey = Object.create(null);
 
 /**
  * Lookup table, keys of the filters by filter text
  * @type Object
  */
 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 usingFiltersByDomain = !("nsIStyleSheetService" in Ci);
+var selectorByFilterId = [];
+
+/**
+ * Lookup table, active filter IDs by domain.
+ */
+var activeFilterIdsByDomain = Object.create(null);
+
+/**
+ * Lookup table, inactive filter IDs by domain.
+ */
+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.
  */
 var defaultDomains = Object.create(null);
 defaultDomains[""] = true;
 
 /**
  * Lookup table, keys are known element hiding exceptions
  * @type Object
@@ skipping 47 matching lines @@
     styleURL = Services.io.newFileURI(styleFile).QueryInterface(Ci.nsIFileURL);
   },
 
   /**
    * Removes all known filters
    */
   clear: function()
   {
     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;
     ElemHide.unapply();
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideFilter} filter
    */
@@ skipping 16 matching lines @@
         return;
 
       let key;
       do {
         key = Math.random().toFixed(15).substr(5);
       } while (key in filterByKey);
 
       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])
+            lookup = activeFilterIdsByDomain;
+          else
+            lookup = inactiveFilterIdsByDomain;
 
-          if (domainMatches[domain])
-            filters[filter.text] = filter;
-          else
-            filters[filter.text] = false;
+          let filterIds = lookup[domain];
+          if (filterIds == undefined)
+            filterIds = lookup[domain] = [];
+
+          filterIds.push(filterId);
         }
       }
 
       ElemHide.isDirty = true;
     }
   },
 
   /**
    * Removes an element hiding filter
    * @param {ElemHideFilter} filter
@@ skipping 13 matching lines @@
     }
     else
     {
       if (!(filter.text in keyByFilter))
         return;
 
       let key = keyByFilter[filter.text];
       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);
+              }
+            }
+          }
+        }
+      }
     }
   },
 
   /**
    * 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];
 
     return null;
   },
 
   /**
    * Will be set to true if apply() is running (reentrance protection).
    * @type Boolean
@@ skipping 176 matching lines @@
   {
     return (key in filterByKey ? filterByKey[key] : null);
   },
 
   /**
    * Returns a list of all selectors active on a particular domain, must not be
    * used in Firefox (when usingFiltersByDomain is false).
    */
   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);
         }
       }
 
       if (currentDomain == "")
         break;
 
       let nextDot = currentDomain.indexOf(".");
       currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
 
     return selectors;
   }
 };