1737889 - Generalize stacking context display list retaining code and reuse display items for leaf block frames

Status: NEW

(Core :: Web Painting, enhancement, P3)

Description

[Miko Mynttinen]

This optimization idea is motivated by the frame tree shape of displaylist_mutate benchmark and it is similar to the plan for bug 1697979.

Because display items for each frame of a block frame line can be built and placed in separate nsDisplayListCollection1, it should be possible to serialize the collection and reuse it during next paint, if the child frames have not been modified.

I implemented a prototype of this as part of bug 1697979 (with the limitation that frames have to be frame tree leaves) and it seemed to perform well.

The tricky bit is handling nested block frames, as in, where to store the previously built display items. TextOverflow clipping2 (which currently destroys display items) can be solved by making it hide display items instead of deleting them.

Comment 1

[Miko Mynttinen]

Attachment: Bug 1737889 - Part 2: Add DisplayItemData r=mstange

Comment 2

[Miko Mynttinen]

Attachment: Bug 1737889 - Part 3: Reuse previously built display items for stacking context frames and leaf block frames r=mstange

Depends on D137542

Comment 3

[Miko Mynttinen]

Determining the right lifetime for display items is giving me a major headache. Initially I had planned this to be "display items are deleted at the end of paint if they are unused". Because of display item deletions during display list building (see bug 1765638), this is not easy.

Consider a scenario where we have a block frame A with text overflow and a child stacking context frame B:

The display list could look like this:

nsDisplayContainer (frame A)
  nsDisplayOpacity (frame B)
      nsDisplayBorder

During stack unwinding:
When leaving frame B, we store the display list (= nsDisplayOpacity and its contents) in DisplayItemData for frame B.
When leaving frame A, we process the text overflow and destroy everything. This leaves destroyed items in DisplayItemData for frame B. Removing destroyed items from DisplayItemData would be difficult because they could have been created arbitrarily deep in this frame subtree, so it would require going through all retained data to ensure that there are no destroyed display items.

We can try to work around this by not destroying the display items and instead we simply do not add them to the resulting display list. Assume we do a paint with no modified frames and successfully reuse the display list (not including display items for frame subtree B since it was dropped). Now all the display items in DisplayItemData for B are unused, and will get destroyed at the end of paint despite no frame modifications or invalidations happening. We again have destroyed items in DisplayItemData.

Similar issues can happen in other places where we destroy display items during display list building: in full screen mode we build a display list for the whole frame tree below the top layer, and then delete everything except the top layer content.

In an attempt to fix this, I added reference counting for display items and extended their lifetime that way. Unfortunately it turns out that this creates a whole new set of problems, because we need to manage reference counts for whole display list subtrees (because display items might have children).

Comment 4

[Miko Mynttinen]

Here are some design notes for the patches attached to this bug.

Basic invariants for reusing display items

During display list building, if a frame

1. has no modified ancestors
2. has no modified descendants
3. is not modified
   then the display items from the previous paint can be reused.

Display items need to stay alive at least until the end of the NEXT paint, unless they are reused.
=> Reusing a display item extends its lifetime by at least one paint.

Frame modification status

• Modified frames are stored in RetainedDisplayListBuilder.
• Before doing a partial display list build, all the ancestor frames for all the modified frames are marked as having modified descendants.
• Determining modified ancestors can be done during display list building time: after encountering a modified frame, consider all child frames as having modified ancestors.
• Currently done before display list building with AnyContentAncestorModified() to avoid difficult to find bugs.

Reusing display items

1. Check the frame modification status.
2. If not modified => reuse the previous display items for that frame subtree.
3. Otherwise => rebuild the display items and retain them until the next paint.

• Note: The current ActiveScrolledRoot of nsDisplayListBuilder needs to be updated based on the reused display items.

Retaining display items

1. If a frame is a stacking context => Store the built nsDisplayList in DisplayItemData, usually this is just one display item.
2. If a frame is a leaf block frame => Store the built nsDisplaySet in DisplayItemData, this is usually 1-4 display items.

• Note: There are no limitation which frames can reuse and retain display items, these two cases were chosen because they are common and somewhat isolated.

DisplayItemData

• Has 1:1 relationship with nsIFrame.

• Replaces nsIFrame::mDisplayItems (SmallPointerArray which contains raw pointers to display items).

• Connected to a frame during display list building (= assign to nsIFrame::mDisplayItemData).

• Disconnected from a frame when the frame is deleted. This is tracked by DisplayItemData::mConnected.

• Owned by nsDisplayListBuilder, allocated and recycled using a free list.

• Owns the display items for that nsIFrame.

• Stores the retained nsDisplayList or nsDisplaySet for that frame subtree.

Comment 5

[Markus Stange [:mstange]]

Thank you, these last two comments are super helpful in understanding what's going on.

I'll try to rephrase to myself why reference counting makes sense here. I'd like to answer the question "Why can a display item have multiple owners, and who are those owners?"

The two owners are:

• the frame that wants to retain its own display items for the next paint, and
• the ancestor display items in the current paint.

A display item needs to survive as long as at least one of these owners needs it. For example, just because a frame doesn't want to retain its own items, we still need that frame's items to survive to the end of the current paint because they're embedded in the ancestor display list and will be painted in this paint. And as the converse example, if a display item does not end up getting used in the current paint by the display items of an ancestor frame (e.g. because it was culled by text-overflow), it still needs to survive if this frame wants to retain its contents for the next paint.

The part I'm still concerned about is the repeated addref of every item in a sub-displaylist for each of its ancestor items / ancestor frames. For example, if I have three nested stacking context frames A, B and C, and the stacking context C contains five child items i - v, then the current patches on this bug cause i - v to be addrefed individually for C, B, and A. Right?
Could we instead make display items own their child items? Then you only need to addref one item and effectively own / retain the entire subtree. So then frame A owns display item a, which owns display item b, which owns display item c, which owns display items i - v. So the only addrefs for items i - v would happen by the nsDisplayWrapList c, as these items are added to c. And then when c is added to b, only c is addrefed.

Comment 6

[Miko Mynttinen]

Empty transactions

WebRenderLayerManager supports empty transactions for situations where multiple paints are requested for the same unmodified frame tree, for example when animations need to be sampled (Bug 1440690, bug 1429932).
This is possible if there are no modified or deleted frames, which means that we can fully reuse the previous display list. Because of the way deleted frames are handled (described below), detecting this currently requires a full iteration over the display list and removal of all the display items that belong to a delete or modified frame. If no changes were made to the display list, we can perform an empty transaction. Otherwise we can still reuse the display list, but we need to do a full transaction.

Deleted and modified frames

Most of the data in display items is based on the corresponding nsIFrame (nsDisplayItem::mFrame) geometry and styles. If the geometry or style changes, the frame is marked modified and a pointer to the frame is added to RetainedDisplayListData (RetainedDisplayListBuilder::mData) in the display root frame (usually ViewportFrame). Currently the display item invalidation is binary: display items for deleted or modified frames should not be reused. We still do this (MergeState::ShouldUseNewItem())1 but it does not work well and probably causes bugs.

In some cases, the display item might depend on multiple frames for invalidation. If a dependent frame is modified or deleted, the invalidation status propagates to the primary frame of the display item. It is slightly odd that display items serve as invalidation links between frames. This should probably be simplified to something like ancestor/descendant based invalidation.

Deleted frames are handled slightly different than modified frames. When frames are deleted, they are not included in the (merging RDL) rebuild region calculations. We also do not track whether frame subtrees have deleted descendants. This adds some complexity, because every reused display item needs to be checked whether it belongs to a deleted frame. If it does, the display item should be removed from all retained data and container display items.

Comment 7

[Miko Mynttinen]

Attachment: Bug 1737889 - Part 1: Change the display item ownership model for non-retained paints r=mstange

Comment 8

[Miko Mynttinen]

The current reference counting implementation has a memory leak issue with the following testcase

<body>
  <div style="width: 100px; height: 100px; will-change: transform;">
    <div style="color: red;" id="changed">
	foo
    </div>
  </div>
  <script>
    function doTest() {
      const e = document.getElementById('changed');
      e.remove();
    }
    window.setTimeout(doTest, 5000);
  </script>

</body>

When div #changed is removed, the frames are destroyed:

[Child 433988: Main Thread]: V/dl.content Removing display item data for frame 7f0b2593bec8 (Text(0)"\n\tfoo\n    ")
[Child 433988: Main Thread]: V/dl.content Removing display item data for frame 7f0b2593bdf8 (Block(div id=changed)(-1))

All the display items belonging to these frames now have their nsIFrame pointer set to nullptr.

The display list building starts and DisplayItemData are invalidated

[Child 433988: Main Thread]: I/dl.content PaintFrame: 7f0b2593b020 (Viewport(-1)), DisplayRoot: 7f0b2593b020 (Viewport(-1)), Builder: 7f0b28e7c000, URI: file:///home/miko/Code/mu2/layout/reftests/display-list/reuse-sc-frame-deleted-1.html
[Child 433988: Main Thread]: I/dl.content nsDisplayListBuilder::BeginFrame()
[Child 433988: Main Thread]: I/dl.content (7f0b28e7c000) RDL - AttemptPartialUpdate, root frame: 7f0b2593b020
[Child 433988: Main Thread]: D/dl.content RDL - Modified frames: 0
[Child 433988: Main Thread]: D/dl.content RDL - Invalidating DisplayItemData
[Child 433988: Main Thread]: V/dl.content RDL - Invalidating DID 7f0b28e35698 (frame: 0): (deleted frame)
[Child 433988: Main Thread]: V/dl.content RDL - Destroying DisplayItemData 7f0b28e35698 (frame 0)
[Child 433988: Main Thread]: V/dl.content RDL - Retaining DID 7f0b28e35a20
[Child 433988: Main Thread]: V/dl.content RDL - Retaining DID 7f0b28e35da0

So far so good. DisplayItemData belonging to deleted frame is detected and destroyed. Since there are no modified frames, all the other retained data should be up to date and available for reuse.

Since there are no modified frames, this is where we should do an empty transaction. Because this is not implemented, we enter the first stacking context frame (Viewport) by calling BuildDisplayListForStackingContext():

[Child 433988: Main Thread]: I/dl.content RDL - Starting partial display list build
[Child 433988: Main Thread]: V/dl.content BuildDisplayListForStackingContext (7f0b2593b020) <
[Child 433988: Main Thread]: D/dl.content RDL - Reusing list data 7f0b28e35da0 for frame 7f0b2593b020

RDL determines that the previous nsDisplayList for the frame can be reused.

Because frames do not track deleted descendent frame status, a preprocessing step is needed:

[Child 433988: Main Thread]: I/dl.content RDL - Starting partial display list build
[Child 433988: Main Thread]: V/dl.content BuildDisplayListForStackingContext (7f0b2593b020) <
[Child 433988: Main Thread]: D/dl.content RDL - Reusing list data 7f0b28e35da0 for frame 7f0b2593b020
[Child 433988: Main Thread]: D/dl.content  Processing item 7f0b28e35020 (CompositorHitTestInfo) (frame: 7f0b2593b1b8) (children: 0) (depth: 0)
[Child 433988: Main Thread]: D/dl.content RDL - Reusing display item 7f0b28e35020 (CompositorHitTestInfo) (frame: 7f0b2593b1b8)
[Child 433988: Main Thread]: D/dl.content  Processing item 7f0b28e35bd8 (AsyncZoom) (frame: 7f0b2593b1b8) (children: 5) (depth: 0)
[Child 433988: Main Thread]: D/dl.content   Processing item 7f0b28e350d8 (CompositorHitTestInfo) (frame: 7f0b2593b0d0) (children: 0) (depth: 1)
[Child 433988: Main Thread]: D/dl.content RDL - Reusing display item 7f0b28e350d8 (CompositorHitTestInfo) (frame: 7f0b2593b0d0)
[Child 433988: Main Thread]: D/dl.content   Processing item 7f0b28e351d8 (CanvasBackgroundColor) (frame: 7f0b2593b0d0) (children: 0) (depth: 1)
[Child 433988: Main Thread]: D/dl.content RDL - Reusing display item 7f0b28e351d8 (CanvasBackgroundColor) (frame: 7f0b2593b0d0)
[Child 433988: Main Thread]: D/dl.content   Processing item 7f0b28e352d8 (CompositorHitTestInfo) (frame: 7f0b2593bb38) (children: 0) (depth: 1)
[Child 433988: Main Thread]: D/dl.content RDL - Reusing display item 7f0b28e352d8 (CompositorHitTestInfo) (frame: 7f0b2593bb38)
[Child 433988: Main Thread]: D/dl.content   Processing item 7f0b28e35390 (CompositorHitTestInfo) (frame: 7f0b2593bc08) (children: 0) (depth: 1)
[Child 433988: Main Thread]: D/dl.content RDL - Reusing display item 7f0b28e35390 (CompositorHitTestInfo) (frame: 7f0b2593bc08)
[Child 433988: Main Thread]: D/dl.content   Processing item 7f0b28e35850 (nsDisplayTransform) (frame: 7f0b2593bd28) (children: 3) (depth: 1)
[Child 433988: Main Thread]: D/dl.content    Processing item 7f0b28e35448 (CompositorHitTestInfo) (frame: 7f0b2593bd28) (children: 0) (depth: 2)
[Child 433988: Main Thread]: D/dl.content RDL - Reusing display item 7f0b28e35448 (CompositorHitTestInfo) (frame: 7f0b2593bd28)
[Child 433988: Main Thread]: D/dl.content    Processing item 7f0b28e35500 (CompositorHitTestInfo) (frame: 0) (children: 0) (depth: 2)
[Child 433988: Main Thread]: D/dl.content    Discarding item 7f0b28e35500 (deleted frame)
[Child 433988: Main Thread]: D/dl.content    Processing item 7f0b28e355b8 (Text) (frame: 0) (children: 0) (depth: 2)
[Child 433988: Main Thread]: D/dl.content    Discarding item 7f0b28e355b8 (deleted frame)
[Child 433988: Main Thread]: D/dl.content RDL - Reusing display item 7f0b28e35850 (nsDisplayTransform) (frame: 7f0b2593bd28)
[Child 433988: Main Thread]: D/dl.content RDL - Reusing display item 7f0b28e35bd8 (AsyncZoom) (frame: 7f0b2593b1b8)
[Child 433988: Main Thread]: V/dl.content > BuildDisplayListForStackingContext (7f0b2593b020)
[Child 433988: Main Thread]: I/dl.content RDL - Finished partial display list build

The preprocessing decrements the reference count for two display items belonging to two deleted frames. They are also removed from the display list owned by nsDisplayTransform.

[Child 433988: Main Thread]: V/dl.content Created display item 7f0b28e35f58 (SolidColor) (frame: 7f0b2593b020)
[Child 433988: Main Thread]: D/dl.content Clearing invalidation state bits
[Child 433988: Main Thread]: V/dl.content Retaining display item 7f0b28e35020 (CompositorHitTestInfo) (f: 7f0b2593b1b8), ref count: 1
[Child 433988: Main Thread]: V/dl.content Retaining display item 7f0b28e350d8 (CompositorHitTestInfo) (f: 7f0b2593b0d0), ref count: 1
[Child 433988: Main Thread]: V/dl.content Retaining display item 7f0b28e351d8 (CanvasBackgroundColor) (f: 7f0b2593b0d0), ref count: 1
[Child 433988: Main Thread]: V/dl.content Retaining display item 7f0b28e352d8 (CompositorHitTestInfo) (f: 7f0b2593bb38), ref count: 1
[Child 433988: Main Thread]: V/dl.content Retaining display item 7f0b28e35390 (CompositorHitTestInfo) (f: 7f0b2593bc08), ref count: 1
[Child 433988: Main Thread]: V/dl.content Retaining display item 7f0b28e35448 (CompositorHitTestInfo) (f: 7f0b2593bd28), ref count: 2
[Child 433988: Main Thread]: V/dl.content Retaining display item 7f0b28e35500 (CompositorHitTestInfo) (f: 0), ref count: 1
[Child 433988: Main Thread]: V/dl.content Retaining display item 7f0b28e355b8 (Text) (f: 0), ref count: 1
[Child 433988: Main Thread]: V/dl.content Retaining display item 7f0b28e35850 (nsDisplayTransform) (f: 7f0b2593bd28), ref count: 2
[Child 433988: Main Thread]: V/dl.content Retaining display item 7f0b28e35bd8 (AsyncZoom) (f: 7f0b2593b1b8), ref count: 1
[Child 433988: Main Thread]: V/dl.content Destroying display item 7f0b28e36030 (SolidColor)
[Child 433988: Main Thread]: V/dl.content Retaining display item 7f0b28e35f58 (SolidColor) (f: 7f0b2593b020), ref count: 0
[Child 433988: Main Thread]: I/dl.content nsDisplayListBuilder::EndFrame()

During a call to nsDisplayListBuilder::FreeDisplayItems(), both removed nsDisplayText and nsDisplayCompositorHitTestInfo items have a reference count of one and they are retained. This is because they originally had a reference count of two, due to nested stacking contexts (viewport and transform).
The bug is that they no longer belong to any DisplayItemData, so they are just leaking memory until a full display list build is performed (and all the retained data is cleared).

Comment 9

[Miko Mynttinen]

When to retain and reuse display items

Currently these patches retain and reuse display items in two places: at the beginning and end of

1. nsIFrame::BuildDisplayListForStackingContext()
2. nsBlockFrame::BuildDisplayList().

This is simple but not optimal. Both of these functions are usually called by nsIFrame::BuildDisplayListForChild() which is one of the costliest functions called during display list building. This would make the beginning of that function a better place to reuse display items.

I quickly tried this out and it resulted in around 25% improvement in the vanilla display list mutate test (which brings it to parity with the merging RDL).

Comment 10

[BugBot [:suhaib / :marco/ :calixte]]

The following patch is waiting for review from an inactive reviewer:

ID	Title	Author	Reviewer Status
D143397	Bug 1737889 - Part 3: Reuse previously built display items for stacking context frames and leaf block frames r=mstange	mikokm	mstange: Resigned from review

:mikokm, could you please find another reviewer?

For more information, please visit auto_nag documentation.

Comment 11

[Timothy Nikkel (:tnikkel)]

Bad bot, that doesn't seem to make any sense.