FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

assert,util: improve deep comparison performance · nodejs/node@cf0eabc · GitHub

/ node Public

Commit cf0eabc

Browse files
BridgeAR
authored and
aduh95
committed
assert,util: improve deep comparison performance
PR-URL: #61076 Reviewed-By: Colin Ihrig <cjihrig@gmail.com> Reviewed-By: Yagiz Nizipli <yagiz@nizipli.com> Reviewed-By: Antoine du Hamel <duhamelantoine1995@gmail.com>
1 parent 42e1f72 commit cf0eabc

2 files changed

Lines changed: 89 additions & 71 deletions

File tree

‎lib/internal/util/comparisons.js‎

Lines changed: 48 additions & 66 deletions
Original file line numberDiff line numberDiff line change
@@ -4,7 +4,6 @@ const {
44
Array,
55
ArrayBuffer,
66
ArrayIsArray,
7-
ArrayPrototypeFilter,
87
ArrayPrototypePush,
98
BigInt,
109
BigInt64Array,
@@ -91,7 +90,7 @@ const wellKnownConstructors = new SafeSet()
9190
.add(WeakMap)
9291
.add(WeakSet);
9392

94-
if (Float16Array) { // TODO(BridgeAR): Remove when regularly supported
93+
if (Float16Array) { // TODO(BridgeAR): Remove when Flag got removed from V8
9594
wellKnownConstructors.add(Float16Array);
9695
}
9796

@@ -126,6 +125,11 @@ const {
126125
getOwnNonIndexProperties,
127126
} = internalBinding('util');
128127

128+
let kKeyObject;
129+
let kExtractable;
130+
let kAlgorithm;
131+
let kKeyUsages;
132+
129133
const kStrict = 2;
130134
const kStrictWithoutPrototypes = 3;
131135
const kLoose = 0;
@@ -151,7 +155,7 @@ function isPartialUint8Array(a, b) {
151155
}
152156
let offsetA = 0;
153157
for (let offsetB = 0; offsetB < lenB; offsetB++) {
154-
while (!ObjectIs(a[offsetA], b[offsetB])) {
158+
while (a[offsetA] !== b[offsetB]) {
155159
offsetA++;
156160
if (offsetA > lenA - lenB + offsetB) {
157161
return false;
@@ -186,11 +190,7 @@ function areSimilarFloatArrays(a, b) {
186190
}
187191

188192
function areSimilarTypedArrays(a, b) {
189-
if (a.byteLength !== b.byteLength) {
190-
return false;
191-
}
192-
return compare(new Uint8Array(a.buffer, a.byteOffset, a.byteLength),
193-
new Uint8Array(b.buffer, b.byteOffset, b.byteLength)) === 0;
193+
return a.byteLength === b.byteLength && compare(a, b) === 0;
194194
}
195195

196196
function areEqualArrayBuffers(buf1, buf2) {
@@ -224,7 +224,7 @@ function isEqualBoxedPrimitive(val1, val2) {
224224
assert.fail(`Unknown boxed type ${val1}`);
225225
}
226226

227-
function isEnumerableOrIdentical(val1, val2, prop, mode, memos, method) {
227+
function isEnumerableOrIdentical(val1, val2, prop, mode, memos) {
228228
return hasEnumerable(val2, prop) || // This is handled by Object.keys()
229229
(mode === kPartial && (val2[prop] === undefined || (prop === 'message' && val2[prop] === ''))) ||
230230
innerDeepEqual(val1[prop], val2[prop], mode, memos);
@@ -394,8 +394,10 @@ function objectComparisonStart(val1, val2, mode, memos) {
394394
return false;
395395
}
396396
} else if (isCryptoKey(val1)) {
397-
const { kKeyObject } = require('internal/crypto/util');
398-
const { kExtractable, kAlgorithm, kKeyUsages } = require('internal/crypto/keys');
397+
if (kKeyObject === undefined) {
398+
kKeyObject = require('internal/crypto/util').kKeyObject;
399+
({ kExtractable, kAlgorithm, kKeyUsages } = require('internal/crypto/keys'));
400+
}
399401
if (!isCryptoKey(val2) ||
400402
val1[kExtractable] !== val2[kExtractable] ||
401403
!innerDeepEqual(val1[kAlgorithm], val2[kAlgorithm], mode, memos) ||
@@ -411,18 +413,11 @@ function objectComparisonStart(val1, val2, mode, memos) {
411413
return keyCheck(val1, val2, mode, memos, kNoIterator);
412414
}
413415

414-
function getEnumerables(val, keys) {
415-
return ArrayPrototypeFilter(keys, (key) => hasEnumerable(val, key));
416-
}
417-
418416
function partialSymbolEquiv(val1, val2, keys2) {
419417
const symbolKeys = getOwnSymbols(val2);
420418
if (symbolKeys.length !== 0) {
421419
for (const key of symbolKeys) {
422420
if (hasEnumerable(val2, key)) {
423-
if (!hasEnumerable(val1, key)) {
424-
return false;
425-
}
426421
ArrayPrototypePush(keys2, key);
427422
}
428423
}
@@ -454,32 +449,19 @@ function keyCheck(val1, val2, mode, memos, iterationType, keys2) {
454449
} else if (keys2.length !== (keys1 = ObjectKeys(val1)).length) {
455450
return false;
456451
} else if (mode === kStrict || mode === kStrictWithoutPrototypes) {
457-
const symbolKeysA = getOwnSymbols(val1);
458-
if (symbolKeysA.length !== 0) {
459-
let count = 0;
460-
for (const key of symbolKeysA) {
461-
if (hasEnumerable(val1, key)) {
462-
if (!hasEnumerable(val2, key)) {
463-
return false;
464-
}
465-
ArrayPrototypePush(keys2, key);
466-
count++;
467-
} else if (hasEnumerable(val2, key)) {
468-
return false;
469-
}
470-
}
471-
const symbolKeysB = getOwnSymbols(val2);
472-
if (symbolKeysA.length !== symbolKeysB.length &&
473-
getEnumerables(val2, symbolKeysB).length !== count) {
474-
return false;
452+
for (const key of getOwnSymbols(val1)) {
453+
if (hasEnumerable(val1, key)) {
454+
ArrayPrototypePush(keys1, key);
475455
}
476-
} else {
477-
const symbolKeysB = getOwnSymbols(val2);
478-
if (symbolKeysB.length !== 0 &&
479-
getEnumerables(val2, symbolKeysB).length !== 0) {
480-
return false;
456+
}
457+
for (const key of getOwnSymbols(val2)) {
458+
if (hasEnumerable(val2, key)) {
459+
ArrayPrototypePush(keys2, key);
481460
}
482461
}
462+
if (keys1.length !== keys2.length) {
463+
return false;
464+
}
483465
}
484466
}
485467

@@ -641,16 +623,14 @@ function partialObjectSetEquiv(array, a, b, mode, memo) {
641623
}
642624

643625
function arrayHasEqualElement(array, val1, mode, memo, comparator, start, end) {
644-
let matched = false;
645626
for (let i = end - 1; i >= start; i--) {
646627
if (comparator(val1, array[i], mode, memo)) {
647-
// Remove the matching element to make sure we do not check that again.
648-
array.splice(i, 1);
649-
matched = true;
650-
break;
628+
// Move the matching element to make sure we do not check that again.
629+
array[i] = array[end];
630+
return true;
651631
}
652632
}
653-
return matched;
633+
return false;
654634
}
655635

656636
function setObjectEquiv(array, a, b, mode, memo) {
@@ -792,18 +772,16 @@ function partialObjectMapEquiv(array, a, b, mode, memo) {
792772
}
793773

794774
function arrayHasEqualMapElement(array, key1, item1, b, mode, memo, comparator, start, end) {
795-
let matched = false;
796775
for (let i = end - 1; i >= start; i--) {
797776
const key2 = array[i];
798777
if (comparator(key1, key2, mode, memo) &&
799778
innerDeepEqual(item1, b.get(key2), mode, memo)) {
800-
// Remove the matching element to make sure we do not check that again.
801-
array.splice(i, 1);
802-
matched = true;
803-
break;
779+
// Move the matching element to make sure we do not check that again.
780+
array[i] = array[end];
781+
return true;
804782
}
805783
}
806-
return matched;
784+
return false;
807785
}
808786

809787
function mapObjectEquiv(array, a, b, mode, memo) {
@@ -892,17 +870,21 @@ function mapEquiv(a, b, mode, memo) {
892870
}
893871

894872
function partialSparseArrayEquiv(a, b, mode, memos, startA, startB) {
895-
let aPos = 0;
896-
const keysA = ObjectKeys(a).slice(startA);
897-
const keysB = ObjectKeys(b).slice(startB);
898-
if (keysA.length < keysB.length) {
873+
let aPos = startA;
874+
const keysA = ObjectKeys(a);
875+
const keysB = ObjectKeys(b);
876+
const keysBLength = keysB.length;
877+
const keysALength = keysA.length;
878+
const lenA = keysALength - startA;
879+
const lenB = keysBLength - startB;
880+
if (lenA < lenB) {
899881
return false;
900882
}
901-
for (let i = 0; i < keysB.length; i++) {
902-
const keyB = keysB[i];
883+
for (let i = 0; i < lenB; i++) {
884+
const keyB = keysB[startB + i];
903885
while (!innerDeepEqual(a[keysA[aPos]], b[keyB], mode, memos)) {
904886
aPos++;
905-
if (aPos > keysA.length - keysB.length + i) {
887+
if (aPos > keysALength - lenB + i) {
906888
return false;
907889
}
908890
}
@@ -973,8 +955,11 @@ function objEquiv(a, b, mode, keys1, keys2, memos, iterationType) {
973955
// property in V8 13.0 compared to calling Object.propertyIsEnumerable()
974956
// and accessing the property regularly.
975957
const descriptor = ObjectGetOwnPropertyDescriptor(a, key);
976-
if (!descriptor?.enumerable ||
977-
!innerDeepEqual(descriptor.value !== undefined ? descriptor.value : a[key], b[key], mode, memos)) {
958+
if (descriptor === undefined || descriptor.enumerable !== true) {
959+
return false;
960+
}
961+
const value = descriptor.writable !== undefined ? descriptor.value : a[key];
962+
if (!innerDeepEqual(value, b[key], mode, memos)) {
978963
return false;
979964
}
980965
}
@@ -1023,10 +1008,7 @@ module.exports = {
10231008
return detectCycles(val1, val2, kLoose);
10241009
},
10251010
isDeepStrictEqual(val1, val2, skipPrototype) {
1026-
if (skipPrototype) {
1027-
return detectCycles(val1, val2, kStrictWithoutPrototypes);
1028-
}
1029-
return detectCycles(val1, val2, kStrict);
1011+
return detectCycles(val1, val2, skipPrototype ? kStrictWithoutPrototypes : kStrict);
10301012
},
10311013
isPartialStrictEqual(val1, val2) {
10321014
return detectCycles(val1, val2, kPartial);

‎test/parallel/test-assert-typedarray-deepequal.js‎

Lines changed: 41 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -35,7 +35,12 @@ suite('equalArrayPairs', () => {
3535
test('', () => {
3636
// eslint-disable-next-line no-restricted-properties
3737
assert.deepEqual(arrayPair[0], arrayPair[1]);
38+
// eslint-disable-next-line no-restricted-properties
39+
assert.deepEqual(arrayPair[1], arrayPair[0]);
3840
assert.deepStrictEqual(arrayPair[0], arrayPair[1]);
41+
assert.deepStrictEqual(arrayPair[1], arrayPair[0]);
42+
assert.partialDeepStrictEqual(arrayPair[0], arrayPair[1]);
43+
assert.partialDeepStrictEqual(arrayPair[1], arrayPair[0]);
3944
});
4045
}
4146
});
@@ -51,10 +56,24 @@ suite('looseEqualArrayPairs', () => {
5156
test('', () => {
5257
// eslint-disable-next-line no-restricted-properties
5358
assert.deepEqual(arrayPair[0], arrayPair[1]);
59+
// eslint-disable-next-line no-restricted-properties
60+
assert.deepEqual(arrayPair[1], arrayPair[0]);
5461
assert.throws(
5562
makeBlock(assert.deepStrictEqual, arrayPair[0], arrayPair[1]),
5663
assert.AssertionError
5764
);
65+
assert.throws(
66+
makeBlock(assert.deepStrictEqual, arrayPair[1], arrayPair[0]),
67+
assert.AssertionError
68+
);
69+
assert.throws(
70+
makeBlock(assert.partialDeepStrictEqual, arrayPair[0], arrayPair[1]),
71+
assert.AssertionError
72+
);
73+
assert.throws(
74+
makeBlock(assert.partialDeepStrictEqual, arrayPair[1], arrayPair[0]),
75+
assert.AssertionError
76+
);
5877
});
5978
}
6079
});
@@ -65,7 +84,7 @@ suite('notEqualArrayPairs', () => {
6584
[new Int16Array(256), new Uint16Array(256)],
6685
[new Int16Array([256]), new Uint16Array([256])],
6786
[new Float64Array([+0.0]), new Float32Array([-0.0])],
68-
[new Uint8Array(2), new Uint8Array(3)],
87+
[new Uint8Array(2), new Uint8Array(3), 'unequal length'],
6988
[new Uint8Array([1, 2, 3]), new Uint8Array([4, 5, 6])],
7089
[new Uint8ClampedArray([300, 2, 3]), new Uint8Array([300, 2, 3])],
7190
[new Uint16Array([2]), new Uint16Array([3])],
@@ -74,17 +93,17 @@ suite('notEqualArrayPairs', () => {
7493
[new Int16Array([-256]), new Uint16Array([0xff00])], // same bits
7594
[new Int32Array([-256]), new Uint32Array([0xffffff00])], // ditto
7695
[new Float16Array([0.1]), new Float16Array([0.0])],
77-
[new Float16Array([0.1]), new Float16Array([0.1, 0.2])],
96+
[new Float16Array([0.1]), new Float16Array([0.1, 0.2]), 'unequal length'],
7897
[new Float32Array([0.1]), new Float32Array([0.0])],
79-
[new Float32Array([0.1]), new Float32Array([0.1, 0.2])],
98+
[new Float32Array([0.1]), new Float32Array([0.1, 0.2]), 'unequal length'],
8099
[new Float64Array([0.1]), new Float64Array([0.0])],
81100
[new Uint8Array([1, 2, 3]).buffer, new Uint8Array([4, 5, 6]).buffer],
82101
[
83102
new Uint8Array(new SharedArrayBuffer(3)).fill(1).buffer,
84103
new Uint8Array(new SharedArrayBuffer(3)).fill(2).buffer,
85104
],
86-
[new ArrayBuffer(2), new ArrayBuffer(3)],
87-
[new SharedArrayBuffer(2), new SharedArrayBuffer(3)],
105+
[new ArrayBuffer(2), new ArrayBuffer(3), 'unequal length'],
106+
[new SharedArrayBuffer(2), new SharedArrayBuffer(3), 'unequal length'],
88107
[new ArrayBuffer(2), new SharedArrayBuffer(3)],
89108
[
90109
new Uint8Array(new ArrayBuffer(3)).fill(1).buffer,
@@ -101,14 +120,31 @@ suite('notEqualArrayPairs', () => {
101120
makeBlock(assert.deepEqual, arrayPair[0], arrayPair[1]),
102121
assert.AssertionError
103122
);
123+
assert.throws(
124+
// eslint-disable-next-line no-restricted-properties
125+
makeBlock(assert.deepEqual, arrayPair[1], arrayPair[0]),
126+
assert.AssertionError
127+
);
104128
assert.throws(
105129
makeBlock(assert.deepStrictEqual, arrayPair[0], arrayPair[1]),
106130
assert.AssertionError
107131
);
132+
assert.throws(
133+
makeBlock(assert.deepStrictEqual, arrayPair[1], arrayPair[0]),
134+
assert.AssertionError
135+
);
108136
assert.throws(
109137
makeBlock(assert.partialDeepStrictEqual, arrayPair[0], arrayPair[1]),
110138
assert.AssertionError
111139
);
140+
if (arrayPair[2]) {
141+
assert.partialDeepStrictEqual(arrayPair[1], arrayPair[0]);
142+
} else {
143+
assert.throws(
144+
makeBlock(assert.partialDeepStrictEqual, arrayPair[1], arrayPair[0]),
145+
assert.AssertionError
146+
);
147+
}
112148
});
113149
}
114150
});

0 commit comments

Comments
 (0)
Back | FazBrowse Home | New Git URL