[css-grid-3][masonry] variable track sizes + dense packing has poor performance

[fantasai]

From @bfgeek in #9041 (comment)

Variable track sizes is problematic with items that span multiple tracks with "dense" packing. To correctly place the item in the correct tracks, you need O(N) layout passes on the item.

[fantasai]

Back to the original issue...

Agreed that having N different track sizes means dense packing would require O(N) layout passes on items added after a gap, and this would be a problem. We suggest adopting a heuristic that brings this closer to O(2) for most cases:

1. Lay out the item in the widest track, and in the narrowest track, and find the shortest height among the two.
2. Skip trying to fit into any gaps that are shorter than that height.

It's possible, but unlikely, that an item's actual shortest height would be at a middling width; and this allows us to avoid a lot of that extra work in the much more common cases where the item definitely won't fit.

[fantasai]

Ok, discussing with @stwrt, new proposal for dense-packing in masonry:

1. Lay out the item in the track where it would be without dense packing.
2. If the item is short enough to fit into an earlier gap in a track with the same used size as this track, move it into that gap.

This avoids doing more than one layout, and it works as expected for explicitly-placed masonry in mixed-size tracks as well as for auto-placed masonry in consistently-sized tracks, and does a reasonable job of dense-packing large collections of auto-placed masonry in mixed-size tracks as well.

[astearns]

In step 2 does it have to be exactly the same used size, or could it be “an earlier gap in a track with a used size at least as large as this track”?

[tabatkins]

Would have to be the same size to actually work; a larger track size usually would make the item shorter (and thus more likely to fit), but not always - say, an aspect-ratio image that fills the track. And even if it did fit, it would still be a second layout, potentially ~doubling the layout cost from turning on dense packing.

---

This algo sounds reasonable to me? In the common case of equal-sized tracks, it'll work naturally to fill holes everywhere; in mixed tracks, it'll at least do some work, without increasing costs beyond that of tracking gaps (which is trivial).

[ethanjv]

The latest algorithm sounds reasonable, as Tab commented, the only cost of this algorithm is keeping track of the gaps. This is fairly doable if we store the current and all previous running positions for each track in the grid axis. However, when you consider items spanning multiple tracks there are a couple of issues that need clarifying:

1. Is it the expectation that, when looking for a previous gap for an item spanning multiple tracks, we use the maximum running position across spanned tracks? The figure below exemplifies how the item might be placed into multiple possible gaps.

2. Combining gaps from multiple tracks is not an easy process, the algorithm would need to consider the complexity of matching a gap from one track with (possibly more than) one gap in the next tracks, implying non-trivial decision making.

Consider trying to place an item spanning 2 tracks in the example below (where all tracks have the same used size), choosing the upper gap in the third track produces the gap highlighted in pink:

While choosing the lower gap produces the following smaller gap:

[fantasai]

@ethanjv Your diagrams are amazing.

[css-meeting-bot]

The CSS Working Group just discussed [css-grid-3][masonry] variable track sizes + dense packing has poor performance, and agreed to the following:

• RESOLVED: Have the proposed algorithm for dense packing, with clarification that it looks at spans with same used size

The full IRC log of that discussion

<kbabbitt> fantasai: one of the challenges brought up with masonry was that we have this dense keyword
<kbabbitt> ... for grid placement
<kbabbitt> ... what does that mean in masonry?
<kbabbitt> ... when you have variable width columns knowing which slots you can place an item into for a perfect result
<kbabbitt> ... would mean having to size the item into each column width, calculate its height in order to figure out if it fits in that slot
<kbabbitt> .. that's a lot of work browser probably doesn't want to do
<kbabbitt> ... we talked abou tit, suggestion is to lay out the item where it would be without dense packing
<kbabbitt> .. likely to stay there
<kbabbitt> ... if it's short enough to fit in a gap left by spanning elements, with the same used width, put it in that gap
<florian> q+
<TabAtkins> q+
<kbabbitt> ... if you have a masonry layout where all tracks are same width, this is perfect algorithm
<kbabbitt> ... if a masonry layout with 2 track widths, an item that would be placed in a wider track would only move into a gap left in a wider track
<kbabbitt> .. likewise for narrow tracks
<kbabbitt> ... in most cases you end up with dense packing you expecty
<kbabbitt> .,.. but if you have a lot of different widths and not many items, maybe you leave gaps that could have been filled
<kbabbitt> ... we think this is close enough and addresses most common use cases for dense packing
<astearns> ack florian
<kbabbitt> florian: I think that makes sence
<kbabbitt> ... supect my line of questioning will be shut down but want to check
<kbabbitt> ... as I was listening and mostly agreeing, was wondering whether, when you check for other columns to move to, check for columns same size or bigger?
<kbabbitt> ... then you would have to relayout but would know it fits
<kbabbitt> fantasai: don't know if it fits due to aspect ratio
<kbabbitt> florian: thanks for confirming
<kbabbitt> ... with that explored think that makes sense
<astearns> ack TabAtkins
<kbabbitt> TabAtkins: also agree with this proposal
<astearns> q+
<kbabbitt> ... ethanjv from microsoft has questions
<kbabbitt> astearns: the way you formulated the issue was talking about tracks with same size
<astearns> ack astearns
<kbabbitt> ... but is it about spanners with same size?
<kbabbitt> fantasai: good clarification, should make sure we get that in spec
<kbabbitt> astearns: other comments or questions?
<astearns> https://github.com//issues/9326#issuecomment-2457881349
<kbabbitt> astearns: Proposed resolution is what is in ^ comment linked above
<kbabbitt> ... with amendment that it's track spans with same used size are possible targets for moving into more dense packing
<kbabbitt> TabAtkins: doesn't only apply to single track items, yes
<kbabbitt> ... 2-track spanner looking at pairs of tracks
<kbabbitt> astearns: objections?
<kbabbitt> RESOLVED: Have the proposed algorithm for dense packing, with clarification that it looks at spans with same used size

[tabatkins]

For @ethanjv's (1): yes, your displayed position options are exactly right.

For (2), we'd pick the higher area in the first picture.