Issues regarding some cache implementations

[Yomguithereal]

Hello @dominictarr and @avoidwork. By running some tests today I think I stumbled upon some issues with the tiny-lru and lru_cache implementations that may explain why they are wildly better at evicts than the other libraries.

If you replace the worker's code by this one (which is the same as the current one but with some more information logged about the beforementioned libraries):

'use strict';

const precise = require('precise'),
  retsu = require('retsu'),
  LRUCache = require('lru_cache').LRUCache,
  Simple = require('simple-lru-cache'),
  Fast = require('lru-fast').LRUCache,
  QuickLRU = require('quick-lru'),
  Modern = require('modern-lru'),
  hyperlru = require('hyperlru'),
  {LRUMap} = require('lru_map'),
  MKC = require('mkc'),
  hyperlruObject = hyperlru(require('hyperlru-object')),
  hyperlruMap = hyperlru(require('hyperlru-map')),
  caches = {
    'lru-cache': () => require('lru-cache')(),
    'lru-fast': n => new Fast(n),
    'js-lru': n => new LRUMap(n),
    'modern-lru': n => new Modernx(n),
    'quick-lru': maxSize => new QuickLRU({maxSize}),
    'secondary-cache': require('secondary-cache'),
    'simple-lru-cache': maxSize => new Simple({maxSize}),
    'tiny-lru': require('tiny-lru'),
    hashlru: require('hashlru'),
    'hyperlru-object': max => hyperlruObject({max}),
    'hyperlru-map': max => hyperlruMap({max}),
    lru_cache: n => new LRUCache(n),
    lru: require('lru'),
    mkc: max => new MKC({max})
  },
  num = 2e5,
  evicts = num * 2,
  times = 5,
  x = 1e6;

self.onmessage = function (ev) {
  const id = ev.data,
    lru = caches[id](num),
    time = {
      'set': [],
      get1: [],
      update: [],
      get2: [],
      evict: []
    },
    results = {
      name: id,
      'set': 0,
      get1: 0,
      update: 0,
      get2: 0,
      evict: 0,
    };

  let n = -1;

  while (++n < times) {
    let stimer = precise().start();
    for (let i = 0; i < num; i++) lru.set(i, Math.random());
    time.set.push(stimer.stop().diff() / x);

    let gtimer = precise().start();
    for (let i = 0; i < num; i++) lru.get(i);
    time.get1.push(gtimer.stop().diff() / x);

    let utimer = precise().start();
    for (let i = 0; i < num; i++) lru.set(i, Math.random());
    time.update.push(utimer.stop().diff() / x);

    const g2timer = precise().start();
    for (let i = 0; i < num; i++) lru.get(i);
    time.get2.push(g2timer.stop().diff() / x);

    let etimer = precise().start();
    for (let i = num; i < evicts; i++) lru.set(i, Math.random());
    time.evict.push(etimer.stop().diff() / x);
  }

  if (id === 'tiny-lru')
    console.log('Size of cache [tiny-lru]', Object.keys(lru.cache).length);

  if (id === 'lru_cache')
    console.log('Size of cache [lru_cache]', Object.keys(lru._keymap).length);

  ['set', 'get1', 'update', 'get2', 'evict'].forEach(i => {
    results[i] = Number((num / retsu.median(time[i]).toFixed(2)).toFixed(0));
  });

  postMessage(JSON.stringify(results));
};

It will log the following:

Size of cache [lru_cache] 400000
Size of cache [tiny-lru] 400000

They both seem, at the end of the benchmark, to have an actual index size which is exactly twice the desired capacity 2e5 (200000).

What's more, if you log the number of times they actually delete from the cache object (using the delete keyword) you'll find that lru_cache deletes way less than other libs and that tiny-lru only actually deletes once. This is why they seem way faster.

For lru_cache I think the erroneous branch is this one:

// ... in the #.put method
  if (this.size === this.limit) {
    // we hit the limit -- remove the head
    return this.shift() // this does a this.size-- somewhere
  } else {
    // increase the size counter
    this.size++
  }
// ...

Because the size is decreased when shifting but not increased back there is a capacity issue that lets the index grow in memory.

For tiny-lru I am unsure where the issue seems to be but I can investigate further if you want.

[avoidwork]

thanks! i'll look into tiny-lru this evening.

[avoidwork]

@Yomguithereal great find! tiny-lru was totally cheating due to a bad line of code I wrote on a really long flight.

Re-opening due to the auto-close of a merge referencing the issue.

[Yomguithereal]

Should we withdraw lru_cache until it is fixed? I think I'll try to submit a PR on the lib's repo if I can find some time.

[avoidwork]

¯\_(ツ)_/¯ could be legit; i haven't read the code. in #20 we've found interesting problem with mkc such that it can't complete a more random benchmark. seems a little nondeterministic.

[Yomguithereal]

lru_cache is definitely leaking memory and not deleting keys when it should. Will try a PR to fix the issue soon.

[Yomguithereal]

Related PR opened here.

[ChrisCinelli]

Some implementations are definetely buggy. Some implementations also offer more features. For example, some have a maxAge expiration feature that may add some overhead Different versions of the same package have also very different results.

I suggest to:

• Do some basic integrity checks
• Report the version of the package being tested
• Report the node version being used
• Report the configuration (hardware and software) of the machine that run tests.

There is also a problem with the benchmark algorithm. But I will write about it in another issue

[avoidwork]

Funny thing about the hardware & software... it's nearly impossible to get a consistent run without an isolated machine solely for this test. Comparing intel to intel cpus is pretty consistent, but windows to a *nix is really different, and intel to amd is really different, and even just multiple back to back can be significantly different based on external factors present on the machine (see https://github.com/dominictarr/bench-lru/pull/28).

The benchmark has been updated to minimize bottlenecking while timing things, and the results are significantly cleaner now.