Issue 235 - Speed up 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
+ */
+var filtersByDomain = Object.create(null);
+
+/**
+ * Indicates whether we are using (and maintaining) the filtersByDomain lookup.
+ * (Will be false for Firefox)
+ * @type Boolean
+ */
+var usingFiltersByDomain = !("nsIStyleSheetService" in Ci);
+
+/**
  * Lookup table, keys are known element hiding exceptions
  * @type Object
  */
 var knownExceptions = Object.create(null);
 
 /**
  * Lookup table, lists of element hiding exceptions by selector
  * @type Object
  */
 var exceptions = Object.create(null);
@@ skipping 10 matching lines @@
  */
 var ElemHide = exports.ElemHide =
 {
   /**
    * Indicates whether filters have been added or removed since the last apply() call.
    * @type Boolean
    */
   isDirty: false,
 
   /**
-   * Inidicates whether the element hiding stylesheet is currently applied.
+   * Indicates whether the element hiding stylesheet is currently applied.
    * @type Boolean
    */
   applied: false,
 
   /**
    * Called on module startup.
    */
   init: function()
   {
     Prefs.addListener(function(name)
     {
       if (name == "enabled")
         ElemHide.apply();
     });
     onShutdown.add(() => ElemHide.unapply());
 
     let styleFile = IO.resolveFilePath(Prefs.data_directory);
     styleFile.append("elemhide.css");
     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);
     knownExceptions = Object.create(null);
     exceptions = Object.create(null);
     ElemHide.isDirty = false;
     ElemHide.unapply();
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideFilter} filter
    */
@@ skipping 15 matching lines @@
       if (filter.text in keyByFilter)
         return;
 
       let key;
       do {
         key = Math.random().toFixed(15).substr(5);
       } while (key in filterByKey);
 
       filterByKey[key] = filter;
       keyByFilter[filter.text] = key;
+
+      if (usingFiltersByDomain)
+      {
+        let domainMatches = filter.domains || {"": true};

[Wladimir Palant, 2016/05/18 13:38:06]

You are iterating over object keys below but {"": true} has more properties than
just "" (unlike filter.domains which doesn't have a prototype). It's probably
best to have a global defaultDomains variable that has this object without
prototype.

[Sebastian Noack, 2016/05/18 13:48:25]

Also note that for..in loops on objects in hash-table mode cause the function to
de-deoptimized in V8. However, whether this is the case here depends a lot of
the context. So please make sure that there is no deopt. And if necessary resort
to Object.keys() + for(;;)

[kzar, 2016/05/18 14:23:00]

Done.

[kzar, 2016/05/18 14:23:00]

The only way I know to check if a function is deoptimized is to find it in the
profiler. It was a little hard to find it but finally found it and the
Elemhide.add function is not deoptimized with this change apparently.
(Unfortunately I only found it in Botttom Up view so far, finding it in Top Down
was even harder.)

+        for (let domain in domainMatches)
+        {
+          domain = domain.toUpperCase();

[Wladimir Palant, 2016/05/18 13:38:06]

This operation is unnecessary, the domains are already upper-case.

[kzar, 2016/05/18 14:23:00]

Done.

+          let filters = filtersByDomain[domain];
+          if (!filters)
+            filters = filtersByDomain[domain] = Object.create(null);
+          filters[filter.text] = domainMatches[domain] && filter;

[Wladimir Palant, 2016/05/18 13:38:05]

I know, Sebastian loves such constructs. Still, I consider this too non-obvious.
Could you write this out, with a proper if statement?

  if (domainMatches[domain])
    filters[filter.text] = filter;
  else
    filters[filter.text] = false;

[kzar, 2016/05/18 14:23:00]

Done.

+        }
+      }
+
       ElemHide.isDirty = true;
     }
   },
 
   /**
    * Removes an element hiding filter
    * @param {ElemHideFilter} filter
    */
   remove: function(filter)
   {
@@ skipping 214 matching lines @@
 
   /**
    * Retrieves an element hiding filter by the corresponding protocol key
    */
   getFilterByKey: function(/**String*/ key) /**Filter*/
   {
     return (key in filterByKey ? filterByKey[key] : null);
   },
 
   /**
-   * Returns a list of all selectors active on a particular domain (currently
-   * used only in Chrome, Opera and Safari).
+   * 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)
   {
-    let result = [];
-    let keys = Object.getOwnPropertyNames(filterByKey);
-    for (let key of keys)
+    if (!usingFiltersByDomain)
+      throw new Error("getSelectorsForDomain can not be used in Firefox!");
+
+    let selectors = [];
+
+    let seenFilters = Object.create(null);
+    let currentDomain = domain ? domain.toUpperCase() : "";
+    while (true)
     {
-      let filter = filterByKey[key];
-      if (specificOnly && (!filter.domains || filter.domains[""]))
-        continue;
+      if (specificOnly && currentDomain == "")
+        break;
 
-      if (filter.isActiveOnDomain(domain) && !this.getException(filter, domain))
-        result.push(filter.selector);
+      let filters = filtersByDomain[currentDomain];
+      if (filters)
+      {
+        for (let filterText in filters)
+        {
+          if (filterText in seenFilters)
+            continue;
+          seenFilters[filterText] = true;
+
+          let filter = filters[filterText];
+          if (filter && !this.getException(filter, domain))
+            selectors.push(filter.selector);
+        }
+      }
+
+      if (currentDomain == "")
+        break;
+
+      let nextDot = currentDomain.indexOf(".");
+      currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
-    return result;
+
+    return selectors;
   }
 };