DescriptionOrderIterator should be O(number of children)
The current implementation is O(number of children * order)!
This change introduces a faster way to iterate over the children by
using a HashMap to keep the subset of children for each 'order' value.
This is a speed vs memory tradeoff as we are now using
O(number of children + order) memory when the existing code was using
O(order) memory).
This is also a stepping stone to speed up CSS Grid Layout painting
and hit-testing by allowing arbitrary children to be collected into
the OrderIterator.
This change doesn't introduce any runtime performance in
PerformanceTests/Layout/flexbox-lots-of-data.html. In a test case
with 1000 flex items with different 'order' that get forced layout
in an infinite loop, this moves OrderIterator::next from the slowest
function (>80%) to among the other functions (~7%).
BUG=256804
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=154445
Patch Set 1 #
Total comments: 2
Messages
Total messages: 8 (0 generated)
|