Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: 93f2fd68619bf07e0e12c2c78995ff5399e2c117
https://github.com/WebKit/WebKit/commit/93f2fd68619bf07e0e12c2c78995ff5399e2c117
Author: Sosuke Suzuki <[email protected]>
Date: 2026-02-06 (Fri, 06 Feb 2026)
Changed paths:
A JSTests/microbenchmarks/deep-rope-slice.js
A JSTests/microbenchmarks/shallow-rope-slice.js
A JSTests/stress/deep-rope-string-slice.js
M Source/JavaScriptCore/runtime/JSString.h
Log Message:
-----------
[JSC] Limit rope traversal depth in `tryJSSubstringImpl`
https://bugs.webkit.org/show_bug.cgi?id=307146
Reviewed by Yusuke Suzuki.
Deep rope strings constructed by repeated concatenation (e.g. s += 'A')
produce a degenerate rope tree of depth n. Each slice call traverses
from root to leaf in O(n), so n slices become O(n²)
In fact, an issue have been reported to Bun where its performance is
significantly inferior to that of Node.js due to this[1]
Convert the tail-recursive implementation to a bounded loop with a
maximum traversal depth of 16. When the limit is exceeded, return
nullptr so that the existing fallback in jsSubstring triggers
resolveRope, flattening the string and making subsequent slices O(1).
The results from the local JetStream were neutral.
Also after inserting debug logs and measuring the depth across the entire
JetStream3, I found that over 95% of the more than 15,000,000 calls to
tryJSSubstringImpl had a depth of 0, while it reached 8 only a single time.
TipOfTree Patched
deep-rope-slice 58.3524+-0.8240 ^ 0.3460+-0.0127 ^
definitely 168.6446x faster
shallow-rope-slice 0.4714+-0.0262 0.4465+-0.0244
might be 1.0556x faster
[1]: https://github.com/oven-sh/bun/issues/26682
Tests: JSTests/microbenchmarks/deep-rope-slice.js
JSTests/microbenchmarks/shallow-rope-slice.js
JSTests/stress/deep-rope-string-slice.js
* JSTests/microbenchmarks/deep-rope-slice.js: Added.
* JSTests/microbenchmarks/shallow-rope-slice.js: Added.
* JSTests/stress/deep-rope-string-slice.js: Added.
(makeDeepRope):
(makeFlat):
* Source/JavaScriptCore/runtime/JSString.h:
(JSC::tryJSSubstringImpl):
(JSC::jsSubstring):
Canonical link: https://commits.webkit.org/306936@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
