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 43 matching lines @@
  */
 var filtersByDomain = Object.create(null);
 
 /**
  * Lookup table, filters by selector. (Only contains filters that have a
  * selector that is unconditionally matched for all domains.)
  */
 var filtersBySelector = Object.create(null);
 
 /**
- * Array of selectors which unconditionally apply to all domains.
- */
-var unconditionalSelectors = [];
+ * This array caches the keys of filtersBySelector table (selectors which
+ * unconditionally apply on all domains). It will be null if the cache needs to
+ * be rebuilt.
+ */
+var unconditionalSelectors = 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 49 matching lines @@
 
   /**
    * Removes all known filters
    */
   clear: function()
   {
     filterByKey = [];
     keyByFilter = Object.create(null);
     filtersByDomain = Object.create(null);
     filtersBySelector = Object.create(null);
-    unconditionalSelectors = [];
+    unconditionalSelectors = null;
     knownExceptions = Object.create(null);
     exceptions = Object.create(null);
     ElemHide.isDirty = false;
     ElemHide.unapply();
   },
 
   _addToFiltersByDomain: function(filter)
   {
     let key = keyByFilter[filter.text];
     let domains = filter.domains || defaultDomains;
@@ skipping 30 matching lines @@
       {
         // If this is the first exception for a previously unconditionally
         // applied element hiding selector we need to take care to update the
         // lookups.
         let unconditionalFilters = filtersBySelector[selector];
         if (unconditionalFilters)
         {
           for (let f of unconditionalFilters)
             this._addToFiltersByDomain(f);
           delete filtersBySelector[selector];
-          let index = unconditionalSelectors.indexOf(selector);
-          unconditionalSelectors.splice(index, 1);
+          unconditionalSelectors = null;
         }
       }
 
       knownExceptions[filter.text] = true;
     }
     else
     {
       if (filter.text in keyByFilter)
         return;
 
       let key = filterByKey.push(filter) - 1;
       keyByFilter[filter.text] = key;
 
       if (usingGetSelectorsForDomain)
       {
-        // The new filter's selector is unconditionally applied to all domains

[Wladimir Palant, 2016/05/24 15:16:18]

This comment belongs inside the if block since it only applies to one branch of
it.

[kzar, 2016/05/25 05:12:24]

Done.

-        if (!filter.domains && !exceptions[filter.selector])

[Wladimir Palant, 2016/05/24 15:16:19]

We don't really care about the value of exceptions[filter.selector] so I'd
prefer !(filter.selector in exceptions).

[kzar, 2016/05/25 05:12:24]

Done.

-        {
+        if (!(filter.domains || filter.selector in exceptions))
+        {
+          // The new filter's selector is unconditionally applied to all domains
           let filters = filtersBySelector[filter.selector];
           if (filters)
           {
             filters.push(filter);
           }
           else
           {
             filtersBySelector[filter.selector] = [filter];
-            unconditionalSelectors.push(filter.selector);
-          }
-        }
-        // The new filter's selector only applies to some domains

[Wladimir Palant, 2016/05/24 15:16:18]

Same here, comment inside the block please.

[kzar, 2016/05/25 05:12:24]

Done.

+            unconditionalSelectors = null;
+          }
+        }
         else
         {
+          // The new filter's selector only applies to some domains
           this._addToFiltersByDomain(filter);
         }
       }
 
       ElemHide.isDirty = true;
     }
   },
 
   /**
    * Removes an element hiding filter
@@ skipping 15 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 (usingGetSelectorsForDomain)

[kzar, 2016/05/24 14:45:22]

I'm worried about the performance of ElemHide.remove now. There is a sometimes
noticeable pause when disabling EasyList. I've tried making
unconditioanlSelectors a lookup, which helps a bit but that slows down
getSelectorsForDomain lots as it then has to call
Object.keys(unconditioanlSelectors) every time.

Any ideas?

[Wladimir Palant, 2016/05/24 15:16:19]

A remove isn't a very common operation. Did you measure it, how long does it
take?

In theory, we could make unconditionalSelectors a sorted list which would allow
much faster searches. However, this will slow down insert operations
considerably (meaning that it makes ElemHide.add() slower).

[kzar, 2016/05/24 17:47:09]

Yea, it's pretty bad - something like 2325ms spent in elemHide.remove when
EasyList is disabled.

I guess you're right that this is kind of an usual operation. Also I realised
the speed is really not too important, the problem is that there is a visible
delay for the user. How about we wrap the subscription toggling code in
adblockplusui/messageResponder.js in a window.setTimeout of 0ms? Unless the user
clicks EasyList on and off repeatedly this fixes the sluggishness in the
interface when removing / disabling a big subscription.

[kzar, 2016/05/24 17:52:12]

Another idea, maybe crazy... removing is expensive but adding is much cheaper.
Perhaps in some situations we should remove everything and then add back in the
filters we need?

[kzar, 2016/05/25 04:57:16]

With Patch Set 5 ElemHide.remove is now down to about 330ms when disabling
EasyList. There is still a pause sometimes but it's far less noticeable.

       {
         let filters = filtersBySelector[filter.selector];
         if (filters)
         {
           if (filters.length > 1)
           {
             let index = filters.indexOf(filter);
             filters.splice(index, 1);
           }
           else
           {
             delete filtersBySelector[filter.selector];
-            let index = unconditionalSelectors.indexOf(filter.selector);
-            unconditionalSelectors.splice(index, 1);
+            unconditionalSelectors = null;
           }
         }
         else
         {
           let domains = filter.domains || defaultDomains;
           for (let domain in domains)
           {
             let filters = filtersByDomain[domain];
             if (filters)
               delete filters[key];
@@ skipping 209 matching lines @@
 
   /**
    * Returns a list of all selectors active on a particular domain, must not be
    * used in Firefox (when usingGetSelectorsForDomain is false).
    */
   getSelectorsForDomain: function(/**String*/ domain, /**Boolean*/ specificOnly)
   {
     if (!usingGetSelectorsForDomain)
       throw new Error("getSelectorsForDomain can not be used in Firefox!");
 
-    let selectors = [];
+    if (!unconditionalSelectors)
+      unconditionalSelectors = Object.keys(filtersBySelector);
+    let selectors = specificOnly ? [] : unconditionalSelectors.slice();
 
     let seenFilters = Object.create(null);
     let currentDomain = domain ? domain.toUpperCase() : "";
     while (true)
     {
       if (specificOnly && currentDomain == "")
         break;
 
       let filters = filtersByDomain[currentDomain];
       if (filters)
@@ skipping 10 matching lines @@
         }
       }
 
       if (currentDomain == "")
         break;
 
       let nextDot = currentDomain.indexOf(".");
       currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
 
-    if (specificOnly)

[Sebastian Noack, 2016/05/24 15:20:07]

Why do you still account for specificOnly inside the loop? As far as I
understand the logic, we can bail out now as soon as there is no next dot
regardless of specificOnly.

[Wladimir Palant, 2016/05/24 15:26:06]

Not all generic filters are in unconditionalSelectors - some have exception
rules applying to them, others exclude particular domains (like
~example.com##foo).

-      return selectors;
-    else

[Sebastian Noack, 2016/05/24 15:20:07]

Nit: extraneous else

[kzar, 2016/05/25 05:12:24]

Done.

-      return unconditionalSelectors.concat(selectors);

[Wladimir Palant, 2016/05/24 15:16:19]

I think we should avoid concatenating two arrays here, just initialize the
selectors array correctly.

  let selectors = specificOnly ? [] : unconditionalSelectors.slice();

[kzar, 2016/05/25 05:12:24]

Done.

+    return selectors;
   }
 };