Title: [147620] trunk/Source/WebCore
- Revision
- 147620
- Author
- [email protected]
- Date
- 2013-04-04 04:10:19 -0700 (Thu, 04 Apr 2013)
Log Message
[CSSRegions] RenderFlowThread::renderRegionForLine should use a faster search method
https://bugs.webkit.org/show_bug.cgi?id=66921
Reviewed by David Hyatt.
The RenderFlowThread::regionAtBlockOffset() function is a hot path for the code using
flow threads because it translates from block coordinates to regions.
Currently the method is O(n), using a linear search through the regions chain to find the
region where a block offset lands.
The patch improves this search by using an interval tree (PODIntervalTree). Before a flow
thread is laid out, each region is updated to hold the size of the portion of the flow it
will receive. This information is gathered inside the interval tree and used to speedup the
search in RenderFlowThread::regionAtBlockOffset(). The algorithm uses a custom adapter
simplified for looking up offsets inside the interval tree.
For now, the interval tree is cleared every time the flow thread portions list is updated.
The implementation can be improved but induces some cmplexity as we'd have to manually manage
the life cycle of the tree's nodes. The performance gains are good enough as is to make this
only optional.
Another important change is now the flow thread portion rectangles will not overflow when
using auto-height regions (or very large regions). The maximum size of the flow is set to
LayoutUnit::max()/2. Any region forcing a greater size will be capped so the thread
won't overflow.
Performance test results:
/Layout/RegionsAuto:Time ms 699.95 181.20 74.11% Better
/Layout/RegionsAutoMaxHeight:Time ms 2083.00 308.55 85.19% Better
/Layout/RegionsFixed:Time ms 726.10 223.65 69.20% Better
/Layout/RegionsFixedShort:Time ms 869.60 288.25 66.85% Better
Tests: See PerformanceTests/Layout/Regions*
* rendering/RenderFlowThread.cpp:
(WebCore::RenderFlowThread::regionAtBlockOffset):
(WebCore::RenderFlowThread::updateRegionsFlowThreadPortionRect):
(WebCore::RenderFlowThread::RegionSearchAdapter::collectIfNeeded):
(WebCore):
* rendering/RenderFlowThread.h:
(WebCore):
Modified Paths
Diff
Modified: trunk/Source/WebCore/ChangeLog (147619 => 147620)
--- trunk/Source/WebCore/ChangeLog 2013-04-04 11:07:16 UTC (rev 147619)
+++ trunk/Source/WebCore/ChangeLog 2013-04-04 11:10:19 UTC (rev 147620)
@@ -1,3 +1,44 @@
+2013-04-04 Andrei Bucur <[email protected]>
+
+ [CSSRegions] RenderFlowThread::renderRegionForLine should use a faster search method
+ https://bugs.webkit.org/show_bug.cgi?id=66921
+
+ Reviewed by David Hyatt.
+
+ The RenderFlowThread::regionAtBlockOffset() function is a hot path for the code using
+ flow threads because it translates from block coordinates to regions.
+ Currently the method is O(n), using a linear search through the regions chain to find the
+ region where a block offset lands.
+ The patch improves this search by using an interval tree (PODIntervalTree). Before a flow
+ thread is laid out, each region is updated to hold the size of the portion of the flow it
+ will receive. This information is gathered inside the interval tree and used to speedup the
+ search in RenderFlowThread::regionAtBlockOffset(). The algorithm uses a custom adapter
+ simplified for looking up offsets inside the interval tree.
+ For now, the interval tree is cleared every time the flow thread portions list is updated.
+ The implementation can be improved but induces some cmplexity as we'd have to manually manage
+ the life cycle of the tree's nodes. The performance gains are good enough as is to make this
+ only optional.
+ Another important change is now the flow thread portion rectangles will not overflow when
+ using auto-height regions (or very large regions). The maximum size of the flow is set to
+ LayoutUnit::max()/2. Any region forcing a greater size will be capped so the thread
+ won't overflow.
+
+ Performance test results:
+ /Layout/RegionsAuto:Time ms 699.95 181.20 74.11% Better
+ /Layout/RegionsAutoMaxHeight:Time ms 2083.00 308.55 85.19% Better
+ /Layout/RegionsFixed:Time ms 726.10 223.65 69.20% Better
+ /Layout/RegionsFixedShort:Time ms 869.60 288.25 66.85% Better
+
+ Tests: See PerformanceTests/Layout/Regions*
+
+ * rendering/RenderFlowThread.cpp:
+ (WebCore::RenderFlowThread::regionAtBlockOffset):
+ (WebCore::RenderFlowThread::updateRegionsFlowThreadPortionRect):
+ (WebCore::RenderFlowThread::RegionSearchAdapter::collectIfNeeded):
+ (WebCore):
+ * rendering/RenderFlowThread.h:
+ (WebCore):
+
2013-04-04 Seokju Kwon <[email protected]>
[Qt] WebSocket errors should be logged to console
Modified: trunk/Source/WebCore/rendering/RenderFlowThread.cpp (147619 => 147620)
--- trunk/Source/WebCore/rendering/RenderFlowThread.cpp 2013-04-04 11:07:16 UTC (rev 147619)
+++ trunk/Source/WebCore/rendering/RenderFlowThread.cpp 2013-04-04 11:10:19 UTC (rev 147620)
@@ -35,6 +35,7 @@
#include "HitTestRequest.h"
#include "HitTestResult.h"
#include "Node.h"
+#include "PODIntervalTree.h"
#include "PaintInfo.h"
#include "RenderBoxRegionInfo.h"
#include "RenderLayer.h"
@@ -370,41 +371,21 @@
{
ASSERT(!m_regionsInvalidated);
- // If no region matches the position and extendLastRegion is true, it will return
- // the last valid region. It is similar to auto extending the size of the last region.
- RenderRegion* lastValidRegion = 0;
-
- LayoutUnit accumulatedLogicalHeight = 0;
-
- // If our flow thread autogenerates its regions, then make sure we ensure those regions exist
- // now.
if (autoGenerationPolicy == AllowRegionAutoGeneration)
autoGenerateRegionsToBlockOffset(offset);
- // FIXME: The regions are always in order, optimize this search.
- for (RenderRegionList::const_iterator iter = m_regionList.begin(); iter != m_regionList.end(); ++iter) {
- RenderRegion* region = *iter;
+ if (offset <= 0)
+ return m_regionList.isEmpty() ? 0 : m_regionList.first();
- if (offset <= 0)
- return region;
+ RegionSearchAdapter adapter(offset);
+ m_regionIntervalTree.allOverlapsWithAdapter<RegionSearchAdapter>(adapter);
- if (extendLastRegion || region->isRenderRegionSet())
- lastValidRegion = region;
+ // If no region was found, the offset is in the flow thread overflow.
+ // The last region will contain the offset if extendLastRegion is set or if the last region is a set.
+ if (!adapter.result() && !m_regionList.isEmpty() && (extendLastRegion || m_regionList.last()->isRenderRegionSet()))
+ return m_regionList.last();
- if (region->hasOverrideHeight() && !inConstrainedLayoutPhase()) {
- accumulatedLogicalHeight += region->overrideLogicalContentHeight();
- if (offset < accumulatedLogicalHeight)
- return region;
- continue;
- }
-
- LayoutRect regionRect = region->flowThreadPortionRect();
- accumulatedLogicalHeight += isHorizontalWritingMode() ? regionRect.height() : regionRect.width();
- if (offset < accumulatedLogicalHeight)
- return region;
- }
-
- return lastValidRegion;
+ return adapter.result();
}
LayoutUnit RenderFlowThread::pageLogicalTopForOffset(LayoutUnit offset)
@@ -828,6 +809,9 @@
ASSERT(!lastRegionWithContent || (!inConstrainedLayoutPhase() && hasAutoLogicalHeightRegions()));
LayoutUnit logicalHeight = 0;
bool emptyRegionsSegment = false;
+ // FIXME: Optimize not to clear the interval all the time. This implies manually managing the tree nodes lifecycle.
+ m_regionIntervalTree.clear();
+ m_regionIntervalTree.initIfNeeded();
for (RenderRegionList::iterator iter = m_regionList.begin(); iter != m_regionList.end(); ++iter) {
RenderRegion* region = *iter;
@@ -836,11 +820,14 @@
region->clearOverrideLogicalContentHeight();
LayoutUnit regionLogicalWidth = region->pageLogicalWidth();
- LayoutUnit regionLogicalHeight = region->logicalHeightOfAllFlowThreadContent();
+ LayoutUnit regionLogicalHeight = std::min<LayoutUnit>(LayoutUnit::max() / 2 - logicalHeight, region->logicalHeightOfAllFlowThreadContent());
LayoutRect regionRect(style()->direction() == LTR ? LayoutUnit() : logicalWidth() - regionLogicalWidth, logicalHeight, regionLogicalWidth, regionLogicalHeight);
region->setFlowThreadPortionRect(isHorizontalWritingMode() ? regionRect : regionRect.transposedRect());
+
+ m_regionIntervalTree.add(RegionIntervalTree::createInterval(logicalHeight, logicalHeight + regionLogicalHeight, region));
+
logicalHeight += regionLogicalHeight;
// Once we find the last region with content the next regions are considered empty.
@@ -972,6 +959,14 @@
return result;
}
+void RenderFlowThread::RegionSearchAdapter::collectIfNeeded(const RegionInterval& interval)
+{
+ if (m_result)
+ return;
+ if (interval.low() <= m_offset && interval.high() > m_offset)
+ m_result = interval.data();
+}
+
CurrentRenderFlowThreadMaintainer::CurrentRenderFlowThreadMaintainer(RenderFlowThread* renderFlowThread)
: m_renderFlowThread(renderFlowThread)
, m_previousRenderFlowThread(0)
Modified: trunk/Source/WebCore/rendering/RenderFlowThread.h (147619 => 147620)
--- trunk/Source/WebCore/rendering/RenderFlowThread.h 2013-04-04 11:07:16 UTC (rev 147619)
+++ trunk/Source/WebCore/rendering/RenderFlowThread.h 2013-04-04 11:10:19 UTC (rev 147620)
@@ -211,6 +211,28 @@
RenderRegion* m_endRegion;
};
+ typedef PODInterval<LayoutUnit, RenderRegion*> RegionInterval;
+ typedef PODIntervalTree<LayoutUnit, RenderRegion*> RegionIntervalTree;
+
+ class RegionSearchAdapter {
+ public:
+ RegionSearchAdapter(LayoutUnit offset)
+ : m_offset(offset)
+ , m_result(0)
+ {
+ }
+
+ const LayoutUnit& lowValue() const { return m_offset; }
+ const LayoutUnit& highValue() const { return m_offset; }
+ void collectIfNeeded(const RegionInterval&);
+
+ RenderRegion* result() const { return m_result; }
+
+ private:
+ LayoutUnit m_offset;
+ RenderRegion* m_result;
+ };
+
// A maps from RenderBox
typedef HashMap<const RenderBox*, RenderRegionRange> RenderRegionRangeMap;
RenderRegionRangeMap m_regionRangeMap;
@@ -221,6 +243,8 @@
unsigned m_autoLogicalHeightRegionsCount;
+ RegionIntervalTree m_regionIntervalTree;
+
bool m_regionsInvalidated : 1;
bool m_regionsHaveUniformLogicalWidth : 1;
bool m_regionsHaveUniformLogicalHeight : 1;
@@ -257,6 +281,17 @@
RenderFlowThread* m_previousRenderFlowThread;
};
+// These structures are used by PODIntervalTree for debugging.
+#ifndef NDEBUG
+template <> struct ValueToString<LayoutUnit> {
+ static String string(const LayoutUnit value) { return String::number(value.toFloat()); }
+};
+
+template <> struct ValueToString<RenderRegion*> {
+ static String string(const RenderRegion* value) { return String::format("%p", value); }
+};
+#endif
+
} // namespace WebCore
#endif // RenderFlowThread_h
_______________________________________________
webkit-changes mailing list
[email protected]
https://lists.webkit.org/mailman/listinfo/webkit-changes
