Bug 118620

Summary: Use a Vector instead of HashSet to compute the orderValues in RenderFlexibleBox
Product: WebKit Reporter: Ryosuke Niwa <rniwa>
Component: Layout and RenderingAssignee: Sergio Villar Senin <svillar>
Status: RESOLVED FIXED    
Severity: Normal CC: andersca, ap, bdakin, buildbot, commit-queue, darin, dino, esprehn+autocc, glenn, hyatt, kling, koivisto, kondapallykalyan, rniwa, svillar
Priority: P2 Keywords: BlinkMergeCandidate
Version: 528+ (Nightly build)   
Hardware: Unspecified   
OS: Unspecified   
Bug Depends on: 123274    
Bug Blocks: 123208    
Attachments:
Description Flags
Patch
none
Patch
none
Archive of layout-test-results from webkit-ews-09 for mac-mountainlion-wk2
none
Archive of layout-test-results from webkit-ews-05 for mac-mountainlion
none
Patch
none
Archive of layout-test-results from webkit-ews-04 for mac-mountainlion
none
Archive of layout-test-results from webkit-ews-12 for mac-mountainlion-wk2
none
Patch
none
Archive of layout-test-results from webkit-ews-14 for mac-mountainlion-wk2
none
Archive of layout-test-results from webkit-ews-07 for mac-mountainlion
none
Archive of layout-test-results from webkit-ews-01 for mac-mountainlion
none
Patch
none
Rebased. Including Antti's suggestions
none
Patch none

Description Ryosuke Niwa 2013-07-12 14:58:00 PDT
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).
Comment 1 Sergio Villar Senin 2013-10-14 04:34:59 PDT
Created attachment 214143 [details]
Patch
Comment 2 Antti Koivisto 2013-10-14 04:49:17 PDT
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]
Comment 3 Antti Koivisto 2013-10-14 04:55:46 PDT
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.
Comment 4 Antti Koivisto 2013-10-14 04:57:02 PDT
Comment on attachment 214143 [details]
Patch

There is quite a bit to change really so lets get another patch.
Comment 5 Andreas Kling 2013-10-14 04:58:26 PDT
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.
Comment 6 Antti Koivisto 2013-10-14 05:04:09 PDT
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.
Comment 7 Sergio Villar Senin 2013-10-14 09:57:18 PDT
Antti what if instead of replacing it with a Vector<int, 1> which has to be orderer and stuff, we use a std::set ?
Comment 8 Antti Koivisto 2013-10-14 11:16:23 PDT
We don't currently use STL containers in WebKit, only algorithms. Whether we should is outside scope of this bug.
Comment 9 Sergio Villar Senin 2013-10-21 03:57:20 PDT
Created attachment 214723 [details]
Patch
Comment 10 Sergio Villar Senin 2013-10-21 04:00:34 PDT
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).
Comment 11 Build Bot 2013-10-21 04:46:50 PDT
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
Comment 12 Build Bot 2013-10-21 04:46:52 PDT
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
Comment 13 Build Bot 2013-10-21 05:05:42 PDT
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
Comment 14 Build Bot 2013-10-21 05:05:46 PDT
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
Comment 15 Antti Koivisto 2013-10-21 10:06:11 PDT
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())
Comment 16 Sergio Villar Senin 2013-10-22 04:17:51 PDT
Created attachment 214836 [details]
Patch
Comment 17 Build Bot 2013-10-22 04:48:22 PDT
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
Comment 18 Build Bot 2013-10-22 04:48:25 PDT
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
Comment 19 Build Bot 2013-10-22 05:08:16 PDT
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
Comment 20 Build Bot 2013-10-22 05:08:19 PDT
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
Comment 21 Sergio Villar Senin 2013-10-22 08:05:12 PDT
(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.
Comment 22 Sergio Villar Senin 2013-10-22 08:24:35 PDT
Created attachment 214859 [details]
Patch
Comment 23 Antti Koivisto 2013-10-22 08:52:15 PDT
> > 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())
Comment 24 Build Bot 2013-10-22 09:06:49 PDT
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
Comment 25 Build Bot 2013-10-22 09:06:52 PDT
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
Comment 26 Build Bot 2013-10-22 09:40:48 PDT
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
Comment 27 Build Bot 2013-10-22 09:40:52 PDT
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
Comment 28 Build Bot 2013-10-22 10:40:21 PDT
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
Comment 29 Build Bot 2013-10-22 10:40:24 PDT
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
Comment 30 Sergio Villar Senin 2013-10-23 04:22:55 PDT
Created attachment 214943 [details]
Patch
Comment 31 Sergio Villar Senin 2013-10-23 07:59:19 PDT
Created attachment 214962 [details]
Rebased. Including Antti's suggestions
Comment 32 Antti Koivisto 2013-10-23 11:48:04 PDT
Comment on attachment 214962 [details]
Rebased. Including Antti's suggestions

r=me
Comment 33 Sergio Villar Senin 2013-10-23 23:52:04 PDT
Committed r157916: <http://trac.webkit.org/changeset/157916>
Comment 34 Alexey Proskuryakov 2013-10-24 09:29:35 PDT
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>
Comment 35 WebKit Commit Bot 2013-10-24 09:31:12 PDT
Re-opened since this is blocked by bug 123274
Comment 36 Antti Koivisto 2013-10-24 09:45:47 PDT
Maybe that hash was needed after all!

The correct data structure here might really be a heap.
Comment 37 Sergio Villar Senin 2013-10-24 09:58:36 PDT
(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.
Comment 38 Sergio Villar Senin 2013-10-25 02:38:24 PDT
Created attachment 215156 [details]
Patch

The problem was the test itself that was generating some output confusing the testing tool
Comment 39 Sergio Villar Senin 2013-10-25 03:30:23 PDT
Comment on attachment 215156 [details]
Patch

Clearing flags on attachment: 215156

Committed r157999: <http://trac.webkit.org/changeset/157999>
Comment 40 Sergio Villar Senin 2013-10-25 03:30:32 PDT
All reviewed patches have been landed.  Closing bug.
Comment 41 Darin Adler 2013-10-25 12:52:56 PDT
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?
Comment 42 Sergio Villar Senin 2013-10-28 00:19:19 PDT
(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.
Comment 43 Sergio Villar Senin 2013-10-28 02:30:32 PDT
(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