Bug 65783 – refactor box-ordinal-group handling so we don't timeout on large values

• Component: New Bugs
• Status: RESOLVED FIXED

[Tony Chang]

refactor box-ordinal-group handling so we don't timeout on large values

[Tony Chang]

Created attachment 103093 [details]
Patch

[Early Warning System Bot]

Comment on attachment 103093 [details]
Patch

Attachment 103093 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/9321157

[Gyuyoung Kim]

Comment on attachment 103093 [details]
Patch

Attachment 103093 [details] did not pass efl-ews (efl):
Output: http://queues.webkit.org/results/9302993

[WebKit Review Bot]

Comment on attachment 103093 [details]
Patch

Attachment 103093 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/9305903

[Gustavo Noronha (kov)]

Comment on attachment 103093 [details]
Patch

Attachment 103093 [details] did not pass gtk-ews (gtk):
Output: http://queues.webkit.org/results/9323054

[Tony Chang]

Created attachment 103099 [details]
Patch

[Dave Hyatt]

Comment on attachment 103099 [details]
Patch

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

This is just way too slow. You'll sort all the kids every time you do a layout. Keep in mind that flex-order is rarely ever going to be used.

A couple of ideas:

(1) Instead of caching only m_lastOrdinal, cache all the specified ordinals as you encounter them when walking. Just make a little inthash.
PROS: Can just do a normal RenderObject walk when box-ordinal-group is 1.
CONS: Do one complete walk of the entire list for each value of box-ordinal-group.
PERFORMANCE: O(n*m) where n is the # of children and m is the number of unique box-ordinal-group values.
MEMORY: O(m) where m is the number of unique box-ordinal-group values stored in the IntHash.

(2) Start off walking the children and only if you encounter a box-ordinal-group value of 1 do you fault to being sorted.
PROS: Will perform better with box-ordinal-group values other than just 1.
CONS: Takes up a lot of extra memory when you only have a couple of box-ordinal-group values (probably the common case).
PERFORMANCE: O(n) where n is the # of children.
MEMORY: O(n) where n is the number of children.

(3) Same as (2) but instead of a single sorted Vector, make an IntHash of (box-ordinal-group) -> Vectors.
PROS: Easy to look only at a specific group.
CONS: Takes up a lot of extra memory still when you only have a couple of box-ordinal-group values.
PERFORMANCE: O(n) where n is the number of children.
MEMORY: O(n) where n is the number of children.

Given the characteristics of flex-order, I'm inclined to favor approach #1. I don't think doing multiple walks of the child list will be that big a deal.

> Source/WebCore/ChangeLog:10
> +        vector and sorts them.  If box-oridinal-group is all the default

Typo. "ordinal"

> Source/WebCore/rendering/RenderDeprecatedFlexibleBox.cpp:85
> +    static bool compareFlexOrder(RenderBox* r1, RenderBox* r2)
> +    {
> +        return r1->style()->boxOrdinalGroup() < r2->style()->boxOrdinalGroup();
> +    }

I don't think compareFlexOrder is the right term. box-ordinal-group is about re-ordering the items. I'd just call the function compare() :).

[Dave Hyatt]

Some clarifications.

For approach (1) you could use an IntHashSet rather than a map.

For approach (3) you could probably special case box-ordinal-group of 1 to just walk the normal child list and to not actually store a sorted Vector, i.e., only hold sorted child lists for the other box-ordinal-groups.

It seems to me that - given the rarity of this feature - approach #1 is the easiest.

[Tony Chang]

I tried to implement approach (1), but HashSet is not sorted, so once we collect the ordinals, we need to manually copy to a Vector and sort it.  The main downside to this approach is the extra memory it uses.

Really what I want is an STL set, but the closest thing I see to that is AVLTree.h.  Perhaps I should just use the AVL tree and before inserting, check to see if the value I'm inserting already exists or not.

Maybe Darin has some data structure advice.

[Tony Chang]

Created attachment 103387 [details]
Patch

[Tony Chang]

I went with (1) and copy to a vector and sort.  AVLTree seemed like a lot of code weight for this edge case (it doesn't appear to be used anywhere except leveldb).  There's also WebCore/platform/PODRedBlackTree, but it would require some modifications to get the max value and if we wanted to make inserts cheap.

[Ojan Vafai]

Comment on attachment 103387 [details]
Patch

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

Code and test looks good to me. Would be good to get at least a high-level OK from Hyatt though.

> Source/WebCore/rendering/RenderDeprecatedFlexibleBox.cpp:28
> +#include "PODRedBlackTree.h"

I think you meant to delete this.

> Source/WebCore/rendering/RenderDeprecatedFlexibleBox.cpp:85
> +                    if (static_cast<size_t>(m_ordinalValues.size()) != m_sortedOrdinalValues.size()) {

Maybe add a comment saying why we do this size check? Namely, that it avoids regenerating and sorting m_sortedOrdinalValues when the iterator is reset, which happens frequently.

[Tony Chang]

Created attachment 105682 [details]
Patch

[Dave Hyatt]

Comment on attachment 105682 [details]
Patch

r=me

[Tony Chang]

Committed r94108: <http://trac.webkit.org/changeset/94108>