Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: da79705ade01755efb0bf2144b1636e4e744a592
https://github.com/WebKit/WebKit/commit/da79705ade01755efb0bf2144b1636e4e744a592
Author: Ahmad Saleem <[email protected]>
Date: 2026-09-04 (Fri, 04 Sep 2026)
Changed paths:
M Source/WTF/wtf/Vector.h
M Source/WebCore/page/scrolling/ScrollingStateTree.cpp
M Tools/TestWebKitAPI/Tests/WTF/Vector.cpp
Log Message:
-----------
ScrollingStateTree::insertNode does redundant work reordering children on
pages with many sibling scrolling nodes
https://bugs.webkit.org/show_bug.cgi?id=322891
rdar://186143008
Reviewed by Chris Dumez and Simon Fraser.
ScrollingStateNode keeps its children in a Vector. When insertNode() moves an
existing node to a new index it called removeChild() (a linear scan plus a tail
memmove) followed by insertChild()/appendChild() (another tail memmove). Since
registerScrollingNodeID() runs this once per layer during every compositing
update, a parent with N children that need reordering does more shifting than
necessary.
Add Vector::moveTo(), which relocates the element at one index to another by
lifting it out, shifting only the elements between the current and target
positions into the gap with Vector's own TypeOperations::moveOverlapping(), and
dropping it back at its new home. Every element outside that range stays put.
ScrollingStateTree::insertNode() now finds the node once and calls moveTo()
instead of remove + insert.
This is a constant-factor improvement, not an asymptotic one: the find() is
still O(n) and moveTo() shifts O(distance) elements, so a full reordering of N
siblings remains O(n^2) in the worst case. What it removes is the redundant
work each reorder did before -- one bounded shift instead of a full-length
remove memmove plus a full-length insert memmove -- and, in the common case
where a node moves only a short distance, the shift touches just the elements
in between rather than the whole tail.
The reorder path is unchanged behaviorally, so it stays covered by existing
tests. A childIndex of notFound (or otherwise past the end) still means
"append": it is clamped to the last slot, preserving the tolerance
insertChild() has long needed for the out-of-range indices that crash data
shows do occur, rather than tripping moveTo()'s bounds assertion. moveTo()
itself gets direct coverage in TestWebKitAPI, including same-position and
move-only element cases.
* Source/WTF/wtf/Vector.h:
(WTF::Vector::moveTo):
* Source/WebCore/page/scrolling/ScrollingStateTree.cpp:
(WebCore::ScrollingStateTree::insertNode):
* Tools/TestWebKitAPI/Tests/WTF/Vector.cpp:
(TestWebKitAPI::TEST):
Canonical link: https://commits.webkit.org/320527@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
