I had a bit of a read of the code surrounding this, since it was interesting and I really don't know it well enough.

The frame tree structure for a table looks like this:

Table
  RowGroup1
    Row1
      Cell1
      Cell2
    Row2
      Cell3
  RowGroup2
    Row3
      Cell4
  ColGroupList<
  ColGroup1
    Column1
    Column2
  ColGroup2
    Column3
  >

Tracing through the display list building code for this gives us this iteration order:

Table BuildDisplayList/DisplayGenericTablePart

  Table box shadow outer

  Table background

  Table box shadow inner

  Table outline

  For-each ColGroup, call BuildDisplayList/DisplayGenericTablePart
    ColGroup box shadow outer

    Build a vector of Column indices in the ColGroup
    For-each RowGroup in the table, call PaintRowGroupBackgroundByColIdx with the Column indices
      For-each Row in the RowGroup
        For-each Cell in the Row
          Add col-group background for the cell if cell is in one of the columns

    For-each Column, call BuildDisplayList/DisplayGenericTablePart
      Column box shadow outer.

      For-each RowGroup in the table, call PaintRowGroupBackgroundByColIdx with the the current Column index
        For-each Row in the RowGroup
          For-each Cell in the Row
            Add column background for the cell if cell is in the current columns

      Column box shadow inner and outline.
    ColGroup box shadow inner and outline.

  For-each RowGroup (principal child list) BuildDisplayList/DisplayGenericTablePart
    RowGroup box shadow outer.

    Call PaintRowGroupBackground
      For-each Row, call PaintRowBackground
        For-each Cell in the Row
          Add the row-group background for the cell

    RowGroup box shadow inner and outline.
		
    For-each Row in the group call BuildDisplayList/DisplayGenericTablePart (uses DisplayRows, maybe using a cursor to optimise iteration)
      Row box shadow outer.

      Call PaintRowBackground
        For-each Cell in the Row
          Add the row background for the cell

      Row box shadow inner and outline.

      For-each Cell in the Row, call BuildDisplayList/DisplayGenericTablePart
        Add display items for cell (border, background, shadows, outline etc), and recurse into descendants.
    
  Table border, or border-collapse borders for the whole table.

(Which is the same as bz said at [1], just worded slightly differently)

I think we could solve all of this by doing a single iteration of the table (just descending through principal children lists), collecting the different types of items separately, and then collating them in the right order at the end.

We can create a temporary nsDisplayListSet to collect all the 'normal' items (items for the cells themselves, and their descendants), and pass this through BuildDisplayList. We can then also create 4 (col-group, col, row-group, row) extra nsDisplayLists (stored centrally somewhere, similar to nsDisplayListBuilder::GetCurrentTableItem), and each cell can also add background items to those lists.

Once we've finished building all the items for the table, we can sort the special lists so that they have the same order as the current iterations, and append all their items to the BorderBackground() list of the outer nsDisplayListSet. Then we append all the items/lists from the temp nsDisplayListSet to the outer, guaranteeing that these items end up after all table-specific backgrounds.

For sorting the special lists, both row-group and row backgrounds should already be in the right order. Column backgrounds need to be sorted by column, but we can look this up easily using nsTableCellFrame::GetColIndex (or cache it when we stored the item to avoid another dereference).

The col-group lists needs to be sorted by col-group, which we don't have an easy way to do (afaict). I believe col-groups are relatively rare, so we can probably not worry about this too much. Maybe build a hashmap of column index -> col-group index?

Doing that would give us a single pass over all the cells, and should make things significantly faster, especially when retaining isn't effective.

[1] https://bugzilla.mozilla.org/show_bug.cgi?id=1409047#c9

Actually, that doesn't entirely work. We need to merge the col-group and col lists, and then sort again by col-group in order to interleave them correctly (and vice versa for the row/row-group sections).

It might be worth just building a list for the column backgrounds and sorting that (per col-group), since that's simple, and is by far the slowest part in the common case.

Looking at the CSS z-index painting order spec [1], it seems like the current order isn't correct.

The current code appears to interleave col-group and column backgrounds (since creation of both of them is within a loop over col-groups), but the spec suggests that all col-groups backgrounds should be painted first.

If we removed some of the nesting so that we had 5 (or 6) separate passes to build all of the layers (col-group, col, row-group, row, cell background, cell contents), then I think my original suggestion would work fully and we'd be more correct.

I still need to figure out how stacking contexts on table parts affect this, and what we'd need to do to handle it.

Does this match your understanding David?

[1] https://www.w3.org/TR/CSS2/zindex.html#q23.0

There's also the box shadow, border and outline for every element involved being added here, and we need to figure out the right spot for all of those.

but the spec suggests that all col-groups backgrounds should be painted first

I think it doesn't matter in practice, since colgroup backgrounds can't overlap each other and neither can column backgrounds. That is, for any given point there is at most one colgroup and one col background that applies at that point.

(In reply to Boris Zbarsky [:bzbarsky, bz on IRC] from comment #12)

but the spec suggests that all col-groups backgrounds should be painted first

I think it doesn't matter in practice, since colgroup backgrounds can't overlap each other and neither can column backgrounds. That is, for any given point there is at most one colgroup and one col background that applies at that point.

I've updated my comment to include the spots where we paint box-shadows, outlines and border.

I think those might affect this here, since the box-shadow for a given element (say a col-group), can extend outside of the column groups bounds and overlap. In the case where we have multiple col-groups with box shadow, I think we'd want the final order to be col-group1-shadow, col-group1-backgrounds-for-each-cell, col-group2-shadow, col-group2-backgrounds-for-each-cell.

The specs seem rather inconsistent here. Both the CSS2 tables description [1] and css-tables-3 [2] suggests that all the various background layers should be done as part of painting the cell background. It's not clear where non-separable background-like things (like box-shadow) should be ordered in that.

CSS2 painting order [3] however, clearly describes all the backgrounds layers for a table being painted as part of the table element, all in separate passes (with actual cell backgrounds included as a pass, before we get to iterating cell contents).

Our current code seems to be a partial mix of the two, where we'd interleave cell contents with cell and row backgrounds, but col and col-group backgrounds are a separate pass.

[1] https://www.w3.org/TR/CSS2/tables.html#table-layers
[2] https://drafts.csswg.org/css-tables-3/#drawing-cell-backgrounds
[3] https://www.w3.org/TR/CSS2/zindex.html#painting-order

As a clearer example, our current code would have a box-shadow on the second col-group on top of the column background for a column within the first col-group. It's not obvious that that's correct (under any of the specs).

I did some experimentation with box-shadows. It appears other browsers treat box-shadow like border in the sense that "Rows, columns, row groups, and column groups cannot have borders (i.e., user agents must ignore the border properties for those elements)."

(In reply to Matt Woodrow (:mattwoodrow) from comment #10)

The current code appears to interleave col-group and column backgrounds (since creation of both of them is within a loop over col-groups), but the spec suggests that all col-groups backgrounds should be painted first.

Yeah, I agree that that's what the spec says. Some other cases (in addition to box-shadow) that might (if they're supported) show this difference could be relative positioning and sticky positioning.

I still need to figure out how stacking contexts on table parts affect this, and what we'd need to do to handle it.

The issue of stacking contexts on table parts isn't really covered by the spec, I think. (Also see bug 35168 comment 38, bug 688556, bug 858333, and bug 1289682 for some slightly related things.)

I had a play with an idea for this on the plane, so I'll assign it to me and try to get something across the line.

Tried out the maze solver test case with my patches:

With patch:

Retaining enabled: 449.41 tiles per second (DL building time starts at 10ms, builds to 30ms as test progresses)
Retaining disabled: 302.38 tiles per second (DL building time constant at around 22ms)

Without patch:

Retaining enabled: 358.17 tiles per second (DL building starts at 10ms, builds to 70ms as test progresses).
Retaining disabled: 121.51 tiles per second (DL building time constant at around 115ms)

It looks like RDL degrades as the test progress since it pays a fixed cost per display item (during merging), and the number of items increases. We also limit retaining to building a single modified rectangle, and the latter phases of the test frequently make modifications in multiple locations, so the rebuild rectangle is large.

Anyway, looks to be more than 5x win (comparing DL build times) on a full rebuild, which will affect mousing over links, first paint, scrolling and other cases that retaining can't (yet) help with.

Most of the code in DisplayGenericTablePart was all within a per-class if statement, so it doesn't add much value, and makes the control flow harder to understand.

Depends on D29272

Depends on D29273

Depends on D29274

This is a behaviour change, but I believe it matches the quoted spec text, and neither blink nor WebKit render these.

Depends on D29275

More scores:

With Chrome 73 I get 462 tiles per second.

If I enabled WebRender (plus patches, and retaining enabled), then I got 1072 tiles per second.

This also changes behaviour a bit, previously we interleaved column and column group backgrounds. where we now put all the column group backgrounds behind all columns.
I believe this is the correct ordering as per CSS2.2 Appendix E, and since the backgrounds don't overlap, it shouldn't be observable.

Depends on D29276

This helps for the next patch, since some of the table backgrounds items want to compute this without position:relative taken into account.

Depends on D29278

This is the main performance improvement, and means that we no longer have to iterate all the cells for each column.

It has a couple of behaviour changes:

The first is that we no longer apply stacking context effects (like opacity) to column and column group backgrounds.
I believe this is correct as per both CSS2.1 Appendix E, and css-tables-3 (quoted in nsTableColFrame::BuildDisplayList).
This matches the behaviour of blink and WebKit.

We also previously created items in column,row ordering, whereas now they will be in row,column. They shouldn't overlap,
so this difference shouldn't be visible.

Depends on D29279

Depends on D29280

Depends on D29281

Two comments that didn't fit in any particular patch:

1. It seems like a bunch of the shadow items are still added unconditionally after the patch series (although maybe a patch I didn't review fixed that), and it might be good to add tests of shadows->HasShadowWithInset(...) for cells, rows, and row groups, like what's in nsFrame::DisplayBorderBackgroundOutline

2. I'm a little worried that we do something weird about image tiling/positioning if columns or column-groups are relatively positioned. But I suspect it's probably OK. Might be worth testing.

(In reply to David Baron :dbaron: 🏴󠁵󠁳󠁣󠁡󠁿 ⌚UTC-7 from comment #30)

Two comments that didn't fit in any particular patch:

1. It seems like a bunch of the shadow items are still added unconditionally after the patch series (although maybe a patch I didn't review fixed that), and it might be good to add tests of shadows->HasShadowWithInset(...) for cells, rows, and row groups, like what's in nsFrame::DisplayBorderBackgroundOutline

Part 3 makes us call Display(Inset|Outeset)BoxShadow from cell/row/row-group BuildDisplayList functions, which includes a check of HasShadowWithInset.

2. I'm a little worried that we do something weird about image tiling/positioning if columns or column-groups are relatively positioned. But I suspect it's probably OK. Might be worth testing.

Would you expect position:relative to have any effect on columns and column groups? I assumed it was ignored like most other properties, and we're painting the backgrounds without taking the column position into account.

(In reply to Matt Woodrow (:mattwoodrow) from comment #31)

2. I'm a little worried that we do something weird about image tiling/positioning if columns or column-groups are relatively positioned. But I suspect it's probably OK. Might be worth testing.

Would you expect position:relative to have any effect on columns and column groups? I assumed it was ignored like most other properties, and we're painting the backgrounds without taking the column position into account.

I would expect position:relative to have no effect on columns and column groups.

Depends on D29447

https://hg.mozilla.org/mozilla-central/rev/a8bd87bfc775
https://hg.mozilla.org/mozilla-central/rev/c0aa0d405e3c
https://hg.mozilla.org/mozilla-central/rev/1782b76bbc22
https://hg.mozilla.org/mozilla-central/rev/5137a23cfbba
https://hg.mozilla.org/mozilla-central/rev/34651ebcbaf4
https://hg.mozilla.org/mozilla-central/rev/e88eae3b48a7
https://hg.mozilla.org/mozilla-central/rev/df9a4342bf97
https://hg.mozilla.org/mozilla-central/rev/69b049f54622
https://hg.mozilla.org/mozilla-central/rev/1c9357112b30
https://hg.mozilla.org/mozilla-central/rev/1ca7d32474c6
https://hg.mozilla.org/mozilla-central/rev/2543d1e28c30