Repository: nodejs/node
Pull request: assert: improve myers diff performance

fix: https://github.com/nodejs/node/issues/57242

I reviewed the codebase and identified both some quick-win optimizations and the primary reason for the performance degradation when generating the error diff.

@Rymar, using the code example you posted in the related issue for testing during the fix, we should achieve performance levels close to what we had with the previous linear algorithm that Node.js used before switching to the Myers algorithm.

/cc @BridgeAR 

Changed files:
filename: benchmark/assert/assertion-error.js
patch: @@ -0,0 +1,38 @@
+'use strict';
+const common = require('../common.js');
+const assert = require('assert');
+
+const bench = common.createBenchmark(main, {
+  n: [10, 50, 200, 500],
+  size: [10, 100],
+  datasetName: ['objects'],
+});
+
+const baseObject = {
+  a: 1,
+  b: {
+    c: 2,
+    d: [3, 4, 5],
+    e: 'fghi',
+    j: {
+      k: 6,
+    },
+  },
+};
+
+function createObjects(size) {
+  return Array.from({ length: size }, () => baseObject);
+}
+
+function main({ n, size }) {
+  bench.start();
+  for (let i = 0; i < n; ++i) {
+    new assert.AssertionError({
+      actual: {},
+      expected: createObjects(size),
+      operator: 'partialDeepStrictEqual',
+      stackStartFunction: () => {},
+    });
+  }
+  bench.end(n);
+}

filename: lib/internal/assert/myers_diff.js
patch: @@ -2,7 +2,6 @@
 
 const {
   ArrayPrototypePush,
-  ArrayPrototypeSlice,
   Int32Array,
   StringPrototypeEndsWith,
 } = primordials;
@@ -16,7 +15,7 @@ function areLinesEqual(actual, expected, checkCommaDisparity) {
     return true;
   }
   if (checkCommaDisparity) {
-    return `${actual},` === expected || actual === `${expected},`;
+    return (actual + ',') === expected || actual === (expected + ',');
   }
   return false;
 }
@@ -26,12 +25,10 @@ function myersDiff(actual, expected, checkCommaDisparity = false) {
   const expectedLength = expected.length;
   const max = actualLength + expectedLength;
   const v = new Int32Array(2 * max + 1);
-
   const trace = [];
 
   for (let diffLevel = 0; diffLevel <= max; diffLevel++) {
-    const newTrace = ArrayPrototypeSlice(v);
-    ArrayPrototypePush(trace, newTrace);
+    ArrayPrototypePush(trace, new Int32Array(v)); // Clone the current state of `v`
 
     for (let diagonalIndex = -diffLevel; diagonalIndex <= diffLevel; diagonalIndex += 2) {
       const offset = diagonalIndex + max;
@@ -89,22 +86,17 @@ function backtrack(trace, actual, expected, checkCommaDisparity) {
 
     while (x > prevX && y > prevY) {
       const actualItem = actual[x - 1];
-      const value =
-        !checkCommaDisparity || StringPrototypeEndsWith(actualItem, ',') ?
-          actualItem :
-          expected[y - 1];
+      const value = checkCommaDisparity && !StringPrototypeEndsWith(actualItem, ',') ? expected[y - 1] : actualItem;
       ArrayPrototypePush(result, { __proto__: null, type: 'nop', value });
       x--;
       y--;
     }
 
     if (diffLevel > 0) {
       if (x > prevX) {
-        ArrayPrototypePush(result, { __proto__: null, type: 'insert', value: actual[x - 1] });
-        x--;
+        ArrayPrototypePush(result, { __proto__: null, type: 'insert', value: actual[--x] });
       } else {
-        ArrayPrototypePush(result, { __proto__: null, type: 'delete', value: expected[y - 1] });
-        y--;
+        ArrayPrototypePush(result, { __proto__: null, type: 'delete', value: expected[--y] });
       }
     }
   }