OrderIterator should be O(number of children)

OrderIterator should be O(number of children)

The current implementation is O(number of children * order)!

This change introduces a faster way to iterate over the children by
using a HashMap to keep the subset of children for each 'order' value.
This is a speed vs memory tradeoff as we are now using
O(number of children + order) memory when the existing code was using
O(order) memory).

This is also a stepping stone to speed up CSS Grid Layout painting
and hit-testing by allowing arbitrary children to be collected into
the OrderIterator.

This change doesn't introduce any runtime performance in
PerformanceTests/Layout/flexbox-lots-of-data.html. In a test case
with 1000 flex items with different 'order' that get forced layout
in an infinite loop, this moves OrderIterator::next from the slowest
function (>80%) to among the other functions (~7%).

BUG=256804
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=154445

[esprehn, 2013-07-17 13:58:28]

Does this still need review? I'd prefer Ojan look at this, but I can do the
review if he's busy.

[Julien - ping for review, 2013-07-17 17:53:44]

On 2013/07/17 13:58:28, esprehn wrote:
> Does this still need review? I'd prefer Ojan look at this, but I can do the
> review if he's busy.

It does! I was trying to get Ojan's or Christian's attention on it as they have
been more involved in this code.

[cbiesinger, 2013-07-17 19:12:38]

lgtm

sorry I didn't get to this sooner!

[Julien - ping for review, 2013-07-17 21:54:53]

On 2013/07/17 19:12:38, cbiesinger wrote:
> lgtm
> 
> sorry I didn't get to this sooner!

Thanks Christian!

[commit-bot: I haz the power, 2013-07-17 21:55:48]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/jchaffraix@chromium.org/18162016/1

[commit-bot: I haz the power, 2013-07-17 23:57:21]

Change committed as 154445

[tony, 2013-07-19 17:36:31]

drive by comments

https://chromiumcodereview.appspot.com/18162016/diff/1/Source/core/rendering/...
File Source/core/rendering/OrderIterator.cpp (right):

https://chromiumcodereview.appspot.com/18162016/diff/1/Source/core/rendering/...
Source/core/rendering/OrderIterator.cpp:57: for (; m_currentChildIndex <
currentOrderChildren.size(); ++m_currentChildIndex) {
Using a for loop here is weird since you always return in body.  This could be
an if statement.

https://chromiumcodereview.appspot.com/18162016/diff/1/Source/core/rendering/...
Source/core/rendering/OrderIterator.cpp:94:
OrderIterator::OrderedValuesMap::AddResult result =
m_iterator.m_orderedValues.add(order, Vector<RenderBox*>());
Can we use a std::map<int, Vector<RenderBox*> > here?  Keeping 2 data structures
seems like extra complexity.