Performance reegression: for..in loops in node 8+ grow superlinearly with object size (even if returning after 1 iteration)

[SimonWoolf]

• Version: differing behaviour on each version; teested on 6.10.0, 7.10.1, 8.11.1, 10.0.0
• Platform: Linux simon-linuxdesktop 4.4.0-116-generic install,windows: symlink iojs -> node? #140-Ubuntu SMP Mon Feb 12 21:23:04 UTC 2018 x86_64 x86_64 x86_64 GNU/Linux

The following benchmark tests a for...in loop that returns after a single iteration.

function isEmptyObj(ob) {
  for(const i in ob) { return false; }
  return true;
}

const objSize = 10*1000;
const rounds = 10*1000;
const b = {};
for(let i=0; i<objSize; i++) {
  b[i] = '...';
}

start = new Date();
for(let i=0; i<rounds; i++) {
  isEmptyObj(b)
}
console.log(`${rounds/1000}k rounds; obj size ${objSize/1000}k takes`, new Date() - start)

Since the loop returns after only one iteration, naively I'd have thought it would be either constant-time with object size, at least sublinear.

In practice it seems to grow either linearly or superlinearly with object size, depending on node version. E.g. for objects between 10k and 30k properties, node 7 is approx linear, node 8 is both much slower generally and also superlinear:

node 7:

$ ~/.asdf/installs/nodejs/7.10.1/bin/node forinbench.js
10k rounds; obj size 10k takes 255
$ ~/.asdf/installs/nodejs/7.10.1/bin/node forinbench.js
10k rounds; obj size 15k takes 374
$ ~/.asdf/installs/nodejs/7.10.1/bin/node forinbench.js
10k rounds; obj size 20k takes 542
$ ~/.asdf/installs/nodejs/7.10.1/bin/node forinbench.js
10k rounds; obj size 30k takes 809

node 8:

$ ~/.asdf/installs/nodejs/8.11.1/bin/node forinbench.js
10k rounds; obj size 10k takes 2294
$ ~/.asdf/installs/nodejs/8.11.1/bin/node forinbench.js
10k rounds; obj size 15k takes 3424
$ ~/.asdf/installs/nodejs/8.11.1/bin/node forinbench.js
10k rounds; obj size 20k takes 9865
$ ~/.asdf/installs/nodejs/8.11.1/bin/node listeners.js 
10k rounds; obj size 30k takes 27435

Node 10 behaves similarly.

(Side note: Node 7 has its own issues, but rather than superlinear growth at past a certain point, it has a sharp discontinuity at around 50.8k:

$ ~/.asdf/installs/nodejs/7.10.1/bin/node listeners.js 
10k rounds; obj size 50.8k takes 1228
$ ~/.asdf/installs/nodejs/7.10.1/bin/node listeners.js 
10k rounds; obj size 50.9k takes 5629

and similarly for node 6 but with the discontinuity at a different point)

---

I realise the practical solution is 'just use Map or Set if you want constant-time isEmpty using .size for large n', and sure, that's what we'll do. But even so, the behaviour in node 8+ compared to 7 and below is clearly a regression, so thought I'd flag it up.

[BridgeAR]

I can confirm this.

@nodejs/v8 @bmeurer PTAL

[bnoordhuis]

I can also confirm but I don't think this needs fixing. In a nutshell:

1. for (let i=0; i<objSize; i++) b[i] = ... - both v6.x and v8.x store i as a number under the hood, not a string
2. for (const i of ob) return false - v8.x transforms the numbers to strings eagerly, v6.x does it lazily; v6.x wins because the for/in loop doesn't use i

Change it to for (const i of ob) global.i = i and v8.x is 30-50% faster, depending on the number of keys.

Change it to for (const i in ob) { if (i>'999') break; global.i = i; } and v8.x still wins out by 5-10%.

Since you don't normally iterate over an object without using the key, I wouldn't call this a bug. I'll close this out but please reopen if more discussion is warranted.