Skip to content

Commit 8b7e7ed

Browse files
ConstellationConstellation
committed
[JSC] Improve String#split for uglify-js-wtb
https://bugs.webkit.org/show_bug.cgi?id=251823 rdar://105104781 Reviewed by Michael Saboff. This patch improves JetStream2/uglify-js-wtb by 1% with String#split optimizations. 1. We should just use ArrayWithContigous array for result of String#split, and let's say `1` capacity at least. At that point, we will always return an array with at least one capacity. So, let's avoid structure transition, and butterfly reallocation. 2. We should search for BoyerMoore lookahead character patterns with Greedy one-character pattern. For example, /\r?\n/ is very frequently used. We should search for [\r\n] character to start matching in this case. However, if we have /\r?\n/ pattern, 1. first character can be [\r\n] 2. second character can be null, or [\n] So, this confuses fixed-sized BoyerMoore lookahead generation. So, when we encounter greedy one-character pattern, we cut the BM prefix length at this point. So, in the above case, we only consider about first character [\r\n] case. This is still beneficial since previously we give up completely when we encounter greedy fixed-sized one-character pattern. ToT Patched string-split-space 130.3261+-0.7798 ^ 125.6028+-0.4402 ^ definitely 1.0376x faster string-split 206.8225+-1.1932 ^ 128.5716+-0.7137 ^ definitely 1.6086x faster * JSTests/microbenchmarks/string-split-space.js: Added. (split): * JSTests/microbenchmarks/string-split.js: Added. (split): * Source/JavaScriptCore/runtime/RegExpPrototype.cpp: (JSC::JSC_DEFINE_HOST_FUNCTION): * Source/JavaScriptCore/yarr/YarrJIT.cpp: Canonical link: https://commits.webkit.org/259941@main
1 parent 35591d2 commit 8b7e7ed

4 files changed

Lines changed: 134 additions & 18 deletions

File tree

‎JSTests/microbenchmarks/string-split-space.js‎

Lines changed: 11 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,11 @@
1+
var string = `Lorem ipsum dolor sit amet, consectetur adipiscing elit, sed do eiusmod tempor incididunt ut labore et dolore magna aliqua. Ut enim ad minim veniam, quis nostrud exercitation ullamco laboris nisi ut aliquip ex ea commodo consequat. Duis aute irure dolor in reprehenderit in voluptate velit esse cillum dolore eu fugiat nulla pariatur. Excepteur sint occaecat cupidatat non proident, sunt in culpa qui officia deserunt mollit anim id est laborum.`;
2+
3+
function split(string, regexp)
4+
{
5+
return string.split(regexp);
6+
}
7+
noInline(split);
8+
9+
var regexp = / /;
10+
for (var i = 0; i < 1e5; ++i)
11+
split(string, regexp);

‎JSTests/microbenchmarks/string-split.js‎

Lines changed: 79 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,79 @@
1+
var string = `Lorem
2+
ipsum
3+
dolor
4+
sit
5+
amet,
6+
consectetur
7+
adipiscing
8+
elit,
9+
sed
10+
do
11+
eiusmod
12+
tempor
13+
incididunt
14+
ut
15+
labore
16+
et
17+
dolore
18+
magna
19+
aliqua.
20+
Ut
21+
enim
22+
ad
23+
minim
24+
veniam,
25+
quis
26+
nostrud
27+
exercitation
28+
ullamco
29+
laboris
30+
nisi
31+
ut
32+
aliquip
33+
ex
34+
ea
35+
commodo
36+
consequat.
37+
Duis
38+
aute
39+
irure
40+
dolor
41+
in
42+
reprehenderit
43+
in
44+
voluptate
45+
velit
46+
esse
47+
cillum
48+
dolore
49+
eu
50+
fugiat
51+
nulla
52+
pariatur.
53+
Excepteur
54+
sint
55+
occaecat
56+
cupidatat
57+
non
58+
proident,
59+
sunt
60+
in
61+
culpa
62+
qui
63+
officia
64+
deserunt
65+
mollit
66+
anim
67+
id
68+
est
69+
laborum.`;
70+
71+
function split(string, regexp)
72+
{
73+
return string.split(regexp);
74+
}
75+
noInline(split);
76+
77+
var regexp = /\r?\n/;
78+
for (var i = 0; i < 1e5; ++i)
79+
split(string, regexp);

‎Source/JavaScriptCore/runtime/RegExpPrototype.cpp‎

Lines changed: 16 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -492,7 +492,7 @@ JSC_DEFINE_HOST_FUNCTION(regExpProtoFuncSplitFast, (JSGlobalObject* globalObject
492492
// 3. [handled by JS builtin] Let S be ? ToString(string).
493493
JSString* inputString = callFrame->argument(0).toString(globalObject);
494494
String input = inputString->value(globalObject);
495-
RETURN_IF_EXCEPTION(scope, encodedJSValue());
495+
RETURN_IF_EXCEPTION(scope, { });
496496
ASSERT(!input.isNull());
497497

498498
// 4. [handled by JS builtin] Let C be ? SpeciesConstructor(rx, %RegExp%).
@@ -505,14 +505,12 @@ JSC_DEFINE_HOST_FUNCTION(regExpProtoFuncSplitFast, (JSGlobalObject* globalObject
505505

506506
// 11. Let A be ArrayCreate(0).
507507
// 12. Let lengthA be 0.
508-
JSArray* result = constructEmptyArray(globalObject, nullptr);
509-
RETURN_IF_EXCEPTION(scope, encodedJSValue());
510508
unsigned resultLength = 0;
511509

512510
// 13. If limit is undefined, let lim be 2^32-1; else let lim be ? ToUint32(limit).
513511
JSValue limitValue = callFrame->argument(1);
514512
unsigned limit = limitValue.isUndefined() ? 0xFFFFFFFFu : limitValue.toUInt32(globalObject);
515-
RETURN_IF_EXCEPTION(scope, encodedJSValue());
513+
RETURN_IF_EXCEPTION(scope, { });
516514

517515
// 14. Let size be the number of elements in S.
518516
unsigned inputSize = input.length();
@@ -522,19 +520,21 @@ JSC_DEFINE_HOST_FUNCTION(regExpProtoFuncSplitFast, (JSGlobalObject* globalObject
522520

523521
// 16. If lim == 0, return A.
524522
if (!limit)
525-
return JSValue::encode(result);
523+
RELEASE_AND_RETURN(scope, JSValue::encode(constructEmptyArray(globalObject, nullptr)));
526524

527525
// 17. If size == 0, then
528526
if (input.isEmpty()) {
529527
// a. Let z be ? RegExpExec(splitter, S).
530528
// b. If z is not null, return A.
531529
// c. Perform ! CreateDataProperty(A, "0", S).
532530
// d. Return A.
531+
JSArray* result = constructEmptyArray(globalObject, nullptr);
532+
RETURN_IF_EXCEPTION(scope, { });
533533
auto matchResult = regexp->match(globalObject, input, 0);
534-
RETURN_IF_EXCEPTION(scope, encodedJSValue());
534+
RETURN_IF_EXCEPTION(scope, { });
535535
if (!matchResult) {
536536
result->putDirectIndex(globalObject, 0, inputString);
537-
RETURN_IF_EXCEPTION(scope, encodedJSValue());
537+
RETURN_IF_EXCEPTION(scope, { });
538538
}
539539
return JSValue::encode(result);
540540
}
@@ -546,6 +546,11 @@ JSC_DEFINE_HOST_FUNCTION(regExpProtoFuncSplitFast, (JSGlobalObject* globalObject
546546
bool regExpIsUnicode = regexp->unicode();
547547

548548
unsigned maxSizeForDirectPath = 100000;
549+
JSArray* result = JSArray::tryCreate(vm, globalObject->arrayStructureForIndexingTypeDuringAllocation(ArrayWithContiguous), 1);
550+
if (UNLIKELY(!result)) {
551+
throwOutOfMemoryError(globalObject, scope);
552+
return { };
553+
}
549554

550555
genericSplit(
551556
globalObject, regexp, input, inputSize, position, matchPosition, regExpIsSticky, regExpIsUnicode,
@@ -561,7 +566,7 @@ JSC_DEFINE_HOST_FUNCTION(regExpProtoFuncSplitFast, (JSGlobalObject* globalObject
561566
return AbortSplit;
562567
return ContinueSplit;
563568
});
564-
RETURN_IF_EXCEPTION(scope, encodedJSValue());
569+
RETURN_IF_EXCEPTION(scope, { });
565570

566571
if (resultLength >= limit)
567572
return JSValue::encode(result);
@@ -592,11 +597,11 @@ JSC_DEFINE_HOST_FUNCTION(regExpProtoFuncSplitFast, (JSGlobalObject* globalObject
592597
return AbortSplit;
593598
return ContinueSplit;
594599
});
595-
RETURN_IF_EXCEPTION(scope, encodedJSValue());
600+
RETURN_IF_EXCEPTION(scope, { });
596601

597602
if (resultLength + dryRunCount > MAX_STORAGE_VECTOR_LENGTH) {
598603
throwOutOfMemoryError(globalObject, scope);
599-
return encodedJSValue();
604+
return { };
600605
}
601606

602607
// OK, we know that if we finish the split, we won't have to OOM.
@@ -615,7 +620,7 @@ JSC_DEFINE_HOST_FUNCTION(regExpProtoFuncSplitFast, (JSGlobalObject* globalObject
615620
return AbortSplit;
616621
return ContinueSplit;
617622
});
618-
RETURN_IF_EXCEPTION(scope, encodedJSValue());
623+
RETURN_IF_EXCEPTION(scope, { });
619624

620625
if (resultLength >= limit)
621626
return JSValue::encode(result);

‎Source/JavaScriptCore/yarr/YarrJIT.cpp‎

Lines changed: 28 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -3890,14 +3890,21 @@ class YarrGenerator final : public YarrJITInfo {
38903890
case PatternTerm::Type::DotStarEnclosure:
38913891
break;
38923892
case PatternTerm::Type::CharacterClass: {
3893-
if (term.quantityType != QuantifierType::FixedCount || term.quantityMaxCount != 1)
3893+
if (term.quantityType != QuantifierType::FixedCount && term.quantityType != QuantifierType::Greedy)
38943894
break;
3895-
if (term.inputPosition != index)
3895+
if (term.quantityMaxCount != 1)
3896+
break;
3897+
if (term.inputPosition != cursor)
38963898
break;
38973899
auto& characterClass = *term.characterClass;
38983900
if (term.invert() || characterClass.m_anyCharacter) {
38993901
bmInfo.setAll(cursor);
3900-
++cursor;
3902+
// If this is greedy one-character pattern "a?", we should not increase cursor.
3903+
// If we see greedy pattern, then we cut bmInfo here to avoid possibility explosion.
3904+
if (term.quantityType == QuantifierType::FixedCount)
3905+
++cursor;
3906+
else
3907+
bmInfo.shortenLength(cursor + 1);
39013908
continue;
39023909
}
39033910
if (!characterClass.m_rangesUnicode.isEmpty())
@@ -3908,13 +3915,21 @@ class YarrGenerator final : public YarrJITInfo {
39083915
bmInfo.addRanges(cursor, characterClass.m_ranges);
39093916
if (!characterClass.m_matches.isEmpty())
39103917
bmInfo.addCharacters(cursor, characterClass.m_matches);
3911-
++cursor;
3918+
3919+
// If this is greedy one-character pattern "a?", we should not increase cursor.
3920+
// If we see greedy pattern, then we cut bmInfo here to avoid possibility explosion.
3921+
if (term.quantityType == QuantifierType::FixedCount)
3922+
++cursor;
3923+
else
3924+
bmInfo.shortenLength(cursor + 1);
39123925
continue;
39133926
}
39143927
case PatternTerm::Type::PatternCharacter: {
3915-
if (term.quantityType != QuantifierType::FixedCount || term.quantityMaxCount != 1)
3928+
if (term.quantityType != QuantifierType::FixedCount && term.quantityType != QuantifierType::Greedy)
3929+
break;
3930+
if (term.quantityMaxCount != 1)
39163931
break;
3917-
if (term.inputPosition != index)
3932+
if (term.inputPosition != cursor)
39183933
break;
39193934
if (U16_LENGTH(term.patternCharacter) != 1 && m_decodeSurrogatePairs)
39203935
break;
@@ -3926,7 +3941,13 @@ class YarrGenerator final : public YarrJITInfo {
39263941
bmInfo.set(cursor, toASCIILower(term.patternCharacter));
39273942
} else
39283943
bmInfo.set(cursor, term.patternCharacter);
3929-
++cursor;
3944+
3945+
// If this is greedy one-character pattern "a?", we should not increase cursor.
3946+
// If we see greedy pattern, then we cut bmInfo here to avoid possibility explosion.
3947+
if (term.quantityType == QuantifierType::FixedCount)
3948+
++cursor;
3949+
else
3950+
bmInfo.shortenLength(cursor + 1);
39303951
continue;
39313952
}
39323953
}

0 commit comments

Comments
 (0)