Replace O(n^2) algorithm from r268709 with O(n) algorithm
Created attachment 412047 [details] Patch
Committed r268852: <https://trac.webkit.org/changeset/268852> All reviewed patches have been landed. Closing bug and clearing flags on attachment 412047 [details].
<rdar://problem/70559804>
Comment on attachment 412047 [details] Patch View in context: https://bugs.webkit.org/attachment.cgi?id=412047&action=review > Source/WebCore/bindings/js/JSDOMConvertRecord.h:141 > + auto iterator = resultMap.find(typedKey); > + if (iterator != resultMap.end()) { > + ASSERT(result[iterator->value].key == typedKey); > + result[iterator->value].value = WTFMove(typedValue); > continue; > } > + resultMap.add(typedKey, result.size()); You can avoid the double hash lookup here by doing the add first and then checking its result: auto addResult = resultMap.add(typedKey, result.size()); if (!addResult.isNewEntry) { ASSERT(result[addResult.iterator->value].key == typedKey); result[addResult.iterator->value].value = WTFMove(typedValue); continue; } (The default behavior of add() does not overwrite existing entries.) Also: Why are you storing both the key and the value in both data structures? Seems like putting just the key into a HashSet would be slightly more efficient.
(In reply to Geoffrey Garen from comment #4) > You can avoid the double hash lookup here by doing the add first and then > checking its result: I've applied this comment as part of https://bugs.webkit.org/show_bug.cgi?id=223219. Thanks! > Also: Why are you storing both the key and the value in both data > structures? Seems like putting just the key into a HashSet would be slightly > more efficient. We store an index of the first |key| occurrence as the |value| so we can update it when the duplicate is found.