diff options
author | Anna Henningsen <anna@addaleax.net> | 2017-05-05 11:04:20 +0200 |
---|---|---|
committer | Anna Henningsen <anna@addaleax.net> | 2017-05-07 21:35:26 +0200 |
commit | 7e5f500c9861708e221e1e5e1d42e92af234583b (patch) | |
tree | 478de9a5bbc2fe50e62511acfc1e9fb5155205a0 /lib | |
parent | 3fd890a06edc82612ed52cd191c8181eee788744 (diff) | |
download | android-node-v8-7e5f500c9861708e221e1e5e1d42e92af234583b.tar.gz android-node-v8-7e5f500c9861708e221e1e5e1d42e92af234583b.tar.bz2 android-node-v8-7e5f500c9861708e221e1e5e1d42e92af234583b.zip |
assert: improve deepEqual perf for large input
Use a Map instead of an array for checking previously found
cyclic references.
This reduces complexity for an array-of-objects case from
O(n²) to O(n·log n).
Fixes: https://github.com/nodejs/node/issues/12842
PR-URL: https://github.com/nodejs/node/pull/12849
Reviewed-By: Colin Ihrig <cjihrig@gmail.com>
Reviewed-By: Joyee Cheung <joyeec9h3@gmail.com>
Reviewed-By: James M Snell <jasnell@gmail.com>
Reviewed-By: Jeremiah Senkpiel <fishrock123@rocketmail.com>
Reviewed-By: Refael Ackermann <refack@gmail.com>
Reviewed-By: Rich Trott <rtrott@gmail.com>
Diffstat (limited to 'lib')
-rw-r--r-- | lib/assert.js | 21 |
1 files changed, 15 insertions, 6 deletions
diff --git a/lib/assert.js b/lib/assert.js index 28eb2fcf20..a1631ff2e6 100644 --- a/lib/assert.js +++ b/lib/assert.js @@ -285,15 +285,24 @@ function _deepEqual(actual, expected, strict, memos) { // Note: this accounts for both named and indexed properties on Arrays. // Use memos to handle cycles. - memos = memos || { actual: [], expected: [] }; - const actualIndex = memos.actual.indexOf(actual); - if (actualIndex !== -1) { - if (actualIndex === memos.expected.indexOf(expected)) { + if (!memos) { + memos = { + actual: { map: new Map(), position: 0 }, + expected: { map: new Map(), position: 0 } + }; + } + + const actualPosition = memos.actual.map.get(actual); + if (actualPosition !== undefined) { + if (actualPosition === memos.expected.map.get(expected)) { return true; } + } else { + memos.actual.map.set(actual, memos.actual.position++); + } + if (!memos.expected.map.has(expected)) { + memos.expected.map.set(expected, memos.expected.position++); } - memos.actual.push(actual); - memos.expected.push(expected); return objEquiv(actual, expected, strict, memos); } |