Modified: trunk/Source/WebCore/ChangeLog (93340 => 93341)
--- trunk/Source/WebCore/ChangeLog 2011-08-18 20:11:24 UTC (rev 93340)
+++ trunk/Source/WebCore/ChangeLog 2011-08-18 20:20:57 UTC (rev 93341)
@@ -1,3 +1,49 @@
+2011-08-18 Julien Chaffraix <[email protected]>
+
+ 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.
+
2011-08-18 Kentaro Hara <[email protected]>
An EventSource constructor should throw TypeError, when the number of arguments is not enough.
Modified: trunk/Source/WebCore/rendering/RenderTableSection.cpp (93340 => 93341)
--- trunk/Source/WebCore/rendering/RenderTableSection.cpp 2011-08-18 20:11:24 UTC (rev 93340)
+++ trunk/Source/WebCore/rendering/RenderTableSection.cpp 2011-08-18 20:20:57 UTC (rev 93341)
@@ -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
Modified: trunk/Source/WebCore/rendering/RenderTableSection.h (93340 => 93341)
--- trunk/Source/WebCore/rendering/RenderTableSection.h 2011-08-18 20:11:24 UTC (rev 93340)
+++ trunk/Source/WebCore/rendering/RenderTableSection.h 2011-08-18 20:20:57 UTC (rev 93341)
@@ -143,6 +143,8 @@
bool ensureRows(int);
void clearGrid();
+ bool hasOverflowingCell() const { return m_overflowingCells.size() || m_forceSlowPaintPathWithOverflowingCell; }
+
RenderObjectChildList m_children;
Vector<RowStruct> m_grid;
@@ -160,8 +162,13 @@
LayoutUnit m_outerBorderAfter;
bool m_needsCellRecalc;
- bool m_hasOverflowingCell;
+ // This HashSet holds the overflowing cells for faster painting.
+ // If we have more than gMaxAllowedOverflowingCellRatio * total cells, it will be empty
+ // and m_forceSlowPaintPathWithOverflowingCell will be set to save memory.
+ HashSet<RenderTableCell*> m_overflowingCells;
+ bool m_forceSlowPaintPathWithOverflowingCell;
+
bool m_hasMultipleCellLevels;
};
