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)
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

index 7e8e12c..410f2a4 100644 (file)
@@ -1,3 +1,54 @@
+2014-04-28  Manuel Rego Casasnovas  <rego@igalia.com>
+
+        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().
+
 2014-04-28  Zan Dobersek  <zdobersek@igalia.com>
 
         std::bitset<>::test() does unnecessary bounds checks on CSSPropertyID bitsets
index e09924f..987f552 100644 (file)
 #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)
-{
-    reset();
-}
-
-void OrderIterator::setOrderValues(OrderValues&& orderValues)
+RenderBox* OrderIterator::currentChild() const
 {
-    reset();
-    m_orderValues = std::move(orderValues);
-    if (m_orderValues.size() < 2)
-        return;
+    if (m_childrenIndex == m_children.size())
+        return nullptr;
 
-    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;
-        }
-
-        if (m_orderIndex == endIndex)
-            return nullptr;
-
-        if (m_orderIndex != cInvalidIndex) {
-            ++m_orderIndex;
-            if (m_orderIndex == endIndex)
-                return nullptr;
-        } else
-            m_orderIndex = 0;
+    ++m_childrenIndex;
+    return currentChild();
+}
 
-        m_currentChild = m_containerBox.firstChildBox();
-    } while (!m_currentChild || m_currentChild->style().order() != m_orderValues[m_orderIndex]);
+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;
+}
 
-    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
index e47c850..1d1f58a 100644 (file)
@@ -41,22 +41,37 @@ class RenderBox;
 
 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
index 48521a8..612c4d3 100644 (file)
@@ -68,7 +68,6 @@ struct RenderFlexibleBox::Violation {
 
 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(Element& element, PassRef<RenderStyle> styl
 
 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 @@ void RenderFlexibleBox::layoutBlock(bool relayoutChildren, LayoutUnit)
 
     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 @@ LayoutUnit RenderFlexibleBox::computeChildMarginValue(const Length& margin)
     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;
index 91b547a..35852c9 100644 (file)
@@ -137,7 +137,7 @@ private:
     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);
 
index ad19103..13ae483 100644 (file)
@@ -164,7 +164,6 @@ public:
 
 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::placeItemsOnGrid()
 
 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 @@ void RenderGrid::populateExplicitGridAndOrderIterator()
     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)