Log Message
[JSC] DUCET level-1 weighs are equal if characters are alphabets https://bugs.webkit.org/show_bug.cgi?id=224047
Reviewed by Saam Barati and Mark Lam.
JSTests:
* stress/ducet-level-3-or-4-comparison.js: Added.
(shouldBe):
Source/_javascript_Core:
ASCII comparison optimization was based on that DUCET level-1 weights are all different (except for 0000 case), but this was wrong.
If we have the same latin letters with different capitalization, then they have the same level-1 weight ('A' v.s. 'a').
In this patch,
1. If we found that the result of level-1 weight comparison is equal, and characters are not equal, then we do level-3 weight comparison.
We do not perform level-2 since they are all the same weight in ASCII (excluding control characters) region.
2. We do not perform level-4 weight comparison since level-1 and level-3 comparison must distinguish the strings. Level-1 weights are equal
only when characters are the same latin letters. And level-3 weight puts different weights for capital latin letters. Since we already know
that these strings are different while they are equal in level-1 weight comparison, the only case is that they have same latin letters in
the same position. In that case, level-3 weight must say different results for these characters so that we never meet "equal" status in
level-3 weight comparison if characters are different.
* runtime/IntlObject.cpp:
* runtime/IntlObject.h:
* runtime/IntlObjectInlines.h:
(JSC::canUseASCIIUCADUCETComparison):
(JSC::compareASCIIWithUCADUCETLevel3):
(JSC::compareASCIIWithUCADUCET):
Modified Paths
- trunk/JSTests/ChangeLog
- trunk/Source/_javascript_Core/ChangeLog
- trunk/Source/_javascript_Core/runtime/IntlObject.cpp
- trunk/Source/_javascript_Core/runtime/IntlObject.h
- trunk/Source/_javascript_Core/runtime/IntlObjectInlines.h
Added Paths
Diff
Modified: trunk/JSTests/ChangeLog (275652 => 275653)
--- trunk/JSTests/ChangeLog 2021-04-08 05:21:10 UTC (rev 275652)
+++ trunk/JSTests/ChangeLog 2021-04-08 05:48:03 UTC (rev 275653)
@@ -1,5 +1,15 @@
2021-04-07 Yusuke Suzuki <[email protected]>
+ [JSC] DUCET level-1 weighs are equal if characters are alphabets
+ https://bugs.webkit.org/show_bug.cgi?id=224047
+
+ Reviewed by Saam Barati and Mark Lam.
+
+ * stress/ducet-level-3-or-4-comparison.js: Added.
+ (shouldBe):
+
+2021-04-07 Yusuke Suzuki <[email protected]>
+
[JSC] Update test262
https://bugs.webkit.org/show_bug.cgi?id=224272
Added: trunk/JSTests/stress/ducet-level-3-or-4-comparison.js (0 => 275653)
--- trunk/JSTests/stress/ducet-level-3-or-4-comparison.js (rev 0)
+++ trunk/JSTests/stress/ducet-level-3-or-4-comparison.js 2021-04-08 05:48:03 UTC (rev 275653)
@@ -0,0 +1,18 @@
+function shouldBe(actual, expected) {
+ if (actual !== expected)
+ throw new Error('bad value: ' + actual);
+}
+
+var collator = new Intl.Collator('en-US');
+
+shouldBe(collator.compare("ABC", "ABD Ã"), -1);
+shouldBe(collator.compare("ABD Ã", "AbE"), -1);
+shouldBe(collator.compare("AbE", "ABC"), 1);
+shouldBe(collator.compare("ABC", "abc"), 1);
+shouldBe(collator.compare("ABC", "ABC"), 0);
+shouldBe(collator.compare("abc", "abc"), 0);
+shouldBe(collator.compare("abc", "abC"), -1);
+
+shouldBe(collator.compare("AB - AS Foobar", "AB - AS Pulheim Käther"), -1);
+shouldBe(collator.compare("AB - AS Pulheim Käther", "Abz - Baz Qux"), -1);
+shouldBe(collator.compare("Abz - Baz Qux", "AB - AS Foobar"), 1);
Modified: trunk/Source/_javascript_Core/ChangeLog (275652 => 275653)
--- trunk/Source/_javascript_Core/ChangeLog 2021-04-08 05:21:10 UTC (rev 275652)
+++ trunk/Source/_javascript_Core/ChangeLog 2021-04-08 05:48:03 UTC (rev 275653)
@@ -1,3 +1,29 @@
+2021-04-07 Yusuke Suzuki <[email protected]>
+
+ [JSC] DUCET level-1 weighs are equal if characters are alphabets
+ https://bugs.webkit.org/show_bug.cgi?id=224047
+
+ Reviewed by Saam Barati and Mark Lam.
+
+ ASCII comparison optimization was based on that DUCET level-1 weights are all different (except for 0000 case), but this was wrong.
+ If we have the same latin letters with different capitalization, then they have the same level-1 weight ('A' v.s. 'a').
+ In this patch,
+
+ 1. If we found that the result of level-1 weight comparison is equal, and characters are not equal, then we do level-3 weight comparison.
+ We do not perform level-2 since they are all the same weight in ASCII (excluding control characters) region.
+ 2. We do not perform level-4 weight comparison since level-1 and level-3 comparison must distinguish the strings. Level-1 weights are equal
+ only when characters are the same latin letters. And level-3 weight puts different weights for capital latin letters. Since we already know
+ that these strings are different while they are equal in level-1 weight comparison, the only case is that they have same latin letters in
+ the same position. In that case, level-3 weight must say different results for these characters so that we never meet "equal" status in
+ level-3 weight comparison if characters are different.
+
+ * runtime/IntlObject.cpp:
+ * runtime/IntlObject.h:
+ * runtime/IntlObjectInlines.h:
+ (JSC::canUseASCIIUCADUCETComparison):
+ (JSC::compareASCIIWithUCADUCETLevel3):
+ (JSC::compareASCIIWithUCADUCET):
+
2021-04-02 Darin Adler <[email protected]>
Use Hasher more, remove IntegerHasher, fix hashing-related mistakes
Modified: trunk/Source/_javascript_Core/runtime/IntlObject.cpp (275652 => 275653)
--- trunk/Source/_javascript_Core/runtime/IntlObject.cpp 2021-04-08 05:21:10 UTC (rev 275652)
+++ trunk/Source/_javascript_Core/runtime/IntlObject.cpp 2021-04-08 05:48:03 UTC (rev 275653)
@@ -432,11 +432,16 @@
// 3. If an input is an ASCII string, no multiple character collation elements exist. So no special handling in UCA step-2 is required. For example, "L·" is not ASCII.
// 4. UCA step-3 handles 0000 weighted characters specially. And ASCII contains these characters. But 0000 elements are used only for rare control characters.
// We can ignore this special handling if ASCII strings do not include control characters.
-// 5. Except 0000 cases, all characters' level-1 weights are different. And level-2 weights are always 0020, which is lower than any level-1 weights.
-// This means that binary comparison in UCA step-4 do not need to check level 2~ weights.
+// 5. Level-1 weights are different except for 0000 cases and capital / lower ASCII characters. All non-0000 elements are larger than 0000.
+// 6. Level-2 weights are always 0020 except for 0000 cases. So if we include 0000 characters, we do not need to perform level-2 weight comparison.
+// 7. In all levels, characters have non-0000 weights if it does not have 0000 weight in level-1.
+// 8. In level-1, weights are the same only when characters are the same latin letters ('A' v.s. 'a'). If level-1 weight comparison says EQUAL, and if characters are not binary-equal,
+// then, the only case is they are including the same latin letters with different capitalization at the same position. Level-3 weight comparison must distinguish them since level-3
+// weight is set only for latin capital letters. Thus, we do not need to perform level-4 weight comparison.
//
-// Based on the above observation, our fast path handles ASCII strings excluding control characters. The following weight is recomputed weights from level-1 weights.
-const uint8_t ducetWeights[128] = {
+// Based on the above observation, our fast path handles ASCII strings excluding control characters. We first compare strings with level-1 weights. And then,
+// if we found they are the same and if we found they are not binary-equal strings, then we perform comparison with level-3 and level-4 weights.
+const uint8_t ducetLevel1Weights[128] = {
0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 2, 3, 4, 5, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0,
@@ -445,16 +450,37 @@
17, 18, 24, 32, 9, 8, 14, 25,
39, 40, 41, 42, 43, 44, 45, 46,
47, 48, 11, 10, 33, 34, 35, 13,
- 23, 50, 52, 54, 56, 58, 60, 62,
- 64, 66, 68, 70, 72, 74, 76, 78,
- 80, 82, 84, 86, 88, 90, 92, 94,
- 96, 98, 100, 19, 26, 20, 31, 7,
- 30, 49, 51, 53, 55, 57, 59, 61,
- 63, 65, 67, 69, 71, 73, 75, 77,
- 79, 81, 83, 85, 87, 89, 91, 93,
- 95, 97, 99, 21, 36, 22, 37, 0,
+ 23, 49, 50, 51, 52, 53, 54, 55,
+ 56, 57, 58, 59, 60, 61, 62, 63,
+ 64, 65, 66, 67, 68, 69, 70, 71,
+ 72, 73, 74, 19, 26, 20, 31, 7,
+ 30, 49, 50, 51, 52, 53, 54, 55,
+ 56, 57, 58, 59, 60, 61, 62, 63,
+ 64, 65, 66, 67, 68, 69, 70, 71,
+ 72, 73, 74, 21, 36, 22, 37, 0,
};
+// Level 2 are all zeros.
+
+const uint8_t ducetLevel3Weights[128] = {
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 1, 1, 1, 1, 1, 1, 1,
+ 1, 1, 1, 1, 1, 1, 1, 1,
+ 1, 1, 1, 1, 1, 1, 1, 1,
+ 1, 1, 1, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0,
+};
+
const LocaleSet& intlCollatorAvailableLocales()
{
static LazyNeverDestroyed<LocaleSet> availableLocales;
Modified: trunk/Source/_javascript_Core/runtime/IntlObject.h (275652 => 275653)
--- trunk/Source/_javascript_Core/runtime/IntlObject.h 2021-04-08 05:21:10 UTC (rev 275652)
+++ trunk/Source/_javascript_Core/runtime/IntlObject.h 2021-04-08 05:48:03 UTC (rev 275653)
@@ -35,7 +35,8 @@
namespace JSC {
-extern const uint8_t ducetWeights[128];
+extern const uint8_t ducetLevel1Weights[128];
+extern const uint8_t ducetLevel3Weights[128];
enum class LocaleMatcher : uint8_t {
Lookup,
Modified: trunk/Source/_javascript_Core/runtime/IntlObjectInlines.h (275652 => 275653)
--- trunk/Source/_javascript_Core/runtime/IntlObjectInlines.h 2021-04-08 05:21:10 UTC (rev 275652)
+++ trunk/Source/_javascript_Core/runtime/IntlObjectInlines.h 2021-04-08 05:48:03 UTC (rev 275653)
@@ -154,12 +154,28 @@
ALWAYS_INLINE bool canUseASCIIUCADUCETComparison(UChar character)
{
- return isASCII(character) && ducetWeights[character];
+ return isASCII(character) && ducetLevel1Weights[character];
}
template<typename CharacterType1, typename CharacterType2>
+UCollationResult compareASCIIWithUCADUCETLevel3(const CharacterType1* characters1, const CharacterType2* characters2, unsigned length)
+{
+ for (unsigned position = 0; position < length; ++position) {
+ auto lhs = characters1[position];
+ auto rhs = characters2[position];
+ uint8_t leftWeight = ducetLevel3Weights[lhs];
+ uint8_t rightWeight = ducetLevel3Weights[rhs];
+ if (leftWeight == rightWeight)
+ continue;
+ return leftWeight > rightWeight ? UCOL_GREATER : UCOL_LESS;
+ }
+ return UCOL_EQUAL;
+}
+
+template<typename CharacterType1, typename CharacterType2>
inline UCollationResult compareASCIIWithUCADUCET(const CharacterType1* characters1, unsigned length1, const CharacterType2* characters2, unsigned length2)
{
+ bool notSameCharacters = false;
unsigned commonLength = std::min(length1, length2);
for (unsigned position = 0; position < commonLength; ++position) {
auto lhs = characters1[position];
@@ -166,15 +182,21 @@
auto rhs = characters2[position];
ASSERT(canUseASCIIUCADUCETComparison(lhs));
ASSERT(canUseASCIIUCADUCETComparison(rhs));
- uint8_t leftWeight = ducetWeights[lhs];
- uint8_t rightWeight = ducetWeights[rhs];
+ if (lhs == rhs)
+ continue;
+ notSameCharacters = true;
+ uint8_t leftWeight = ducetLevel1Weights[lhs];
+ uint8_t rightWeight = ducetLevel1Weights[rhs];
if (leftWeight == rightWeight)
continue;
return leftWeight > rightWeight ? UCOL_GREATER : UCOL_LESS;
}
- if (length1 == length2)
+ if (length1 == length2) {
+ if (notSameCharacters)
+ return compareASCIIWithUCADUCETLevel3(characters1, characters2, length1);
return UCOL_EQUAL;
+ }
return length1 > length2 ? UCOL_GREATER : UCOL_LESS;
}
_______________________________________________ webkit-changes mailing list [email protected] https://lists.webkit.org/mailman/listinfo/webkit-changes
