Changeset 280570 in webkit
- Timestamp:
- Aug 2, 2021, 4:43:16 PM (5 years ago)
- Location:
- trunk
- Files:
-
- 3 added
- 4 edited
-
JSTests/ChangeLog (modified) (1 diff)
-
JSTests/stress/regexp-bm-search-character-non-fixed-size.js (added)
-
JSTests/stress/regexp-bm-search-many-candidate-zero-length.js (added)
-
JSTests/stress/regexp-bm-search-non-fixed-size.js (added)
-
Source/JavaScriptCore/ChangeLog (modified) (1 diff)
-
Source/JavaScriptCore/yarr/YarrJIT.cpp (modified) (13 diffs)
-
Source/JavaScriptCore/yarr/YarrJIT.h (modified) (3 diffs)
Legend:
- Unmodified
- Added
- Removed
-
trunk/JSTests/ChangeLog
r280546 r280570 1 2021-08-02 Yusuke Suzuki <ysuzuki@apple.com> 2 3 [JSC] Yarr BoyerMoore search should support character-class 4 https://bugs.webkit.org/show_bug.cgi?id=228613 5 6 Reviewed by Saam Barati. 7 8 * stress/regexp-bm-search-character-non-fixed-size.js: Added. 9 (shouldBe): 10 * stress/regexp-bm-search-many-candidate-zero-length.js: Added. 11 (shouldBe): 12 (regexp.a.b.c.d.e.f.g.h.i.j.k.l.m.n.o.p.q.r.s.t.u.v.w.x.y.z.0.1.2.3.4.5.6.7.8.9.t.v.n.r): 13 * stress/regexp-bm-search-non-fixed-size.js: Added. 14 (shouldBe): 15 1 16 2021-08-02 Yusuke Suzuki <ysuzuki@apple.com> 2 17 -
trunk/Source/JavaScriptCore/ChangeLog
r280569 r280570 1 2021-08-02 Yusuke Suzuki <ysuzuki@apple.com> 2 3 [JSC] Yarr BoyerMoore search should support character-class 4 https://bugs.webkit.org/show_bug.cgi?id=228613 5 6 Reviewed by Saam Barati. 7 8 This patch adds character-class support for BoyerMoore lookahead search in Yarr. 9 Currently, we only support fixed-sized character-class. We can extend it for repeat cases in the future. 10 11 To apply this character-class thing to jQuery's RegExp, we also allow non-fixed-sized disjunction. 12 For example, /aaaa.*|bbbb/'s disjunction is not fixed-sized. But still we can use (aaaa|bbbb) prefix since 13 this part is fixed-sized and we know minimum-size of this disjunction is 4. 14 15 Plus, instead of giving up BoyerMoore search when we found non-supported terms, we shorten BoyerMoore search 16 length not to include this term so that we can still have a chance to leverage BoyerMoore search. In the case 17 of /aaaa|bbbb|ccc(d|e|f)/, we previously gave up since it finds `(d|e|f)`. But now, instead we shorten the length 18 from 4 to 3, and construct search pattern with `aaa|bbb|ccc`. 19 20 This patch improves jquery-todomvc-regexp by 20%. 21 22 ToT Patched 23 24 jquery-todomvc-regexp 545.3561+-0.6968 ^ 451.6117+-0.4613 ^ definitely 1.2076x faster 25 26 This improves Speedometer2/jQuery-TodoMVC by 2%. 27 28 ---------------------------------------------------------------------------------------------------------------------------------- 29 | subtest | ms | ms | b / a | pValue (significance using False Discovery Rate) | 30 ---------------------------------------------------------------------------------------------------------------------------------- 31 | Elm-TodoMVC |123.470833 |123.550000 |1.000641 | 0.841600 | 32 | VueJS-TodoMVC |26.883333 |26.950000 |1.002480 | 0.846732 | 33 | EmberJS-TodoMVC |127.708333 |127.754167 |1.000359 | 0.934206 | 34 | BackboneJS-TodoMVC |50.545833 |50.445833 |0.998022 | 0.679610 | 35 | Preact-TodoMVC |20.879167 |20.791667 |0.995809 | 0.796541 | 36 | AngularJS-TodoMVC |137.479167 |137.275000 |0.998515 | 0.729817 | 37 | Vanilla-ES2015-TodoMVC |69.079167 |68.912500 |0.997587 | 0.524325 | 38 | Inferno-TodoMVC |65.604167 |66.120833 |1.007876 | 0.145549 | 39 | Flight-TodoMVC |77.029167 |76.708333 |0.995835 | 0.518562 | 40 | Angular2-TypeScript-TodoMVC |40.516667 |40.812500 |1.007302 | 0.513386 | 41 | VanillaJS-TodoMVC |54.762500 |54.895833 |1.002435 | 0.647381 | 42 | jQuery-TodoMVC |255.950000 |250.425000 |0.978414 | 0.000000 (significant) | 43 | EmberJS-Debug-TodoMVC |341.745833 |342.804167 |1.003097 | 0.219937 | 44 | React-TodoMVC |88.854167 |88.700000 |0.998265 | 0.568405 | 45 | React-Redux-TodoMVC |151.266667 |150.804167 |0.996942 | 0.256403 | 46 | Vanilla-ES2015-Babel-Webpack-TodoMVC |65.783333 |65.645833 |0.997910 | 0.437464 | 47 ---------------------------------------------------------------------------------------------------------------------------------- 48 a mean = 246.52898 49 b mean = 246.85128 50 pValue = 0.3927330278 51 (Bigger means are better.) 52 1.001 times better 53 Results ARE NOT significant 54 55 * yarr/YarrJIT.cpp: 56 (JSC::Yarr::BoyerMooreInfo::shortenLength): 57 (JSC::Yarr::BoyerMooreInfo::setAll): 58 (JSC::Yarr::BoyerMooreInfo::addCharacters): 59 (JSC::Yarr::BoyerMooreInfo::addRanges): 60 * yarr/YarrJIT.h: 61 (JSC::Yarr::BoyerMooreBitmap::add): 62 (JSC::Yarr::BoyerMooreBitmap::addCharacters): 63 (JSC::Yarr::BoyerMooreBitmap::addRanges): 64 (JSC::Yarr::BoyerMooreBitmap::setAll): 65 (JSC::Yarr::BoyerMooreBitmap::isAllSet const): 66 1 67 2021-08-02 Stephan Szabo <stephan.szabo@sony.com> 2 68 -
trunk/Source/JavaScriptCore/yarr/YarrJIT.cpp
r280544 r280570 64 64 65 65 unsigned length() const { return m_characters.size(); } 66 void shortenLength(unsigned length) 67 { 68 ASSERT(length <= this->length()); 69 m_characters.shrink(length); 70 } 66 71 67 72 void set(unsigned index, UChar32 character) 68 73 { 69 74 m_characters[index].add(character); 75 } 76 77 void setAll(unsigned index) 78 { 79 m_characters[index].setAll(); 80 } 81 82 void addCharacters(unsigned index, const Vector<UChar32>& characters) 83 { 84 m_characters[index].addCharacters(characters); 85 } 86 87 void addRanges(unsigned index, const Vector<CharacterRange>& range) 88 { 89 m_characters[index].addRanges(range); 70 90 } 71 91 … … 125 145 unsigned end = 0; 126 146 constexpr unsigned maxCandidatesPerCharacter = 32; 147 static_assert(maxCandidatesPerCharacter < BoyerMooreBitmap::mapSize); 127 148 for (unsigned limit = 4; limit < maxCandidatesPerCharacter; limit *= 2) { 128 149 auto [newPoint, newBegin, newEnd] = findBestCharacterSequence(limit); … … 2382 2403 unsigned mapCount = map.count(); 2383 2404 // If candiate characters are <= 2, checking each is better than using vector. 2405 JumpList outOfLengthFailure; 2406 JumpList matched; 2407 dataLogLnIf(YarrJITInternal::verbose, "BM Bitmap is ", map); 2408 // Patterns like /[]/ have zero candidates. Since it is rare, we do not do nothing for now. 2409 if (!mapCount) 2410 break; 2384 2411 if (mapCount <= 2) { 2385 2412 UChar32 character1 = map.findBit(0, true); … … 2392 2419 dataLogLnIf(Options::verboseRegExpCompilation(), "Found 1-or-2 characters lookahead character:(0x", hex(character1), "),character2:(", hex(character2), "),isMaskEffective:(", isMaskEffective,"),range:[", beginIndex, ", ", endIndex, ")"); 2393 2420 2394 JumpList matched;2395 2421 auto loopHead = label(); 2396 2422 readCharacter(m_checkedOffset - endIndex + 1, regT0); … … 2400 2426 if (mapCount == 2) 2401 2427 matched.append(branch32(Equal, regT0, TrustedImm32(character2))); 2402 o p.m_jumps.append(jumpIfNoAvailableInput(endIndex - beginIndex));2428 outOfLengthFailure.append(jumpIfNoAvailableInput(endIndex - beginIndex)); 2403 2429 jump().linkTo(loopHead, this); 2404 matched.link(this);2405 2430 } else { 2406 2431 const auto* pointer = getBoyerMooreBitmap(map); … … 2417 2442 load64(BaseIndex(regT1, regT2, TimesEight), regT2); 2418 2443 urshift64(regT0, regT2); // We can ignore upper bits and only lower 6bits are effective. 2419 auto matched = branchTest64(NonZero, regT2, TrustedImm32(1));2444 matched.append(branchTest64(NonZero, regT2, TrustedImm32(1))); 2420 2445 #elif CPU(X86_64) 2421 2446 static_assert(sizeof(BoyerMooreBitmap::Map::WordType) == sizeof(uint64_t)); … … 2426 2451 and32(TrustedImm32(1), regT2); 2427 2452 load64(BaseIndex(regT1, regT2, TimesEight), regT2); 2428 auto matched = branchTestBit64(NonZero, regT2, regT0); // We can ignore upper bits since modulo-64 is performed.2453 matched.append(branchTestBit64(NonZero, regT2, regT0)); // We can ignore upper bits since modulo-64 is performed. 2429 2454 #else 2430 2455 static_assert(sizeof(BoyerMooreBitmap::Map::WordType) == sizeof(uint32_t)); … … 2436 2461 load32(BaseIndex(regT1, regT2, TimesFour), regT2); 2437 2462 urshift32(regT0, regT2); // We can ignore upper bits and only lower 5bits are effective. 2438 auto matched = branchTest32(NonZero, regT2, TrustedImm32(1));2439 #endif 2440 o p.m_jumps.append(jumpIfNoAvailableInput(endIndex - beginIndex));2463 matched.append(branchTest32(NonZero, regT2, TrustedImm32(1))); 2464 #endif 2465 outOfLengthFailure.append(jumpIfNoAvailableInput(endIndex - beginIndex)); 2441 2466 jump().linkTo(loopHead, this); 2442 matched.link(this);2443 2467 } 2444 2468 2445 2469 // If the pattern size is not fixed, then store the start index for use if we match. 2470 // This is used for adjusting match-start when we failed to find the start with BoyerMoore search. 2471 if (!m_pattern.m_body->m_hasFixedSize) { 2472 outOfLengthFailure.link(this); 2473 if (alternative->m_minimumSize) { 2474 move(index, regT0); 2475 sub32(Imm32(alternative->m_minimumSize), regT0); 2476 setMatchStart(regT0); 2477 } else 2478 setMatchStart(index); 2479 op.m_jumps.append(jump()); 2480 } else 2481 op.m_jumps.append(outOfLengthFailure); 2482 2483 matched.link(this); 2484 // If the pattern size is not fixed, then store the start index for use if we match. 2485 // This is used for adjusting match-start when we start pattern matching with the updated index 2486 // by BoyerMoore search. 2446 2487 if (!m_pattern.m_body->m_hasFixedSize) { 2447 2488 if (alternative->m_minimumSize) { … … 3843 3884 // FIXME: Support unicode flag. 3844 3885 // https://bugs.webkit.org/show_bug.cgi?id=228611 3845 if (disjunction->m_minimumSize && disjunction->m_hasFixedSize &&!m_pattern.sticky() && !m_pattern.unicode()) {3886 if (disjunction->m_minimumSize && !m_pattern.sticky() && !m_pattern.unicode()) { 3846 3887 auto bmInfo = BoyerMooreInfo::create(std::min<unsigned>(disjunction->m_minimumSize, BoyerMooreInfo::maxLength)); 3847 3888 if (collectBoyerMooreInfo(disjunction, currentAlternativeIndex, bmInfo.get())) { … … 3891 3932 // that and construct fast searching with long stride. 3892 3933 3893 ASSERT(disjunction->m_hasFixedSize); // We only support fixed-sized lookahead for BoyerMoore search.3894 3934 ASSERT(disjunction->m_minimumSize); 3895 3935 3896 3936 // FIXME: Support nested disjunctions (e.g. /(?:abc|def|g(?:hi|jk))/). 3897 3937 // https://bugs.webkit.org/show_bug.cgi?id=228614 3898 // FIXME: Support character-class (e.g. /[\d]test/).3899 // https://bugs.webkit.org/show_bug.cgi?id=2286133900 3938 // FIXME: Support non-fixed-sized lookahead (e.g. /.*abc/ and extract "abc" sequence). 3901 3939 // https://bugs.webkit.org/show_bug.cgi?id=228612 … … 3910 3948 case PatternTerm::Type::AssertionEOL: 3911 3949 case PatternTerm::Type::AssertionWordBoundary: 3912 case PatternTerm::Type::CharacterClass:3913 3950 case PatternTerm::Type::BackReference: 3914 3951 case PatternTerm::Type::ForwardReference: … … 3916 3953 case PatternTerm::Type::ParentheticalAssertion: 3917 3954 case PatternTerm::Type::DotStarEnclosure: 3918 return false; 3955 break; 3956 case PatternTerm::Type::CharacterClass: { 3957 if (term.quantityType != QuantifierType::FixedCount || term.quantityMaxCount != 1) 3958 break; 3959 if (term.inputPosition != index) 3960 break; 3961 auto& characterClass = *term.characterClass; 3962 if (term.invert() || characterClass.m_anyCharacter) { 3963 bmInfo.setAll(cursor); 3964 ++cursor; 3965 continue; 3966 } 3967 if (characterClass.m_table) { 3968 bmInfo.setAll(cursor); 3969 ++cursor; 3970 continue; 3971 } 3972 if (!characterClass.m_rangesUnicode.isEmpty()) 3973 bmInfo.addRanges(cursor, characterClass.m_rangesUnicode); 3974 if (!characterClass.m_matchesUnicode.isEmpty()) 3975 bmInfo.addCharacters(cursor, characterClass.m_matchesUnicode); 3976 if (!characterClass.m_ranges.isEmpty()) 3977 bmInfo.addRanges(cursor, characterClass.m_ranges); 3978 if (!characterClass.m_matches.isEmpty()) 3979 bmInfo.addCharacters(cursor, characterClass.m_matches); 3980 ++cursor; 3981 continue; 3982 } 3919 3983 case PatternTerm::Type::PatternCharacter: { 3920 3984 if (term.quantityType != QuantifierType::FixedCount || term.quantityMaxCount != 1) 3921 return false;3985 break; 3922 3986 if (term.inputPosition != index) 3923 return false;3987 break; 3924 3988 if (U16_LENGTH(term.patternCharacter) != 1 && m_decodeSurrogatePairs) 3925 return false;3989 break; 3926 3990 // For case-insesitive compares, non-ascii characters that have different 3927 3991 // upper & lower case representations are already converted to a character class. … … 3933 3997 bmInfo.set(cursor, term.patternCharacter); 3934 3998 ++cursor; 3935 break;3999 continue; 3936 4000 } 3937 4001 } 3938 } 3939 } 3940 dataLogLnIf(YarrJITInternal::verbose, "Characters collected"); 3941 return true; 4002 dataLogLnIf(YarrJITInternal::verbose, "Shortening to ", cursor); 4003 bmInfo.shortenLength(cursor); 4004 break; 4005 } 4006 } 4007 return bmInfo.length(); 3942 4008 } 3943 4009 -
trunk/Source/JavaScriptCore/yarr/YarrJIT.h
r280544 r280570 62 62 63 63 class BoyerMooreBitmap { 64 WTF_MAKE_NONCOPYABLE(BoyerMooreBitmap); 64 65 WTF_MAKE_FAST_ALLOCATED(BoyerMooreBitmap); 65 66 public: … … 76 77 void add(UChar32 character) 77 78 { 79 if (isAllSet()) 80 return; 78 81 unsigned position = character & mapMask; 79 82 if (position != static_cast<unsigned>(character)) … … 84 87 } 85 88 } 89 90 void addCharacters(const Vector<UChar32>& characters) 91 { 92 if (isAllSet()) 93 return; 94 if (characters.size() >= mapSize) { 95 setAll(); 96 return; 97 } 98 for (UChar character : characters) 99 add(character); 100 } 101 102 void addRanges(const Vector<CharacterRange>& ranges) 103 { 104 if (ranges.size() >= mapSize) { 105 setAll(); 106 return; 107 } 108 for (CharacterRange range : ranges) { 109 if (isAllSet()) 110 return; 111 if (static_cast<unsigned>(range.end - range.begin + 1) >= mapSize) { 112 setAll(); 113 return; 114 } 115 for (UChar32 character = range.begin; character <= range.end; ++character) 116 add(character); 117 } 118 } 119 120 void setAll() 121 { 122 m_count = mapSize; 123 } 124 125 bool isAllSet() const { return m_count == mapSize; } 86 126 87 127 private:
Note:
See TracChangeset
for help on using the changeset viewer.
