Bug 118620 – Use a Vector instead of HashSet to compute the orderValues in RenderFlexibleBox

• Status: RESOLVED
• Resolution: FIXED
• Component: Layout and Rendering

[Ryosuke Niwa]

We should probably merge https://chromium.googlesource.com/chromium/blink/+/f8d1285399d9e1ee079e2babf4fd8c6f337855d7

Also, special-case the very much common case of only having the
default order value of 0.

This accounts for ~1% of the profile on flexbox-lots-of-data.html
from crbug.com/249986. Order is extremely uncommon. If there turn
out to be sites that use a large number of different order values,
then we have to rethink how we store this data (i.e. right now
we loop over all the flex items for each order value).

[Sergio Villar Senin]

Created attachment 214143 [details]
Patch

[Antti Koivisto]

Comment on attachment 214143 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=214143&action=review

r=me with these fixes.

> Source/WebCore/rendering/RenderFlexibleBox.cpp:59
> +    std::sort(orderValues.begin(), orderValues.end());
> +
> +

Please remove the extra empty line.

> Source/WebCore/rendering/RenderFlexibleBox.cpp:64
> +    // This is inefficient if there are many repeated values, but
> +    // saves a lot of allocations when the values are unique. By far,
> +    // the common case is that there's exactly one item in the list
> +    // (the default order value of 0).
> +    m_orderValues.reserveInitialCapacity(orderValues.size());

The comment is overly long and adds little value.

> Source/WebCore/rendering/RenderFlexibleBox.cpp:74
> +    int previous = orderValues[0];
> +    m_orderValues.append(previous);
> +    for (size_t i = 1; i < orderValues.size(); ++i) {
> +        int current = orderValues[i];
> +        if (current == previous)
> +            continue;
> +        m_orderValues.append(current);
> +        previous = current;
> +    }

Please get rid of the current and previous variables and just use orderValues[i], orderValues[i-1]

[Antti Koivisto]

Comment on attachment 214143 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=214143&action=review

> Source/WebCore/rendering/RenderFlexibleBox.cpp:957
> +    if (anyChildHasDefaultOrderValue) {
> +        // Avoid growing the vector to the default capacity of 16 if we're only going to put one item in it.
> +        if (orderValues.isEmpty())
> +            orderValues.reserveInitialCapacity(1);
> +        orderValues.append(0);
> +    }

I think we can just use Vector<int, 1> instead of this clumsy optimisation.

[Antti Koivisto]

Comment on attachment 214143 [details]
Patch

There is quite a bit to change really so lets get another patch.

[Andreas Kling]

Comment on attachment 214143 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=214143&action=review

> Source/WebCore/rendering/RenderFlexibleBox.cpp:72
> +        m_orderValues.append(current);

You can use uncheckedAppend() here since you know that there will always be space for {orderValues.size()} elements.

[Antti Koivisto]

Comment on attachment 214143 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=214143&action=review

>> Source/WebCore/rendering/RenderFlexibleBox.cpp:74
>> +    int previous = orderValues[0];
>> +    m_orderValues.append(previous);
>> +    for (size_t i = 1; i < orderValues.size(); ++i) {
>> +        int current = orderValues[i];
>> +        if (current == previous)
>> +            continue;
>> +        m_orderValues.append(current);
>> +        previous = current;
>> +    }
> 
> Please get rid of the current and previous variables and just use orderValues[i], orderValues[i-1]

The whole loop can probably be replaced by a call to std::unique.

[Sergio Villar Senin]

Antti what if instead of replacing it with a Vector<int, 1> which has to be orderer and stuff, we use a std::set ?

[Antti Koivisto]

We don't currently use STL containers in WebKit, only algorithms. Whether we should is outside scope of this bug.

[Sergio Villar Senin]

Created attachment 214723 [details]
Patch

[Sergio Villar Senin]

The thing I don't like about my patch is that I'm removing the constness of the argument to the set() function just to try to minimize the amount of copies. If our assumption that the most common case is just a few order values is correct then I guess I should change it (we are copying all the values in any case with the current code).

[Build Bot]

Comment on attachment 214723 [details]
Patch

Attachment 214723 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.appspot.com/results/8868001

New failing tests:
mathml/presentation/scripts-horizontal-alignment.html

[Build Bot]

Created attachment 214726 [details]
Archive of layout-test-results from webkit-ews-09 for mac-mountainlion-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: webkit-ews-09  Port: mac-mountainlion-wk2  Platform: Mac OS X 10.8.5

[Build Bot]

Comment on attachment 214723 [details]
Patch

Attachment 214723 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/8758006

New failing tests:
mathml/presentation/scripts-horizontal-alignment.html

[Build Bot]

Created attachment 214728 [details]
Archive of layout-test-results from webkit-ews-05 for mac-mountainlion

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: webkit-ews-05  Port: mac-mountainlion  Platform: Mac OS X 10.8.5

[Antti Koivisto]

Comment on attachment 214723 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=214723&action=review

> Source/WebCore/rendering/RenderFlexibleBox.cpp:941
> +    if (anyChildHasDefaultOrderValue)
> +        orderValues.append(0);

You don't need anyChildHasDefaultOrderValue boolean.  You can just do

If (orderValue.isEmpty() && firstChildBox())

[Sergio Villar Senin]

Created attachment 214836 [details]
Patch

[Build Bot]

Comment on attachment 214836 [details]
Patch

Attachment 214836 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/8818257

New failing tests:
mathml/presentation/scripts-horizontal-alignment.html
mathml/presentation/multiscript-subscriptshift.html
platform/mac/accessibility/mathml-elements.html
mathml/presentation/multiscript-superscriptshift.html
mathml/presentation/multiscripts-positions.html
mathml/presentation/scripts-underover.html
platform/mac/accessibility/mathml-multiscript.html
css3/flexbox/style-change.html

[Build Bot]

Created attachment 214838 [details]
Archive of layout-test-results from webkit-ews-04 for mac-mountainlion

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: webkit-ews-04  Port: mac-mountainlion  Platform: Mac OS X 10.8.5

[Build Bot]

Comment on attachment 214836 [details]
Patch

Attachment 214836 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.appspot.com/results/8848278

New failing tests:
mathml/presentation/scripts-horizontal-alignment.html
mathml/presentation/multiscript-subscriptshift.html
platform/mac/accessibility/mathml-elements.html
mathml/presentation/multiscript-superscriptshift.html
mathml/presentation/multiscripts-positions.html
mathml/presentation/scripts-underover.html
platform/mac/accessibility/mathml-multiscript.html
css3/flexbox/style-change.html

[Build Bot]

Created attachment 214840 [details]
Archive of layout-test-results from webkit-ews-12 for mac-mountainlion-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: webkit-ews-12  Port: mac-mountainlion-wk2  Platform: Mac OS X 10.8.5

[Sergio Villar Senin]

(In reply to comment #15)
> (From update of attachment 214723 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=214723&action=review
> 
> > Source/WebCore/rendering/RenderFlexibleBox.cpp:941
> > +    if (anyChildHasDefaultOrderValue)
> > +        orderValues.append(0);
> 
> You don't need anyChildHasDefaultOrderValue boolean.  You can just do
> 
> If (orderValue.isEmpty() && firstChildBox())

Actually we can't do this because we never append 0 inside the loop (as it's the most common value). We need to know not only if there is some child but also if any of them is actually 0.

[Sergio Villar Senin]

Created attachment 214859 [details]
Patch

[Antti Koivisto]

> > If (orderValue.isEmpty() && firstChildBox())
> 
> Actually we can't do this because we never append 0 inside the loop (as it's the most common value). We need to know not only if there is some child but also if any of them is actually 0.

I know. I'm just saying you don't need the boolean. (the above should say orderValues.isEmpty())

[Build Bot]

Comment on attachment 214859 [details]
Patch

Attachment 214859 [details] did not pass mac-wk2-ews (mac-wk2):
Output: http://webkit-queues.appspot.com/results/8888352

New failing tests:
mathml/presentation/scripts-horizontal-alignment.html

[Build Bot]

Created attachment 214861 [details]
Archive of layout-test-results from webkit-ews-14 for mac-mountainlion-wk2

The attached test failures were seen while running run-webkit-tests on the mac-wk2-ews.
Bot: webkit-ews-14  Port: mac-mountainlion-wk2  Platform: Mac OS X 10.8.5

[Build Bot]

Comment on attachment 214859 [details]
Patch

Attachment 214859 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/8908313

New failing tests:
mathml/presentation/scripts-horizontal-alignment.html

[Build Bot]

Created attachment 214865 [details]
Archive of layout-test-results from webkit-ews-07 for mac-mountainlion

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: webkit-ews-07  Port: mac-mountainlion  Platform: Mac OS X 10.8.5

[Build Bot]

Comment on attachment 214859 [details]
Patch

Attachment 214859 [details] did not pass mac-ews (mac):
Output: http://webkit-queues.appspot.com/results/8878366

New failing tests:
mathml/presentation/scripts-horizontal-alignment.html

[Build Bot]

Created attachment 214870 [details]
Archive of layout-test-results from webkit-ews-01 for mac-mountainlion

The attached test failures were seen while running run-webkit-tests on the mac-ews.
Bot: webkit-ews-01  Port: mac-mountainlion  Platform: Mac OS X 10.8.5

[Sergio Villar Senin]

Created attachment 214943 [details]
Patch

[Sergio Villar Senin]

Created attachment 214962 [details]
Rebased. Including Antti's suggestions

[Antti Koivisto]

Comment on attachment 214962 [details]
Rebased. Including Antti's suggestions

r=me

[Sergio Villar Senin]

Committed r157916: <http://trac.webkit.org/changeset/157916>

[Alexey Proskuryakov]

This broke perfbot, so I'm going to roll out in a moment.

There are no diffs, but search for Layout/flexbox-lots-of-data.html in <http://build.webkit.org/builders/Apple%20MountainLion%20Release%20%28Perf%29/builds/6878/steps/perf-test/logs/stdio>

[WebKit Commit Bot]

Re-opened since this is blocked by bug 123274

[Antti Koivisto]

Maybe that hash was needed after all!

The correct data structure here might really be a heap.

[Sergio Villar Senin]

(In reply to comment #36)
> Maybe that hash was needed after all!

Let's see first why the test was not running :) The change didn't break any test actually, because as I told ap, the test was added by this change.

[Sergio Villar Senin]

Created attachment 215156 [details]
Patch

The problem was the test itself that was generating some output confusing the testing tool

[Sergio Villar Senin]

Comment on attachment 215156 [details]
Patch

Clearing flags on attachment: 215156

Committed r157999: <http://trac.webkit.org/changeset/157999>

[Sergio Villar Senin]

All reviewed patches have been landed.  Closing bug.

[Darin Adler]

Comment on attachment 215156 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=215156&action=review

> Source/WebCore/rendering/RenderFlexibleBox.h:82
> +        void setOrderValues(const OrderValues&);

This seems like a good place to use move semantics so we don’t have to allocate a new vector. Can we have this take OrderValues&& instead and use std::move?

[Sergio Villar Senin]

(In reply to comment #41)
> (From update of attachment 215156 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=215156&action=review
> 
> > Source/WebCore/rendering/RenderFlexibleBox.h:82
> > +        void setOrderValues(const OrderValues&);
> 
> This seems like a good place to use move semantics so we don’t have to allocate a new vector. Can we have this take OrderValues&& instead and use std::move?

Sure, I'll change it before landing.

[Sergio Villar Senin]

(In reply to comment #42)
> (In reply to comment #41)
> > (From update of attachment 215156 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=215156&action=review
> > 
> > > Source/WebCore/rendering/RenderFlexibleBox.h:82
> > > +        void setOrderValues(const OrderValues&);
> > 
> > This seems like a good place to use move semantics so we don’t have to allocate a new vector. Can we have this take OrderValues&& instead and use std::move?
> 
> Sure, I'll change it before landing.

I meant, in a follow up patch because it landed on friday