Use Map object for caching filter matches

[mjethani]

Background

Using a Map object for maintaining a URL-to-filter cache in CombinedMatcher would be significantly better in terms of performance. It also makes the code easier to read.

Here's a simple test:

function foo()
{
  const getRandom = n => Math.floor(Math.random() * n).toString(2);

  let cache = Object.create(null);

  for (let i = 0; i < 1000000; i++)
    cache[getRandom(1000)] = Math.random();

  console.log(Object.keys(cache).length + " entries");

  let lookupKeys = new Array(1000000);
  for (let i = 0; i < lookupKeys.length; i++)
    lookupKeys[i] = getRandom(1000000);

  let s = +new Date();
  let n = 0;
  for (let i = 0; i < lookupKeys.length; i++)
  {
    let key = lookupKeys[i];
    if (key in cache)
      n++;
  }

  console.log(n + " hits");

  return +new Date() - s;
}

This creates a cache of ~600-650 entries and then tries a million random matches. It gets about the same number of hits out of a million. We are mainly testing the speed of key in cache here.

let n = 0;
for (let i = 0; i < 10; i++)
  n += foo();
console.log(n + " milliseconds");

On my machine this takes ~4 seconds on Node.js (V8).

Now if we change it to the following:

function foo()
{
  const getRandom = n => Math.floor(Math.random() * n).toString(2);

  let cache = new Map();

  for (let i = 0; i < 1000000; i++)
    cache.set(getRandom(1000), Math.random());

  console.log(cache.size + " entries");

  let lookupKeys = new Array(1000000);
  for (let i = 0; i < lookupKeys.length; i++)
    lookupKeys[i] = getRandom(1000000);

  let s = +new Date();
  let n = 0;
  for (let i = 0; i < lookupKeys.length; i++)
  {
    let key = lookupKeys[i];
    if (cache.has(key))
      n++;
  }

  console.log(n + " hits");

  return +new Date() - s;
}

On my machine this takes ~900 milliseconds.

We can also test the speed of setting the value, which I find to also be faster for a Map object.

Lookups are significantly faster so that the following code:

if (key in cache)
  return cache[key];

Can be changed to:

let value = cache.get(key);
if (value !== undefined)
  return value;

This saves us an extra lookup if we only assume that there will never be an entry with a value of undefined.

lib/matcher.js already uses Map objects for other things.

What to change

Change CombinedMatcher.resultCache to be of type Map.<string,Filter> and use the aforementioned single lookup optimization.

[abpbot]

A commit referencing this issue has landed:
​Issue 6467 - Use Map object for caching filter matches