Performance regression in 4.x with objects paired with delete

[mhart]

This spun out from exploring isaacs/node-lru-cache#54

It may very well be a v8 issue, but I haven't been able to find the right circumstances to reproduce due to v8's lack of setImmediate

When running the following program in 4.x (on Linux or Mac), there's a huge slowdown around iteration 92000 that does not occur in 3.x or below:

var lruCache = Object.create(null)
var i = 0
var last = Date.now()
var max = 4097 // lowering to 4096 fixes the problem

function next() {
  lruCache[i] = true
  if (i >= max) delete lruCache[i - max]

  i++

  if (i > 200000) return

  if ((i % 2000) === 0) {
    var now = Date.now()
    console.log({
      duration: now - last,
      iteration: i,
    })
    last = now
  }

  setImmediate(next)
}

next()

So in 4.x the output looks like:

$ node test.js
{ duration: 6, iteration: 2000 }
{ duration: 22, iteration: 4000 }
{ duration: 6, iteration: 6000 }
{ duration: 4, iteration: 8000 }
{ duration: 3, iteration: 10000 }
...
{ duration: 5, iteration: 90000 }
{ duration: 3, iteration: 92000 }
{ duration: 4870, iteration: 94000 }
{ duration: 5151, iteration: 96000 }
{ duration: 5336, iteration: 98000 }
{ duration: 782, iteration: 100000 }
{ duration: 7, iteration: 102000 }
{ duration: 5, iteration: 104000 }
...
{ duration: 8, iteration: 200000 }

Using 3.3.1 or lowering max to 4096 looks like:

{ duration: 7, iteration: 2000 }
{ duration: 18, iteration: 4000 }
{ duration: 9, iteration: 6000 }
...
{ duration: 7, iteration: 90000 }
{ duration: 6, iteration: 92000 }
{ duration: 6, iteration: 94000 }
{ duration: 7, iteration: 96000 }
...
{ duration: 5, iteration: 198000 }
{ duration: 9, iteration: 200000 }

I'm 85% sure this is the same issue, or at least very similar to the one that's exhibited in isaacs/node-lru-cache#54 – just as a more refined reproduction. The main difference is in the lru-cache issue it doesn't seem to ever speed up again (some sort of reoptimization?).

[trevnorris]

You may want to try switching over to Map() instead. I see the behavior your describing on v4.2.1 using an object, but if you switch to using Map#set() and Map#delete() the performance lag disappears.

But regardless as you stated this is a v8 issue. Don't believe there's much we can do about that.

[aheckmann]

Yes, a Map "fixes" the issue. Agreed its really a V8 bug that I haven't made time to report. isaacs/node-lru-cache#55

[aheckmann]

Started the discussion here. I recommend closing this one.

[mhart]

Great, thanks @ofrobots and @aheckmann 👍