1558926 - WR DisplayList interning

Status: RESOLVED FIXED

(Core :: Graphics: WebRender, task, P3)

Description

[Aria Beingessner [:Gankra]]

As described in https://hackmd.io/3aWAtVFMR3q4mWjkxXibzg?view#DL-interning-API

It would be good for gecko to somehow register sections/items in the WR DL with some "interning id" so that in future DLs it can just push InternedItem(id) instead of recomputing/resending that part of the WR DL.

This would likely be integrated with existing gecko mechanisms like retained display lists and/or whatever FrameLayerBuilder is doing to avoid repainting based on display items not changing.

As a datapoint: ~75% of most display lists are just text display items and their glyphs. So interning those would potentially be a huge win. Especially since it's really expensive for webrender to hash those to see if it can apply picture caching.

Comment 1

[Aria Beingessner [:Gankra]]

This would also probably solve the issue we have with text selection getting really bogged down on text-node heavy pages.

Comment 2

[Aria Beingessner [:Gankra]]

My gut reaction for how this should be designed for webrender_api would just be adding these 3 new display items:

SetInterning(u64),
ClearInterning,
InternedDisplayItem(u64),

(I don't think we want to support nesting here, hence Set/Clear instead of Push/Pop)

The reason for having a scoped construct is because Gecko display items often lower to multiple Webrender display items, and it would be very nice/convenient for Gecko items to just store a single ID. I doubt that having more fine-grained invalidation would be super useful...?

Alternatively we can/should just hardcode this for TextDisplayItem and/or its glyphs array, because those are the nastiest things..?

Comment 3

[Aria Beingessner [:Gankra]]

One possible motivation for restricting interning to TextDisplayItem/Glyphs is so that something like "the text is the same but color/shadows are being animated" can take advantage of interning.

Alternatively this could be a compelling usecase for nested interning, so that we could intern "the whole item" as well as just "the glyphs". And so if nothing changes we can keep sending "the whole item" but if it does change we can send a new item with interned "the glyphs".

However such a nested scheme raises issues about interning lifetimes. I had imagined interns would just be discarded if a display list was sent without using that intern. In such a nested scheme we would want to occasionally "revive" the nested intern, which otherwise wasn't being used? Although perhaps a parent intern can keep all of its children alive..? Otherwise we need a way for gecko to say "hey this is REALLY expired, throw it away".

Comment 4

[Glenn Watson [:gw]]

The other item which (probably?) would benefit most from interning after text runs are clip chains / items.

Comment 5

[Aria Beingessner [:Gankra]]

Miko was very excited to work on this as their first webrender project, and they know gecko retaining well so it makes sense to me.

We discussed this this afternoon, and sketched out some reasonable details that can be tweaked/expanded incrementally. The barebones impl is vaguely shaped like:

// In gecko
nsDisplayText::CreateWebRenderCommands:
    if !(this->WasRetained())
        builder.PushInternedItem(this->GetProperty(WRInterningId));
    else:
        let id = GetNewId();
        builder.SetInterningId(id);

        // normal builder code
        
        builder.ClearInterningId();
        this->SetProperty(WRInterningId, id);


// In WR backend
flatten_items:
    match item {
      ...
      // Note clip_id and spatial_id were added by the builder
      // as we need to inject these into the interned repr
      InternedItem(id, clip_id, spatial_id) => {
        self.add_interned_items_with_clip_and_scroll(id, clip_id, spatial_id);
      }
      
      SetInterningId(id) => {
        self.interner = self.create_interner_with_id(id);
      }
      
      ClearInterningId => {
        self.add_interned_items(id);
        self.interner = None;
      }

      // Example sketch of how each item is handled...
      Text(..) => {
          // some code that computes the processed text item
          let text = ...;
          if let Some(interner) = self.interner.as_mut() {
            interner.add(text);
          }
    }

Comment 6

[Aria Beingessner [:Gankra]]

Attachment: interning-talk.jpg

picture of whiteboard from discussion

Comment 7

[Aria Beingessner [:Gankra]]

It was noted that currently gecko display list retaining is very fragile. For instance all items are invalidated when scrolling because their positions change.

The webrender backend picture caching/interning code is more robust, in that it hashes each display item, and also relativizes coordinates, so that it works under scrolling.

It is desirable to move this logic into the gecko side so we don't have to send items over just to be hashed. But it would also be desirable to not even hash when we know nothing has changed. We can incrementally develop a more robust system with the design I outlined.

Comment 8

[Miko Mynttinen]

Attachment: 1558926.diff

Current WIP patch. At the moment this approach seems a bit tricky due to filter/glyph/clip data that is stored in slices in WR DL.

Comment 9

[Miko Mynttinen]

Attachment: wr-dl-interning-140819.patch

Attached is the new WIP version of WebRender DL deltas.

The current implementation works as follows:
When a WebRender display list is built from a Gecko display list, the WR display items that are built for reusable Gecko display items are surrounded by DisplayItem::StartItem(key) and DisplayItem::EndItem markers. The key for DisplayItem::StartItem is a unique identifier that is used to cache the WR display items, per pipeline and per document.
On successive partial Gecko display list builds, before the WR display items for a reused Gecko display item would be built, WebRenderCommandBuilder checks if the WR display items for this Gecko display item have already been sent to WR backend. If so, the WR display items will not be built, and will instead be replaced with DisplayItem::InternedItem(key) marker. This avoids the cost of building WR display items, and should make it possible to send less data to WR backend. During WR display list flattening InternedItem markers will be replaced with the previously cached deserialized WR display items. This saves the cost of deserializing the display list data for more complicated display items.

Because of how Gecko and WR display list building works, there are some limitations and issues:

• Display items can only be reused for successive partial display list builds. This means that whenever Gecko performs a full display list build, the cached display items need to be cleared from the WR backend. This is signaled by a new partial_update flag in BuiltDisplayListDescriptor.
• Because WebRender sometimes processes display lists multiple times (first child pipeline display list, then root pipeline display list, and then child pipeline display list again), the cached display items are stored per pipeline, and the caches are only populated once.
• Clip ids can change, so the InternedItem marker needs to handle this somehow.
• WebRenderCommandBuilder needs to always create the same WR display items for the same Gecko display item. They cannot rely on external state, other than clip and space. It is unclear if this is currently the case.
• Some display list data is sent as slices (glyphs, filters) which need special handling.

Current problems:
This patch is buggy and slow. The changing clip ids are not handled and will cause a crash. Some things are copied unnecessarily.
Implementing this change has turned out to be difficult due to the fact that the display list iteration code and serialization/deserialization is a bit complicated and already quite optimized.

• I am particularly unhappy about how this patch handles the cached items in DisplayListFlattener. Before the serialization was changed in bug 1550640, I had written a patch that performed this in BuiltDisplayListIter instead. The tricky part with this approach is dealing with the immutability assumptions, recursion during display list iteration, and sub iterators.
• The current StartItem/EndItem approach seems slow and bloated, a better solution would be to have a special "header" display item that includes the unique key, and information on how many items following should be cached under that key. This could be done by building WR display items to a temporary storage in WR DisplayListBuilder, then appending the header item to actual display item storage, along with the previously serialized display items.
• The cache keys are currently VERY large (12 bytes, 64 bit pointer + 32 bit uint) because these are what Gecko uses. They can be replaced with simple integers that are mapped to Gecko display item keys in WebRenderCommandBuilder.

Comment 10

[Miko Mynttinen]

Attachment: wr-dl-deltas-191016.patch

Comment 11

[Miko Mynttinen]

Attachment: Bug 1558926 - Part 1: Add data structures and pref for display item caching r=kvark

Comment 12

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

There are some r+ patches which didn't land and no activity in this bug for 2 weeks.
:miko, could you have a look please?
For more information, please visit auto_nag documentation.

Comment 13

[Miko Mynttinen]

Attachment: Bug 1558926 - Part 2: Use DisplayItemCache in WebRenderCommandBuilder r=kvark

Depends on D50221

Comment 14

[Miko Mynttinen]

Attachment: Bug 1558926 - Part 3: Add support for additional WebRender display list data r=kvark

Depends on D60756

Comment 15

[Miko Mynttinen]

Attachment: Bug 1558926 - Part 4: Avoid display list updates for removed pipelines r=kvark

Depends on D60759

Comment 16

[Miko Mynttinen]

Attachment: Bug 1558926 - Part 5: Store a reference to cached display item data in DisplayItemRef r=kvark

Depends on D60760

Comment 17

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/a4d9a1af297a
Part 1: Add data structures and pref for display item caching r=kvark
https://hg.mozilla.org/integration/autoland/rev/30481c41873a
Part 2: Use DisplayItemCache in WebRenderCommandBuilder
https://hg.mozilla.org/integration/autoland/rev/92b415dac733
Part 3: Add support for additional WebRender display list data
https://hg.mozilla.org/integration/autoland/rev/1865e6d29dcf
Part 4: Avoid display list updates for removed pipelines
https://hg.mozilla.org/integration/autoland/rev/974bcab6b1bf
Part 5: Store a reference to cached display item data in DisplayItemRef

Comment 18

[Cristian Brindusan [:cbrindusan]]

Backed out 5 changesets (bug 1558926) for WebRender build bustages.
https://hg.mozilla.org/integration/autoland/rev/65b1787817bdd4addf847582f564a68afabdb932

Push with failures:
https://treeherder.mozilla.org/#/jobs?repo=autoland&resultStatus=pending%2Crunning%2Csuccess%2Ctestfailed%2Cbusted%2Cexception&revision=974bcab6b1bf3cea22595e23d06cd9457d302299&selectedJob=286394837

Failure log:
https://treeherder.mozilla.org/logviewer.html#?job_id=286394837&repo=autoland

Comment 19

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/8ac92137eff9
Part 1: Add data structures and pref for display item caching r=kvark
https://hg.mozilla.org/integration/autoland/rev/8c51225cdfa3
Part 2: Use DisplayItemCache in WebRenderCommandBuilder
https://hg.mozilla.org/integration/autoland/rev/8ef0c5a62e56
Part 3: Add support for additional WebRender display list data
https://hg.mozilla.org/integration/autoland/rev/96290c1e1a5f
Part 4: Avoid display list updates for removed pipelines
https://hg.mozilla.org/integration/autoland/rev/84e3a48f0843
Part 5: Store a reference to cached display item data in DisplayItemRef

Comment 20

[Andrei Ciure[:aciure]]

https://hg.mozilla.org/mozilla-central/rev/8ac92137eff9
https://hg.mozilla.org/mozilla-central/rev/8c51225cdfa3
https://hg.mozilla.org/mozilla-central/rev/8ef0c5a62e56
https://hg.mozilla.org/mozilla-central/rev/96290c1e1a5f
https://hg.mozilla.org/mozilla-central/rev/84e3a48f0843