Node: Comparing arrays with `assert` seems to take polynomial time.

[akdor1154]

• 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.

[refack]

tl;dr: Yes
The current algorithm does not optimize for Arrays so it recurses into each element, I'm not sure it's O(exp(n)) probably O(n**m) where m is the depth of your elements.

In OSS as in OSS, you are welcome to submit an improvement. If you are interested a good place to start is https://github.com/nodejs/node/blob/master/lib/assert.js#L392

[refack]

A simpler option is to add a comment in the docs https://github.com/nodejs/node/blob/master/doc/api/assert.md#assertdeepequalactual-expected-message

[addaleax]

It should be O(n²) right now, I think – it’s iterating over the array in a linear fashion, but currently does an .indexOf over all objects it has already seen to check whether possible circular references match.

This is fixable (to O(n log n)), though: https://github.com/nodejs/node/pull/12849