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 = [];
-
-/**
- * Indicates that the unconditionalSelectors Array needs to be regenerated.
- */
-var unconditionalSelectorsDirty = false;
+ * 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 = [];
-    unconditionalSelectorsDirty = false;
+    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];
-          unconditionalSelectorsDirty = true;
+          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)
       {
         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];
-            unconditionalSelectorsDirty = true;
+            unconditionalSelectors = null;
           }
         }
         else
         {
           // The new filter's selector only applies to some domains
           this._addToFiltersByDomain(filter);
         }
       }
 
       ElemHide.isDirty = true;
@@ skipping 33 matching lines @@
         if (filters)
         {
           if (filters.length > 1)
           {
             let index = filters.indexOf(filter);
             filters.splice(index, 1);
           }
           else
           {
             delete filtersBySelector[filter.selector];
-            unconditionalSelectorsDirty = true;
+            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!");
 
-    if (unconditionalSelectorsDirty)
-    {
+    if (!unconditionalSelectors)
       unconditionalSelectors = Object.keys(filtersBySelector);
-      unconditionalSelectorsDirty = false;
-    }
     let selectors = specificOnly ? [] : unconditionalSelectors.slice();

[Sebastian Noack, 2016/05/25 07:30:49]

You can skip the unconditionalSelectorsDirty logic in the specificOnly case:

let selectors;
if (specificOnly)
{
  selectors = [];
}
else
{
  if (unconditionalSelectorsDirty)
  {
     unconditionalSelectors = Object.keys(filtersBySelector);
     unconditionalSelectorsDirty = false;
  }
  selectors = unconditionalSelectors.slice();
}

[Sebastian Noack, 2016/05/25 07:30:49]

Also note that if you'd call Object.keys() unconditionally, you can avoid the
isDirty logic and don't have to copy the list. But that would still be notably
slower? Just want to make sure, since the way you did it initally, the array was
copied anyway by Array.concat().

[Sebastian Noack, 2016/05/25 07:40:26]

One more thing, if we need that is dirty logic, how about just setting
unconditionalSelectors to null instead adding yet another global variable? That
way the code is a little shorter, and we won't leak outdated data.

[kzar, 2016/05/25 08:05:19]

Done.

[kzar, 2016/05/25 08:05:19]

I know I could skip restoring unconditionalSelectors if specificOnly is true but
there's not much point.

[kzar, 2016/05/25 08:05:19]

Yep, just double checked and it's still quite a bit slower using Object.keys()
every time even without the concat.

[Sebastian Noack, 2016/05/25 08:11:56]

Besides a speedup in specificOnly case which might be negligible, it also
improves the code locality and makes the purpose of that logic slightly easier
to understand IMO. Also it will be even shorter now where you only have one
variable.

[kzar, 2016/05/25 08:29:04]

I disagree on this one, but I see your point. I'll leave it up to Wladimir to
decide.

[Wladimir Palant, 2016/05/25 10:43:03]

Frankly, while I can see the arguments towards only setting
unconditionalSelectors when needed, it's not really important enough to be
changed. The flow won't necessarily become more readable if we do, and it's
already fine as is.

 
     let seenFilters = Object.create(null);
     let currentDomain = domain ? domain.toUpperCase() : "";
     while (true)
     {
       if (specificOnly && currentDomain == "")
         break;
 
       let filters = filtersByDomain[currentDomain];
       if (filters)
@@ skipping 13 matching lines @@
       if (currentDomain == "")
         break;
 
       let nextDot = currentDomain.indexOf(".");
       currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
 
     return selectors;
   }
 };