Significant map/reduce performance regression in node 12

[kbjr]

• Version: v12.1.0
• Platform: Windows 10 64-bit

Some background: I recently read an old article that, among other things, looked at performance in Node (6 at the time) for map/reduce vs using a for loop, and after seeing a comment by someone else about the recent performance changes in later version of V8, decided to see if there was any difference in the results in later version of Node. So I set out to try and reproduce their test and results, and started looking at newer versions of Node to compare, and ended up stumbling upon what appears to be a rather significant performance regression.

The test is fairly simple, take a list of 32 million random numbers, and calculate the sum of the squares. The full code for the test I ran can be found here: https://gist.github.com/kbjr/1a551ddb3b59e9685b04bb051daef44c

But the two basic samples are this:

const result = data
  .map((x) => x ** 2)
  .reduce((memo, x) => memo + x, 0);

let result = 0;

for (let i = 0; i < data.length; i++) {
  result += data[i] ** 2;
}

The for loop version is faster, but that has always been the case and is not the point of this issue. Here are the results I got from running this test on 10.15.0:

runMapReduce        12602.4ms   13285.9ms   12729.4ms
runForEach          2407.41ms   2358.85ms   2432.26ms
runForLoop          69.4525ms   47.4004ms   56.8418ms
runForLoopNoLength  66.4152ms   51.5009ms   55.3084ms

Which looks about the same as the original results in the article I had read, so I wasn't really surprised at the outcome. What did surprise me was when I ran the test again on 12.1.0:

runMapReduce        126262ms    126607ms    129501ms
runForEach          1451.66ms   1457.29ms   1490.63ms
runForLoop          38.9766ms   45.9452ms   34.7133ms
runForLoopNoLength  38.9530ms   44.0065ms   35.1938ms

The other tests actually all got some small speed ups, but the map/reduce slowed down by basically a whole order of magnitude.

[devsnek]

iirc fast paths for handling holey arrays (the one you create is holey) were removed while rewriting parts of v8 internals.

@nodejs/v8

[Trott]

iirc fast paths for handling holey arrays (the one you create is holey) were removed while rewriting parts of v8 internals.

By "holey", you mean "has gaps"? I don't think data has gaps in the code provided:

let data = new Array(size);

for (let i = 0; i < size; i++) {
	data[i] = rand();
}

Or am I misunderstanding?

[devsnek]

@Trott it's an internal array kind in V8 describing its memory layout. holey arrays operate more like dictionaries since they could be missing indices. afaik even though the array is eventually filled it remains in that initial type.

[kbjr]

@devsnek If we assume that is accurate, does that mean that populating the array like

const data = [ ];

for (...) {
  data.push(rand());
}

should remove this "holey" status and make the process fast again?

If that's the case, I would be happy to rerun the test like this to verify.

[devsnek]

@kbjr that would indeed not be a holey array

[kbjr]

So, I ran the test again like this, but the results are basically the same:

runMapReduce        126969ms    126892ms    126506ms
runForEach          1642.75ms   1642.28ms   1688.50ms
runForLoop          37.5993ms   42.6008ms   34.8042ms
runForLoopNoLength  36.9135ms   45.7981ms   34.7570ms

The code change:

// let data = new Array(size);

// for (let i = 0; i < size; i++) {
// 	data[i] = rand();
// }

let data = [ ];

for (let i = 0; i < size; i++) {
	data.push(rand());
}

[devsnek]

i guess that's not the issue then :)

Something contributing to this might be my rewrite of v8's exp operator which did make it a bit slower (and more accurate), but i doubt that would result in the enormous difference here.

[kbjr]

What interests me the most is that there doesn't seem to be an impact on the forEach test (in fact, its actually a bit faster).

If it was something to do with the way V8 reads the array (or how the exp operator works), I would expect to see a similar result in that test as well (or all of them, if it were the exp operator).

My gut instinct would be something to do with the map function and the way it creates the new array, but that's just a hunch. I'm going to try breaking the test apart into a map and a reduce and see if one of those steps separately is indeed causing the majority of the slow down.

[kbjr]

Okay, I ran the map and reduce separately with the following new tests:

let squares;

const runMap = () => runWithTimer(() => {
	squares = data.map((x) => x ** 2);
});

const runReduce = () => runWithTimer(() => {
	const result = squares.reduce((memo, x) => memo + x, 0);
});

And here are the results (only run once because I'm lazy and this takes a while):

runMap              126779ms
runReduce           862.096ms

So it is most definitely the map call that is slow.

[kbjr]

I'm going to try map without the exponent, just to rule that out as well...

[kbjr]

As expected, removing the exponent had basically no effect:

runMap              124786ms
runReduce           883.284ms

// squares = data.map((x) => x ** 2);
squares = data.map((x) => x);

So, it seems the real regression is as simple as, the map function is very slow, even if you do literally nothing in the callback.

[kbjr]

So, here's the most basic, reproducible case:

console.log('Creating test data');

const data = [ ];

for (let i = 0; i < 32000000; i++) {
	data.push(Math.random() * 100);
}

console.log('Running test');

const start = Date.now();

data.map((x) => x);

console.log(`Done. Duration: ${Date.now() - start}ms`);

And the output:

λ nvm use 10.15
10.15.0
Now using node v10.15.0 (64-bit)

λ node .\map-regression.js
Creating test data
Running test
Done. Duration: 6060ms

λ nvm use 12.3.1
Now using node v12.3.1 (64-bit)

λ node .\map-regression.js
Creating test data
Running test
Done. Duration: 125899ms

[devsnek]

weeee ok i read through the actual source and found that the fast path now only considers PACKED_SMI_ELEMENTS (arrays of 32 bit integers). Indeed if I use data.push(Math.floor(Math.random() * 100)); the time drops to around 500ms.

[targos]

/cc @bmeurer