Changeset 159741 in webkit


Ignore:
Timestamp:
Nov 25, 2013 12:22:08 AM (10 years ago)
Author:
svillar@igalia.com
Message:

[CSS Grid Layout] Cache several vectors to avoid malloc/free churn
https://bugs.webkit.org/show_bug.cgi?id=123995

Reviewed by Dean Jackson.

From Blink r158228 by <jchaffraix@chromium.org>

Laying-out the grid items means a lot of calls to
distributeSpaceToTracks() and
resolveContentBasedTrackSizingFunctionsForItems() as they're
called in a loop. This means that there is a lot of malloc/free
going on there. By moving the vectors used by these methods to a
new class which is kept during the whole layout process we save a
lot of those calls.

This obviously mean that the price we pay for a significant
perfomance improvement is that we keep the maximum allocation till
the end of each layout, but it's an amount of memory that we have
to allocate anyway. The improvement in the
auto-grid-lots-of-data.html perf test is ~24% (165 runs/s vs 207
runs/s).

No new tests required as we're just refactoring code to a new
helper class. Nevertheless the performance improvement is backed
by the perf test mentioned above.

  • rendering/RenderGrid.cpp:

(WebCore::RenderGrid::GridSizingData::GridSizingData):
(WebCore::RenderGrid::computedUsedBreadthOfGridTracks):
(WebCore::RenderGrid::resolveContentBasedTrackSizingFunctions):
(WebCore::RenderGrid::resolveContentBasedTrackSizingFunctionsForItems):
(WebCore::RenderGrid::distributeSpaceToTracks):
(WebCore::RenderGrid::layoutGridItems):
(WebCore::RenderGrid::findChildLogicalPosition):

  • rendering/RenderGrid.h:
Location:
trunk/Source/WebCore
Files:
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/Source/WebCore/ChangeLog

    r159737 r159741  
     12013-11-18  Sergio Villar Senin  <svillar@igalia.com>
     2
     3        [CSS Grid Layout] Cache several vectors to avoid malloc/free churn
     4        https://bugs.webkit.org/show_bug.cgi?id=123995
     5
     6        Reviewed by Dean Jackson.
     7
     8        From Blink r158228 by <jchaffraix@chromium.org>
     9
     10        Laying-out the grid items means a lot of calls to
     11        distributeSpaceToTracks() and
     12        resolveContentBasedTrackSizingFunctionsForItems() as they're
     13        called in a loop. This means that there is a lot of malloc/free
     14        going on there. By moving the vectors used by these methods to a
     15        new class which is kept during the whole layout process we save a
     16        lot of those calls.
     17
     18        This obviously mean that the price we pay for a significant
     19        perfomance improvement is that we keep the maximum allocation till
     20        the end of each layout, but it's an amount of memory that we have
     21        to allocate anyway. The improvement in the
     22        auto-grid-lots-of-data.html perf test is ~24% (165 runs/s vs 207
     23        runs/s).
     24
     25        No new tests required as we're just refactoring code to a new
     26        helper class. Nevertheless the performance improvement is backed
     27        by the perf test mentioned above.
     28
     29        * rendering/RenderGrid.cpp:
     30        (WebCore::RenderGrid::GridSizingData::GridSizingData):
     31        (WebCore::RenderGrid::computedUsedBreadthOfGridTracks):
     32        (WebCore::RenderGrid::resolveContentBasedTrackSizingFunctions):
     33        (WebCore::RenderGrid::resolveContentBasedTrackSizingFunctionsForItems):
     34        (WebCore::RenderGrid::distributeSpaceToTracks):
     35        (WebCore::RenderGrid::layoutGridItems):
     36        (WebCore::RenderGrid::findChildLogicalPosition):
     37        * rendering/RenderGrid.h:
     38
    1392013-11-24  Brady Eidson  <beidson@apple.com>
    240
  • trunk/Source/WebCore/rendering/RenderGrid.cpp

    r159685 r159741  
    142142};
    143143
     144class RenderGrid::GridSizingData {
     145    WTF_MAKE_NONCOPYABLE(GridSizingData);
     146public:
     147    GridSizingData(size_t gridColumnCount, size_t gridRowCount)
     148        : columnTracks(gridColumnCount)
     149        , rowTracks(gridRowCount)
     150    {
     151    }
     152
     153    Vector<GridTrack> columnTracks;
     154    Vector<GridTrack> rowTracks;
     155    Vector<size_t> contentSizedTracksIndex;
     156
     157    // Performance optimization: hold onto these Vectors until the end of Layout to avoid repeated malloc / free.
     158    Vector<LayoutUnit> distributeTrackVector;
     159    Vector<GridTrack*> filteredTracks;
     160};
     161
    144162RenderGrid::RenderGrid(Element& element, PassRef<RenderStyle> style)
    145163    : RenderBlock(element, std::move(style), 0)
     
    277295}
    278296
    279 void RenderGrid::computedUsedBreadthOfGridTracks(TrackSizingDirection direction, Vector<GridTrack>& columnTracks, Vector<GridTrack>& rowTracks)
     297void RenderGrid::computedUsedBreadthOfGridTracks(TrackSizingDirection direction, GridSizingData& sizingData)
    280298{
    281299    LayoutUnit availableLogicalSpace = (direction == ForColumns) ? availableLogicalWidth() : availableLogicalHeight(IncludeMarginBorderPadding);
    282     Vector<GridTrack>& tracks = (direction == ForColumns) ? columnTracks : rowTracks;
    283     Vector<size_t> contentSizedTracks;
     300    Vector<GridTrack>& tracks = (direction == ForColumns) ? sizingData.columnTracks : sizingData.rowTracks;
     301    sizingData.contentSizedTracksIndex.shrink(0);
    284302    for (size_t i = 0; i < tracks.size(); ++i) {
    285303        GridTrack& track = tracks[i];
     
    294312
    295313        if (trackSize.isContentSized())
    296             contentSizedTracks.append(i);
    297     }
    298 
    299     if (!contentSizedTracks.isEmpty())
    300         resolveContentBasedTrackSizingFunctions(direction, columnTracks, rowTracks, contentSizedTracks);
     314            sizingData.contentSizedTracksIndex.append(i);
     315    }
     316
     317    if (!sizingData.contentSizedTracksIndex.isEmpty())
     318        resolveContentBasedTrackSizingFunctions(direction, sizingData);
    301319
    302320    for (size_t i = 0; i < tracks.size(); ++i) {
     
    313331        tracksForDistribution[i] = tracks.data() + i;
    314332
    315     distributeSpaceToTracks(tracksForDistribution, 0, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth, availableLogicalSpace);
     333    distributeSpaceToTracks(tracksForDistribution, 0, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth, sizingData, availableLogicalSpace);
    316334
    317335    // 4. Grow all Grid tracks having a fraction as the MaxTrackSizingFunction.
     
    483501}
    484502
    485 void RenderGrid::resolveContentBasedTrackSizingFunctions(TrackSizingDirection direction, Vector<GridTrack>& columnTracks, Vector<GridTrack>& rowTracks, Vector<size_t>& contentSizedTracks)
     503void RenderGrid::resolveContentBasedTrackSizingFunctions(TrackSizingDirection direction, GridSizingData& sizingData)
    486504{
    487505    // FIXME: Split the grid tracks into groups that doesn't overlap a <flex> grid track.
    488506
    489     for (size_t i = 0; i < contentSizedTracks.size(); ++i) {
    490         GridIterator iterator(m_grid, direction, contentSizedTracks[i]);
     507    for (size_t i = 0; i < sizingData.contentSizedTracksIndex.size(); ++i) {
     508        GridIterator iterator(m_grid, direction, sizingData.contentSizedTracksIndex[i]);
    491509        while (RenderBox* gridItem = iterator.nextGridItem()) {
    492             resolveContentBasedTrackSizingFunctionsForItems(direction, columnTracks, rowTracks, gridItem, &GridTrackSize::hasMinOrMaxContentMinTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
    493             resolveContentBasedTrackSizingFunctionsForItems(direction, columnTracks, rowTracks, gridItem, &GridTrackSize::hasMaxContentMinTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
    494             resolveContentBasedTrackSizingFunctionsForItems(direction, columnTracks, rowTracks, gridItem, &GridTrackSize::hasMinOrMaxContentMaxTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
    495             resolveContentBasedTrackSizingFunctionsForItems(direction, columnTracks, rowTracks, gridItem, &GridTrackSize::hasMaxContentMaxTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
    496         }
    497 
    498         GridTrack& track = (direction == ForColumns) ? columnTracks[i] : rowTracks[i];
     510            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMinOrMaxContentMinTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
     511            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMaxContentMinTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::usedBreadth, &GridTrack::growUsedBreadth);
     512            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMinOrMaxContentMaxTrackBreadth, &RenderGrid::minContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
     513            resolveContentBasedTrackSizingFunctionsForItems(direction, sizingData, gridItem, &GridTrackSize::hasMaxContentMaxTrackBreadth, &RenderGrid::maxContentForChild, &GridTrack::maxBreadthIfNotInfinite, &GridTrack::growMaxBreadth);
     514        }
     515
     516        GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[i] : sizingData.rowTracks[i];
    499517        if (track.m_maxBreadth == infinity)
    500518            track.m_maxBreadth = track.m_usedBreadth;
     
    502520}
    503521
    504 void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(TrackSizingDirection direction, Vector<GridTrack>& columnTracks, Vector<GridTrack>& rowTracks, RenderBox* gridItem, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction)
     522void RenderGrid::resolveContentBasedTrackSizingFunctionsForItems(TrackSizingDirection direction, GridSizingData& sizingData, RenderBox* gridItem, FilterFunction filterFunction, SizingFunction sizingFunction, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction)
    505523{
    506524    const GridCoordinate coordinate = cachedGridCoordinate(gridItem);
     
    508526    const size_t finalTrackIndex = (direction == ForColumns) ? coordinate.columns.finalPositionIndex : coordinate.rows.finalPositionIndex;
    509527
    510     Vector<GridTrack*> tracks;
     528    sizingData.filteredTracks.shrink(0);
    511529    for (size_t trackIndex = initialTrackIndex; trackIndex <= finalTrackIndex; ++trackIndex) {
    512530        const GridTrackSize& trackSize = gridTrackSize(direction, trackIndex);
     
    514532            continue;
    515533
    516         GridTrack& track = (direction == ForColumns) ? columnTracks[trackIndex] : rowTracks[trackIndex];
    517         tracks.append(&track);
    518     }
    519 
    520     if (tracks.isEmpty())
     534        GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndex] : sizingData.rowTracks[trackIndex];
     535        sizingData.filteredTracks.append(&track);
     536    }
     537
     538    if (sizingData.filteredTracks.isEmpty())
    521539        return;
    522540
    523     LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(gridItem, direction, columnTracks);
     541    LayoutUnit additionalBreadthSpace = (this->*sizingFunction)(gridItem, direction, sizingData.columnTracks);
    524542    for (size_t trackIndexForSpace = initialTrackIndex; trackIndexForSpace <= finalTrackIndex; ++trackIndexForSpace) {
    525         GridTrack& track = (direction == ForColumns) ? columnTracks[trackIndexForSpace] : rowTracks[trackIndexForSpace];
     543        GridTrack& track = (direction == ForColumns) ? sizingData.columnTracks[trackIndexForSpace] : sizingData.rowTracks[trackIndexForSpace];
    526544        additionalBreadthSpace -= (track.*trackGetter)();
    527545    }
    528546
    529547    // FIXME: We should pass different values for |tracksForGrowthAboveMaxBreadth|.
    530     distributeSpaceToTracks(tracks, &tracks, trackGetter, trackGrowthFunction, additionalBreadthSpace);
     548    distributeSpaceToTracks(sizingData.filteredTracks, &sizingData.filteredTracks, trackGetter, trackGrowthFunction, sizingData, additionalBreadthSpace);
    531549}
    532550
     
    536554}
    537555
    538 void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<GridTrack*>* tracksForGrowthAboveMaxBreadth, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, LayoutUnit& availableLogicalSpace)
     556void RenderGrid::distributeSpaceToTracks(Vector<GridTrack*>& tracks, Vector<GridTrack*>* tracksForGrowthAboveMaxBreadth, AccumulatorGetter trackGetter, AccumulatorGrowFunction trackGrowthFunction, GridSizingData& sizingData, LayoutUnit& availableLogicalSpace)
    539557{
    540558    std::sort(tracks.begin(), tracks.end(), sortByGridTrackGrowthPotential);
    541559
    542560    size_t tracksSize = tracks.size();
    543     Vector<LayoutUnit> updatedTrackBreadths(tracksSize);
     561    sizingData.distributeTrackVector.resize(tracksSize);
    544562
    545563    for (size_t i = 0; i < tracksSize; ++i) {
     
    549567        LayoutUnit growthShare = std::max(LayoutUnit(), std::min(availableLogicalSpaceShare, track.m_maxBreadth - trackBreadth));
    550568        // We should never shrink any grid track or else we can't guarantee we abide by our min-sizing function.
    551         updatedTrackBreadths[i] = trackBreadth + growthShare;
     569        sizingData.distributeTrackVector[i] = trackBreadth + growthShare;
    552570        availableLogicalSpace -= growthShare;
    553571    }
     
    557575        for (size_t i = 0; i < tracksSize; ++i) {
    558576            LayoutUnit growthShare = availableLogicalSpace / (tracksSize - i);
    559             updatedTrackBreadths[i] += growthShare;
     577            sizingData.distributeTrackVector[i] += growthShare;
    560578            availableLogicalSpace -= growthShare;
    561579        }
     
    563581
    564582    for (size_t i = 0; i < tracksSize; ++i) {
    565         LayoutUnit growth = updatedTrackBreadths[i] - (tracks[i]->*trackGetter)();
     583        LayoutUnit growth = sizingData.distributeTrackVector[i] - (tracks[i]->*trackGetter)();
    566584        if (growth >= 0)
    567585            (tracks[i]->*trackGrowthFunction)(growth);
     
    761779    placeItemsOnGrid();
    762780
    763     Vector<GridTrack> columnTracks(gridColumnCount());
    764     Vector<GridTrack> rowTracks(gridRowCount());
    765     computedUsedBreadthOfGridTracks(ForColumns, columnTracks, rowTracks);
    766     ASSERT(tracksAreWiderThanMinTrackBreadth(ForColumns, columnTracks));
    767     computedUsedBreadthOfGridTracks(ForRows, columnTracks, rowTracks);
    768     ASSERT(tracksAreWiderThanMinTrackBreadth(ForRows, rowTracks));
     781    GridSizingData sizingData(gridColumnCount(), gridRowCount());
     782    computedUsedBreadthOfGridTracks(ForColumns, sizingData);
     783    ASSERT(tracksAreWiderThanMinTrackBreadth(ForColumns, sizingData.columnTracks));
     784    computedUsedBreadthOfGridTracks(ForRows, sizingData);
     785    ASSERT(tracksAreWiderThanMinTrackBreadth(ForRows, sizingData.rowTracks));
    769786
    770787    for (RenderBox* child = firstChildBox(); child; child = child->nextSiblingBox()) {
    771         LayoutPoint childPosition = findChildLogicalPosition(child, columnTracks, rowTracks);
     788        LayoutPoint childPosition = findChildLogicalPosition(child, sizingData);
    772789
    773790        // Because the grid area cannot be styled, we don't need to adjust
     
    778795        // FIXME: For children in a content sized track, we clear the overrideContainingBlockContentLogicalHeight
    779796        // in minContentForChild / maxContentForChild which means that we will always relayout the child.
    780         LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, columnTracks);
    781         LayoutUnit overrideContainingBlockContentLogicalHeight = gridAreaBreadthForChild(child, ForRows, rowTracks);
     797        LayoutUnit overrideContainingBlockContentLogicalWidth = gridAreaBreadthForChild(child, ForColumns, sizingData.columnTracks);
     798        LayoutUnit overrideContainingBlockContentLogicalHeight = gridAreaBreadthForChild(child, ForRows, sizingData.rowTracks);
    782799        if (oldOverrideContainingBlockContentLogicalWidth != overrideContainingBlockContentLogicalWidth || (oldOverrideContainingBlockContentLogicalHeight != overrideContainingBlockContentLogicalHeight && (child->hasRelativeLogicalHeight() || child->hasViewportPercentageLogicalHeight())))
    783800            child->setNeedsLayout(MarkOnlyThis);
     
    803820    }
    804821
    805     for (size_t i = 0; i < rowTracks.size(); ++i)
    806         setLogicalHeight(logicalHeight() + rowTracks[i].m_usedBreadth);
     822    for (size_t i = 0; i < sizingData.rowTracks.size(); ++i)
     823        setLogicalHeight(logicalHeight() + sizingData.rowTracks[i].m_usedBreadth);
    807824
    808825    // FIXME: We should handle min / max logical height.
     
    10341051}
    10351052
    1036 LayoutPoint RenderGrid::findChildLogicalPosition(RenderBox* child, const Vector<GridTrack>& columnTracks, const Vector<GridTrack>& rowTracks)
     1053LayoutPoint RenderGrid::findChildLogicalPosition(RenderBox* child, const GridSizingData& sizingData)
    10371054{
    10381055    const GridCoordinate& coordinate = cachedGridCoordinate(child);
     
    10411058    LayoutPoint offset(borderAndPaddingStart(), borderAndPaddingBefore());
    10421059    // FIXME: |columnTrack| and |rowTrack| should be smaller than our column / row count.
    1043     for (size_t i = 0; i < coordinate.columns.initialPositionIndex && i < columnTracks.size(); ++i)
    1044         offset.setX(offset.x() + columnTracks[i].m_usedBreadth);
    1045     for (size_t i = 0; i < coordinate.rows.initialPositionIndex && i < rowTracks.size(); ++i)
    1046         offset.setY(offset.y() + rowTracks[i].m_usedBreadth);
     1060    for (size_t i = 0; i < coordinate.columns.initialPositionIndex && i < sizingData.columnTracks.size(); ++i)
     1061        offset.setX(offset.x() + sizingData.columnTracks[i].m_usedBreadth);
     1062    for (size_t i = 0; i < coordinate.rows.initialPositionIndex && i < sizingData.rowTracks.size(); ++i)
     1063        offset.setY(offset.y() + sizingData.rowTracks[i].m_usedBreadth);
    10471064
    10481065    // FIXME: Handle margins on the grid item.
  • trunk/Source/WebCore/rendering/RenderGrid.h

    r159684 r159741  
    6565
    6666    class GridIterator;
     67    class GridSizingData;
    6768    enum TrackSizingDirection { ForColumns, ForRows };
    68     void computedUsedBreadthOfGridTracks(TrackSizingDirection, Vector<GridTrack>& columnTracks, Vector<GridTrack>& rowTracks);
     69    void computedUsedBreadthOfGridTracks(TrackSizingDirection, GridSizingData&);
    6970    LayoutUnit computeUsedBreadthOfMinLength(TrackSizingDirection, const GridLength&) const;
    7071    LayoutUnit computeUsedBreadthOfMaxLength(TrackSizingDirection, const GridLength&, LayoutUnit usedBreadth) const;
    7172    LayoutUnit computeUsedBreadthOfSpecifiedLength(TrackSizingDirection, const Length&) const;
    72     void resolveContentBasedTrackSizingFunctions(TrackSizingDirection, Vector<GridTrack>& columnTracks, Vector<GridTrack>& rowTracks, Vector<size_t>& contentSizedTracks);
     73    void resolveContentBasedTrackSizingFunctions(TrackSizingDirection, GridSizingData&);
    7374
    7475    void growGrid(TrackSizingDirection);
     
    9091    typedef void (GridTrack::* AccumulatorGrowFunction)(LayoutUnit);
    9192    typedef bool (GridTrackSize::* FilterFunction)() const;
    92     void resolveContentBasedTrackSizingFunctionsForItems(TrackSizingDirection, Vector<GridTrack>& columnTracks, Vector<GridTrack>& rowTracks, RenderBox*, FilterFunction, SizingFunction, AccumulatorGetter, AccumulatorGrowFunction);
    93     void distributeSpaceToTracks(Vector<GridTrack*>&, Vector<GridTrack*>* tracksForGrowthAboveMaxBreadth, AccumulatorGetter, AccumulatorGrowFunction, LayoutUnit& availableLogicalSpace);
     93    void resolveContentBasedTrackSizingFunctionsForItems(TrackSizingDirection, GridSizingData&, RenderBox*, FilterFunction, SizingFunction, AccumulatorGetter, AccumulatorGrowFunction);
     94    void distributeSpaceToTracks(Vector<GridTrack*>&, Vector<GridTrack*>* tracksForGrowthAboveMaxBreadth, AccumulatorGetter, AccumulatorGrowFunction, GridSizingData&, LayoutUnit& availableLogicalSpace);
    9495
    9596    double computeNormalizedFractionBreadth(Vector<GridTrack>&, TrackSizingDirection, LayoutUnit availableLogicalSpace) const;
     
    103104    LayoutUnit minContentForChild(RenderBox*, TrackSizingDirection, Vector<GridTrack>& columnTracks);
    104105    LayoutUnit maxContentForChild(RenderBox*, TrackSizingDirection, Vector<GridTrack>& columnTracks);
    105     LayoutPoint findChildLogicalPosition(RenderBox*, const Vector<GridTrack>& columnTracks, const Vector<GridTrack>& rowTracks);
     106    LayoutPoint findChildLogicalPosition(RenderBox*, const GridSizingData&);
    106107    GridCoordinate cachedGridCoordinate(const RenderBox*) const;
    107108
Note: See TracChangeset for help on using the changeset viewer.