Bug 218062 – Replace O(n^2) algorithm from r268709 with O(n) algorithm

• Component: New Bugs
• Status: RESOLVED FIXED

[Alex Christensen]

Replace O(n^2) algorithm from r268709 with O(n) algorithm

[Alex Christensen]

Created attachment 412047 [details]
Patch

[EWS]

Committed r268852: <https://trac.webkit.org/changeset/268852>

All reviewed patches have been landed. Closing bug and clearing flags on attachment 412047 [details].

[Radar WebKit Bug Importer]

<rdar://problem/70559804>

[Geoffrey Garen]

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.

[Alexey Shvayka]

(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.