Object property delete/set in loop got very slow in Node 12 (quadratic?)

[cakoose]

I was benchmarking different data structures and noticed a huge slowdown for the following test case:

1. Create an object with a bunch 20-character string properties, the value is always set to the number 1.
2. Loop over each key: delete it from the object and add it back.

The performance of object and Map is roughly the same in Node 11.15.0. In Node 12, the object version gets really slow (~10x slower for a 100-element object, ~60x slower for a 1000-element object).

Here's my full test case:

"package.json"

{
    "dependencies": {
        "benchmark": "2.1.4"
    }
}

"main.js"

const Benchmark = require('benchmark')

const digits = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVXYZ';

function randomString(length) {
    const parts = [];
    for (let i = 0; i < length; i++) {
        parts.push(digits.charAt(Math.random() * digits.length));
    }
    return parts.join('');
}

console.log(`Node ${process.versions.node}, V8 ${process.versions.v8}`);

for (const size of [10, 100, 1000, 10000]) {
    const keys = []
    const object = {};
    const map = new Map();
    for (let i = 0; i < size; i++) {
        const key = randomString(20);
        keys.push(key);
        object[key] = 1;
        map.set(key, 1);
    }

    const suite = new Benchmark.Suite();
    {
        let keyI = 0;
        suite.add('Object', () => {
            const key = keys[keyI++];
            if (keyI >= keys.length) {
                keyI = 0;
            }
            delete object[key];
            object[key] = 1;
        });
    }

    {
        let keyI = 0;
        suite.add('Map', () => {
            const key = keys[keyI++];
            if (keyI >= keys.length) {
                keyI = 0;
            }
            map.delete(key);
            map.set(key, 1);
        });
    }

    suite.on('cycle', event => {
      console.log('  ' + String(event.target));
    });

    console.log(`size: ${size}`);
    suite.run();
}

Results

Node 11.15.0, V8 7.0.276.38-node.19
size: 10
  Object x 12,638,709 ops/sec ±2.40% (88 runs sampled)
  Map x 18,837,340 ops/sec ±1.18% (88 runs sampled)
size: 100
  Object x 18,198,146 ops/sec ±1.08% (92 runs sampled)
  Map x 16,736,960 ops/sec ±2.69% (81 runs sampled)
size: 1000
  Object x 9,668,335 ops/sec ±4.26% (75 runs sampled)
  Map x 14,076,212 ops/sec ±2.19% (81 runs sampled)
size: 10000
  Object x 7,074,321 ops/sec ±1.51% (86 runs sampled)
  Map x 11,127,011 ops/sec ±1.69% (87 runs sampled)

Node 12.0.0, V8 7.4.288.21-node.16
size: 10
  Object x 5,006,773 ops/sec ±10.47% (41 runs sampled)
  Map x 18,186,938 ops/sec ±1.41% (90 runs sampled)
size: 100
  Object x 1,026,833 ops/sec ±115.69% (9 runs sampled)
  Map x 16,332,681 ops/sec ±2.39% (85 runs sampled)
size: 1000
  Object x 204,617 ops/sec ±226.52% (9 runs sampled)
  Map x 14,577,494 ops/sec ±1.44% (87 runs sampled)
size: 10000
  Object x 89,706 ops/sec ±202.29% (26 runs sampled)
  Map x 11,407,806 ops/sec ±2.25% (86 runs sampled)

Node 12.6.0, V8 7.5.288.22-node.14
size: 10
  Object x 4,848,704 ops/sec ±8.96% (47 runs sampled)
  Map x 13,350,969 ops/sec ±1.14% (87 runs sampled)
size: 100
  Object x 1,331,497 ops/sec ±128.56% (11 runs sampled)
  Map x 14,494,479 ops/sec ±1.71% (86 runs sampled)
size: 1000
  Object x 360,305 ops/sec ±208.01% (14 runs sampled)
  Map x 11,921,007 ops/sec ±1.29% (88 runs sampled)
size: 10000
  Object x 74,324 ops/sec ±202.57% (27 runs sampled)
  Map x 10,444,440 ops/sec ±1.14% (89 runs sampled)

[mscdex]

You should consider posting this to the V8 issue tracker.

[mscdex]

I also noticed that trying to run this code in node v10 and newer with --trace-turbo-inlining causes a segfault.

[Trott]

@nodejs/v8

[cakoose]

Filed on V8 tracker: https://bugs.chromium.org/p/v8/issues/detail?id=9442

[ex1st]

Maybe #31957 fixes this?

[cakoose]

Yup, looks like that fixed it on master.

I built Node at that commit and the immediately previous one and ran the benchmark again:

$ ~/h/node/repo/node main.js
Node 14.0.0-pre, V8 7.9.317.25-node.30
size: 10
  Object x 9,172,669 ops/sec ±3.27% (88 runs sampled)
  Map x 15,452,855 ops/sec ±4.00% (78 runs sampled)
size: 100
  Object x 11,036,564 ops/sec ±3.89% (82 runs sampled)
  Map x 15,277,354 ops/sec ±2.99% (82 runs sampled)
size: 1000
  Object x 8,262,450 ops/sec ±2.96% (84 runs sampled)
  Map x 12,838,733 ops/sec ±1.84% (87 runs sampled)
size: 10000
  Object x 3,971,972 ops/sec ±2.04% (87 runs sampled)
  Map x 10,300,059 ops/sec ±1.58% (89 runs sampled)

It still slows down at larger sizes, but nearly as much as at the previous commit:

$ ~/h/node/repo/node main.js
Node 14.0.0-pre, V8 7.9.317.25-node.29
size: 10
  Object x 4,187,852 ops/sec ±10.83% (43 runs sampled)
  Map x 15,466,479 ops/sec ±3.89% (80 runs sampled)
size: 100
  Object x 1,230,706 ops/sec ±128.68% (13 runs sampled)
  Map x 14,030,877 ops/sec ±4.20% (83 runs sampled)
size: 1000
  Object x 330,952 ops/sec ±206.06% (15 runs sampled)
  Map x 11,542,606 ops/sec ±3.70% (77 runs sampled)
size: 10000
  Object x 75,340 ops/sec ±191.86% (38 runs sampled)
  Map x 8,580,973 ops/sec ±4.94% (74 runs sampled)