Changeset 157916 in webkit


Ignore:
Timestamp:
Oct 23, 2013 11:53:10 PM (10 years ago)
Author:
svillar@igalia.com
Message:

Use a Vector instead of HashSet to computed the orderValues in RenderFlexibleBox
https://bugs.webkit.org/show_bug.cgi?id=118620

Reviewed by Antti Koivisto.

PerformanceTests:

From Blink r152960 by <ojan@chromium.org>

New performance test for layouts in flexboxes.

  • Layout/flexbox-lots-of-data.html: Added.

Source/WebCore:

Turns out that order is extremelly uncommon so using a Vector is
much less expensive. This also special-cases the much common case
of only having order of value 0 by using Vectors with just one
preallocated member.

Also added the performance test that shows a ~1% win when using a
vector instead of the HashSet.

  • rendering/RenderFlexibleBox.cpp:

(WebCore::RenderFlexibleBox::OrderIterator::setOrderValues):
(WebCore::RenderFlexibleBox::layoutBlock):
(WebCore::RenderFlexibleBox::computeMainAxisPreferredSizes):

  • rendering/RenderFlexibleBox.h:
Location:
trunk
Files:
1 added
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/PerformanceTests/ChangeLog

    r157009 r157916  
     12013-10-14  Sergio Villar Senin  <svillar@igalia.com>
     2
     3        Use a Vector instead of HashSet to computed the orderValues in RenderFlexibleBox
     4        https://bugs.webkit.org/show_bug.cgi?id=118620
     5
     6        Reviewed by Antti Koivisto.
     7
     8        From Blink r152960 by <ojan@chromium.org>
     9
     10        New performance test for layouts in flexboxes.
     11
     12        * Layout/flexbox-lots-of-data.html: Added.
     13
    1142013-10-06  Ryosuke Niwa  <rniwa@webkit.org>
    215
  • trunk/Source/WebCore/ChangeLog

    r157915 r157916  
     12013-10-14  Sergio Villar Senin  <svillar@igalia.com>
     2
     3        Use a Vector instead of HashSet to computed the orderValues in RenderFlexibleBox
     4        https://bugs.webkit.org/show_bug.cgi?id=118620
     5
     6        Reviewed by Antti Koivisto.
     7
     8        Turns out that order is extremelly uncommon so using a Vector is
     9        much less expensive. This also special-cases the much common case
     10        of only having order of value 0 by using Vectors with just one
     11        preallocated member.
     12
     13        Also added the performance test that shows a ~1% win when using a
     14        vector instead of the HashSet.
     15
     16        * rendering/RenderFlexibleBox.cpp:
     17        (WebCore::RenderFlexibleBox::OrderIterator::setOrderValues):
     18        (WebCore::RenderFlexibleBox::layoutBlock):
     19        (WebCore::RenderFlexibleBox::computeMainAxisPreferredSizes):
     20        * rendering/RenderFlexibleBox.h:
     21
    1222013-10-23  ChangSeok Oh  <changseok.oh@collabora.com>
    223
  • trunk/Source/WebCore/rendering/RenderFlexibleBox.cpp

    r157828 r157916  
    4040namespace WebCore {
    4141
    42 // Normally, -1 and 0 are not valid in a HashSet, but these are relatively likely order: values. Instead,
    43 // we make the two smallest int values invalid order: values (in the css parser code we clamp them to
    44 // int min + 2).
    45 struct RenderFlexibleBox::OrderHashTraits : WTF::GenericHashTraits<int> {
    46     static const bool emptyValueIsZero = false;
    47     static int emptyValue() { return std::numeric_limits<int>::min(); }
    48     static void constructDeletedValue(int& slot) { slot = std::numeric_limits<int>::min() + 1; }
    49     static bool isDeletedValue(int value) { return value == std::numeric_limits<int>::min() + 1; }
    50 };
    51 
    5242RenderFlexibleBox::OrderIterator::OrderIterator(const RenderFlexibleBox* flexibleBox)
    5343    : m_flexibleBox(flexibleBox)
     
    5747}
    5848
    59 void RenderFlexibleBox::OrderIterator::setOrderValues(const OrderHashSet& orderValues)
     49void RenderFlexibleBox::OrderIterator::setOrderValues(const OrderValues& orderValues)
    6050{
    6151    reset();
    62     copyToVector(orderValues, m_orderValues);
     52    m_orderValues = orderValues;
     53    if (m_orderValues.size() < 2)
     54        return;
     55
    6356    std::sort(m_orderValues.begin(), m_orderValues.end());
     57    auto nextElement = std::unique(m_orderValues.begin(), m_orderValues.end());
     58    m_orderValues.shrinkCapacity(nextElement - m_orderValues.begin());
    6459}
    6560
     
    349344
    350345    Vector<LineContext> lineContexts;
    351     OrderHashSet orderValues;
     346    OrderIterator::OrderValues orderValues;
    352347    computeMainAxisPreferredSizes(orderValues);
    353348    m_orderIterator.setOrderValues(orderValues);
     
    909904}
    910905
    911 void RenderFlexibleBox::computeMainAxisPreferredSizes(OrderHashSet& orderValues)
    912 {
     906void RenderFlexibleBox::computeMainAxisPreferredSizes(OrderIterator::OrderValues& orderValues)
     907{
     908    ASSERT(orderValues.isEmpty());
     909
    913910    for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
    914         orderValues.add(child->style()->order());
     911        // Avoid growing the vector for the common-case default value of 0. This optimizes the most common case which is
     912        // one or a few values with the default order 0
     913        int order = child->style()->order();
     914        if (orderValues.isEmpty() || orderValues.last() != order)
     915            orderValues.append(order);
    915916
    916917        if (child->isOutOfFlowPositioned())
  • trunk/Source/WebCore/rendering/RenderFlexibleBox.h

    r157907 r157916  
    7474    };
    7575
    76     struct OrderHashTraits;
    77     typedef HashSet<int, DefaultHash<int>::Hash, OrderHashTraits> OrderHashSet;
    78 
    7976    class OrderIterator {
    8077        WTF_MAKE_NONCOPYABLE(OrderIterator);
    8178    public:
     79        typedef Vector<int, 1> OrderValues;
     80
    8281        OrderIterator(const RenderFlexibleBox*);
    83         void setOrderValues(const OrderHashSet&);
     82        void setOrderValues(const OrderValues&);
    8483        RenderBox* currentChild() const { return m_currentChild; }
    8584        RenderBox* first();
     
    9089        const RenderFlexibleBox* m_flexibleBox;
    9190        RenderBox* m_currentChild;
    92         Vector<int> m_orderValues;
     91        OrderValues m_orderValues;
    9392        Vector<int>::const_iterator m_orderValuesIterator;
    9493    };
     
    154153
    155154    LayoutUnit computeChildMarginValue(const Length& margin);
    156     void computeMainAxisPreferredSizes(OrderHashSet&);
     155    void computeMainAxisPreferredSizes(OrderIterator::OrderValues&);
    157156    LayoutUnit adjustChildSizeForMinAndMax(RenderBox&, LayoutUnit childSize);
    158157    bool computeNextFlexLine(OrderedFlexItemList& orderedChildren, LayoutUnit& preferredMainAxisExtent, double& totalFlexGrow, double& totalWeightedFlexShrink, LayoutUnit& minMaxAppliedMainAxisExtent, bool& hasInfiniteLineLength);
Note: See TracChangeset for help on using the changeset viewer.