[webkit-changes] [WebKit/WebKit] d6426c: [JSC] Add BoyerMooreHorspool search to DFG / FTL

[Yusuke Suzuki]

  Branch: refs/heads/main
  Home:   https://github.com/WebKit/WebKit
  Commit: d6426c81236a2be90f2454d85ebf155d2e5beb4e
      https://github.com/WebKit/WebKit/commit/d6426c81236a2be90f2454d85ebf155d2e5beb4e
  Author: Yusuke Suzuki <ysuzuki at apple.com>
  Date:   2022-09-09 (Fri, 09 Sep 2022)

  Changed paths:
    A JSTests/microbenchmarks/string-replace-benchmark.js
    M PerformanceTests/DecoderTest/Configurations/Base.xcconfig
    M Source/JavaScriptCore/dfg/DFGCommonData.h
    M Source/JavaScriptCore/dfg/DFGGraph.h
    M Source/JavaScriptCore/dfg/DFGJITCompiler.cpp
    M Source/JavaScriptCore/dfg/DFGOperations.cpp
    M Source/JavaScriptCore/dfg/DFGOperations.h
    M Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp
    M Source/JavaScriptCore/ftl/FTLLink.cpp
    M Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp
    M Source/WTF/WTF.xcodeproj/project.pbxproj
    M Source/WTF/wtf/CMakeLists.txt
    M Source/WTF/wtf/text/ASCIILiteral.h
    A Source/WTF/wtf/text/StringSearch.h
    M Tools/TestWebKitAPI/CMakeLists.txt
    M Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj
    A Tools/TestWebKitAPI/Tests/WTF/StringSearch.cpp

  Log Message:
  -----------
  [JSC] Add BoyerMooreHorspool search to DFG / FTL
https://bugs.webkit.org/show_bug.cgi?id=244924

Reviewed by Alexey Shvayka.

In DFG / FTL, it is possible that we can find what string is used for searching in String#replace.
So, in compiler, we can construct preprocessed table so that we can make String#replace faster.

In this patch, we deploy Boyer-Moore-Horspool (BMH) search[1], which allows large skips for matching failures for substring,
accelerate the matching significantly. We use BMH since it offers good memory-performance tradeoff.

Currently, we deploy it only for pattern which is smaller than or equal to 256 length for table size efficiency.
We can extend it to 16bit offset table, 32bit offset table. But we consider it as a future work.

In microbenchmarks, we observed 43% improvement. We also found that this is 0.2-0.3% Speedometer2.1 improvement,
in particular Vanilla families get 1-2% improvement with high confidence.

                                         ToT                     Patched

    string-replace-benchmark      121.2814+-0.6856     ^     84.5948+-0.6012        ^ definitely 1.4337x faster

[1]: https://en.wikipedia.org/wiki/Boyer–Moore–Horspool_algorithm

* JSTests/microbenchmarks/string-replace-benchmark.js: Added.
(fill):
(test.template.li.data.id.string_appeared_here.div.input):
(test.template.li.data.id.string_appeared_here.div):
(test.label.button):
* Source/JavaScriptCore/dfg/DFGCommonData.h:
* Source/JavaScriptCore/dfg/DFGGraph.h:
* Source/JavaScriptCore/dfg/DFGJITCompiler.cpp:
(JSC::DFG::JITCompiler::link):
* Source/JavaScriptCore/dfg/DFGOperations.cpp:
(JSC::DFG::stringReplaceStringString):
(JSC::DFG::JSC_DEFINE_JIT_OPERATION):
* Source/JavaScriptCore/dfg/DFGOperations.h:
* Source/JavaScriptCore/dfg/DFGSpeculativeJIT.cpp:
* Source/JavaScriptCore/ftl/FTLLink.cpp:
(JSC::FTL::link):
* Source/JavaScriptCore/ftl/FTLLowerDFGToB3.cpp:
(JSC::FTL::DFG::LowerDFGToB3::compileCompareStrictEq):
* Source/WTF/WTF.xcodeproj/project.pbxproj:
* Source/WTF/wtf/CMakeLists.txt:
* Source/WTF/wtf/text/ASCIILiteral.h:
(WTF::ASCIILiteral::length const):
* Source/WTF/wtf/text/StringSearch.h: Added.
(WTF::BoyerMooreHorspoolTable::BoyerMooreHorspoolTable):
(WTF::BoyerMooreHorspoolTable::find const):
(WTF::BoyerMooreHorspoolTable::findInner const):
* Tools/TestWebKitAPI/CMakeLists.txt:
* Tools/TestWebKitAPI/TestWebKitAPI.xcodeproj/project.pbxproj:
* Tools/TestWebKitAPI/Tests/WTF/StringSearch.cpp: Added.
(TestWebKitAPI::TEST):

Canonical link: https://commits.webkit.org/254342@main