Issue 235 - Improved performance of ElemHide.getSelectorsForDomain()

lib/elemHide.js

Index: lib/elemHide.js
===================================================================
--- a/lib/elemHide.js
+++ b/lib/elemHide.js
@@ -59,6 +59,12 @@
 let styleURL = null;
 
 /**
+ * Lookup table, blocking filters by domain which they are applied to
+ * @type Object
+ */
+let filtersByDomain = Object.create(null);
+
+/**
  * Element hiding component
  * @class
  */
@@ -105,6 +111,7 @@
     keyByFilter = Object.create(null);
     knownExceptions = Object.create(null);
     exceptions = Object.create(null);
+    filtersByDomain = Object.create(null);
     ElemHide.isDirty = false;
     ElemHide.unapply();
   },
@@ -131,6 +138,28 @@
       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.

+      {
+        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.

+        }
+
+        for (let domain in domains)
+        {
+          if (!(domain in filtersByDomain))
+          {
+            filtersByDomain[domain] = Object.create(null);
+            filtersByDomain[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 key;
       do {
         key = Math.random().toFixed(15).substr(5);
@@ -164,6 +193,26 @@
       if (!(filter.text in keyByFilter))
         return;
 
+      if (!("nsIStyleSheetService" in Ci))
+      {
+        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.

+        }
+
+        for (let domain in domains)
+        {
+          if (domain in filtersByDomain && filter.text in filtersByDomain[domain])
+          {
+            delete filtersByDomain[domain][filter.text];
+            if (!--filtersByDomain[domain]._length)
+              delete filtersByDomain[domain];
+          }
+        }
+      }
+
       let key = keyByFilter[filter.text];
       delete filterByKey[key];
       delete keyByFilter[filter.text];
@@ -377,16 +426,59 @@
    */
   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 result = [];
-    for (let key in filterByKey)
+    let selectors = [];
+    domain = domain.toUpperCase();
+
+    if (!specificOnly)
     {
-      let filter = filterByKey[key];
-      if (specificOnly && (!filter.domains || filter.domains[""]))
-        continue;
+      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;
+          }
+        }
+      }
+    }
 
-      if (filter.isActiveOnDomain(domain) && !this.getException(filter, domain))
-        result.push(filter.selector);
+    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()`.

+            }
+          }
+        }
+      }
+
+      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 result;
+
+    return selectors;
   }
 };