Title: [268852] trunk/Source/WebCore
- Revision
- 268852
- Author
- [email protected]
- Date
- 2020-10-21 21:50:33 -0700 (Wed, 21 Oct 2020)
Log 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 <[email protected]> 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:
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (268851 => 268852)
--- trunk/Source/WebCore/ChangeLog 2020-10-22 02:18:52 UTC (rev 268851)
+++ trunk/Source/WebCore/ChangeLog 2020-10-22 04:50:33 UTC (rev 268852)
@@ -1,3 +1,17 @@
+2020-10-21 Alex Christensen <[email protected]>
+
+ 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 <[email protected]>
REGRESSION(r268798): Fix build without ENABLE_LAYOUT_FORMATTING_CONTEXT
Modified: trunk/Source/WebCore/bindings/js/JSDOMConvertRecord.h (268851 => 268852)
--- trunk/Source/WebCore/bindings/js/JSDOMConvertRecord.h 2020-10-22 02:18:52 UTC (rev 268851)
+++ trunk/Source/WebCore/bindings/js/JSDOMConvertRecord.h 2020-10-22 04:50:33 UTC (rev 268852)
@@ -96,6 +96,7 @@
JSC::JSObject* object = JSC::asObject(value);
ReturnType result;
+ HashMap<KeyType, size_t> resultMap;
// 4. Let keys be ? O.[[OwnPropertyKeys]]().
JSC::PropertyNameArray keys(vm, JSC::PropertyNameMode::Strings, JSC::PrivateSymbolMode::Exclude);
@@ -131,15 +132,19 @@
// Note: It's possible that typedKey is already in result if K is USVString and key contains unpaired surrogates.
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) });
}
}
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
