Comparing arrays with assert seems to take polynomial time. #12842
Description
- Version: 6.10.3 x64
- Platform: OS X 12.4
Comparing two arrays with assert.deepEqual or .deepStrictEqual seems to take a polynomial amount of time relative to the array size.
Quick code:
function longTest(n) {
const bigSource = Array.apply(null, Array(n));
const a1 = bigSource.map((n) => ({ yarp: 'yarp', nope: {yarp: '123', a: [1,2,3]} }));
const a2 = bigSource.map((n) => ({ yarp: 'yarp', nope: {yarp: '123', a: [1,2,3]} }));
//a2[a2.length - 1].nope = 'nope';
const tStart = Date.now();
assert.deepEqual(a2, a1);
const tEnd = Date.now();
const dt = tEnd - tStart;
return dt;
}
let n = 1;
for (let i = 0; i<=40; i++) {
n = Math.round(n*1.5);
const dt = longTest(n);
console.log(`${n}, ${dt}`)
}Returns a list of (n),(time) pairs.
On my machine, the output of this is
2, 2
3, 0
5, 0
8, 0
12, 1
18, 1
27, 6
41, 5
62, 1
93, 1
140, 2
210, 3
315, 5
473, 7
710, 11
1065, 21
1598, 40
2397, 70
3596, 135
5394, 270
8091, 581
12137, 1184
18206, 2590
27309, 5679
40964, 12539
61446, 28906
92169, 63617
Graphed, this looks like
Or to illustrate what I think I'm seeing, we can plot on a log-log scale graph:
Just to be explicit, I would expect this operation to take O(n) time.
I'm quite possibly doing something very silly, so apologies in advance if I'm unknowingly spluttering over my own mistakes.