Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: e1def8f4e5fdd2c8cbce4fa68c8e228f02041e83
https://github.com/WebKit/WebKit/commit/e1def8f4e5fdd2c8cbce4fa68c8e228f02041e83
Author: Shu-yu Guo <[email protected]>
Date: 2026-07-31 (Fri, 31 Jul 2026)
Changed paths:
A JSTests/microbenchmarks/regexp-sequential-parencontext-groups.js
A JSTests/stress/regexp-parencontext-large-frame.js
A JSTests/stress/regexp-parencontext-multi-alt-backreference.js
A JSTests/stress/regexp-parencontext-sibling-frame-slots.js
M Source/JavaScriptCore/yarr/YarrJIT.cpp
M Source/JavaScriptCore/yarr/YarrPattern.cpp
M Source/JavaScriptCore/yarr/YarrPattern.h
Log Message:
-----------
[YARR] Don't save sibling and ancestor sibling frame slots for ParenContext
https://bugs.webkit.org/show_bug.cgi?id=318174
rdar://180908109
Reviewed by Yusuke Suzuki.
The YARR JIT's ParenContext save area, used to snapshot inter-iteration state
for capturing/backtrackable repeating parenthesized groups, was sized to the
entire pattern's call frame. This meant every repeating group's ParenContext
reserved space for, and coped on each iteration copied, its own interior frame
slots in addition to every sibling and ancestor-sibling term's frame slots.
For patterns with several repeating groups in sequence (e.g.
/(a|b)+(c|d)+(e|f)+.../), each group's frame slots are laid out after the
previous ones', so the whole-frame save area grows with the pattern and the
amount of work redundantly copied per group grows with it, resulting in the
copying being quadratic in the number of groups.
This PR optimizes copying the be linear.
A repeating group's PatternDisjunction is laid out at frame offsets
[frameLocation + YarrStackSpaceForBackTrackInfoParentheses, m_callFrameSize),
and nothing outside that range is ever touched while looping over that
group's iterations: a forward continuation into a following term
reinitializes that term's own backtrack slots before reading them, and a
backtrack into the group's own content only re-touches its own interior
range. So the save area only needs to be as large as the largest such
interior range across the whole pattern, and slots can be saved/restored
using indices relative to the group's own base rather than absolute
frame-slot indices.
ParenContext objects are fixed sizes for all parenthesized groups in a pattern.
Currently this is the whole pattern body's frame size. This PR changes it so
that it's the maximum interior frame size across all repeating groups.
This PR also adds a microbenchmark with a chain of 250 sequential quantified
alternation groups, matched and force-backtracked 3000 times. This change makes
this ~53x faster.
* JSTests/microbenchmarks/regexp-sequential-parencontext-groups.js: Added.
(buildPattern):
(buildMatchingInput):
* JSTests/stress/regexp-parencontext-large-frame.js: Added.
(shouldBe):
* JSTests/stress/regexp-parencontext-multi-alt-backreference.js: Added.
(shouldBe):
* JSTests/stress/regexp-parencontext-sibling-frame-slots.js: Added.
(shouldBe):
* Source/JavaScriptCore/yarr/YarrJIT.cpp:
* Source/JavaScriptCore/yarr/YarrPattern.cpp:
(JSC::Yarr::YarrPatternConstructor::setupAlternativeOffsets):
* Source/JavaScriptCore/yarr/YarrPattern.h:
(JSC::Yarr::YarrPattern::resetForReparsing):
Canonical link: https://commits.webkit.org/318318@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
