Changeset 268852 in webkit

Timestamp:

Oct 21, 2020, 9:50:33 PM (6 years ago)

Author:

commit-queue@webkit.org

Message:

Replace O(n^{2) algorithm from r268709 with O(n) algorithm
​https://bugs.webkit.org/show_bug.cgi?id=218062}

Patch by Alex Christensen <​achristensen@webkit.org> on 2020-10-21
Reviewed by Alexey Shvayka.

r268709 introduced a Vector::findMatching call inside a loop that populates the Vector.
This causes very slow construction of URLSearchParams with large dictionaries with 16-bit keys.
To speed things up, keep a HashMap of the 16-bit strings we have already inserted to their index in the Vector
so we don't need to search the Vector.

• bindings/js/JSDOMConvertRecord.h:

Location:

trunk/Source/WebCore

Files:

• ChangeLog (modified) (1 diff)
• bindings/js/JSDOMConvertRecord.h (modified) (2 diffs)

trunk/Source/WebCore/ChangeLog

@@ +1 @@
+2020-10-21  Alex Christensen  <achristensen@webkit.org>
+
+        Replace O(n^2) algorithm from r268709 with O(n) algorithm
+        https://bugs.webkit.org/show_bug.cgi?id=218062
+
+        Reviewed by Alexey Shvayka.
+
+        r268709 introduced a Vector::findMatching call inside a loop that populates the Vector.
+        This causes very slow construction of URLSearchParams with large dictionaries with 16-bit keys.
+        To speed things up, keep a HashMap of the 16-bit strings we have already inserted to their index in the Vector
+        so we don't need to search the Vector.
+
+        * bindings/js/JSDOMConvertRecord.h:
+
 2020-10-21  Carlos Alberto Lopez Perez  <clopez@igalia.com>
 

trunk/Source/WebCore/bindings/js/JSDOMConvertRecord.h

@@ -97 +97 @@
     
         ReturnType result;
+        HashMap<KeyType, size_t> resultMap;
     
         // 4. Let keys be ? O.[[OwnPropertyKeys]]().
@@ -132 +133 @@
                 if constexpr (std::is_same_v<K, IDLUSVString>) {
                     if (!typedKey.is8Bit()) {
-                        auto index = result.findMatching([&](auto& entry) { return entry.key == typedKey; });
-                        if (index != notFound) {
-                            result[index].value = typedValue;
+                        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());
                     }
-                }
+                } else
+                    UNUSED_VARIABLE(resultMap);
                 
-                result.append({ typedKey, typedValue });
+                // 5. Otherwise, append to result a mapping (typedKey, typedValue).
+                result.append({ WTFMove(typedKey), WTFMove(typedValue) });
             }
         }