Title: [256826] trunk/Source/WebCore
Revision
256826
Author
obru...@igalia.com
Date
2020-02-18 06:47:47 -0800 (Tue, 18 Feb 2020)

Log Message

[css-grid] Improve performance of track sizing algorithm for spanning items
https://bugs.webkit.org/show_bug.cgi?id=207852

Reviewed by Javier Fernandez.

Calculating the used sizing function for a track is not a very expensive
operation, but it's not trivial either, and the track sizing algorithm
needs to access sizing functions all over the place. This ends up having
a performance cost, especially for spanning items.

Intrinsic contributions from items that span a single track are handled
in a simpler way than when the span is greater than 1. In the former
case, SizeTrackToFitNonSpanningItem only calculates the track sizing
function of each track once per each item in that track. But in the
latter case we not only calculate the track sizing function of multiple
tracks per item, we also repeat this 5 times in order to handle the
various TrackSizeComputationPhase.

Therefore, to increase performance, this patch caches the used track
sizing functions in the tracks themselves.

This is a port of these Chromium patches:
- https://chromium-review.googlesource.com/c/chromium/src/+/1901292
- https://chromium-review.googlesource.com/c/chromium/src/+/1919140
- https://chromium-review.googlesource.com/c/chromium/src/+/1940107

Chromium has a auto-grid-lots-of-spanning-data perf test. In WebKit, its
performance improves by 40% with this patch.

* rendering/GridTrackSizingAlgorithm.cpp:
(WebCore::GridTrack::setCachedTrackSize):
(WebCore::GridTrackSizingAlgorithm::sizeTrackToFitNonSpanningItem):
(WebCore::GridTrackSizingAlgorithm::spanningItemCrossesFlexibleSizedTracks const):
(WebCore::GridTrackSizingAlgorithm::increaseSizesToAccommodateSpanningItems):
(WebCore::GridTrackSizingAlgorithm::estimatedGridAreaBreadthForChild const):
(WebCore::GridTrackSizingAlgorithm::isIntrinsicSizedGridArea const):
(WebCore::GridTrackSizingAlgorithm::calculateGridTrackSize const):
(WebCore::GridTrackSizingAlgorithm::computeFlexFactorUnitSize const):
(WebCore::GridTrackSizingAlgorithm::computeFlexSizedTracksGrowth const):
(WebCore::GridTrackSizingAlgorithm::findFrUnitSize const):
(WebCore::GridTrackSizingAlgorithmStrategy::minSizeForChild const):
(WebCore::normalizedFlexFraction):
(WebCore::IndefiniteSizeStrategy::findUsedFlexFraction const):
(WebCore::GridTrackSizingAlgorithm::initializeTrackSizes):
(WebCore::GridTrackSizingAlgorithm::tracksAreWiderThanMinTrackBreadth const):
* rendering/GridTrackSizingAlgorithm.h:
(WebCore::GridTrack::cachedTrackSize const):

Modified Paths

Diff

Modified: trunk/Source/WebCore/ChangeLog (256825 => 256826)


--- trunk/Source/WebCore/ChangeLog	2020-02-18 14:15:41 UTC (rev 256825)
+++ trunk/Source/WebCore/ChangeLog	2020-02-18 14:47:47 UTC (rev 256826)
@@ -1,3 +1,53 @@
+2020-02-18  Oriol Brufau  <obru...@igalia.com>
+
+        [css-grid] Improve performance of track sizing algorithm for spanning items
+        https://bugs.webkit.org/show_bug.cgi?id=207852
+
+        Reviewed by Javier Fernandez.
+
+        Calculating the used sizing function for a track is not a very expensive
+        operation, but it's not trivial either, and the track sizing algorithm
+        needs to access sizing functions all over the place. This ends up having
+        a performance cost, especially for spanning items.
+
+        Intrinsic contributions from items that span a single track are handled
+        in a simpler way than when the span is greater than 1. In the former
+        case, SizeTrackToFitNonSpanningItem only calculates the track sizing
+        function of each track once per each item in that track. But in the
+        latter case we not only calculate the track sizing function of multiple
+        tracks per item, we also repeat this 5 times in order to handle the
+        various TrackSizeComputationPhase.
+
+        Therefore, to increase performance, this patch caches the used track
+        sizing functions in the tracks themselves.
+
+        This is a port of these Chromium patches:
+        - https://chromium-review.googlesource.com/c/chromium/src/+/1901292
+        - https://chromium-review.googlesource.com/c/chromium/src/+/1919140
+        - https://chromium-review.googlesource.com/c/chromium/src/+/1940107
+
+        Chromium has a auto-grid-lots-of-spanning-data perf test. In WebKit, its
+        performance improves by 40% with this patch.
+
+        * rendering/GridTrackSizingAlgorithm.cpp:
+        (WebCore::GridTrack::setCachedTrackSize):
+        (WebCore::GridTrackSizingAlgorithm::sizeTrackToFitNonSpanningItem):
+        (WebCore::GridTrackSizingAlgorithm::spanningItemCrossesFlexibleSizedTracks const):
+        (WebCore::GridTrackSizingAlgorithm::increaseSizesToAccommodateSpanningItems):
+        (WebCore::GridTrackSizingAlgorithm::estimatedGridAreaBreadthForChild const):
+        (WebCore::GridTrackSizingAlgorithm::isIntrinsicSizedGridArea const):
+        (WebCore::GridTrackSizingAlgorithm::calculateGridTrackSize const):
+        (WebCore::GridTrackSizingAlgorithm::computeFlexFactorUnitSize const):
+        (WebCore::GridTrackSizingAlgorithm::computeFlexSizedTracksGrowth const):
+        (WebCore::GridTrackSizingAlgorithm::findFrUnitSize const):
+        (WebCore::GridTrackSizingAlgorithmStrategy::minSizeForChild const):
+        (WebCore::normalizedFlexFraction):
+        (WebCore::IndefiniteSizeStrategy::findUsedFlexFraction const):
+        (WebCore::GridTrackSizingAlgorithm::initializeTrackSizes):
+        (WebCore::GridTrackSizingAlgorithm::tracksAreWiderThanMinTrackBreadth const):
+        * rendering/GridTrackSizingAlgorithm.h:
+        (WebCore::GridTrack::cachedTrackSize const):
+
 2020-02-18  Chris Lord  <cl...@igalia.com>
 
         [ARM] Build failure on arm due to invalid use of incomplete type 'class WebCore::ImageData' in FEBlendNEON.h

Modified: trunk/Source/WebCore/rendering/GridTrackSizingAlgorithm.cpp (256825 => 256826)


--- trunk/Source/WebCore/rendering/GridTrackSizingAlgorithm.cpp	2020-02-18 14:15:41 UTC (rev 256825)
+++ trunk/Source/WebCore/rendering/GridTrackSizingAlgorithm.cpp	2020-02-18 14:47:47 UTC (rev 256826)
@@ -83,6 +83,11 @@
     m_growthLimitCap = growthLimitCap;
 }
 
+void GridTrack::setCachedTrackSize(const GridTrackSize& cachedTrackSize)
+{
+    m_cachedTrackSize = cachedTrackSize;
+}
+
 void GridTrack::ensureGrowthLimitIsBiggerThanBaseSize()
 {
     if (m_growthLimit != infinity && m_growthLimit < m_baseSize)
@@ -239,7 +244,7 @@
 void GridTrackSizingAlgorithm::sizeTrackToFitNonSpanningItem(const GridSpan& span, RenderBox& gridItem, GridTrack& track)
 {
     unsigned trackPosition = span.startLine();
-    GridTrackSize trackSize = gridTrackSize(m_direction, trackPosition);
+    const auto& trackSize = tracks(m_direction)[trackPosition].cachedTrackSize();
 
     if (trackSize.hasMinContentMinTrackBreadth()) {
         track.setBaseSize(std::max(track.baseSize(), m_strategy->minContentForChild(gridItem)));
@@ -261,8 +266,9 @@
 
 bool GridTrackSizingAlgorithm::spanningItemCrossesFlexibleSizedTracks(const GridSpan& itemSpan) const
 {
+    const Vector<GridTrack>& trackList = tracks(m_direction);
     for (auto trackPosition : itemSpan) {
-        const GridTrackSize& trackSize = gridTrackSize(m_direction, trackPosition);
+        const auto& trackSize = trackList[trackPosition].cachedTrackSize();
         if (trackSize.minTrackBreadth().isFlex() || trackSize.maxTrackBreadth().isFlex())
             return true;
     }
@@ -440,8 +446,8 @@
         growBeyondGrowthLimitsTracks.shrink(0);
         LayoutUnit spanningTracksSize;
         for (auto trackPosition : itemSpan) {
-            const GridTrackSize& trackSize = gridTrackSize(m_direction, trackPosition);
-            GridTrack& track = tracks(m_direction)[trackPosition];
+            GridTrack& track = allTracks[trackPosition];
+            const auto& trackSize = track.cachedTrackSize();
             spanningTracksSize += trackSizeForTrackSizeComputationPhase(phase, track, ForbidInfinity);
             if (!shouldProcessTrackForTrackSizeComputationPhase(phase, trackSize))
                 continue;
@@ -561,10 +567,10 @@
     bool gridAreaIsIndefinite = false;
     Optional<LayoutUnit> availableSize = availableSpace(direction);
     for (auto trackPosition : span) {
-        // We may need to estimate the grid area size before running the track
-        // sizing algorithm in order to perform the pre-layout of orthogonal
-        // items.
-        GridTrackSize trackSize = wasSetup() ? gridTrackSize(direction, trackPosition) : rawGridTrackSize(direction, trackPosition);
+        // We may need to estimate the grid area size before running the track sizing algorithm in order to perform the pre-layout of orthogonal items.
+        // We cannot use tracks(direction)[trackPosition].cachedTrackSize() because tracks(direction) is empty, since we are either performing pre-layout
+        // or are running the track sizing algorithm in the opposite direction and haven't run it in the desired direction yet.
+        const auto& trackSize = wasSetup() ? calculateGridTrackSize(direction, trackPosition) : rawGridTrackSize(direction, trackPosition);
         GridLength maxTrackSize = trackSize.maxTrackBreadth();
         if (maxTrackSize.isContentSized() || maxTrackSize.isFlex() || isRelativeGridLengthAsAuto(maxTrackSize, direction))
             gridAreaIsIndefinite = true;
@@ -621,7 +627,7 @@
     GridTrackSizingDirection direction = gridDirectionForAxis(axis);
     const GridSpan& span = m_grid.gridItemSpan(child, direction);
     for (auto trackPosition : span) {
-        GridTrackSize trackSize = rawGridTrackSize(direction, trackPosition);
+        const auto& trackSize = rawGridTrackSize(direction, trackPosition);
         // We consider fr units as 'auto' for the min sizing function.
         // FIXME(jfernandez): https://github.com/w3c/csswg-drafts/issues/2611
         //
@@ -636,7 +642,7 @@
     return false;
 }
 
-GridTrackSize GridTrackSizingAlgorithm::gridTrackSize(GridTrackSizingDirection direction, unsigned translatedIndex) const
+GridTrackSize GridTrackSizingAlgorithm::calculateGridTrackSize(GridTrackSizingDirection direction, unsigned translatedIndex) const
 {
     ASSERT(wasSetup());
     // Collapse empty auto repeat tracks if auto-fit.
@@ -675,7 +681,7 @@
         if (tracksToTreatAsInflexible && tracksToTreatAsInflexible->contains(index))
             continue;
         LayoutUnit baseSize = tracks[index].baseSize();
-        double flexFactor = gridTrackSize(m_direction, index).maxTrackBreadth().flex();
+        double flexFactor = tracks[index].cachedTrackSize().maxTrackBreadth().flex();
         // treating all such tracks as inflexible.
         if (baseSize > hypotheticalFactorUnitSize * flexFactor) {
             leftOverSpace -= baseSize;
@@ -698,7 +704,7 @@
     const Vector<GridTrack>& allTracks = tracks(m_direction);
     for (size_t i = 0; i < numFlexTracks; ++i) {
         unsigned trackIndex = m_flexibleSizedTracksIndex[i];
-        auto trackSize = gridTrackSize(m_direction, trackIndex);
+        const auto& trackSize = allTracks[trackIndex].cachedTrackSize();
         ASSERT(trackSize.maxTrackBreadth().isFlex());
         LayoutUnit oldBaseSize = allTracks[trackIndex].baseSize();
         LayoutUnit newBaseSize = std::max(oldBaseSize, LayoutUnit(flexFraction * trackSize.maxTrackBreadth().flex()));
@@ -716,7 +722,7 @@
     double flexFactorSum = 0;
     Vector<unsigned, 8> flexibleTracksIndexes;
     for (auto trackIndex : tracksSpan) {
-        GridTrackSize trackSize = gridTrackSize(m_direction, trackIndex);
+        const auto& trackSize = allTracks[trackIndex].cachedTrackSize();
         if (!trackSize.maxTrackBreadth().isFlex())
             leftOverSpace -= allTracks[trackIndex].baseSize();
         else {
@@ -810,8 +816,9 @@
     if (childSize.isAuto() && childMinSize.isAuto() && overflowIsVisible) {
         auto minSize = minContentForChild(child);
         LayoutUnit maxBreadth;
+        auto allTracks = m_algorithm.tracks(direction());
         for (auto trackPosition : m_algorithm.grid().gridItemSpan(child, direction())) {
-            GridTrackSize trackSize = m_algorithm.gridTrackSize(direction(), trackPosition);
+            const auto& trackSize = allTracks[trackPosition].cachedTrackSize();
             if (!trackSize.hasFixedMaxTrackBreadth())
                 return minSize;
             maxBreadth += valueForLength(trackSize.maxTrackBreadth().length(), availableSpace().valueOr(0_lu));
@@ -947,8 +954,9 @@
 }
 
 
-static inline double normalizedFlexFraction(const GridTrack& track, double flexFactor)
+static inline double normalizedFlexFraction(const GridTrack& track)
 {
+    double flexFactor = track.cachedTrackSize().maxTrackBreadth().flex();
     return track.baseSize() / std::max<double>(1, flexFactor);
 }
 
@@ -961,7 +969,7 @@
     for (const auto& trackIndex : flexibleSizedTracksIndex) {
         // FIXME: we pass TrackSizing to gridTrackSize() because it does not really matter
         // as we know the track is a flex sized track. It'd be nice not to have to do that.
-        flexFraction = std::max(flexFraction, normalizedFlexFraction(allTracks[trackIndex], gridTrackSize(direction, trackIndex).maxTrackBreadth().flex()));
+        flexFraction = std::max(flexFraction, normalizedFlexFraction(allTracks[trackIndex]));
     }
 
     const Grid& grid = m_algorithm.grid();
@@ -1104,8 +1112,8 @@
     // 1. Initialize per Grid track variables.
     for (unsigned i = 0; i < allTracks.size(); ++i) {
         GridTrack& track = allTracks[i];
-        const GridTrackSize& trackSize = gridTrackSize(m_direction, i);
-
+        const auto& trackSize = calculateGridTrackSize(m_direction, i);
+        track.setCachedTrackSize(trackSize);
         track.setBaseSize(initialBaseSize(trackSize));
         track.setGrowthLimit(initialGrowthLimit(trackSize, track.baseSize()));
         track.setInfinitelyGrowable(false);
@@ -1352,7 +1360,7 @@
 {
     const Vector<GridTrack>& allTracks = tracks(m_direction);
     for (size_t i = 0; i < allTracks.size(); ++i) {
-        GridTrackSize trackSize = gridTrackSize(m_direction, i);
+        const auto& trackSize = allTracks[i].cachedTrackSize();
         if (initialBaseSize(trackSize) > allTracks[i].baseSize())
             return false;
     }

Modified: trunk/Source/WebCore/rendering/GridTrackSizingAlgorithm.h (256825 => 256826)


--- trunk/Source/WebCore/rendering/GridTrackSizingAlgorithm.h	2020-02-18 14:15:41 UTC (rev 256825)
+++ trunk/Source/WebCore/rendering/GridTrackSizingAlgorithm.h	2020-02-18 14:47:47 UTC (rev 256826)
@@ -73,6 +73,13 @@
     void setGrowthLimitCap(Optional<LayoutUnit>);
     Optional<LayoutUnit> growthLimitCap() const { return m_growthLimitCap; }
 
+    const GridTrackSize& cachedTrackSize() const
+    {
+        ASSERT(m_cachedTrackSize.hasValue());
+        return m_cachedTrackSize.value();
+    }
+    void setCachedTrackSize(const GridTrackSize&);
+
 private:
     bool isGrowthLimitBiggerThanBaseSize() const { return growthLimitIsInfinite() || m_growthLimit >= m_baseSize; }
 
@@ -84,6 +91,7 @@
     LayoutUnit m_tempSize { 0 };
     Optional<LayoutUnit> m_growthLimitCap;
     bool m_infinitelyGrowable { false };
+    Optional<GridTrackSize> m_cachedTrackSize;
 };
 
 class GridTrackSizingAlgorithm final {
@@ -137,7 +145,7 @@
 private:
     Optional<LayoutUnit> availableSpace() const;
     bool isRelativeGridLengthAsAuto(const GridLength&, GridTrackSizingDirection) const;
-    GridTrackSize gridTrackSize(GridTrackSizingDirection, unsigned translatedIndex) const;
+    GridTrackSize calculateGridTrackSize(GridTrackSizingDirection, unsigned translatedIndex) const;
     const GridTrackSize& rawGridTrackSize(GridTrackSizingDirection, unsigned translatedIndex) const;
 
     // Helper methods for step 1. initializeTrackSizes().
@@ -265,8 +273,6 @@
     LayoutUnit logicalHeightForChild(RenderBox&) const;
     bool updateOverrideContainingBlockContentSizeForChild(RenderBox&, GridTrackSizingDirection, Optional<LayoutUnit> = WTF::nullopt) const;
 
-    GridTrackSize gridTrackSize(GridTrackSizingDirection direction, size_t translatedIndex) const { return m_algorithm.gridTrackSize(direction, translatedIndex); }
-
     // GridTrackSizingAlgorithm accessors for subclasses.
     LayoutUnit computeTrackBasedSize() const { return m_algorithm.computeTrackBasedSize(); }
     GridTrackSizingDirection direction() const { return m_algorithm.m_direction; }
_______________________________________________
webkit-changes mailing list
webkit-changes@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-changes

Reply via email to