1637145 - Improve the performance when generating FlexLines for flex container's non-first-in-flows

Status: RESOLVED FIXED

(Core :: Layout: Flexbox, task, P1)

Description

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Per dholbert's review comment, the way we generate FlexLines for flex container's non-first-in-flows has the worst-case performance of O(n^3) where n is the number of flex items.

We should improve the performance.

Comment 1

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

This will be my next todo after bug 1622935 landed.

Comment 2

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Attachment: Bug 1637145 Part 2 - Use FlexItemIterator to improve the performance when generating FlexLines and FlexItems for flex container's next-in-flows.

By changing the FlexLines and FlexItems generated in flex container's
first-in-flow in CSS "order" aware order (i.e. reverse them again if the
flex container's internal axes are reversed), we can construct FlexItems
for flex container's next-in-flows in linear time because once we find a
FlexItem in the stored FlexLines via FlexItemIterator to construct a new
FlexItem for a child frame, the FlexItem for the next child frame can
only be found in a later entry (either in a later item in the same line,
or an item in a later line).

Depends on D75154

Comment 3

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Attachment: Bug 1637145 Part 3 - Setup NS_STATE_FLEX_NORMAL_FLOW_CHILDREN_IN_CSS_ORDER for flex container's next-in-flows.

Depends on D75155

Comment 4

[Ting-Yu Lin [:TYLin] (PST, UTC-8)]

Attachment: Bug 1637145 Part 1 - Create a helper method for the code that generates FlexLines and FlexItems for a flex container's next-in-flows.

Comment 5

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/ad89f466d991
Part 1 - Create a helper method for the code that generates FlexLines and FlexItems for a flex container's next-in-flows. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/dfd3e63d3371
Part 2 - Use FlexItemIterator to improve the performance when generating FlexLines and FlexItems for flex container's next-in-flows. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/2924b52f3b3f
Part 3 - Setup NS_STATE_FLEX_NORMAL_FLOW_CHILDREN_IN_CSS_ORDER for flex container's next-in-flows. r=dholbert

Comment 6

[Atila Butkovits]

https://hg.mozilla.org/mozilla-central/rev/ad89f466d991
https://hg.mozilla.org/mozilla-central/rev/dfd3e63d3371
https://hg.mozilla.org/mozilla-central/rev/2924b52f3b3f