OrderIterator refactoring to avoid extra loops
authorrego@igalia.com <rego@igalia.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 28 Apr 2014 08:27:06 +0000 (08:27 +0000)
committerrego@igalia.com <rego@igalia.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Mon, 28 Apr 2014 08:27:06 +0000 (08:27 +0000)
commit794e1eccaefc384306c1e450f7e9fae0e2a659a6
treeefe5e0cb465b7f6bfb8f3c19e2d5ca615766c30b
parent70c667718f32e618343bd17544e665cb295c2693
OrderIterator refactoring to avoid extra loops
https://bugs.webkit.org/show_bug.cgi?id=119061

Reviewed by Darin Adler.

This patch removes order values Vector and use a Vector of pairs instead. The pairs are formed by a child
(RenderBox) and the index of this child. In addition, OrderIterator code is simplified.

It provides a helper class OrderIteratorPopulator, used for manipulating the Vector directly. Which allows to
consolidate the code into a single implementation across flexbox and grid. OrderIteratorPopulator part is based
on a patch from Blink r153971 by <jchaffraix@chromium.org>.

Current implementation is O(number of children * number of order values). Now it will just do a sort operation
and then a regular loop. So if you have different order values in a flexbox or grid the performance will
improve.

Comparing results of perf-tests:
* Layout/auto-grid-lots-of-data: ~0.5% worse.
* Layout/fixed-grid-lots-of-data: ~0.5% worse.
* Layout/fixed-grid-lots-of-data (setting 100 different order values): ~50% better.
* Layout/flexbox-lots-of-data: ~5% better.

No new tests, already covered by current tests.

* rendering/OrderIterator.cpp:
(WebCore::OrderIterator::currentChild): Return current child according to m_childrenIndex.
(WebCore::OrderIterator::first): Initialize m_childrenIndex and return current child.
(WebCore::OrderIterator::next): Increase m_childrenIndex and return current child.
(WebCore::compareByOrderValueAndIndex): Sorts the Vector by order value and index.
(WebCore::OrderIteratorPopulator::~OrderIteratorPopulator): Calls compareByOrderValueAndIndex() if there is any
child with non default order value.
(WebCore::OrderIteratorPopulator::collectChild): Adds the child and index to the Vector. Update
m_allChildrenHaveDefaultOrderValue accordingly.
(WebCore::OrderIterator::OrderIterator): Deleted.
(WebCore::OrderIterator::setOrderValues): Deleted.
(WebCore::OrderIterator::reset): Deleted.
* rendering/OrderIterator.h:
(WebCore::OrderIteratorPopulator::OrderIteratorPopulator): New helper class to manipulate the Vector.
(WebCore::OrderIterator::currentChild): Deleted.
* rendering/RenderFlexibleBox.cpp:
(WebCore::RenderFlexibleBox::RenderFlexibleBox): Remove OrderIterator intialization.
(WebCore::RenderFlexibleBox::layoutBlock): Remove unneeded code related to old OrderValues vector.
(WebCore::RenderFlexibleBox::prepareOrderIteratorAndMargins): Populate OrderIterator using collectChild().
(WebCore::RenderFlexibleBox::computeMainAxisPreferredSizes): Deleted.
* rendering/RenderFlexibleBox.h: Rename computeMainAxisPreferredSizes() to prepareOrderIteratorAndMargins().
* rendering/RenderGrid.cpp:
(WebCore::RenderGrid::RenderGrid): Remove OrderIterator initialization.
(WebCore::RenderGrid::populateExplicitGridAndOrderIterator): Populate OrderIterator using collectChild().

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@167879 268f45cc-cd09-0410-ab3c-d52691b4dbfc
Source/WebCore/ChangeLog
Source/WebCore/rendering/OrderIterator.cpp
Source/WebCore/rendering/OrderIterator.h
Source/WebCore/rendering/RenderFlexibleBox.cpp
Source/WebCore/rendering/RenderFlexibleBox.h
Source/WebCore/rendering/RenderGrid.cpp