Branch: refs/heads/main
Home: https://github.com/WebKit/WebKit
Commit: b24e9a4a55b5f96f91532375e98c36d7f879794a
https://github.com/WebKit/WebKit/commit/b24e9a4a55b5f96f91532375e98c36d7f879794a
Author: Chris Dumez <[email protected]>
Date: 2026-03-27 (Fri, 27 Mar 2026)
Changed paths:
M Source/WTF/wtf/Deque.h
M Tools/TestWebKitAPI/Tests/WTF/Deque.cpp
Log Message:
-----------
Optimize Deque::takeFirst(predicate) and takeLast(predicate)
https://bugs.webkit.org/show_bug.cgi?id=310877
Reviewed by Darin Adler.
The old implementation cycled elements through the deque: it would
`takeFirst/takeLast` each element, check the predicate, and `append/prepend`
non-matching elements to the opposite end. When a match was found at
position k, this required 2k+1 move-constructions (k to cycle past
non-matching elements, plus k more to unwind them back to their original
positions).
Replace this with `findIf` (or `std::find_if` with reverse iterators for
takeLast) to locate the matching element with zero moves, then a single
move to extract the result, followed by `remove(iterator)` to close the
gap. This reduces the total moves from O(2k) to O(min(k, n-k)), the cost
of `remove(iterator)` shifting the shorter side of the buffer.
Test: Tools/TestWebKitAPI/Tests/WTF/Deque.cpp
* Source/WTF/wtf/Deque.h:
* Tools/TestWebKitAPI/Tests/WTF/Deque.cpp:
(TestWebKitAPI::TEST(WTF_Deque, TakeFirstWithPredicate)):
(TestWebKitAPI::TEST(WTF_Deque, TakeFirstWithPredicateNoMatch)):
(TestWebKitAPI::TEST(WTF_Deque, TakeFirstWithPredicateFirstElement)):
(TestWebKitAPI::TEST(WTF_Deque, TakeFirstWithPredicateLastElement)):
(TestWebKitAPI::TEST(WTF_Deque, TakeFirstWithPredicateSingleElement)):
(TestWebKitAPI::TEST(WTF_Deque, TakeLastWithPredicate)):
(TestWebKitAPI::TEST(WTF_Deque, TakeLastWithPredicateNoMatch)):
(TestWebKitAPI::TEST(WTF_Deque, TakeLastWithPredicateLastElement)):
(TestWebKitAPI::TEST(WTF_Deque, TakeLastWithPredicateFirstElement)):
(TestWebKitAPI::TEST(WTF_Deque, TakeFirstWithPredicateWrappedBuffer)):
(TestWebKitAPI::TEST(WTF_Deque, TakeLastWithPredicateWrappedBuffer)):
Canonical link: https://commits.webkit.org/310141@main
To unsubscribe from these emails, change your notification settings at
https://github.com/WebKit/WebKit/settings/notifications
