Bug 65491 – Implement a faster path for painting tables with overflowing cells

• Component: Layout and Rendering
• Status: RESOLVED FIXED

[Julien Chaffraix]

Painting may be taking 15% of the time when dealing with big tables with some overflowing cell (even if those are not visible).

The reason being that the code default to repainting all the cells if there is an overflowing cell.

Patch forthcoming to try to balance the 2 behaviors by repainting smartly if the overflowing cells are sparse.

[Julien Chaffraix]

Created attachment 102570 [details]
Proposed algorithmic change: Use a memory / performance tradeoff to paint fastly without blowing up the memory.

[Dave Hyatt]

Comment on attachment 102570 [details]
Proposed algorithmic change: Use a memory / performance tradeoff to paint fastly without blowing up the memory.

I need to see some tests. I want to make sure this is really about overflowing cells and that this isn't an issue of saying something overflows when it doesn't. Can you show me the real-world test case or issue that is motivating these changes?

[Dave Hyatt]

Comment on attachment 102570 [details]
Proposed algorithmic change: Use a memory / performance tradeoff to paint fastly without blowing up the memory.

View in context: https://bugs.webkit.org/attachment.cgi?id=102570&action=review

> Source/WebCore/rendering/RenderTableSection.cpp:1077
> +            // FIXME: It is possible that we repaint the same cell twice here. However we make sure the overflowing cells are sparse in the table.
> +            // This should ensure that this is still a win.

You can't ever paint the same cell twice. If the cell has any transparency, this will result you seeing both copies stacked on top of one another, won't it?

[Dave Hyatt]

Comment on attachment 102570 [details]
Proposed algorithmic change: Use a memory / performance tradeoff to paint fastly without blowing up the memory.

View in context: https://bugs.webkit.org/attachment.cgi?id=102570&action=review

Minusing because of the double painting issue since that would cause a regression.

> Source/WebCore/rendering/RenderTableSection.cpp:1097
> -            std::stable_sort(cells.begin(), cells.end(), compareCellPositions);
> +            if (!m_overflowingCells.size())
> +                std::stable_sort(cells.begin(), cells.end(), compareCellPositions);
> +            else
> +                std::stable_sort(cells.begin(), cells.end(), compareCellPositionsWithOverflowingCells);

Is it really necessary to have a different comparison function here? Does compareCellPositions not look at rows?

> Source/WebCore/rendering/RenderTableSection.cpp:1212
> -    if (m_hasOverflowingCell) {
> +    if (hasOverflowingCell()) {

Why not patch hit testing as well? You've left it slow?

[Julien Chaffraix]

(In reply to comment #2)
> (From update of attachment 102570 [details])
> Can you show me the real-world test case or issue that is motivating these changes?

My real world test case is Google Docs where they are using tables to display the content. The size of the tables can get pretty big and depending on your configuration overflowing cells may be allowed. In this case, regardless of how many cells are displayed you will always draw all of them because of the overflowing content. I will attach a synthetic test case I am using. It is a smaller version of the one I am using for profiling.

[Julien Chaffraix]

Created attachment 103644 [details]
Reduced use case

This is a 10 x 10 table, the second cell of the second row ("0") has overflowing content and triggers us to use the slow path because m_hasOverflowingCell is true. The test case I use for profiling is 500x500 but it follows the same pattern except that we have more cells overflowing and they are randomly spread in the table.

[Julien Chaffraix]

> > Source/WebCore/rendering/RenderTableSection.cpp:1097
> > -            std::stable_sort(cells.begin(), cells.end(), compareCellPositions);
> > +            if (!m_overflowingCells.size())
> > +                std::stable_sort(cells.begin(), cells.end(), compareCellPositions);
> > +            else
> > +                std::stable_sort(cells.begin(), cells.end(), compareCellPositionsWithOverflowingCells);
> 
> Is it really necessary to have a different comparison function here? Does compareCellPositions not look at rows?

We do. compareCellPositions only look at rows (not the columns inside a row) because:
1. they add the cells in order
2. use a stable sort so that we keep the ordering inside a row

To be able to use the same ordering we would need to be smarter when inserting our cells from the 2 different sorted arrays. I sided with using a more complicated comparison as it was easier to get it right. It also has the advantage of not slowing down the other code paths.

> > Source/WebCore/rendering/RenderTableSection.cpp:1212
> > -    if (m_hasOverflowingCell) {
> > +    if (hasOverflowingCell()) {
> 
> Why not patch hit testing as well? You've left it slow?

Indeed, I did not want to disturb hit testing in this patch. Also we would need to hit test all our overflowing cells and then find the right one which would complicate the existing code. If you are fine with that, I would prefer to push this change to a following patch.

[Julien Chaffraix]

(In reply to comment #3)
> (From update of attachment 102570 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=102570&action=review
> 
> > Source/WebCore/rendering/RenderTableSection.cpp:1077
> > +            // FIXME: It is possible that we repaint the same cell twice here. However we make sure the overflowing cells are sparse in the table.
> > +            // This should ensure that this is still a win.
> 
> You can't ever paint the same cell twice. If the cell has any transparency, this will result you seeing both copies stacked on top of one another, won't it?

That's a good point. I don't see any difference on Chromium and Qt after testing with opacity and overflow (even if we do repaint some overflowing cells twice in a row). I will rework the patch to remove this problem. Thanks!

[Julien Chaffraix]

Created attachment 103686 [details]
Better version: do not repaint the same cell twice, tweaked the change for more performance.

[Dave Hyatt]

Comment on attachment 103686 [details]
Better version: do not repaint the same cell twice, tweaked the change for more performance.

View in context: https://bugs.webkit.org/attachment.cgi?id=103686&action=review

Minusing for the HashSet improvement that can be made.

> Source/WebCore/ChangeLog:21
> +        (WebCore::RenderTableSection::layoutRows): Added some code to accumulute the overflowing cells

Typo: accumulate

> Source/WebCore/rendering/RenderTableSection.cpp:1064
> +            HashSet<RenderTableCell*> spanningAndOverflowingCells = m_overflowingCells;

Don't do it this way. Just check both hash tables in the code below. This is going to do a complete copy of the HashTable and that's slow.

> Source/WebCore/rendering/RenderTableSection.cpp:1073
> +                        if (spanningAndOverflowingCells.contains(current.cells[i]))
> +                            continue;

Just check both HashSets individually here.

[Dave Hyatt]

(In reply to comment #8)
> (In reply to comment #3)
> > (From update of attachment 102570 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=102570&action=review
> > 
> > > Source/WebCore/rendering/RenderTableSection.cpp:1077
> > > +            // FIXME: It is possible that we repaint the same cell twice here. However we make sure the overflowing cells are sparse in the table.
> > > +            // This should ensure that this is still a win.
> > 
> > You can't ever paint the same cell twice. If the cell has any transparency, this will result you seeing both copies stacked on top of one another, won't it?
> 
> That's a good point. I don't see any difference on Chromium and Qt after testing with opacity and overflow (even if we do repaint some overflowing cells twice in a row). I will rework the patch to remove this problem. Thanks!

I mentioned this on IRC, but just for anyone else following along, you should use rgba colors to test double painting. If you use opacity, the painting of the cell gets farmed out to a RenderLayer, so the RenderTableSection code is no longer used.

[Julien Chaffraix]

Comment on attachment 103686 [details]
Better version: do not repaint the same cell twice, tweaked the change for more performance.

View in context: https://bugs.webkit.org/attachment.cgi?id=103686&action=review

> Source/WebCore/ChangeLog:12
> +        (likely due to adding the duplicate check for every cells instead of just if we have some spanning cells).

I redid the measurements and found the actual slowdown to be within the statistical noise after the suggested changes. The speedup is confirmed though. Likely something that tainted my measurements (I used a local apache server for the tests which may have added some issues though should have impacted both measures). I did make sure the caches were warm in both experiments.

[Julien Chaffraix]

Created attachment 103807 [details]
New version: taking Dave's comment into account.

[Dave Hyatt]

Comment on attachment 103807 [details]
New version: taking Dave's comment into account.

View in context: https://bugs.webkit.org/attachment.cgi?id=103807&action=review

r=me with one suggested correction.

> Source/WebCore/rendering/RenderTableSection.cpp:1072
> +                        if (m_overflowingCells.contains(current.cells[i]))
> +                            continue;

Just make this part of an or with the other check, so that you don't waste time checking the overflow hash for non-spanning cells.

if (current.cells[i]->rowSpan() > 1 || current.cells[i]->colSpan() > 1) {
    if (m_overflowingCells.contains(current.cells[i]) || spanningCells.contains(current.cells[i]))
        continue;
    spanningCells.add(current.cells[i]);
}

[Julien Chaffraix]

Comment on attachment 103807 [details]
New version: taking Dave's comment into account.

View in context: https://bugs.webkit.org/attachment.cgi?id=103807&action=review

>> Source/WebCore/rendering/RenderTableSection.cpp:1072
>> +                            continue;
> 
> Just make this part of an or with the other check, so that you don't waste time checking the overflow hash for non-spanning cells.
> 
> if (current.cells[i]->rowSpan() > 1 || current.cells[i]->colSpan() > 1) {
>     if (m_overflowingCells.contains(current.cells[i]) || spanningCells.contains(current.cells[i]))
>         continue;
>     spanningCells.add(current.cells[i]);
> }

As discussed on IRC, we need to check every cells to avoid adding duplicated cells (basically the cells in the intersection between overflowing and visible should not be added twice).

[WebKit Review Bot]

Comment on attachment 103807 [details]
New version: taking Dave's comment into account.

Clearing flags on attachment: 103807

Committed r93341: <http://trac.webkit.org/changeset/93341>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.