Changeset 251736 in webkit

Timestamp:

Oct 29, 2019 2:43:30 PM (4 years ago)

Author:

ysuzuki@apple.com

Message:

[JSC] Add fast path for String#localeCompare
​https://bugs.webkit.org/show_bug.cgi?id=202676

Reviewed by Mark Lam.

JSTests:

• stress/locale-compare-bits.js: Added.

(shouldBe):

Source/JavaScriptCore:

When String#localeCompare is invoked, we are setting up UCharIterator to iterate code points.
But this is too slow since its implementation is invoking function pointer for each code point
to get next code point. Strings have many code points typically. Invoking function pointer so many times
takes too much time just for locale-aware comparison.

This patch revises the implementation by adding 2 fast path and 1 slow path. The slow path requires extra memory,
but it is soon released (not GC-managed).

1. If both strings are ASCII (not Latin1), we use ucol_strcollUTF8.
2. If both strings are 16-bit, we use ucol_strcoll.
3. Otherwise, we convert strings to 16-bit strings, and then we use ucol_strcoll.

JetStream2/cdjs is improved from 56 to 85 on iMac Pro (50%).

• runtime/IntlCollator.cpp:

(JSC::IntlCollator::compareStrings):

• tools/JSDollarVM.cpp:

(JSC::functionMake16BitStringIfPossible):
(JSC::JSDollarVM::finishCreation):

Source/WTF:

• wtf/text/StringView.h:

(WTF::StringView::isAllASCII const):

Tools:

• TestWebKitAPI/Tests/WTF/StringView.cpp:

(TestWebKitAPI::TEST):

Location:

trunk

Files:

• JSTests/ChangeLog (modified) (1 diff)
• JSTests/stress/locale-compare-bits.js (added)
• Source/JavaScriptCore/ChangeLog (modified) (1 diff)
• Source/JavaScriptCore/runtime/IntlCollator.cpp (modified) (1 diff)
• Source/JavaScriptCore/tools/JSDollarVM.cpp (modified) (2 diffs)
• Source/WTF/ChangeLog (modified) (1 diff)
• Source/WTF/wtf/text/StringView.h (modified) (2 diffs)
• Tools/ChangeLog (modified) (1 diff)
• Tools/TestWebKitAPI/Tests/WTF/StringView.cpp (modified) (1 diff)

trunk/JSTests/ChangeLog

@@ +1 @@
+2019-10-29  Yusuke Suzuki  <ysuzuki@apple.com>
+
+        [JSC] Add fast path for String#localeCompare
+        https://bugs.webkit.org/show_bug.cgi?id=202676
+
+        Reviewed by Mark Lam.
+
+        * stress/locale-compare-bits.js: Added.
+        (shouldBe):
+
 2019-10-28  Yusuke Suzuki  <ysuzuki@apple.com>
 

trunk/Source/JavaScriptCore/ChangeLog

@@ +1 @@
+2019-10-29  Yusuke Suzuki  <ysuzuki@apple.com>
+
+        [JSC] Add fast path for String#localeCompare
+        https://bugs.webkit.org/show_bug.cgi?id=202676
+
+        Reviewed by Mark Lam.
+
+        When String#localeCompare is invoked, we are setting up UCharIterator to iterate code points.
+        But this is too slow since its implementation is invoking function pointer for each code point
+        to get next code point. Strings have many code points typically. Invoking function pointer so many times
+        takes too much time just for locale-aware comparison.
+
+        This patch revises the implementation by adding 2 fast path and 1 slow path. The slow path requires extra memory,
+        but it is soon released (not GC-managed).
+
+        1. If both strings are ASCII (not Latin1), we use ucol_strcollUTF8.
+        2. If both strings are 16-bit, we use ucol_strcoll.
+        3. Otherwise, we convert strings to 16-bit strings, and then we use ucol_strcoll.
+
+        JetStream2/cdjs is improved from 56 to 85 on iMac Pro (50%).
+
+        * runtime/IntlCollator.cpp:
+        (JSC::IntlCollator::compareStrings):
+        * tools/JSDollarVM.cpp:
+        (JSC::functionMake16BitStringIfPossible):
+        (JSC::JSDollarVM::finishCreation):
+
 2019-10-28  Yusuke Suzuki  <ysuzuki@apple.com>
 

trunk/Source/JavaScriptCore/runtime/IntlCollator.cpp

@@ -343 +343 @@
 
     UErrorCode status = U_ZERO_ERROR;
-    UCharIterator iteratorX = createIterator(x);
-    UCharIterator iteratorY = createIterator(y);
-    auto result = ucol_strcollIter(m_collator.get(), &iteratorX, &iteratorY, &status);
+    UCollationResult result = UCOL_EQUAL;
+    if (x.is8Bit() && y.is8Bit() && x.isAllASCII() && y.isAllASCII())
+        result = ucol_strcollUTF8(m_collator.get(), bitwise_cast<const char*>(x.characters8()), x.length(), bitwise_cast<const char*>(y.characters8()), y.length(), &status);
+    else {
+        auto getCharacters = [&] (const StringView& view, Vector<UChar>& buffer) -> const UChar* {
+            if (!view.is8Bit())
+                return view.characters16();
+            buffer.resize(view.length());
+            StringImpl::copyCharacters(buffer.data(), view.characters8(), view.length());
+            return buffer.data();
+        };
+
+        Vector<UChar> xBuffer;
+        Vector<UChar> yBuffer;
+        const UChar* xCharacters = getCharacters(x, xBuffer);
+        const UChar* yCharacters = getCharacters(y, yBuffer);
+        result = ucol_strcoll(m_collator.get(), xCharacters, x.length(), yCharacters, y.length());
+    }
     if (U_FAILURE(status))
         return throwException(globalObject, scope, createError(globalObject, "Failed to compare strings."_s));

trunk/Source/JavaScriptCore/tools/JSDollarVM.cpp

@@ -2556 +2556 @@
 }
 
+static EncodedJSValue JSC_HOST_CALL functionMake16BitStringIfPossible(JSGlobalObject* globalObject, CallFrame* callFrame)
+{
+    DollarVMAssertScope assertScope;
+    VM& vm = globalObject->vm();
+    auto scope = DECLARE_THROW_SCOPE(vm);
+    String string = callFrame->argument(0).toWTFString(globalObject);
+    RETURN_IF_EXCEPTION(scope, { });
+    if (!string.is8Bit())
+        return JSValue::encode(jsString(vm, WTFMove(string)));
+    Vector<UChar> buffer;
+    buffer.resize(string.length());
+    StringImpl::copyCharacters(buffer.data(), string.characters8(), string.length());
+    return JSValue::encode(jsString(vm, String::adopt(WTFMove(buffer))));
+}
+
 void JSDollarVM::finishCreation(VM& vm)
 {
@@ -2678 +2693 @@
 
     addFunction(vm, "isWasmSupported", functionIsWasmSupported, 0);
+    addFunction(vm, "make16BitStringIfPossible", functionMake16BitStringIfPossible, 1);
 }
 

trunk/Source/WTF/ChangeLog

@@ +1 @@
+2019-10-29  Yusuke Suzuki  <ysuzuki@apple.com>
+
+        [JSC] Add fast path for String#localeCompare
+        https://bugs.webkit.org/show_bug.cgi?id=202676
+
+        Reviewed by Mark Lam.
+
+        * wtf/text/StringView.h:
+        (WTF::StringView::isAllASCII const):
+
 2019-10-26  Chris Lord  <clord@igalia.com>
 

trunk/Source/WTF/wtf/text/StringView.h

@@ -93 +93 @@
     const UChar* characters16() const;
 
+    bool isAllASCII() const;
+
     String toString() const;
     String toStringWithoutCopying() const;
@@ -404 +406 @@
 }
 
+inline bool StringView::isAllASCII() const
+{
+    if (is8Bit())
+        return charactersAreAllASCII(characters8(), length());
+    return charactersAreAllASCII(characters16(), length());
+}
+
 class StringView::UpconvertedCharacters {
     WTF_MAKE_FAST_ALLOCATED;

trunk/Tools/ChangeLog

@@ +1 @@
+2019-10-29  Yusuke Suzuki  <ysuzuki@apple.com>
+
+        [JSC] Add fast path for String#localeCompare
+        https://bugs.webkit.org/show_bug.cgi?id=202676
+
+        Reviewed by Mark Lam.
+
+        * TestWebKitAPI/Tests/WTF/StringView.cpp:
+        (TestWebKitAPI::TEST):
+
 2019-10-27  Wenson Hsieh  <wenson_hsieh@apple.com>
 

trunk/Tools/TestWebKitAPI/Tests/WTF/StringView.cpp

@@ -972 +972 @@
 }
 
+TEST(WTF, StringViewIsAllASCII)
+{
+    EXPECT_TRUE(StringView(String("Hello")).isAllASCII());
+    EXPECT_TRUE(StringView(String("Cocoa")).isAllASCII());
+    EXPECT_FALSE(StringView(String("📱")).isAllASCII());
+    EXPECT_FALSE(StringView(String("\u0080")).isAllASCII());
+    EXPECT_TRUE(StringView(String(bitwise_cast<const UChar*>(u"Hello"))).isAllASCII());
+}
+
 } // namespace TestWebKitAPI