- Revision
- 167879
- Author
- [email protected]
- Date
- 2014-04-28 01:27:06 -0700 (Mon, 28 Apr 2014)
Log Message
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 <[email protected]>.
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().
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (167878 => 167879)
--- trunk/Source/WebCore/ChangeLog 2014-04-28 08:16:15 UTC (rev 167878)
+++ trunk/Source/WebCore/ChangeLog 2014-04-28 08:27:06 UTC (rev 167879)
@@ -1,3 +1,54 @@
+2014-04-28 Manuel Rego Casasnovas <[email protected]>
+
+ 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 <[email protected]>.
+
+ 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().
+
2014-04-28 Zan Dobersek <[email protected]>
std::bitset<>::test() does unnecessary bounds checks on CSSPropertyID bitsets
Modified: trunk/Source/WebCore/rendering/OrderIterator.cpp (167878 => 167879)
--- trunk/Source/WebCore/rendering/OrderIterator.cpp 2014-04-28 08:16:15 UTC (rev 167878)
+++ trunk/Source/WebCore/rendering/OrderIterator.cpp 2014-04-28 08:27:06 UTC (rev 167879)
@@ -32,66 +32,51 @@
#include "config.h"
#include "OrderIterator.h"
-#include "RenderFlexibleBox.h"
-#include "RenderGrid.h"
+#include "RenderBox.h"
namespace WebCore {
-static const int cInvalidIndex = -1;
-
-OrderIterator::OrderIterator(RenderBox& containerBox)
- : m_containerBox(containerBox)
+RenderBox* OrderIterator::currentChild() const
{
- reset();
-}
+ if (m_childrenIndex == m_children.size())
+ return nullptr;
-void OrderIterator::setOrderValues(OrderValues&& orderValues)
-{
- reset();
- m_orderValues = std::move(orderValues);
- if (m_orderValues.size() < 2)
- return;
-
- std::sort(m_orderValues.begin(), m_orderValues.end());
- auto nextElement = std::unique(m_orderValues.begin(), m_orderValues.end());
- m_orderValues.shrinkCapacity(nextElement - m_orderValues.begin());
+ return m_children[m_childrenIndex].first;
}
RenderBox* OrderIterator::first()
{
- reset();
- return next();
+ m_childrenIndex = 0;
+ return currentChild();
}
RenderBox* OrderIterator::next()
{
- int endIndex = m_orderValues.size();
- do {
- if (m_currentChild) {
- m_currentChild = m_currentChild->nextSiblingBox();
- continue;
- }
+ ++m_childrenIndex;
+ return currentChild();
+}
- if (m_orderIndex == endIndex)
- return nullptr;
+static bool compareByOrderValueAndIndex(std::pair<RenderBox*, int> childAndIndex1, std::pair<RenderBox*, int> childAndIndex2)
+{
+ if (childAndIndex1.first->style().order() != childAndIndex2.first->style().order())
+ return childAndIndex1.first->style().order() < childAndIndex2.first->style().order();
+ return childAndIndex1.second < childAndIndex2.second;
+}
- if (m_orderIndex != cInvalidIndex) {
- ++m_orderIndex;
- if (m_orderIndex == endIndex)
- return nullptr;
- } else
- m_orderIndex = 0;
-
- m_currentChild = m_containerBox.firstChildBox();
- } while (!m_currentChild || m_currentChild->style().order() != m_orderValues[m_orderIndex]);
-
- return m_currentChild;
+OrderIteratorPopulator::~OrderIteratorPopulator()
+{
+ if (!m_allChildrenHaveDefaultOrderValue)
+ std::sort(m_iterator.m_children.begin(), m_iterator.m_children.end(), compareByOrderValueAndIndex);
}
-void OrderIterator::reset()
+void OrderIteratorPopulator::collectChild(RenderBox& child)
{
- m_currentChild = nullptr;
- m_orderIndex = cInvalidIndex;
+ std::pair<RenderBox*, int> childAndIndex = { &child, m_childIndex++ };
+ m_iterator.m_children.append(childAndIndex);
+
+ if (m_allChildrenHaveDefaultOrderValue && child.style().order())
+ m_allChildrenHaveDefaultOrderValue = false;
}
+
} // namespace WebCore
Modified: trunk/Source/WebCore/rendering/OrderIterator.h (167878 => 167879)
--- trunk/Source/WebCore/rendering/OrderIterator.h 2014-04-28 08:16:15 UTC (rev 167878)
+++ trunk/Source/WebCore/rendering/OrderIterator.h 2014-04-28 08:27:06 UTC (rev 167879)
@@ -41,24 +41,39 @@
class OrderIterator {
public:
- OrderIterator(RenderBox&);
+ friend class OrderIteratorPopulator;
- typedef Vector<int, 1> OrderValues;
- void setOrderValues(OrderValues&&);
-
- RenderBox* currentChild() const { return m_currentChild; }
+ RenderBox* currentChild() const;
RenderBox* first();
RenderBox* next();
private:
void reset();
- RenderBox& m_containerBox;
- RenderBox* m_currentChild;
- OrderValues m_orderValues;
- int m_orderIndex;
+ Vector<std::pair<RenderBox*, int>> m_children;
+ size_t m_childrenIndex;
};
+class OrderIteratorPopulator {
+public:
+ OrderIteratorPopulator(OrderIterator& iterator)
+ : m_iterator(iterator)
+ , m_childIndex(0)
+ , m_allChildrenHaveDefaultOrderValue(true)
+ {
+ m_iterator.m_children.clear();
+ }
+
+ ~OrderIteratorPopulator();
+
+ void collectChild(RenderBox&);
+
+private:
+ OrderIterator& m_iterator;
+ size_t m_childIndex;
+ bool m_allChildrenHaveDefaultOrderValue;
+};
+
} // namespace WebCore
#endif // OrderIterator_h
Modified: trunk/Source/WebCore/rendering/RenderFlexibleBox.cpp (167878 => 167879)
--- trunk/Source/WebCore/rendering/RenderFlexibleBox.cpp 2014-04-28 08:16:15 UTC (rev 167878)
+++ trunk/Source/WebCore/rendering/RenderFlexibleBox.cpp 2014-04-28 08:27:06 UTC (rev 167879)
@@ -68,7 +68,6 @@
RenderFlexibleBox::RenderFlexibleBox(Element& element, PassRef<RenderStyle> style)
: RenderBlock(element, std::move(style), 0)
- , m_orderIterator(*this)
, m_numberOfInFlowChildrenOnFirstLine(-1)
{
setChildrenInline(false); // All of our children must be block-level.
@@ -76,7 +75,6 @@
RenderFlexibleBox::RenderFlexibleBox(Document& document, PassRef<RenderStyle> style)
: RenderBlock(document, std::move(style), 0)
- , m_orderIterator(*this)
, m_numberOfInFlowChildrenOnFirstLine(-1)
{
setChildrenInline(false); // All of our children must be block-level.
@@ -275,13 +273,11 @@
dirtyForLayoutFromPercentageHeightDescendants();
- Vector<LineContext> lineContexts;
- OrderIterator::OrderValues orderValues;
- computeMainAxisPreferredSizes(orderValues);
- m_orderIterator.setOrderValues(std::move(orderValues));
+ prepareOrderIteratorAndMargins();
ChildFrameRects oldChildRects;
appendChildFrameRects(oldChildRects);
+ Vector<LineContext> lineContexts;
layoutFlexItems(relayoutChildren, lineContexts);
updateLogicalHeight();
@@ -834,16 +830,12 @@
return minimumValueForLength(margin, availableSize);
}
-void RenderFlexibleBox::computeMainAxisPreferredSizes(OrderIterator::OrderValues& orderValues)
+void RenderFlexibleBox::prepareOrderIteratorAndMargins()
{
- ASSERT(orderValues.isEmpty());
+ OrderIteratorPopulator populator(m_orderIterator);
for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
- // Avoid growing the vector for the common-case default value of 0. This optimizes the most common case which is
- // one or a few values with the default order 0
- int order = child->style().order();
- if (orderValues.isEmpty() || orderValues.last() != order)
- orderValues.append(order);
+ populator.collectChild(*child);
if (child->isOutOfFlowPositioned())
continue;
Modified: trunk/Source/WebCore/rendering/RenderFlexibleBox.h (167878 => 167879)
--- trunk/Source/WebCore/rendering/RenderFlexibleBox.h 2014-04-28 08:16:15 UTC (rev 167878)
+++ trunk/Source/WebCore/rendering/RenderFlexibleBox.h 2014-04-28 08:27:06 UTC (rev 167879)
@@ -137,7 +137,7 @@
LayoutUnit marginBoxAscentForChild(RenderBox&);
LayoutUnit computeChildMarginValue(const Length& margin);
- void computeMainAxisPreferredSizes(OrderIterator::OrderValues&);
+ void prepareOrderIteratorAndMargins();
LayoutUnit adjustChildSizeForMinAndMax(RenderBox&, LayoutUnit childSize);
bool computeNextFlexLine(OrderedFlexItemList& orderedChildren, LayoutUnit& preferredMainAxisExtent, double& totalFlexGrow, double& totalWeightedFlexShrink, LayoutUnit& minMaxAppliedMainAxisExtent, bool& hasInfiniteLineLength);
Modified: trunk/Source/WebCore/rendering/RenderGrid.cpp (167878 => 167879)
--- trunk/Source/WebCore/rendering/RenderGrid.cpp 2014-04-28 08:16:15 UTC (rev 167878)
+++ trunk/Source/WebCore/rendering/RenderGrid.cpp 2014-04-28 08:27:06 UTC (rev 167879)
@@ -164,7 +164,6 @@
RenderGrid::RenderGrid(Element& element, PassRef<RenderStyle> style)
: RenderBlock(element, std::move(style), 0)
- , m_orderIterator(*this)
{
// All of our children must be block level.
setChildrenInline(false);
@@ -699,17 +698,12 @@
void RenderGrid::populateExplicitGridAndOrderIterator()
{
- // FIXME: We should find a way to share OrderValues's initialization code with RenderFlexibleBox.
- OrderIterator::OrderValues orderValues;
+ OrderIteratorPopulator populator(m_orderIterator);
size_t maximumRowIndex = std::max<size_t>(1, explicitGridRowCount());
size_t maximumColumnIndex = std::max<size_t>(1, explicitGridColumnCount());
for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
- // Avoid growing the vector for the common-case default value of 0. This optimizes the most common case which is
- // one or a few values with the default order 0
- int order = child->style().order();
- if (orderValues.isEmpty() || orderValues.last() != order)
- orderValues.append(order);
+ populator.collectChild(*child);
// This function bypasses the cache (cachedGridCoordinate()) as it is used to build it.
std::unique_ptr<GridSpan> rowPositions = resolveGridPositionsFromStyle(child, ForRows);
@@ -726,8 +720,6 @@
m_grid.grow(maximumRowIndex);
for (size_t i = 0; i < m_grid.size(); ++i)
m_grid[i].grow(maximumColumnIndex);
-
- m_orderIterator.setOrderValues(std::move(orderValues));
}
void RenderGrid::placeSpecifiedMajorAxisItemsOnGrid(const Vector<RenderBox*>& autoGridItems)
