Implement a faster path for painting tables with overflowing cells
https://bugs.webkit.org/show_bug.cgi?id=65491
This change introduces a smarter way of painting if the table is big enough and we have a small amount
of overflowing cells in the table. The new path does a binary search of the cells to repaint but adds
the overflowing cells to the repainting cells.
This saves ~50% when doing programmatic scrolling throught JS on a 500x100 table with some overflowing
cells. Also we cap the memory usage to a ratio of the total size of the table to avoid blowing up the
memory.
Reviewed by David Hyatt.
No new tests as the behavior should be the same.
* rendering/RenderTableSection.cpp:
(WebCore::RenderTableSection::RenderTableSection):
(WebCore::RenderTableSection::layoutRows): Added some code to accumulate the overflowing cells
in an internal HashSet (we don't need to keep them sorted and it makes it easier to use them during
painting). If we hit the cap, flip the boolean value and clear the HashSet as the slow path does not
care about the cell's information. Make sure that the "has overflowing cells" information is still
properly encoded on our 2 values.
(WebCore::compareCellPositionsWithOverflowingCells): Added this method as we are doing a more
complicated sort:
* the old path would sort one (mostly sorted) array by rows only as the stable sort would
take care of keeping the column ordering inside a row.
* the new path basically has to sort an unsorted array (taken partly from the HashSet).
(WebCore::RenderTableSection::paintObject): Tweaked the logic to account for difference between
m_forceSlowPaintPathWithOverflowingCell and has some overflowing cells. Also we make sure we don't
repaint the same cell twice.
(WebCore::RenderTableSection::nodeAtPoint): Changed to hasOverflowingCell(). We don't apply our
fast path optimization here.
* rendering/RenderTableSection.h: Transformed our original boolean into
a HashSet and a boolean. The HashSet holds up the CellStruct that are overflowing
until we reach the memory threshold. After this is hit, we just set the boolean
to avoid using too much memory.
(WebCore::RenderTableSection::hasOverflowingCell): This is the new way to determine
if we have any overflowing cell, used only for hit testing.
git-svn-id: http://svn.webkit.org/repository/webkit/trunk@93341 268f45cc-cd09-0410-ab3c-d52691b4dbfc
diff --git a/Source/WebCore/rendering/RenderTableSection.cpp b/Source/WebCore/rendering/RenderTableSection.cpp
index 3d6ff3c..c5aca9c 100644
--- a/Source/WebCore/rendering/RenderTableSection.cpp
+++ b/Source/WebCore/rendering/RenderTableSection.cpp
@@ -44,6 +44,10 @@
using namespace HTMLNames;
+// Those 2 variables are used to balance the memory consumption vs the repaint time on big tables.
+static unsigned gMinTableSizeToUseFastPaintPathWithOverflowingCell = 75 * 75;
+static float gMaxAllowedOverflowingCellRatioForFastPaintPath = 0.1f;
+
static inline void setRowLogicalHeightToRowStyleLogicalHeightIfNotRelative(RenderTableSection::RowStruct* row)
{
ASSERT(row && row->rowRenderer);
@@ -62,7 +66,6 @@
, m_outerBorderBefore(0)
, m_outerBorderAfter(0)
, m_needsCellRecalc(false)
- , m_hasOverflowingCell(false)
, m_hasMultipleCellLevels(false)
{
// init RenderObject attributes
@@ -424,7 +427,8 @@
// Set the width of our section now. The rows will also be this width.
setLogicalWidth(table()->contentLogicalWidth());
m_overflow.clear();
- m_hasOverflowingCell = false;
+ m_overflowingCells.clear();
+ m_forceSlowPaintPathWithOverflowingCell = false;
if (toAdd && totalRows && (m_rowPos[totalRows] || !nextSibling())) {
LayoutUnit totalHeight = m_rowPos[totalRows] + toAdd;
@@ -649,6 +653,12 @@
setLogicalHeight(m_rowPos[totalRows]);
+ unsigned totalCellsCount = nEffCols * totalRows;
+ int maxAllowedOverflowingCellsCount = totalCellsCount < gMinTableSizeToUseFastPaintPathWithOverflowingCell ? 0 : gMaxAllowedOverflowingCellRatioForFastPaintPath * totalCellsCount;
+
+#ifndef NDEBUG
+ bool hasOverflowingCell = false;
+#endif
// Now that our height has been determined, add in overflow from cells.
for (int r = 0; r < totalRows; r++) {
for (int c = 0; c < nEffCols; c++) {
@@ -659,10 +669,23 @@
if (r < totalRows - 1 && cell == primaryCellAt(r + 1, c))
continue;
addOverflowFromChild(cell);
- m_hasOverflowingCell |= cell->hasVisualOverflow();
+#ifndef NDEBUG
+ hasOverflowingCell |= cell->hasVisualOverflow();
+#endif
+ if (cell->hasVisualOverflow() && !m_forceSlowPaintPathWithOverflowingCell) {
+ m_overflowingCells.add(cell);
+ if (m_overflowingCells.size() > maxAllowedOverflowingCellsCount) {
+ // We need to set m_forcesSlowPaintPath only if there is a least one overflowing cells as the hit testing code rely on this information.
+ m_forceSlowPaintPathWithOverflowingCell = true;
+ // The slow path does not make any use of the overflowing cells info, don't hold on to the memory.
+ m_overflowingCells.clear();
+ }
+ }
}
}
+ ASSERT(hasOverflowingCell == this->hasOverflowingCell());
+
statePusher.pop();
return height();
}
@@ -914,6 +937,16 @@
return elem1->row() < elem2->row();
}
+// This comparison is used only when we have overflowing cells as we have an unsorted array to sort. We thus need
+// to sort both on rows and columns to properly repaint.
+static inline bool compareCellPositionsWithOverflowingCells(RenderTableCell* elem1, RenderTableCell* elem2)
+{
+ if (elem1->row() != elem2->row())
+ return elem1->row() < elem2->row();
+
+ return elem1->col() < elem2->col();
+}
+
void RenderTableSection::paintCell(RenderTableCell* cell, PaintInfo& paintInfo, const LayoutPoint& paintOffset)
{
LayoutPoint cellPoint = flipForWritingMode(cell, paintOffset, ParentToChildFlippingAdjustment);
@@ -951,7 +984,6 @@
void RenderTableSection::paintObject(PaintInfo& paintInfo, const LayoutPoint& paintOffset)
{
// Check which rows and cols are visible and only paint these.
- // FIXME: Could use a binary search here.
unsigned totalRows = m_gridRows;
unsigned totalCols = table()->columns().size();
@@ -970,8 +1002,7 @@
localRepaintRect.setX(width() - localRepaintRect.maxX());
}
- // If some cell overflows, just paint all of them.
- if (!m_hasOverflowingCell) {
+ if (!m_forceSlowPaintPathWithOverflowingCell) {
LayoutUnit before = (style()->isHorizontalWritingMode() ? localRepaintRect.y() : localRepaintRect.x()) - os;
// binary search to find a row
startrow = std::lower_bound(m_rowPos.begin(), m_rowPos.end(), before) - m_rowPos.begin();
@@ -994,7 +1025,7 @@
unsigned startcol = 0;
unsigned endcol = totalCols;
// FIXME: Implement RTL.
- if (!m_hasOverflowingCell && style()->isLeftToRightDirection()) {
+ if (!m_forceSlowPaintPathWithOverflowingCell && style()->isLeftToRightDirection()) {
LayoutUnit start = (style()->isHorizontalWritingMode() ? localRepaintRect.x() : localRepaintRect.y()) - os;
Vector<LayoutUnit>& columnPos = table()->columnPositions();
startcol = std::lower_bound(columnPos.begin(), columnPos.end(), start) - columnPos.begin();
@@ -1010,7 +1041,7 @@
++endcol;
}
if (startcol < endcol) {
- if (!m_hasMultipleCellLevels) {
+ if (!m_hasMultipleCellLevels && !m_overflowingCells.size()) {
// Draw the dirty cells in the order that they appear.
for (unsigned r = startrow; r < endrow; r++) {
for (unsigned c = startcol; c < endcol; c++) {
@@ -1022,26 +1053,41 @@
}
}
} else {
- // Draw the cells in the correct paint order.
+ // The overflowing cells should be scarce to avoid adding a lot of cells to the HashSet.
+ ASSERT(m_overflowingCells.size() < totalRows * totalCols * gMaxAllowedOverflowingCellRatioForFastPaintPath);
+
+ // To make sure we properly repaint the section, we repaint all the overflowing cells that we collected.
Vector<RenderTableCell*> cells;
+ copyToVector(m_overflowingCells, cells);
+
HashSet<RenderTableCell*> spanningCells;
+
for (unsigned r = startrow; r < endrow; r++) {
for (unsigned c = startcol; c < endcol; c++) {
CellStruct& current = cellAt(r, c);
if (!current.hasCells())
continue;
for (unsigned i = 0; i < current.cells.size(); ++i) {
+ if (m_overflowingCells.contains(current.cells[i]))
+ continue;
+
if (current.cells[i]->rowSpan() > 1 || current.cells[i]->colSpan() > 1) {
if (spanningCells.contains(current.cells[i]))
continue;
spanningCells.add(current.cells[i]);
}
+
cells.append(current.cells[i]);
}
}
}
+
// Sort the dirty cells by paint order.
- std::stable_sort(cells.begin(), cells.end(), compareCellPositions);
+ if (!m_overflowingCells.size())
+ std::stable_sort(cells.begin(), cells.end(), compareCellPositions);
+ else
+ std::sort(cells.begin(), cells.end(), compareCellPositionsWithOverflowingCells);
+
int size = cells.size();
// Paint the cells.
for (int i = 0; i < size; ++i)
@@ -1155,7 +1201,7 @@
if (hasOverflowClip() && !overflowClipRect(adjustedLocation).intersects(result.rectForPoint(pointInContainer)))
return false;
- if (m_hasOverflowingCell) {
+ if (hasOverflowingCell()) {
for (RenderObject* child = lastChild(); child; child = child->previousSibling()) {
// FIXME: We have to skip over inline flows, since they can show up inside table rows
// at the moment (a demoted inline <form> for example). If we ever implement a
