Skip to content

assert: improve deepEqual perf for large input

Use a Map instead of an array for checking previously found cyclic references.

This reduces complexity for an array-of-objects case from O(n²) to O(n·log n).

Case from the issue, new output:

2, 3
3, 0
5, 0
8, 4
12, 2
18, 1
27, 4
41, 3
62, 1
93, 3
140, 4
210, 10
315, 5
473, 11
710, 16
1065, 25
1598, 40
2397, 75
3596, 119
5394, 150
8091, 216
12137, 296
18206, 419
27309, 681
40964, 944
61446, 1439
92169, 2424

Fixes: https://github.com/nodejs/node/issues/12842

Checklist
  • make -j4 test (UNIX), or vcbuild test (Windows) passes
  • tests and/or benchmarks are included
  • documentation is changed or added
  • commit message follows commit guidelines
Affected core subsystem(s)

Merge request reports

Loading