Skip to content

assert: improve deepEqual Set and Map worst case

Rodrigo Muino Tomonari requested to merge github/fork/BridgeAR/improve-assert-o-notation into master

This change improves the algorithm for the worst case from O(n^2) to O(n log n) by using a lazily initiated set for object keys and a special handling for loose equal primitives.

In addition a few comments got fixed and a few statements simplified.

There is still 100% coverage and I heavily tested weird cases.

Benchmarks:

 assert/deepequal-set.js method="deepEqual_looseMatches" len=500 n=500             6810.50 %        *** 4.878337e-16
 assert/deepequal-set.js method="deepEqual_mixed" len=500 n=500                    1004.55 %        *** 6.872133e-24
 assert/deepequal-set.js method="deepEqual_objectOnly" len=500 n=500               1077.10 %        *** 7.799749e-21
 assert/deepequal-set.js method="deepEqual_primitiveOnly" len=500 n=500              62.80 %        *** 8.981486e-11
 assert/deepequal-set.js method="deepStrictEqual_mixed" len=500 n=500               994.50 %        *** 1.788847e-15
 assert/deepequal-set.js method="deepStrictEqual_objectOnly" len=500 n=500         1089.84 %        *** 7.120327e-17
 assert/deepequal-set.js method="deepStrictEqual_primitiveOnly" len=500 n=500         3.58 %            2.607197e-01
 assert/deepequal-set.js method="notDeepEqual_looseMatches" len=500 n=500          6795.11 %        *** 4.752399e-13
 assert/deepequal-set.js method="notDeepEqual_mixed" len=500 n=500                  777.34 %        *** 2.503238e-27
 assert/deepequal-set.js method="notDeepEqual_objectOnly" len=500 n=500             409.91 %        *** 3.435125e-17
 assert/deepequal-set.js method="notDeepEqual_primitiveOnly" len=500 n=500          183.85 %        *** 8.764397e-29
 assert/deepequal-set.js method="notDeepStrictEqual_mixed" len=500 n=500              4.43 %          * 2.496594e-02
 assert/deepequal-set.js method="notDeepStrictEqual_objectOnly" len=500 n=500       437.70 %        *** 1.406055e-27
 assert/deepequal-set.js method="notDeepStrictEqual_primitiveOnly" len=500 n=500      3.13 %            3.144997e-01


 assert/deepequal-map.js method="deepEqual_looseMatches" len=500 n=500             1814.34 %        *** 1.700744e-20
 assert/deepequal-map.js method="deepEqual_mixed" len=500 n=500                     952.35 %        *** 1.807387e-17
 assert/deepequal-map.js method="deepEqual_objectOnly" len=500 n=500               1042.38 %        *** 1.482305e-16
 assert/deepequal-map.js method="deepEqual_primitiveOnly" len=500 n=500             133.51 %        *** 1.363842e-16
 assert/deepequal-map.js method="deepStrictEqual_mixed" len=500 n=500               996.73 %        *** 3.463207e-19
 assert/deepequal-map.js method="deepStrictEqual_objectOnly" len=500 n=500         1072.64 %        *** 2.516677e-17
 assert/deepequal-map.js method="deepStrictEqual_primitiveOnly" len=500 n=500        81.57 %        *** 2.526982e-18
 assert/deepequal-map.js method="notDeepEqual_looseMatches" len=500 n=500          1787.48 %        *** 4.458942e-20
 assert/deepequal-map.js method="notDeepEqual_mixed" len=500 n=500                  598.92 %        *** 1.020276e-14
 assert/deepequal-map.js method="notDeepEqual_objectOnly" len=500 n=500             407.62 %        *** 7.984672e-23
 assert/deepequal-map.js method="notDeepEqual_primitiveOnly" len=500 n=500          179.22 %        *** 8.525884e-17
 assert/deepequal-map.js method="notDeepStrictEqual_mixed" len=500 n=500             -1.87 %            7.260855e-01
 assert/deepequal-map.js method="notDeepStrictEqual_objectOnly" len=500 n=500       429.53 %        *** 3.240289e-20
 assert/deepequal-map.js method="notDeepStrictEqual_primitiveOnly" len=500 n=500     63.90 %        *** 1.195866e-14
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)

assert

Merge request reports