Issue 235 - Improved performance of ElemHide.getSelectorsForDomain()

lib/elemHide.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-2015 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 41 matching lines @@
  */
 let exceptions = Object.create(null);
 
 /**
  * Currently applied stylesheet URL
  * @type nsIURI
  */
 let styleURL = null;
 
 /**
- * Lookup table, blocking filters by domain which they are applied to
+ * Lookup table, filter selectors by domain which they are applied to
  * @type Object
  */
-let filtersByDomain = Object.create(null);
+let selectorsByDomain = Object.create(null);
+
+/**
+ * Indicates whether stylesheets can be used for element hiding
+ * @type Boolean
+ */
+let canUseStylesheets = ("nsIStyleSheetService" in Ci);
 
 /**
  * Element hiding component
  * @class
  */
 let ElemHide = exports.ElemHide =
 {
   /**
    * Indicates whether filters have been added or removed since the last apply() call.
    * @type Boolean
@@ skipping 28 matching lines @@
 
   /**
    * Removes all known filters
    */
   clear: function()
   {
     filterByKey = Object.create(null);
     keyByFilter = Object.create(null);
     knownExceptions = Object.create(null);
     exceptions = Object.create(null);
-    filtersByDomain = Object.create(null);
+    selectorsByDomain = Object.create(null);
     ElemHide.isDirty = false;
     ElemHide.unapply();
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideFilter} filter
    */
   add: function(filter)
   {
     if (filter instanceof ElemHideException)
     {
       if (filter.text in knownExceptions)
         return;
 
       let selector = filter.selector;
       if (!(selector in exceptions))
         exceptions[selector] = [];
       exceptions[selector].push(filter);
       knownExceptions[filter.text] = true;
     }
     else
     {
       if (filter.text in keyByFilter)
         return;
 
-      if (!("nsIStyleSheetService" in Ci))

[Wladimir Palant, 2015/02/23 19:20:16]

Looking up things in Components.interfaces isn't such a fast operation in
Firefox, doing that for 15k filters will take up 15ms on my computer. How about
storing that value in a global boolean flag?

[Thomas Greiner, 2015/03/12 16:00:06]

Done.

+      if (!canUseStylesheets)
       {
         let domains = filter.domains;
         if (domains === null)
         {
           domains = Object.create(null);
-          domains[""] = undefined;

[Wladimir Palant, 2015/02/23 19:20:16]

This should be true, not undefined.

[Thomas Greiner, 2015/03/12 16:00:06]

Done.

+          domains[""] = true;
         }
 
         for (let domain in domains)
         {
-          if (!(domain in filtersByDomain))
+          if (!(domain in selectorsByDomain))
           {
-            filtersByDomain[domain] = Object.create(null);
-            filtersByDomain[domain]._length = 0;
+            selectorsByDomain[domain] = Object.create(null);
+            selectorsByDomain[domain].$length = 0;
           }
 
-          filtersByDomain[domain][filter.text] = filter.isActiveOnDomain(domain);

[Wladimir Palant, 2015/02/23 19:20:16]

The very point of this functionality is to avoid calling isActiveOnDomain() too
much - it's a slow operation. Why not |filtersByDomain[domain][filter.text] =
domains[domain]|?

[Thomas Greiner, 2015/03/12 16:00:06]

Done, you're right that it appears to be redundant here.

-          filtersByDomain[domain]._length++;

[Wladimir Palant, 2015/02/23 19:20:16]

Strictly speaking, _length isn't an invalid domain name. How about using
something like " length" for this property name? A collision with a domain name
should be impossible, not merely unlikely.

[Thomas Greiner, 2015/03/12 16:00:06]

That's true but that might make it difficult to spot the difference between the
names " length" and "length" and therefore could cause issues in the future. Due
to that I chose "$length" instead.

+          let selectors = selectorsByDomain[domain];
+          if (!(filter.selector in selectors))
+          {
+            selectors[filter.selector] = {
+              isActive: false,
+              count: 0
+            };
+          }
+          selectors[filter.selector].isActive |= domains[domain];
+          selectors[filter.selector].count++;
+
+          selectors.$length++;
         }
       }
 
       let key;
       do {
         key = Math.random().toFixed(15).substr(5);
       } while (key in filterByKey);
 
       filterByKey[key] = filter;
       keyByFilter[filter.text] = key;
@@ skipping 16 matching lines @@
       let index = list.indexOf(filter);
       if (index >= 0)
         list.splice(index, 1);
       delete knownExceptions[filter.text];
     }
     else
     {
       if (!(filter.text in keyByFilter))
         return;
 
-      if (!("nsIStyleSheetService" in Ci))
+      if (!canUseStylesheets)
       {
         let domains = filter.domains;
         if (!domains)
         {
           domains = Object.create(null);
-          domains[""] = undefined;

[Wladimir Palant, 2015/02/23 19:20:16]

This should be true, not undefined.

[Thomas Greiner, 2015/03/12 16:00:06]

Done.

+          domains[""] = true;
         }
 
         for (let domain in domains)
         {
-          if (domain in filtersByDomain && filter.text in filtersByDomain[domain])
+          if (domain in selectorsByDomain
+            && filter.selector in selectorsByDomain[domain]
+            && !--selectorsByDomain[domain][filter.selector].$length)
           {
-            delete filtersByDomain[domain][filter.text];
-            if (!--filtersByDomain[domain]._length)
-              delete filtersByDomain[domain];
+            delete selectorsByDomain[domain][filter.selector];
+            if (!--selectorsByDomain[domain].$length)
+              delete selectorsByDomain[domain];
           }
         }
       }
 
       let key = keyByFilter[filter.text];
       delete filterByKey[key];
       delete keyByFilter[filter.text];
       ElemHide.isDirty = true;
     }
   },
 
   /**
    * Checks whether an exception rule is registered for a filter on a particular
    * domain.
    */
-  getException: function(/**Filter*/ filter, /**String*/ docDomain) /**ElemHideException*/
-  {
-    if (!(filter.selector in exceptions))
+  getException: function(/**String*/ selector, /**String*/ docDomain) /**ElemHideException*/
+  {
+    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 81 matching lines @@
           }
         }
 
         FilterNotifier.triggerListeners("elemhideupdate");
       }
     }.bind(this));
 
     this._applying = true;
   },
 
-  _generateCSSContent: function()
+  _generateCSSContent: function*()
   {
     // Grouping selectors by domains
     let domains = Object.create(null);
     let hasFilters = false;
     for (let key in filterByKey)
     {
       let filter = filterByKey[key];
       let domain = filter.selectorDomain || "";
 
       let list;
@@ skipping 69 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).

[Wladimir Palant, 2015/02/23 19:20:16]

This comment is no longer correct. Either way, it should say now that this
function cannot be used in Firefox, not merely that it isn't being used.

[Thomas Greiner, 2015/03/12 16:00:06]

Done.

-   */
-  getSelectorsForDomain: function(/**String*/ domain, /**Boolean*/ specificOnly)
-  {

[Wladimir Palant, 2015/02/23 19:20:16]

How about an exception here on Firefox, to explain that this function cannot be
used there?

[Thomas Greiner, 2015/03/12 16:00:06]

Done.

-    let selectors = [];
-    domain = domain.toUpperCase();
-
-    if (!specificOnly)
-    {
-      let filterTexts = filtersByDomain[""];
-      if (filterTexts)
-      {
-        for (let filterText in filterTexts)
-        {
-          if (filterTexts[filterText])
-          {
-            let filter = filterByKey[keyByFilter[filterText]];
-            if (!filter)
-              continue;
-            
-            let selector = filter.selector;
-            if (filter.isActiveOnDomain(docDomain) && !this.getException(selector, docDomain))

[Thomas Greiner, 2015/03/12 16:00:06]

Done.

-              selectors[selectors.length] = selector;
-          }
-        }
-      }
-    }
-
+   * Returns a list of all selectors active on a particular domain (it cannot
+   * be used in Firefox).
+   */
+  getSelectorsForDomain: function(/**String*/ docDomain, /**Boolean*/ specificOnly)
+  {
+    if (canUseStylesheets)
+      throw new Error("Use of getSelectorsForDomain is limited to platforms which cannot inject stylesheets");
+
+    let selectors = Object.create(null);
+    let domain = docDomain.toUpperCase();
     while (true)
     {
-      if (domain && domain in filtersByDomain)
-      {
-        let filterTexts = filtersByDomain[domain];
-        if (filterTexts)

[Wladimir Palant, 2015/02/23 19:20:16]

This check seems pointless - if a property exists then its value can only be an
object, you make sure of that.

[Thomas Greiner, 2015/03/12 16:00:06]

Done.

-        {
-          for (let filterText in filterTexts)
-          {
-            if (filterTexts[filterText])
-            {
-              let filter = filterByKey[keyByFilter[filterText]];

[Wladimir Palant, 2015/02/23 19:20:16]

let filter = Filter.fromText(filterText);

[Thomas Greiner, 2015/03/12 16:00:06]

Done.

-              if (!filter)
-                continue;
-              
-              let selector = filter.selector;
-              if (!this.getException(selector, docDomain))
-                selectors[selectors.length] = selector;

[Wladimir Palant, 2015/02/23 19:20:16]

You meant using selectors.push(), right?

[Thomas Greiner, 2015/03/12 16:00:06]

This turned out to be about ~3ms faster for each call of getSelectorsForDomain()
on my machine. That amounts to an additional ~50ms of total delay of page load
time that I measured on bild.de.

Therefore I chose to go with this instead of `Array.push()`.

-            }
-          }
-        }
-      }
+      if (domain in selectorsByDomain && (domain != "" || !specificOnly))
+      {
+        let domainSelectors = selectorsByDomain[domain];
+        let filterSelectors = Object.getOwnPropertyNames(domainSelectors);
+        for (let filterSelector of filterSelectors)
+        {
+          if (filterSelector == "$length"
+            || filterSelector in selectors
+            || !domainSelectors[filterSelector].isActive
+            || this.getException(filterSelector, docDomain))
+            continue;

[Wladimir Palant, 2015/07/30 11:26:53]

Even with the inconsistent logic changes you are implementing, this is still
wrong. !domainSelectors[filterSelector].isActive shouldn't mean "oh well, maybe
some other domain is allowed" - it's really "oops, should not apply, stop now."
Meaning that ~foo.example.com,example.com##foo really shouldn't apply on
foo.example.com even if that filter is allowed on example.com. Same goes for
exceptions, if we have foo.example.com#@#foo then example.com##foo should *not*
apply on foo.example.com.

I recommend adding unit tests for all the scenarios I mention in the review
comments. I feel like you are consistently forgetting to test the edge cases.

+
+          selectors[filterSelector] = null;
+        }
+      }
+
+      if (domain == "")
+        break;
 
       let nextDot = domain.indexOf(".");
-      if (nextDot < 0)
-        break;
-      domain = domain.substr(nextDot + 1);
-    }

[Wladimir Palant, 2015/02/23 19:20:16]

This logic is wrong, we can have a filter
~subdomain.example.com,example.com##foo. Then
filtersByDomain["subdomain.example.com"][..] will be false,
filtersByDomain["example.com"][..] will be true on the other hand. Your code
currently looks only at the "true" values and will happily apply that filter on
subdomain.example.com as well.

If a filter was "blacklisted" at a subdomain level it should be ignored for a
higher level domain. This means that you will need looking up the value for a
particular filter, so you need another object:

  let result = Object.create(null);
  ...
  if (!(filterText in result))
    result[filterText] = filterTexts[filterText];
  ...
  return Object.keys(result)
               .map(Filter.fromText)
               .filter(f => !this.getException(filter.selector, docDomain))
               .map(f => f.selector);

Note that I'm not actually suggesting using that Array.map and Array.filter
(these are slow), merely explaining what I mean.

Note also handling specificOnly flag should be possible inside the loop - it's
merely about whether to process "" after all the other domains.

[Thomas Greiner, 2015/03/12 16:00:06]

Indeed, that's true. I added the `ignorableFilters` array to track filters that
should be ignored for higher-level domains.

FYI: I've also implemented your suggested approach and on average it turned out
to be even slower than the existing approach (e.g. ~10ms on bild.de).

I created a BitBucket repo to showcase both approaches (including the code for
checking the performance):
- greiner:
https://bitbucket.org/greiner12/elemhide/commits/3b2da2848b3781b954bad806187d...
- trev:
https://bitbucket.org/greiner12/elemhide/commits/b3a6ca182480c03b2bf4e1b3054c...

-
-    return selectors;
+      domain = (nextDot < 0) ? "" : domain.substr(nextDot + 1);
+    }
+
+    return Object.getOwnPropertyNames(selectors);
   }
 };