Issue 6467 - Use Map object for caching filter matches

lib/matcher.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 230 matching lines @@
 /**
  * Combines a matcher for blocking and exception rules, automatically sorts
  * rules into two Matcher instances.
  * @constructor
  * @augments Matcher
  */
 function CombinedMatcher()
 {
   this.blacklist = new Matcher();
   this.whitelist = new Matcher();
-  this.resultCache = Object.create(null);
+  this.resultCache = new Map();
 }
 exports.CombinedMatcher = CombinedMatcher;
 
 /**
  * Maximal number of matching cache entries to be kept
  * @type {number}
  */
 CombinedMatcher.maxCacheEntries = 1000;
 
 CombinedMatcher.prototype =
 {
   /**
    * Matcher for blocking rules.
    * @type {Matcher}
    */
   blacklist: null,
 
   /**
    * Matcher for exception rules.
    * @type {Matcher}
    */
   whitelist: null,
 
   /**
    * Lookup table of previous matchesAny results
-   * @type {Object}
+   * @type {Map.<string,Filter>}
    */
   resultCache: null,
 
   /**
-   * Number of entries in resultCache

[Manish Jethani, 2018/03/10 15:54:37]

There's no need for cacheEntries anymore.

-   * @type {number}
-   */
-  cacheEntries: 0,
-
-  /**
    * @see Matcher#clear
    */
   clear()
   {
     this.blacklist.clear();
     this.whitelist.clear();
-    this.resultCache = Object.create(null);
-    this.cacheEntries = 0;
+    this.resultCache.clear();
   },
 
   /**
    * @see Matcher#add
    * @param {Filter} filter
    */
   add(filter)
   {
     if (filter instanceof WhitelistFilter)
       this.whitelist.add(filter);
     else
       this.blacklist.add(filter);
 
-    if (this.cacheEntries > 0)
-    {
-      this.resultCache = Object.create(null);
-      this.cacheEntries = 0;
-    }
+    this.resultCache.clear();

[Manish Jethani, 2018/03/10 15:54:37]

We don't have to check the size here because we're not creating a new object.

[sergei, 2018/03/12 12:03:00]

I'm pretty sure that now it's even faster, tough if someone wants I will be very
interested in the profiling results.

   },
 
   /**
    * @see Matcher#remove
    * @param {Filter} filter
    */
   remove(filter)
   {
     if (filter instanceof WhitelistFilter)
       this.whitelist.remove(filter);
     else
       this.blacklist.remove(filter);
 
-    if (this.cacheEntries > 0)
-    {
-      this.resultCache = Object.create(null);
-      this.cacheEntries = 0;
-    }
+    this.resultCache.clear();
   },
 
   /**
    * @see Matcher#findKeyword
    * @param {Filter} filter
    * @return {string} keyword
    */
   findKeyword(filter)
   {
     if (filter instanceof WhitelistFilter)
@@ skipping 75 matching lines @@
   },
 
   /**
    * @see Matcher#matchesAny
    * @inheritdoc
    */
   matchesAny(location, typeMask, docDomain, thirdParty, sitekey, specificOnly)
   {
     let key = location + " " + typeMask + " " + docDomain + " " + thirdParty +
       " " + sitekey + " " + specificOnly;
-    if (key in this.resultCache)
-      return this.resultCache[key];
 
-    let result = this.matchesAnyInternal(location, typeMask, docDomain,
-                                         thirdParty, sitekey, specificOnly);
+    let result = this.resultCache.get(key);
+    if (result !== undefined)

[Manish Jethani, 2018/03/10 15:54:37]

Assumption: an entry will never have a value of undefined. I checked and we're
not setting the value to undefined (directly or indirectly) anywhere.

[sergei, 2018/03/12 12:03:01]

AFAIK our coding style says to rather use `typeof result != "undefined"`, though
I find `result !== undefined` better. Let's discuss it in #eyeo-js.

[Manish Jethani, 2018/03/12 13:42:42]

This is really not about coding style. The cache can have a legitimate entry
with a value of null, which is equal to undefined using non-strict equality. If
we want to find out if the cache actually has no entry for the given key, we
have to compare with undefined using strict equality.

The alternative would be to use Map.has but then we'd be doing an extra lookup,
which is what I find is unnecessary.

[sergei, 2018/03/12 17:48:31]

Please take a look around in this file, whenever one could use `!== undefined`,
`typeof ...` is used. In addition typeof does not conflict with having null
values because `typeof null` is "object".

BTW, currently I cannot find that in the coding style but I'm pretty sure that
it was there because I had written the same code several times and several times
someone told me about that.

[Manish Jethani, 2018/03/12 18:59:21]

Done.

[sergei, 2018/03/13 13:56:41]

I still think we should discuss whether we use typeof == "undefined" or !==
undefined in IRC.

[Manish Jethani, 2018/03/13 14:32:49]

Yes, let's have that discussion.

+      return result;
 
-    if (this.cacheEntries >= CombinedMatcher.maxCacheEntries)
-    {
-      this.resultCache = Object.create(null);
-      this.cacheEntries = 0;
-    }
+    result = this.matchesAnyInternal(location, typeMask, docDomain,
+                                     thirdParty, sitekey, specificOnly);
 
-    this.resultCache[key] = result;
-    this.cacheEntries++;
+    if (this.resultCache.size >= CombinedMatcher.maxCacheEntries)

[Manish Jethani, 2018/03/10 15:54:37]

Again, we don't have to create a new object every time we hit the cache size
limit.

+      this.resultCache.clear();
+
+    this.resultCache.set(key, result);
 
     return result;
   }
 };
 
 /**
  * Shared CombinedMatcher instance that should usually be used.
  * @type {CombinedMatcher}
  */
 exports.defaultMatcher = new CombinedMatcher();