Repository: nodejs/node
Pull request: assert,util: improve comparison performance

```benchmark: rework assert benchmarks for correctness```

```
This reworks most assert benchmarks to provide more reliable test
cases that also test more cases than before while keeping the
runtime low.
```

```test: remove obsolete util.isDeepStrictEqual tests```

```
These tests are a copy of the assert tests that verify the
deep equal comparison algorithm. There is no need to duplicate the
tests as changing one would require to change the tests in two
places without knowing which ones to actually rely upon.
```

```assert,util: improve deep equal comparison performance```

```
This is mainly a performance improvement for a lot of simple cases.
Diverging elements are detected earlier and equal entries are
partially also detected faster.

A small correctness patch is also included where recursions now
stop as soon as either side has a circular structure. Before, both
sides had to have a circular structure at the specific comparison
which could have caused more checks that likely fail at a later
point.
```

Signed-off-by: Ruben Bridgewater <ruben@bridgewater.de>
<details>
  <summary>Benchmark</summary>

```
                                                                                                                      confidence improvement accuracy (*)   (**)   (***)
assert/deepequal-buffer.js method='deepEqual' arrayBuffer=0 strict=0 len=100 n=20000                                          **      3.84 %       ±2.48% ±3.29%  ±4.25%
assert/deepequal-buffer.js method='deepEqual' arrayBuffer=0 strict=0 len=1000 n=20000                                         **      3.18 %       ±2.27% ±3.00%  ±3.89%
assert/deepequal-buffer.js method='deepEqual' arrayBuffer=0 strict=1 len=100 n=20000                                           *      2.93 %       ±2.41% ±3.20%  ±4.14%
assert/deepequal-buffer.js method='deepEqual' arrayBuffer=0 strict=1 len=1000 n=20000                                                 0.92 %       ±2.28% ±3.03%  ±3.91%
assert/deepequal-buffer.js method='deepEqual' arrayBuffer=1 strict=0 len=100 n=20000                                           *      3.23 %       ±3.13% ±4.16%  ±5.40%
assert/deepequal-buffer.js method='deepEqual' arrayBuffer=1 strict=0 len=1000 n=20000                                                -0.92 %       ±4.38% ±5.81%  ±7.52%
assert/deepequal-buffer.js method='deepEqual' arrayBuffer=1 strict=1 len=100 n=20000                                                  1.98 %       ±2.31% ±3.06%  ±3.95%
assert/deepequal-buffer.js method='deepEqual' arrayBuffer=1 strict=1 len=1000 n=20000                                         **      3.30 %       ±2.27% ±3.01%  ±3.89%
assert/deepequal-buffer.js method='notDeepEqual' arrayBuffer=0 strict=1 len=100 n=20000                                      ***      5.99 %       ±3.09% ±4.10%  ±5.31%
assert/deepequal-buffer.js method='notDeepEqual' arrayBuffer=0 strict=1 len=1000 n=20000                                     ***      6.81 %       ±2.59% ±3.45%  ±4.47%
assert/deepequal-buffer.js method='notDeepEqual' arrayBuffer=1 strict=1 len=100 n=20000                                               0.76 %       ±3.18% ±4.22%  ±5.48%
assert/deepequal-buffer.js method='notDeepEqual' arrayBuffer=1 strict=1 len=1000 n=20000                                       *     -3.71 %       ±3.21% ±4.28%  ±5.57%
assert/deepequal-buffer.js method='unequal_length' arrayBuffer=0 strict=1 len=100 n=20000                                    ***      8.82 %       ±2.55% ±3.38%  ±4.37%
assert/deepequal-buffer.js method='unequal_length' arrayBuffer=0 strict=1 len=1000 n=20000                                   ***      7.09 %       ±2.85% ±3.77%  ±4.88%
assert/deepequal-buffer.js method='unequal_length' arrayBuffer=1 strict=1 len=100 n=20000                                             0.20 %       ±2.67% ±3.53%  ±4.57%
assert/deepequal-buffer.js method='unequal_length' arrayBuffer=1 strict=1 len=1000 n=20000                                            1.87 %       ±2.99% ±3.96%  ±5.13%
assert/deepequal-map.js method='deepEqual_mixed' strict=0 len=500 n=500                                                      ***     19.51 %       ±1.73% ±2.29%  ±2.96%
assert/deepequal-map.js method='deepEqual_mixed' strict=1 len=500 n=500                                                      ***     20.58 %       ±1.75% ±2.32%  ±3.00%
assert/deepequal-map.js method='deepEqual_objectOnly' strict=0 len=500 n=500                                                 ***     20.77 %       ±1.87% ±2.48%  ±3.20%
assert/deepequal-map.js method='deepEqual_objectOnly' strict=1 len=500 n=500                                                 ***     22.47 %       ±1.72% ±2.28%  ±2.96%
assert/deepequal-map.js method='deepEqual_primitiveOnly' strict=0 len=500 n=500                                                       1.78 %       ±2.61% ±3.46%  ±4.48%
assert/deepequal-map.js method='deepEqual_primitiveOnly' strict=1 len=500 n=500                                                       0.79 %       ±2.49% ±3.30%  ±4.27%
assert/deepequal-map.js method='notDeepEqual_mixed' strict=0 len=500 n=500                                                   ***     56.17 %       ±5.56% ±7.38%  ±9.55%
assert/deepequal-map.js method='notDeepEqual_mixed' strict=1 len=500 n=500                                                   ***     45.24 %       ±6.05% ±8.03% ±10.41%
assert/deepequal-map.js method='notDeepEqual_objectOnly' strict=0 len=500 n=500                                              ***     18.69 %       ±2.56% ±3.39%  ±4.38%
assert/deepequal-map.js method='notDeepEqual_objectOnly' strict=1 len=500 n=500                                              ***     17.77 %       ±2.03% ±2.69%  ±3.48%
assert/deepequal-map.js method='notDeepEqual_primitiveOnly' strict=0 len=500 n=500                                                    1.24 %       ±2.48% ±3.29%  ±4.26%
assert/deepequal-map.js method='notDeepEqual_primitiveOnly' strict=1 len=500 n=500                                                    2.57 %       ±3.30% ±4.37%  ±5.65%
assert/deepequal-object.js method='deepEqual' strict=1 size=100 n=2000                                                       ***      3.69 %       ±1.41% ±1.87%  ±2.42%
assert/deepequal-object.js method='deepEqual' strict=1 size=1000 n=200                                                       ***      4.32 %       ±1.22% ±1.61%  ±2.08%
assert/deepequal-object.js method='deepEqual' strict=1 size=10000 n=25                                                       ***      4.20 %       ±1.21% ±1.60%  ±2.07%
assert/deepequal-object.js method='notDeepEqual' strict=1 size=100 n=2000                                                    ***     -6.46 %       ±3.16% ±4.20%  ±5.45%
assert/deepequal-object.js method='notDeepEqual' strict=1 size=1000 n=200                                                            -1.87 %       ±7.45% ±9.89% ±12.85%
assert/deepequal-object.js method='notDeepEqual' strict=1 size=10000 n=25                                                    ***    -10.13 %       ±5.38% ±7.13%  ±9.24%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=0 n=100000 primitive='array'                           ***     63.57 %       ±2.67% ±3.53%  ±4.58%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=0 n=100000 primitive='boolean'                           *      3.52 %       ±3.40% ±4.50%  ±5.84%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=0 n=100000 primitive='circular'                        ***     83.55 %       ±3.85% ±5.13%  ±6.70%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=0 n=100000 primitive='date'                                     1.78 %       ±2.62% ±3.47%  ±4.48%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=0 n=100000 primitive='empty_object'                             1.91 %       ±3.34% ±4.43%  ±5.75%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=0 n=100000 primitive='number'                                   0.44 %       ±3.82% ±5.06%  ±6.54%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=0 n=100000 primitive='object_other_property'                   -1.74 %       ±4.14% ±5.49%  ±7.10%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=0 n=100000 primitive='object'                          ***    106.78 %       ±2.99% ±3.98%  ±5.18%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=0 n=100000 primitive='regexp'                            *      2.69 %       ±2.34% ±3.10%  ±4.01%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=0 n=100000 primitive='set_object'                      ***     77.80 %       ±2.95% ±3.91%  ±5.08%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=0 n=100000 primitive='set_simple'                      ***     87.92 %       ±3.13% ±4.16%  ±5.38%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=0 n=100000 primitive='string'                                  -1.14 %       ±3.42% ±4.53%  ±5.85%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=1 n=100000 primitive='array'                           ***     60.87 %       ±2.81% ±3.74%  ±4.86%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=1 n=100000 primitive='boolean'                          **     -4.95 %       ±3.72% ±4.94%  ±6.41%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=1 n=100000 primitive='circular'                        ***     40.07 %       ±2.48% ±3.29%  ±4.26%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=1 n=100000 primitive='date'                                     0.51 %       ±1.83% ±2.42%  ±3.13%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=1 n=100000 primitive='empty_object'                            -0.05 %       ±1.91% ±2.53%  ±3.27%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=1 n=100000 primitive='number'                           **      4.42 %       ±3.04% ±4.03%  ±5.21%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=1 n=100000 primitive='object_other_property'                    0.85 %       ±3.48% ±4.61%  ±5.96%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=1 n=100000 primitive='object'                          ***     60.84 %       ±3.61% ±4.79%  ±6.22%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=1 n=100000 primitive='regexp'                            *      3.24 %       ±2.61% ±3.46%  ±4.48%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=1 n=100000 primitive='set_object'                      ***     60.77 %       ±2.76% ±3.66%  ±4.75%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=1 n=100000 primitive='set_simple'                      ***     57.80 %       ±2.15% ±2.86%  ±3.70%
assert/deepequal-prims-and-objs-big-loop.js method='deepEqual' strict=1 n=100000 primitive='string'                                  -1.97 %       ±3.26% ±4.32%  ±5.59%
assert/deepequal-prims-and-objs-big-loop.js method='notDeepEqual' strict=1 n=100000 primitive='array'                        ***     61.67 %       ±2.62% ±3.48%  ±4.52%
assert/deepequal-prims-and-objs-big-loop.js method='notDeepEqual' strict=1 n=100000 primitive='boolean'                               0.04 %       ±3.64% ±4.83%  ±6.24%
assert/deepequal-prims-and-objs-big-loop.js method='notDeepEqual' strict=1 n=100000 primitive='circular'                     ***     45.44 %       ±3.45% ±4.59%  ±5.95%
assert/deepequal-prims-and-objs-big-loop.js method='notDeepEqual' strict=1 n=100000 primitive='date'                                  1.25 %       ±3.52% ±4.66%  ±6.03%
assert/deepequal-prims-and-objs-big-loop.js method='notDeepEqual' strict=1 n=100000 primitive='empty_object'                   *      3.10 %       ±3.03% ±4.01%  ±5.19%
assert/deepequal-prims-and-objs-big-loop.js method='notDeepEqual' strict=1 n=100000 primitive='number'                         *      4.24 %       ±3.88% ±5.14%  ±6.64%
assert/deepequal-prims-and-objs-big-loop.js method='notDeepEqual' strict=1 n=100000 primitive='object_other_property'                 1.20 %       ±3.77% ±4.99%  ±6.45%
assert/deepequal-prims-and-objs-big-loop.js method='notDeepEqual' strict=1 n=100000 primitive='object'                               -0.80 %       ±3.64% ±4.84%  ±6.32%
assert/deepequal-prims-and-objs-big-loop.js method='notDeepEqual' strict=1 n=100000 primitive='regexp'                                2.16 %       ±2.22% ±2.95%  ±3.82%
assert/deepequal-prims-and-objs-big-loop.js method='notDeepEqual' strict=1 n=100000 primitive='set_object'                   ***     52.14 %       ±2.40% ±3.19%  ±4.13%
assert/deepequal-prims-and-objs-big-loop.js method='notDeepEqual' strict=1 n=100000 primitive='set_simple'                   ***     56.10 %       ±3.01% ±4.00%  ±5.18%
assert/deepequal-prims-and-objs-big-loop.js method='notDeepEqual' strict=1 n=100000 primitive='string'                               -0.89 %       ±4.20% ±5.56%  ±7.20%
assert/deepequal-set.js method='deepEqual_mixed' strict=0 len=500 n=500                                                      ***     18.11 %       ±2.45% ±3.25%  ±4.20%
assert/deepequal-set.js method='deepEqual_mixed' strict=1 len=500 n=500                                                      ***     18.87 %       ±2.13% ±2.82%  ±3.65%
assert/deepequal-set.js method='deepEqual_objectOnly' strict=0 len=500 n=500                                                 ***     22.78 %       ±2.27% ±3.00%  ±3.89%
assert/deepequal-set.js method='deepEqual_objectOnly' strict=1 len=500 n=500                                                 ***     20.37 %       ±2.16% ±2.87%  ±3.71%
assert/deepequal-set.js method='deepEqual_primitiveOnly' strict=0 len=500 n=500                                              ***      6.36 %       ±3.27% ±4.35%  ±5.64%
assert/deepequal-set.js method='deepEqual_primitiveOnly' strict=1 len=500 n=500                                              ***      9.87 %       ±2.51% ±3.32%  ±4.30%
assert/deepequal-set.js method='notDeepEqual_mixed' strict=0 len=500 n=500                                                   ***     12.85 %       ±4.26% ±5.65%  ±7.31%
assert/deepequal-set.js method='notDeepEqual_mixed' strict=1 len=500 n=500                                                   ***     35.77 %       ±5.82% ±7.72% ±10.00%
assert/deepequal-set.js method='notDeepEqual_objectOnly' strict=0 len=500 n=500                                              ***     17.64 %       ±2.44% ±3.23%  ±4.18%
assert/deepequal-set.js method='notDeepEqual_objectOnly' strict=1 len=500 n=500                                              ***     13.59 %       ±2.30% ±3.05%  ±3.96%
assert/deepequal-set.js method='notDeepEqual_primitiveOnly' strict=0 len=500 n=500                                             *      2.90 %       ±2.60% ±3.44%  ±4.45%
assert/deepequal-set.js method='notDeepEqual_primitiveOnly' strict=1 len=500 n=500                                           ***     10.72 %       ±2.58% ±3.42%  ±4.42%
assert/deepequal-simple-array-and-set.js method='deepEqual_Array' strict=0 len=20000 n=25                                             0.02 %       ±4.40% ±5.82%  ±7.53%
assert/deepequal-simple-array-and-set.js method='deepEqual_Array' strict=1 len=20000 n=25                                            -1.03 %       ±2.78% ±3.69%  ±4.78%
assert/deepequal-simple-array-and-set.js method='deepEqual_Set' strict=0 len=20000 n=25                                      ***      6.75 %       ±2.79% ±3.70%  ±4.80%
assert/deepequal-simple-array-and-set.js method='deepEqual_Set' strict=1 len=20000 n=25                                      ***      5.23 %       ±2.90% ±3.84%  ±4.98%
assert/deepequal-simple-array-and-set.js method='notDeepEqual_Array' strict=0 len=20000 n=25                                  **     -3.90 %       ±2.70% ±3.57%  ±4.62%
assert/deepequal-simple-array-and-set.js method='notDeepEqual_Array' strict=1 len=20000 n=25                                  **     -3.29 %       ±2.45% ±3.25%  ±4.22%
assert/deepequal-simple-array-and-set.js method='notDeepEqual_Set' strict=0 len=20000 n=25                                           -1.71 %       ±3.13% ±4.15%  ±5.37%
assert/deepequal-simple-array-and-set.js method='notDeepEqual_Set' strict=1 len=20000 n=25                                   ***      7.96 %       ±2.84% ±3.77%  ±4.87%
```
</details>

Changed files:
filename: doc/api/assert.md
patch: @@ -546,10 +546,6 @@ An alias of [`assert.ok()`][].
 <!-- YAML
 added: v0.1.21
 changes:
-  - version: REPLACEME
-    pr-url: https://github.com/nodejs/node/pull/46593
-    description: Recursion now stops when either side encounters a circular
-                 reference.
   - version: v18.0.0
     pr-url: https://github.com/nodejs/node/pull/41020
     description: Regular expressions lastIndex property is now compared as well.
@@ -621,7 +617,7 @@ are also recursively evaluated by the following rules.
 * [Object wrappers][] are compared both as objects and unwrapped values.
 * `Object` properties are compared unordered.
 * [`Map`][] keys and [`Set`][] items are compared unordered.
-* Recursion stops when both sides differ or either side encounters a circular
+* Recursion stops when both sides differ or both sides encounter a circular
   reference.
 * Implementation does not test the [`[[Prototype]]`][prototype-spec] of
   objects.
@@ -731,10 +727,6 @@ parameter is an instance of an [`Error`][] then it will be thrown instead of the
 <!-- YAML
 added: v1.2.0
 changes:
-  - version: REPLACEME
-    pr-url: https://github.com/nodejs/node/pull/46593
-    description: Recursion now stops when either side encounters a circular
-                 reference.
   - version: v18.0.0
     pr-url: https://github.com/nodejs/node/pull/41020
     description: Regular expressions lastIndex property is now compared as well.
@@ -788,7 +780,7 @@ are recursively evaluated also by the following rules.
 * [Object wrappers][] are compared both as objects and unwrapped values.
 * `Object` properties are compared unordered.
 * [`Map`][] keys and [`Set`][] items are compared unordered.
-* Recursion stops when both sides differ or either side encounters a circular
+* Recursion stops when both sides differ or both sides encounter a circular
   reference.
 * [`WeakMap`][] and [`WeakSet`][] comparison does not rely on their values. See
   below for further details.

filename: lib/internal/util/comparisons.js
patch: @@ -343,10 +343,7 @@ function keyCheck(val1, val2, strict, memos, iterationType, aKeys) {
   if (memos.set === undefined) {
     if (memos.deep === false) {
       if (memos.a === val1) {
-        return memos.b === val2;
-      }
-      if (memos.b === val2) {
-        return false;
+        if (memos.b === val2) return true;
       }
       memos.c = val1;
       memos.d = val2;
@@ -366,12 +363,9 @@ function keyCheck(val1, val2, strict, memos, iterationType, aKeys) {
 
   const originalSize = set.size;
   set.add(val1);
-  if (originalSize === set.size) {
-    return set.has(val2);
-  }
   set.add(val2);
-  if (originalSize === set.size - 1) {
-    return false;
+  if (originalSize === set.size) {
+    return true;
   }
 
   const areEq = objEquiv(val1, val2, strict, aKeys, memos, iterationType);

filename: test/parallel/test-assert-deep.js
patch: @@ -425,7 +425,7 @@ assertNotDeepOrStrict(
   b.a = {};
   b.a.a = a;
 
-  assertNotDeepOrStrict(a, b);
+  assertDeepAndStrictEqual(a, b);
 }
 
 {
@@ -435,7 +435,7 @@ assertNotDeepOrStrict(
   b.a = b;
   const c = {};
   c.a = a;
-  assertNotDeepOrStrict(b, c);
+  assertDeepAndStrictEqual(b, c);
 }
 
 {
@@ -445,7 +445,7 @@ assertNotDeepOrStrict(
   b.add(b);
   const c = new Set();
   c.add(a);
-  assertNotDeepOrStrict(b, c);
+  assertDeepAndStrictEqual(b, c);
 }
 
 // https://github.com/nodejs/node-v0.x-archive/pull/7178