[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.

[tabatkins]

It also interacts badly if you want to allow "auto-spanning", where an element will get a span based on its width. This might be a good mode to allow, possibly even with some author control - if an image is >X% of the track width, make it span 2 instead of 1 (or a larger span, as appropriate).

With variable-width tracks this is at minimum problematic for layout, and might be inherently circular (I haven't given it enough thought yet to be certain).

[fantasai]

@tabatkins I think auto-spanning is a separate issue. :) And an equally applicable request for Grid.

[tabatkins]

Nah, it's part of this issue - if we do auto-spanning (and I think Masonry libraries do sometimes have this feature), then variable-size tracks are even more problematic. (And it would be equally problematic for Grid, I think.)

[fantasai]

@tabatkins I don't see what that has to do with dense packing. Filed as #10089

[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.