Closed Bug 1623225 Opened 4 years ago Closed 4 years ago

Store FlexItems and FlexLines in nsTArrays instead of linked lists

Categories

(Core :: Layout: Flexbox, task)

task
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla76
Tracking Status
firefox76 --- fixed

People

(Reporter: TYLin, Assigned: TYLin)

References

Details

Attachments

(6 files)

In this bug, I'd like to revert the decision made in bug 983434, and to store FlexItems and FlexLines in nsTArrays instead of linked lists. Also since inserting elements at the start of an array is inefficient, I'll also request eAllowBottomToTopChildOrdering to stop FlexItem and FlexLines from being stored in the reverse order. I'll use the example in bug 983427 to explain why storing the line and items in reversed order might not be needed to implement flex item fragmentation.

Before performing the final reflow of all the flex items a single-line column container, we've already determined each flex item's position and size as if they are not in a pagination environment. Hence each flex item will be reflow at its designated position across in the page/column. So, even if the flex item ABCD is reflow first, its available block-size is from its block-axis position to the flex container's content block-end.

 +-----+
 |+---+|
 ||E F||
 ||G H||
 |+---+|
 |+---+|
 ||A B||
 ||C D||
 |+---+|
 +-----+

  PAGE1       PAGE2
 +-----+     |     |
 |+---+|     ||C D||
 ||E F||     |+---+|
 ||G H||     +-----+
 |+---+|
 |+---+| <-- item ABCD's available block-size starts here
 ||A B||

If in the end, it is necessary to reflow the child from top to bottom, we can always traverse the FlexLines and FlexItems backward.

In the next part, we are going to change nsFlexLine::mItems to store in
nsTArray and remove mNumItems.

When eAllowBottomToTopChildOrdering flag is not requested, we reverse
axes internally when the flex items are positioned from bottom to top.
This makes FlexLines or FlexItems to be inserted at the front of their
data structures when they are generated.

In the next parts, we will store FlexLines and FlexItems in nsTArray
instead of LinkedList, and it makes inserting elements at front very
expensive. Since we haven't implemented flex item fragmentation yet, and
eAllowBottomToTopChildOrdering might not needed, we can use the
eAllowBottomToTopChildOrdering to avoid the expensive path on
non-fragmenting flex layout for now.

If eAllowBottomToTopChildOrdering turns out to be needed in fragmenting
the flex items, we can either traverse FlexLines and FlexItems
backwards, or drop eAllowBottomToTopChildOrdering flag and fix the
performance impact by reversing the order of FlexLines and FlexItems
after they are fully constructed.

Depends on D67262

Notable changes in this part.

  • GetFirstItem() and GetLastItem() now returns a reference to the
    FlexItem (if such an item exists). The caller is required to test the
    FlexLine's emptiness before calling the two methods.

  • Deploy range-based for-loop to iterate all FlexItem in a FlexLine via
    a new Items() method.

  • The bookkeeping mNumItems is no longer needed as nsTArray::Length() is
    sufficient.

  • Use "." instead "->" because we now store FlexItem in an nsTArray.

Depends on D67263

Assignee: nobody → aethanyc
Status: NEW → ASSIGNED
Attachment #9134027 - Attachment description: Bug 1623225 Part 2 - Convert AxisTrackerFlags to an enum class, and request eAllowBottomToTopChildOrdering on AxisTracker. → Bug 1623225 Part 2 - Convert AxisTrackerFlags to an enum class.
Attachment #9134028 - Attachment description: Bug 1623225 Part 3 - Store FlexLines in nsTArrays instead of LinkedLists. → Bug 1623225 Part 3 - Store FlexItems in nsTArrays instead of LinkedLists.

Rather than inserting FlexLines and FlexItems at the front of the array,
which is inefficient, we reverse them after they are fully constructed.

nsTArray::Reverse() (or std::reverse()) is implemented by std::swap. To
make FlexItem swappable, i.e. FlexItem needs to be move-constructible
and move-assignable), we can simply drop all the const qualifiers for
all the member variables to have compiler generates move-constructor and
move-assignment operator.

Depends on D67265

Attachment #9134030 - Attachment description: Bug 1623225 Part 5 - Change GenerateFlexItemForChild to return FlexItem on the stack. → Bug 1623225 Part 6 - Construct FlexItem directly at the end of FlexLine::Items().
Pushed by aethanyc@gmail.com:
https://hg.mozilla.org/integration/autoland/rev/8c7625b9f662
Part 1 - Use nsFlexLine::NumItems() to replace all the read-only direct usages of mNumItems. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/c4a6b45ed12c
Part 2 - Convert AxisTrackerFlags to an enum class. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/b2365cff1862
Part 3 - Store FlexItems in nsTArrays instead of LinkedLists. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/3b2a048639c3
Part 4 - Store FlexLines in nsTArrays instead of LinkedLists. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/3928834326a7
Part 5 - Reverse FlexLines and FlexItems if the axes are reversed internally. r=dholbert
https://hg.mozilla.org/integration/autoland/rev/96ae6f058d3c
Part 6 - Construct FlexItem directly at the end of FlexLine::Items(). r=dholbert

Is this connected to performance or memory-usage improvements?

(In reply to Jens Hausdorf :jens1o [ni? me] from comment #9)

Is this connected to performance or memory-usage improvements?

This bug is not fixed with performance or memory-usage in mind, although in general accessing elements in an nsTArray could be a bit faster than in a linked-list. FlexItem and FlexLine were originally stored in the arrays, and changed to store in linked-list in bug 983434. This reverts the design.

Component: Layout → Layout: Flexbox
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Created:
Updated:
Size: