Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: cf507455abeb87f095f6013616fc883b89625297
https://github.com/WebKit/WebKit/commit/cf507455abeb87f095f6013616fc883b89625297
Author: Yusuke Suzuki <[email protected]>
Date: 2026-03-05 (Thu, 05 Mar 2026)
Changed paths:
M Source/WTF/wtf/text/AdaptiveStringSearcher.h
Log Message:
-----------
[WTF] Use simple SIMD pair search
https://bugs.webkit.org/show_bug.cgi?id=309157
rdar://171707400
Reviewed by Yijia Huang.
Boyer-Moore / Boyer-Moore-Horspool algorithms are elegant, but in many
cases, this is a bit hard to be executed on modern CPU due to frequent
table access and non-linear memory access via skipping. On modern CPU,
bulk scanning via SIMD in a predictable manner is simply faster in many
cases. This patch implements SIMD pair search, taking first and last
character from the needle and detecting the range which matches first
and last characters. And strictly checking this range is matching against
the needle.
But SIMD pair search can have drawbacks: if first and last characters are
the ones which can be seen frequently, and the pattern is adversarial,
then it becomes very slow. So when we failed with false-positive SIMD
matching 16 times, we switch to Boyer-Moore-Horspool.
* Source/WTF/wtf/text/AdaptiveStringSearcher.h:
(WTF::AdaptiveStringSearcher::AdaptiveStringSearcher):
(WTF::SubjectChar>::initialSearch):
Canonical link: https://commits.webkit.org/308755@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
