[CSS Grid Layout] Speed up painting on large grids

[CSS Grid Layout] Speed up painting on large grids

The painting code wasn't using the grid's struture during painting.
This lead to an algorithm that would try all grid items, regardless
of whether they were outside the area to be painted.

This change makes the painting code do a binary search over the
computed grid coordinates and paint only the children that are in
these grid areas. OrderIterator was changed to be able to store the
children during collection and iterate over them, instead of always
going over all the children.

On a 200x200 grid with one grid item in each grid area, this brings
the paint time from 20ms to 2ms. Unfortunately, such a test case
cannot be added as it would require significant changes to work with
our infrastructure that would make the test not very representative
of the original use case.

The test case can be found on the associated bug (comment 5)

BUG=248151
Committed: https://src.chromium.org/viewvc/blink?view=rev&revision=157993

[Julien - ping for review, 2013-08-08 22:36:25]

Some speed-up change, the patch has an issue with grid items overflowing grid
areas (see the same issue for tables). The approach is to fix that in a
follow-up but could be fixed inline (with some extra complexity though).

[Julien - ping for review, 2013-09-17 20:57:16]

Ojan, any comment on the change? I am fine going either way but know that adding
similar code for overflowing cells has added a significant complexity that we
would need to test in grid.

[ojan, 2013-09-17 23:55:27]

lgtm

Can you upload your test case to the bug and link to it from your change
description? That way, someone working on this code years from now can reproduce
the perf improvement.

[Julien - ping for review, 2013-09-18 21:47:18]

On 2013/09/17 23:55:27, ojan wrote:
> lgtm
> 
> Can you upload your test case to the bug and link to it from your change
> description? That way, someone working on this code years from now can
reproduce
> the perf improvement.

Done, thanks Ojan!

[commit-bot: I haz the power, 2013-09-18 21:47:33]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/jchaffraix@chromium.org/22642010/1

[commit-bot: I haz the power, 2013-09-18 21:47:35]

Failed to apply patch for Source/core/rendering/RenderGrid.cpp:
While running patch -p1 --forward --force --no-backup-if-mismatch;
  patching file Source/core/rendering/RenderGrid.cpp
  Hunk #1 succeeded at 856 with fuzz 2 (offset 14 lines).
  Hunk #2 FAILED at 1094.
  1 out of 2 hunks FAILED -- saving rejects to file
Source/core/rendering/RenderGrid.cpp.rej

Patch:       Source/core/rendering/RenderGrid.cpp
Index: Source/core/rendering/RenderGrid.cpp
diff --git a/Source/core/rendering/RenderGrid.cpp
b/Source/core/rendering/RenderGrid.cpp
index
3a9e0a728995d5f6299b9e17e1de1a1cefc964eb..17f25783f683a51de992840f14c9a9614331a13d
100644
--- a/Source/core/rendering/RenderGrid.cpp
+++ b/Source/core/rendering/RenderGrid.cpp
@@ -842,6 +842,8 @@ void RenderGrid::layoutGridItems()
     computedUsedBreadthOfGridTracks(ForRows, columnTracks, rowTracks);
     ASSERT(tracksAreWiderThanMinTrackBreadth(ForRows, rowTracks));
 
+    populateGridPositions(columnTracks, rowTracks);
+
     for (RenderBox* child = firstChildBox(); child; child =
child->nextSiblingBox()) {
         LayoutPoint childPosition = findChildLogicalPosition(child,
columnTracks, rowTracks);
 
@@ -1092,25 +1094,69 @@ LayoutUnit RenderGrid::gridAreaBreadthForChild(const
RenderBox* child, TrackSizi
     return gridAreaBreadth;
 }
 
+void RenderGrid::populateGridPositions(const Vector<GridTrack>& columnTracks,
const Vector<GridTrack>& rowTracks)
+{
+    m_columnPositions.resize(columnTracks.size() + 1);
+    m_columnPositions[0] = borderAndPaddingStart();
+    for (size_t i = 0; i < m_columnPositions.size() - 1; ++i)
+        m_columnPositions[i + 1] = m_columnPositions[i] +
columnTracks[i].m_usedBreadth;
+
+    m_rowPositions.resize(rowTracks.size() + 1);
+    m_rowPositions[0] = borderAndPaddingBefore();
+    for (size_t i = 0; i < m_rowPositions.size() - 1; ++i)
+        m_rowPositions[i + 1] = m_rowPositions[i] + rowTracks[i].m_usedBreadth;
+}
+
 LayoutPoint RenderGrid::findChildLogicalPosition(RenderBox* child, const
Vector<GridTrack>& columnTracks, const Vector<GridTrack>& rowTracks)
 {
     const GridCoordinate& coordinate = cachedGridCoordinate(child);
 
-    // The grid items should be inside the grid container's border box, that's
why they need to be shifted.
-    LayoutPoint offset(borderAndPaddingStart(), borderAndPaddingBefore());
-    // FIXME: |columnTrack| and |rowTrack| should be smaller than our column /
row count.
-    for (size_t i = 0; i < coordinate.columns.initialPositionIndex && i <
columnTracks.size(); ++i)
-        offset.setX(offset.x() + columnTracks[i].m_usedBreadth);
-    for (size_t i = 0; i < coordinate.rows.initialPositionIndex && i <
rowTracks.size(); ++i)
-        offset.setY(offset.y() + rowTracks[i].m_usedBreadth);
+    ASSERT(coordinate.columns.initialPositionIndex < columnTracks.size());
+    ASSERT(coordinate.rows.initialPositionIndex < rowTracks.size());
 
     // FIXME: Handle margins on the grid item.
-    return offset;
+    return
LayoutPoint(m_columnPositions[coordinate.columns.initialPositionIndex],
m_rowPositions[coordinate.rows.initialPositionIndex]);
+}
+
+static GridSpan dirtiedGridAreas(const Vector<LayoutUnit>& coordinates,
LayoutUnit start, LayoutUnit end)
+{
+    // This function does a binary search over the coordinates.
+    // FIXME: This doesn't work with grid items overflowing their grid areas
and should be tested & fixed.
+
+    size_t startGridAreaIndex = std::upper_bound(coordinates.begin(),
coordinates.end() - 1, start) - coordinates.begin();
+    if (startGridAreaIndex > 0)
+        --startGridAreaIndex;
+
+    size_t endGridAreaIndex = std::upper_bound(coordinates.begin() +
startGridAreaIndex, coordinates.end() - 1, end) - coordinates.begin();
+    return GridSpan(startGridAreaIndex, endGridAreaIndex);
 }
 
 void RenderGrid::paintChildren(PaintInfo& paintInfo, const LayoutPoint&
paintOffset)
 {
-    for (RenderBox* child = m_orderIterator.first(); child; child =
m_orderIterator.next())
+    ASSERT_WITH_SECURITY_IMPLICATION(!gridIsDirty());
+
+    LayoutRect localRepaintRect = paintInfo.rect;
+    localRepaintRect.moveBy(-paintOffset);
+
+    GridSpan dirtiedColumns = dirtiedGridAreas(m_columnPositions,
localRepaintRect.x(), localRepaintRect.maxX());
+    GridSpan dirtiedRows = dirtiedGridAreas(m_rowPositions,
localRepaintRect.y(), localRepaintRect.maxY());
+
+    OrderIterator paintIterator(this);
+    {
+        OrderIteratorPopulator populator(paintIterator);
+
+        for (size_t row = dirtiedRows.initialPositionIndex; row <
dirtiedRows.finalPositionIndex; ++row) {
+            for (size_t column = dirtiedColumns.initialPositionIndex; column <
dirtiedColumns.finalPositionIndex; ++column) {
+                const Vector<RenderBox*, 1> children = m_grid[row][column];
+                // FIXME: If we start adding spanning children in all grid
areas they span, this
+                // would make us paint them several times, which is wrong!
+                for (size_t j = 0; j < children.size(); ++j)
+                    populator.storeChild(children[j]);
+            }
+        }
+    }
+
+    for (RenderBox* child = paintIterator.first(); child; child =
paintIterator.next())
         paintChild(child, paintInfo, paintOffset);
 }

[commit-bot: I haz the power, 2013-09-18 23:09:12]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/jchaffraix@chromium.org/22642010/9001

[commit-bot: I haz the power, 2013-09-18 23:12:57]

Retried try job too often on blink_presubmit for step(s) presubmit
http://build.chromium.org/p/tryserver.chromium/buildstatus?builder=blink_pres...

[commit-bot: I haz the power, 2013-09-19 00:34:56]

CQ is trying da patch. Follow status at
https://chromium-status.appspot.com/cq/jchaffraix@chromium.org/22642010/9001

[commit-bot: I haz the power, 2013-09-19 02:03:22]

Change committed as 157993