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
@@ skipping 28 matching lines @@
 /**
  * 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)>>}
  */
 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 = Object.create(null);
+let filterKeyBySelector = new Map();
 
 /**
  * This array caches the keys of filterKeyBySelector table (selectors which
  * unconditionally apply on all domains). It will be null if the cache needs to
  * be rebuilt.
  */
 let unconditionalSelectors = null;
 
 /**
  * This array caches the values of filterKeyBySelector table (filterIds for
  * selectors which unconditionally apply on all domains). It will be null if the
  * 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.

- * @type {Object}
+ * @type {Set.<string>}
  */
-let knownExceptions = Object.create(null);
+let knownExceptions = new Set();
 
 /**
  * Lookup table, lists of element hiding exceptions by selector
- * @type {Object}
+ * @type {Map.<string,Filter>}
  */
-let exceptions = Object.create(null);
+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 = [];
-    keyByFilter = new Map();
-    filtersByDomain = new Map();
-    filterKeyBySelector = Object.create(null);
     unconditionalSelectors = unconditionalFilterKeys = null;
-    knownExceptions = Object.create(null);
-    exceptions = Object.create(null);
     FilterNotifier.emit("elemhideupdate");
   },
 
   _addToFiltersByDomain(key, filter)
   {
     let domains = filter.domains || defaultDomains;
     for (let [domain, isIncluded] of domains)
     {
       let filters = filtersByDomain.get(domain);
       if (!filters)
         filtersByDomain.set(domain, filters = new Map());
       filters.set(key, isIncluded ? filter : false);
     }
   },
 
   /**
    * Add a new element hiding filter
    * @param {ElemHideFilter} filter
    */
   add(filter)
   {
     if (filter instanceof ElemHideException)
     {
-      if (filter.text in knownExceptions)
+      if (knownExceptions.has(filter.text))
         return;
 
       let {selector} = filter;
-      if (!(selector in exceptions))
-        exceptions[selector] = [];
-      exceptions[selector].push(filter);
+      let list = exceptions.get(selector);
+      if (list)
+        list.push(filter);
+      else
+        exceptions.set(selector, [filter]);
 
       // If this is the first exception for a previously unconditionally
       // applied element hiding selector we need to take care to update the
       // lookups.
-      let filterKey = filterKeyBySelector[selector];
+      let filterKey = filterKeyBySelector.get(selector);
       if (typeof filterKey != "undefined")
       {
         this._addToFiltersByDomain(filterKey, filterByKey[filterKey]);
-        delete filterKeyBySelector[selector];
+        filterKeyBySelector.delete(selector);
         unconditionalSelectors = unconditionalFilterKeys = null;
       }
 
-      knownExceptions[filter.text] = true;
+      knownExceptions.add(filter.text);
     }
     else
     {
       if (keyByFilter.has(filter))
         return;
 
       let key = filterByKey.push(filter) - 1;
       keyByFilter.set(filter, key);
 
-      if (!(filter.domains || filter.selector in exceptions))
+      if (!(filter.domains || exceptions.has(filter.selector)))
       {
         // The new filter's selector is unconditionally applied to all domains
-        filterKeyBySelector[filter.selector] = key;
+        filterKeyBySelector.set(filter.selector, key);
         unconditionalSelectors = unconditionalFilterKeys = null;
       }
       else
       {
         // The new filter's selector only applies to some domains
         this._addToFiltersByDomain(key, filter);
       }
     }
 
     FilterNotifier.emit("elemhideupdate");
   },
 
   _removeFilterKey(key, filter)
   {
-    if (filterKeyBySelector[filter.selector] == key)
+    if (filterKeyBySelector.get(filter.selector) == key)
     {
-      delete filterKeyBySelector[filter.selector];
+      filterKeyBySelector.delete(filter.selector);
       unconditionalSelectors = unconditionalFilterKeys = null;
       return;
     }
 
     // We haven't found this filter in unconditional filters, look in
     // filtersByDomain.
     let domains = filter.domains || defaultDomains;
     for (let domain of domains.keys())
     {
       let filters = filtersByDomain.get(domain);
       if (filters)
         filters.delete(key);
     }
   },
 
   /**
    * Removes an element hiding filter
    * @param {ElemHideFilter} filter
    */
   remove(filter)
   {
     if (filter instanceof ElemHideException)
     {
-      if (!(filter.text in knownExceptions))
+      if (!knownExceptions.has(filter.text))
         return;
 
-      let list = exceptions[filter.selector];
+      let list = exceptions.get(filter.selector);
       let index = list.indexOf(filter);
       if (index >= 0)
         list.splice(index, 1);
-      delete knownExceptions[filter.text];
+      knownExceptions.delete(filter.text);
     }
     else
     {
       let key = keyByFilter.get(filter);
       if (typeof key == "undefined")
         return;
 
       delete filterByKey[key];
       keyByFilter.delete(filter);
       this._removeFilterKey(key, filter);
     }
 
     FilterNotifier.emit("elemhideupdate");
   },
 
   /**
    * 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)
   {
-    if (!(filter.selector in exceptions))
+    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;
 
-    let list = exceptions[filter.selector];
     for (let i = list.length - 1; i >= 0; i--)
     {
       if (list[i].isActiveOnDomain(docDomain))
         return list[i];
     }
 
     return null;
   },
 
   /**
@@ skipping 32 matching lines @@
     return domains;
   },
 
   /**
    * Returns a list of selectors that apply on each website unconditionally.
    * @returns {string[]}
    */
   getUnconditionalSelectors()
   {
     if (!unconditionalSelectors)
-      unconditionalSelectors = Object.keys(filterKeyBySelector);
+      unconditionalSelectors = [...filterKeyBySelector.keys()];
     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.

-    {
-      let selectors = this.getUnconditionalSelectors();
-      unconditionalFilterKeys = [];
-      for (let selector of selectors)
-        unconditionalFilterKeys.push(filterKeyBySelector[selector]);
-    }
+      unconditionalFilterKeys = [...filterKeyBySelector.values()];
     return unconditionalFilterKeys.slice();
   },
 
 
   /**
    * Constant used by getSelectorsForDomain to return all selectors applying to
    * a particular hostname.
    */
   ALL_MATCHING: 0,
 
@@ skipping 32 matching lines @@
     if (typeof criteria == "undefined")
       criteria = ElemHide.ALL_MATCHING;
     if (criteria < ElemHide.NO_UNCONDITIONAL)
     {
       selectors = this.getUnconditionalSelectors();
       if (provideFilterKeys)
         filterKeys = this.getUnconditionalFilterKeys();
     }
 
     let specificOnly = (criteria >= ElemHide.SPECIFIC_ONLY);
-    let seenFilters = Object.create(null);
+    let seenFilters = new Set();
     let currentDomain = domain ? domain.toUpperCase() : "";
     while (true)
     {
       if (specificOnly && currentDomain == "")
         break;
 
       let filters = filtersByDomain.get(currentDomain);
       if (filters)
       {
         for (let [filterKey, filter] of filters)
         {
-          if (filterKey in seenFilters)
+          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[filterKey] = true;
+          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;
   }
 };