[css-grid-3] intrinsic track sizing algorithm for masonry can go exponential in complexity.

[bfgeek]

https://drafts.csswg.org/css-grid-3/#track-sizing

Currently you need to place everything in every possible position. With subgrid this means that the complexity can go ~exponential (or sub-exponential).

<div style="grid-template: masonry / repeat(10, auto);">
  <div style="grid-template: subgrid / subgrid; grid-column: auto / span 6;"> <!-- 5 positions -->
    <div style="grid-template: subgrid / subgrid; grid-column: auto / span 3;"> <!-- 4 positions -->
      <div></div> <!-- 3 positions -->
    </div>
  </div>
</div>

In the above example there are 60 positions you need to test (each subgrid level might have different margin/border/padding which needs to be taken into account for the items contribution in a particular position along with many other factors).

In Blink we've spent most of our performance work in layout fixing exponential time bugs - developers really care about layout time performance. While these issues were quality of implementation bugs (and not a core problem with a particular spec), having exponential time complexity in a spec seems bad[1].

[1] - Exponential time complexity doesn't care how powerful your CPU is - it'll always win.

[ByteEater-pl]

Exponential in what? The subgrid nesting level? If so, it it really such a bad thing? Do deeply nested subgrids with masonry have compelling use cases?

[fantasai]

Discussed with the Apple/WebKit team...

We agree that subgridded masonry within masonry can create an exponential calculation. However this only affects intrinsic track sizing, so the dangers here are limited to: intrinsically sized masonry tracks combined with multiple levels of subgridded masonry nesting combined with large numbers of tracks.

We don't think the cases where these calculations become unmanageable will be common:

• We expect most use cases with large numbers of tracks to use non-intrinsic track sizes.
• We don't expect deep nesting of masonry within masonry in general, and even less likely with intrinsic track sizing.

To address the "but what if concerns", we're OK with introducing a UA-defined limit on e.g. the depth of masonry subgrid items that can contribute sizing back up to the master grid. A limit like this can prevent exponential explosion, while still allowing

• A limited amount of masonry nesting with intrinsic track sizing, if needed. (We don't expect much depth is needed here here, maybe 1 or 2 levels would likely satisfy any use cases.)
• Limitless depth of subgridding with fixed-size tracks.
• Interleaving Grid and Masonry subgrids in the nesting structure, which we believe is an important use case, and which requires compatible track sizing between Grid and Masonry.

[kizu]

I really think that spanning items should not contribute to the width of the columns in masonry. Even in a regular grid, this is the behavior that I find unnecessary and often harmful, and I don't think there are many legit use cases for wanting this in a masonry layout. As an author, when I want some element to span other columns/rows, I want it to adapt to whatever there is, not to contribute. (copying this part from #9041 (comment))

When some auto column has only spanning items contributing to it, I would rather consider it be minmax(0px, 1fr) (when with regular auto) or just 0px when it is in a repeating context.

[tabatkins]

I really think that spanning items should not contribute to the width of the columns in masonry.

I disagree. Like, if you have repeat(5, min-content), and an item spans two of those columns, we do want to make sure the track size is large enough that the two columns it spans will contain its min-content size. After all, the whole reason you gave it a span might be because you expected it to be large. If we don't contribute its size to the tracks, then it'll happen to work fine if it's min-content size is less than twice that of the non-spanning items, but it'll overflow if it is larger than double. That seems pretty bad.

[kizu]

In my practice, I never encountered use cases for this. Usually, to be resilient, elements tend to have a small min-content, adapting in one way or another to the context. Even the opposite: numerous times I had to give these spanning items contain to stop this behavior. I would be interested in seeing any real-life cases that rely on the spanning items contributing their min-content.

While I think it could be useful to have a control over if any particular spanning item contributes its min-content to the columns for regular grids, I am not talking about changing how it works now, but about a compromise that will enable masonry-type grids with spanning items. I will always take this limitation compared to the absence of a feature completely.

[tabatkins]

I am not talking about changing how it works now, but about a compromise that will enable masonry-type grids with spanning items. I will always take this limitation compared to the absence of a feature completely.

As we outlined over in #9041 (comment), spanning items and intrinsic tracks are totally fine perf-wise, if all the tracks are the same intrinsic size. (And spanning items across fixed/flexible tracks aren't problematic at all.) It's just when you mix an intrinsic track with some different-sized tracks (intrinsic or not) that you run into these issues.

And so far, we haven't seen any example of Masonry grids that want to exceed that limitation - if they want intrinsic sizes, they want them all the same; if they want different sizes, they want fixed/flexible sizes, rather than intrinsic ones. So we should be just fine handling spanning items properly.