Issue 6559 - Use maps and sets where appropriate

lib/elemHide.js

 /*
  * This file is part of Adblock Plus <https://adblockplus.org/>,
  * Copyright (C) 2006-present 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
  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * GNU General Public License for more details.
  *
  * You should have received a copy of the GNU General Public License
  * along with Adblock Plus.  If not, see <http://www.gnu.org/licenses/>.
  */
 
 "use strict";
 
 /**
  * @fileOverview Element hiding implementation.
  */
 
 const {ElemHideException} = require("./filterClasses");
 const {FilterNotifier} = require("./filterNotifier");
 
 /**
  * Lookup table, filters by their associated key
- * @type {Object}
+ * @type {Filter[]}
  */
 let filterByKey = [];
 
 /**
  * Lookup table, keys of the filters by filter
- * @type {Map.<Filter,string>}
+ * @type {Map.<Filter,number>}
  */
 let keyByFilter = new Map();
 
 /**
  * Nested lookup table, filter (or false if inactive) by filter key by domain.
  * (Only contains filters that aren't unconditionally matched for all domains.)
- * @type {Map.<string,Map.<string,(Filter|boolean)>>}
+ * @type {Map.<string,Map.<number,(Filter|boolean)>>}
  */
 let filtersByDomain = new Map();
 
 /**
  * Lookup table, filter key by selector. (Only used for selectors that are
  * unconditionally matched for all domains.)
  * @type {Map.<string,number>}
  */
 let filterKeyBySelector = new Map();
 
@@ skipping 10 matching lines @@
  * cache needs to be rebuilt.
  */
 let unconditionalFilterKeys = null;
 
 /**
  * Object to be used instead when a filter has a blank domains property.
  */
 let defaultDomains = new Map([["", true]]);
 
 /**
- * Lookup table, keys are known element hiding exceptions

[kzar, 2018/04/06 11:42:20]

Nit: This comment reads a bit weirdly now that it's a Set IMO

[Manish Jethani, 2018/04/06 12:44:09]

Done.

+ * Set containing known element hiding exceptions
  * @type {Set.<string>}
  */
 let knownExceptions = new Set();
 
 /**
  * Lookup table, lists of element hiding exceptions by selector
  * @type {Map.<string,Filter>}
  */
 let exceptions = new Map();
 
 /**
  * Container for element hiding filters
  * @class
  */
 let ElemHide = exports.ElemHide = {
   /**
    * Removes all known filters
    */
   clear()
   {
     for (let collection of [keyByFilter, filtersByDomain, filterKeyBySelector,

[Manish Jethani, 2018/04/06 05:36:16]

Note that there's no need to create new objects for each of these, we can just
call the clear method to start over.

                             knownExceptions, exceptions])
     {
       collection.clear();
     }
     filterByKey = [];
     unconditionalSelectors = unconditionalFilterKeys = null;
     FilterNotifier.emit("elemhideupdate");
   },
 
   _addToFiltersByDomain(key, filter)
@@ skipping 116 matching lines @@
 
   /**
    * Checks whether an exception rule is registered for a filter on a particular
    * domain.
    * @param {Filter} filter
    * @param {string} docDomain
    * @return {ElemHideException}
    */
   getException(filter, docDomain)
   {
     let list = exceptions.get(filter.selector);

[Manish Jethani, 2018/04/06 05:36:16]

If list is falsy we know it's undefined, since we only ever set it to an array.

[kzar, 2018/04/06 11:42:20]

Acknowledged.

     if (!list)
       return null;
 
     for (let i = list.length - 1; i >= 0; i--)
     {
       if (list[i].isActiveOnDomain(docDomain))
         return list[i];
     }
 
     return null;
@@ skipping 46 matching lines @@
     return unconditionalSelectors.slice();
   },
 
   /**
    * Returns a list of filter keys for selectors which apply to all websites
    * without exception.
    * @returns {number[]}
    */
   getUnconditionalFilterKeys()
   {
     if (!unconditionalFilterKeys)

[Manish Jethani, 2018/04/06 05:36:16]

Essentially we're getting the values of filterKeyBySelector, we can just use the
values method here.

[kzar, 2018/04/06 11:42:20]

Previously we were caching though.

But come to think of it I don't think the provideFilterKeys parameter is used
any more since we switched to Firefox WebExt. I just had a look through the
codebases to confirm as well. If so we can remove this anyway. Could you double
check too?

[Manish Jethani, 2018/04/06 12:44:09]

So it looks like we could do away with the concept of filter keys altogether?
Now since we have maps/sets we don't need to generate keys, we can directly look
up by the filter in a map/set. Anyway, all of this should be a separate patch.

Yes I checked, at least provideFilterKeys isn't used anywhere.

[kzar, 2018/04/06 13:07:54]

Cool, so looks like we could remove that parameter and associated stuff like
getUncoditionalFilterKeys. 
Good point, I think you might be right. I'll open an issue for that and get a
review together, unless you mind?
Yea, agreed. But in that case please could you put the logic of
getUncoditionalFilterKeys back to how it was (except where it needed to be
different since Objects were replaced with Maps/Sets).

[Manish Jethani, 2018/04/06 13:34:37]

Sure, go ahead.
Done.

-      unconditionalFilterKeys = [...filterKeyBySelector.values()];
+    {
+      let selectors = this.getUnconditionalSelectors();
+      unconditionalFilterKeys = [];
+      for (let selector of selectors)
+        unconditionalFilterKeys.push(filterKeyBySelector.get(selector));
+    }
     return unconditionalFilterKeys.slice();
   },
 
 
   /**
    * Constant used by getSelectorsForDomain to return all selectors applying to
    * a particular hostname.
    */
   ALL_MATCHING: 0,
 
@@ skipping 44 matching lines @@
     while (true)
     {
       if (specificOnly && currentDomain == "")
         break;
 
       let filters = filtersByDomain.get(currentDomain);
       if (filters)
       {
         for (let [filterKey, filter] of filters)
         {
           if (seenFilters.has(filterKey))

[kzar, 2018/04/06 11:42:20]

This is a hotspot, we spent quite some time getting it to run faster. So please
be careful to test your changes didn't slow things down. Looking through my
notes one (simplistic) test we used was this:

(function() {
  var start = performance.now();
  for (var i = 0; i < 1000; i += 1)
    ElemHide.getSelectorsForDomain("www.extremetech.com");
  return performance.now() - start;
}());


(I'm not against the change, I think it might even speed things up. At the time
IIRC we wanted to use a Map / Set but coudn't due to the old Safari versions we
supported.)

[Manish Jethani, 2018/04/06 12:44:09]

I ran this particular test and it's 2s vs 1.6s on Chrome and 6s vs. 3.8s on
Firefox. On both platforms the new code performs faster.

[kzar, 2018/04/06 13:07:54]

Acknowledged.

[Manish Jethani, 2018/04/06 13:44:11]

BTW I tried replacing `filterKey in seenFilters` with
`[].hasOwnProperty.call(seenFilters, filterKey)` and then just
`seenFilters[filterKey]`, in the latter case the performance comes close to Set,
but Set still performs the best.

             continue;
           seenFilters.add(filterKey);
 
           if (filter && !this.getException(filter, domain))
           {
             selectors.push(filter.selector);
             // It is faster to always push the key, even if not required.
             filterKeys.push(filterKey);
           }
         }
       }
 
       if (currentDomain == "")
         break;
 
       let nextDot = currentDomain.indexOf(".");
       currentDomain = nextDot == -1 ? "" : currentDomain.substr(nextDot + 1);
     }
 
     if (provideFilterKeys)
       return [selectors, filterKeys];
     return selectors;
   }
 };