Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 802150baed8ddc888da813f8a5c076de17e152a3
https://github.com/WebKit/WebKit/commit/802150baed8ddc888da813f8a5c076de17e152a3
Author: Yusuke Suzuki <[email protected]>
Date: 2024-02-02 (Fri, 02 Feb 2024)
Changed paths:
A JSTests/stress/string-index-of-pathological.js
A JSTests/stress/v8-string-indexof-1.js
A JSTests/stress/v8-string-indexof-2.js
M Source/JavaScriptCore/dfg/DFGOperations.cpp
M Source/JavaScriptCore/runtime/StringPrototype.cpp
M Source/JavaScriptCore/runtime/StringPrototypeInlines.h
M Source/JavaScriptCore/runtime/VM.cpp
M Source/JavaScriptCore/runtime/VM.h
M Source/WTF/WTF.xcodeproj/project.pbxproj
M Source/WTF/wtf/CMakeLists.txt
M Source/WTF/wtf/text/ASCIIFastPath.h
A Source/WTF/wtf/text/AdaptiveStringSearcher.h
M Source/WTF/wtf/text/StringView.cpp
M Source/WTF/wtf/text/StringView.h
Log Message:
-----------
[WTF] Adopt adaptive string searching
https://bugs.webkit.org/show_bug.cgi?id=268635
rdar://121082299
Reviewed by Mark Lam.
This patch adopts V8's StringSearch class. We tailor it to our use and name it
AdaptiveStringSearcher.
We add `StringView::find(AdaptiveStringSearcherTables&, ...)` function which
uses `AdaptiveStringSearcher`,
when the table is attached. In this way, we can use this function even without
JSC VM for example.
The mechanism of this class is that, it requires additional space for large
table (AdaptiveStringSearcherTables).
And it *adaptively* switches string searching algorithm: linearSearch ->
boyerMooreHorspoolSearch -> boyerMooreSearch.
The reason is that the latter requires more costly preprocess to populate table
data. For very simple case, linearSearch suffice,
but for more complex cases, the preprocess gets paid, and
boyerMooreHorspoolSearch / boyerMooreSearch works better for performance.
* Source/JavaScriptCore/dfg/DFGOperations.cpp:
(JSC::DFG::JSC_DEFINE_JIT_OPERATION):
* Source/JavaScriptCore/runtime/StringPrototype.cpp:
(JSC::stringIndexOfImpl):
(JSC::JSC_DEFINE_HOST_FUNCTION):
(JSC::stringIncludesImpl):
* Source/JavaScriptCore/runtime/StringPrototypeInlines.h:
(JSC::stringReplaceStringString):
(JSC::replaceUsingStringSearch):
* Source/JavaScriptCore/runtime/VM.cpp:
(JSC::VM::VM):
* Source/JavaScriptCore/runtime/VM.h:
(JSC::VM::adaptiveStringSearcherTables):
* Source/WTF/WTF.xcodeproj/project.pbxproj:
* Source/WTF/wtf/CMakeLists.txt:
* Source/WTF/wtf/text/ASCIIFastPath.h:
(WTF::charactersAreAllLatin1):
* Source/WTF/wtf/text/AdaptiveStringSearcher.h: Added.
(WTF::AdaptiveStringSearcherBase::exceedsOneByte):
(WTF::AdaptiveStringSearcherBase::alignDown):
(WTF::AdaptiveStringSearcherBase::getHighestValueByte):
(WTF::AdaptiveStringSearcherBase::findFirstCharacter):
(WTF::AdaptiveStringSearcherTables::badCharShiftTable):
(WTF::AdaptiveStringSearcherTables::goodSuffixShiftTable):
(WTF::AdaptiveStringSearcherTables::suffixTable):
(WTF::AdaptiveStringSearcher::AdaptiveStringSearcher):
(WTF::AdaptiveStringSearcher::search):
(WTF::AdaptiveStringSearcher::alphabetSize):
(WTF::AdaptiveStringSearcher::failSearch):
(WTF::AdaptiveStringSearcher::charOccurrence):
(WTF::AdaptiveStringSearcher::badCharTable):
(WTF::AdaptiveStringSearcher::goodSuffixShiftTable):
(WTF::AdaptiveStringSearcher::suffixTable):
(WTF::SubjectChar>::singleCharSearch):
(WTF::SubjectChar>::linearSearch):
(WTF::SubjectChar>::boyerMooreSearch):
(WTF::SubjectChar>::populateBoyerMooreTable):
(WTF::SubjectChar>::boyerMooreHorspoolSearch):
(WTF::SubjectChar>::populateBoyerMooreHorspoolTable):
(WTF::SubjectChar>::initialSearch):
(WTF::searchString):
(WTF::searchStringRaw):
* Source/WTF/wtf/text/StringView.cpp:
(WTF::StringView::find const):
* Source/WTF/wtf/text/StringView.h:
Canonical link: https://commits.webkit.org/274033@main
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
