GeezerVison is showing github.com — assert: improve myers diff performance · nodejs/node@2daee76
File treeExpand file treeCollapse file tree Open diff view settings Expand file treeCollapse file tree Open diff view settings Collapse file Copy file name to clipboard +38Lines changed: 38 additions & 0 deletions | Original file line number | Diff line number | Diff line change |
|---|
| | 1 | +'use strict'; | | 2 | +const common = require('../common.js'); | | 3 | +const assert = require('assert'); | | 4 | + | | 5 | +const bench = common.createBenchmark(main, { | | 6 | + n: [10, 50, 200, 500], | | 7 | + size: [10, 100], | | 8 | + datasetName: ['objects'], | | 9 | +}); | | 10 | + | | 11 | +const baseObject = { | | 12 | + a: 1, | | 13 | + b: { | | 14 | + c: 2, | | 15 | + d: [3, 4, 5], | | 16 | + e: 'fghi', | | 17 | + j: { | | 18 | + k: 6, | | 19 | + }, | | 20 | + }, | | 21 | +}; | | 22 | + | | 23 | +function createObjects(size) { | | 24 | + return Array.from({ length: size }, () => baseObject); | | 25 | +} | | 26 | + | | 27 | +function main({ n, size }) { | | 28 | + bench.start(); | | 29 | + for (let i = 0; i < n; ++i) { | | 30 | + new assert.AssertionError({ | | 31 | + actual: {}, | | 32 | + expected: createObjects(size), | | 33 | + operator: 'partialDeepStrictEqual', | | 34 | + stackStartFunction: () => {}, | | 35 | + }); | | 36 | + } | | 37 | + bench.end(n); | | 38 | +} |
Collapse file Copy file name to clipboardExpand all lines: lib/internal/assert/myers_diff.js +5-13Lines changed: 5 additions & 13 deletions | Original file line number | Diff line number | Diff line change |
|---|
| 2 | 2 |
| 3 | 3 | const { | 4 | 4 | ArrayPrototypePush, | 5 | | - ArrayPrototypeSlice, | 6 | 5 | Int32Array, | 7 | 6 | StringPrototypeEndsWith, | 8 | 7 | } = primordials; | @@ -16,7 +15,7 @@ function areLinesEqual(actual, expected, checkCommaDisparity) { | 16 | 15 | return true; | 17 | 16 | } | 18 | 17 | if (checkCommaDisparity) { | 19 | | - return `${actual},` === expected || actual === `${expected},`; | | 18 | + return (actual + ',') === expected || actual === (expected + ','); | 20 | 19 | } | 21 | 20 | return false; | 22 | 21 | } | @@ -26,12 +25,10 @@ function myersDiff(actual, expected, checkCommaDisparity = false) { | 26 | 25 | const expectedLength = expected.length; | 27 | 26 | const max = actualLength + expectedLength; | 28 | 27 | const v = new Int32Array(2 * max + 1); | 29 | | - | 30 | 28 | const trace = []; | 31 | 29 |
| 32 | 30 | for (let diffLevel = 0; diffLevel <= max; diffLevel++) { | 33 | | - const newTrace = ArrayPrototypeSlice(v); | 34 | | - ArrayPrototypePush(trace, newTrace); | | 31 | + ArrayPrototypePush(trace, new Int32Array(v)); // Clone the current state of `v` | 35 | 32 |
| 36 | 33 | for (let diagonalIndex = -diffLevel; diagonalIndex <= diffLevel; diagonalIndex += 2) { | 37 | 34 | const offset = diagonalIndex + max; | @@ -89,22 +86,17 @@ function backtrack(trace, actual, expected, checkCommaDisparity) { | 89 | 86 |
| 90 | 87 | while (x > prevX && y > prevY) { | 91 | 88 | const actualItem = actual[x - 1]; | 92 | | - const value = | 93 | | - !checkCommaDisparity || StringPrototypeEndsWith(actualItem, ',') ? | 94 | | - actualItem : | 95 | | - expected[y - 1]; | | 89 | + const value = checkCommaDisparity && !StringPrototypeEndsWith(actualItem, ',') ? expected[y - 1] : actualItem; | 96 | 90 | ArrayPrototypePush(result, { __proto__: null, type: 'nop', value }); | 97 | 91 | x--; | 98 | 92 | y--; | 99 | 93 | } | 100 | 94 |
| 101 | 95 | if (diffLevel > 0) { | 102 | 96 | if (x > prevX) { | 103 | | - ArrayPrototypePush(result, { __proto__: null, type: 'insert', value: actual[x - 1] }); | 104 | | - x--; | | 97 | + ArrayPrototypePush(result, { __proto__: null, type: 'insert', value: actual[--x] }); | 105 | 98 | } else { | 106 | | - ArrayPrototypePush(result, { __proto__: null, type: 'delete', value: expected[y - 1] }); | 107 | | - y--; | | 99 | + ArrayPrototypePush(result, { __proto__: null, type: 'delete', value: expected[--y] }); | 108 | 100 | } | 109 | 101 | } | 110 | 102 | } | |
|