The merge algorithm is currently: For-each item i in the new list: If the item has a matching item in the old list: Remove items from the start of the old list up until we reach an item that also exists in the new list (leaving the matched item in place): Add valid items to the merged list, destroy invalid items. Add i into the merged list. If the start of the old list matches i, remove and destroy it, otherwise mark the old version of i as used. Add all remaining valid items from the old list into the merged list, skipping over (and destroying) any that are marked as used. We also know that items that exist only in one list must not have a defined ordering relative to each other (see comment at top of RetainedDisplayListBuilder.cpp). The inner loop of the algorithm adds all items that exist only in the old list, and we only run that inner loop if the new item is in the old list. We then add the new item. In the case where the new item isn't in the old list (and we'd normally skip the inner loop), the ordering between it and all the old list items the inner loop would would add is undefined, so it should be ok to run the inner loop and put them first. Making that change gives us this algorithm: For-each item i in the new list: Remove items from the start of the old list up until we reach an item that also exists in the new list (leaving the matched item in place): Add valid items to the merged list, destroy invalid items. Add i into the merged list. If the start of the old list matches i, remove and destroy it, otherwise mark the old version of i as used. Add all remaining valid items from the old list into the merged list, skipping over (and destroying) any that are marked as used. This no longer has any cases where we need to check if an item exists in the old list, so we can stop building that hashtable.

Comment on attachment 8952607 [details] Bug 1439809 - Store the display list index on the display items during PreProcessDisplayList so that we can do lookup without a hashtable. https://reviewboard.mozilla.org/r/221844/#review228686 I went through the examples in the comment above the function, and they seem to work as expected. It might be out of scope of this bug, but I think that this function is a bit fragile, and I would really like to see automated tests for all these cases (with and without children). That way we could avoid subtle bugs that we have been experiencing almost every time this function has been touched. ::: layout/painting/RetainedDisplayListBuilder.cpp:474 (Diff revision 1) > + // pointer but has the same key. If we do find one there, then we need to find out if it's > + // in this display list or another one, which the hashtable solves. > + // We could lazily initialize the hashtable until we get to a case that actually needs it. > + modified = true; > + if (newMatch->IsMerged()) { > + // TODO: Come up with a testcase that exercises this new codepath This issue is a reminder to add a testcase. Could you please also add a comment when this path is taken? ::: layout/painting/nsDisplayList.h:2808 (Diff revision 1) > + return mMergedItem; > + } > + > + void SetMerged() > + { > + mMergedItem = true; I think we need to flip this back to false somewhere.

Comment on attachment 8952607 [details] Bug 1439809 - Store the display list index on the display items during PreProcessDisplayList so that we can do lookup without a hashtable. https://reviewboard.mozilla.org/r/221844/#review230044 Seems reasonable. I second Miko's request to add a test for the case that that comment calls out.

(In reply to Miko Mynttinen [:miko] from comment #2) > ::: layout/painting/nsDisplayList.h:2808 > (Diff revision 1) > > + return mMergedItem; > > + } > > + > > + void SetMerged() > > + { > > + mMergedItem = true; > > I think we need to flip this back to false somewhere. We only ever check for IsMerged() on items from the new list, where they should have been initialized to false.

Pushed by mwoodrow@mozilla.com: https://hg.mozilla.org/integration/mozilla-inbound/rev/dd8af18e26d4 Change the display list merging algorithm to no longer require a hashtable of the old display list items. r=miko,mstange

Bad news: the new algorithm gets the wrong result in some cases. Here's a testcase. We should probably back this patch out for now. (I created this testcase when I tried to break Jeff's patch in bug 1388842 comment 43, then Jeff and I tried to see how our existing known-good algorithm deals with it, so we walked through it on a whiteboard and found out that it doesn't get it right.)

Hmm, the testcase is not very reliable. It shows the bug more often if I move the mouse during the "animation". Not sure why.

Here's a slightly different version that works with the current version of the merge algorithm, and fails when I back it out. In both cases step2 comes up with a display list that is valid, but not the order that would be created by doing a full build. The two algorithms differ in the order that they insert items when the head of both lists exist only in that list, so we need slightly different modifications to trigger the same intermediate list. From there step3 tries to use the valid-but-not-canonical list and gets the merge wrong, and this bug is consistent between algorithms. I think I understand how to fix this, but it looks like it breaks the opportunity to get rid of the hashtable :(

The possible fix is in bug 1443027

Backout by mwoodrow@mozilla.com: https://hg.mozilla.org/integration/mozilla-inbound/rev/508c318e3e8f Back out changeset dd8af18e26d4 for having incorrect merging behaviour and causing crashes. r=backout

The backout was also merged to m-c. https://hg.mozilla.org/mozilla-central/rev/508c318e3e8f

Comment on attachment 8969513 [details] Bug 1439809 - Store the display list index on the display items during PreProcessDisplayList so that we can do lookup without a hashtable. https://reviewboard.mozilla.org/r/238276/#review244484 ::: layout/painting/RetainedDisplayListBuilder.cpp:244 (Diff revision 1) > mItem->Destroy(aBuilder->Builder()); > mItem = nullptr; > } > > +bool > +OldItemInfo::IsChanged() { line break before { ::: layout/painting/RetainedDisplayListBuilder.cpp:249 (Diff revision 1) > +OldItemInfo::IsChanged() { > + return !mItem || mItem->HasDeletedFrame() || !mItem->CanBeReused(); > +} > + > /** > * A C++ implementation of Markus Stange's merge-dags algorthim. Could you fix the typo in algorithm while you're here? ::: layout/painting/nsDisplayList.h:2853 (Diff revision 1) > mozilla::DisplayItemData* GetDisplayItemData() { return mDisplayItemData; } > > + // Set the nsDisplayList that this item belongs to, and what > + // index it is within that list. Temporary state for merging > + // used by RetainedDisplayListBuilder. > + void SetMergeListIndex(nsDisplayList* aList, uint32_t aIndex) Hmm, would it be better to call it OldListIndex instead of MergeListIndex? You're calling it when you're doing the pre-pass over the old list, not when adding things into the merged list.

(In reply to Markus Stange [:mstange] from comment #17) > > ::: layout/painting/nsDisplayList.h:2853 > (Diff revision 1) > > mozilla::DisplayItemData* GetDisplayItemData() { return mDisplayItemData; } > > > > + // Set the nsDisplayList that this item belongs to, and what > > + // index it is within that list. Temporary state for merging > > + // used by RetainedDisplayListBuilder. > > + void SetMergeListIndex(nsDisplayList* aList, uint32_t aIndex) > > Hmm, would it be better to call it OldListIndex instead of MergeListIndex? > You're calling it when you're doing the pre-pass over the old list, not when > adding things into the merged list. The naming was mainly for people reading nsDisplayList.h to make it clear that it was specific to the merging code. I guess the comment should be sufficient though, so I'll change it.

Comment on attachment 8952607 [details] Bug 1439809 - Store the display list index on the display items during PreProcessDisplayList so that we can do lookup without a hashtable. https://reviewboard.mozilla.org/r/221844/#review244722

Comment on attachment 8970389 [details] Bug 1439809 - Add an index parameter to nsDisplayWrapList to prevent scrollbar frames from creating duplicates. https://reviewboard.mozilla.org/r/239162/#review244850

Pushed by mwoodrow@mozilla.com: https://hg.mozilla.org/integration/autoland/rev/5daa11905109 Add an index parameter to nsDisplayWrapList to prevent scrollbar frames from creating duplicates. r=mattwoodrow https://hg.mozilla.org/integration/autoland/rev/02904a082859 Store the display list index on the display items during PreProcessDisplayList so that we can do lookup without a hashtable. r=miko,mstange

https://hg.mozilla.org/mozilla-central/rev/5daa11905109 https://hg.mozilla.org/mozilla-central/rev/02904a082859

some perf wins: == Change summary for alert #12878 (as of Tue, 24 Apr 2018 05:06:20 GMT) == Improvements: 12% displaylist_mutate linux64 pgo e10s stylo 3,485.02 -> 3,069.82 10% displaylist_mutate linux64 opt e10s stylo 3,777.97 -> 3,386.92 10% displaylist_mutate windows10-64 pgo e10s stylo4,141.16 -> 3,735.60 9% displaylist_mutate windows7-32 pgo e10s stylo 4,738.19 -> 4,288.81 9% displaylist_mutate osx-10-10 opt e10s stylo 8,120.54 -> 7,395.99 9% displaylist_mutate osx-10-10 opt e10s stylo 8,177.29 -> 7,448.59 8% displaylist_mutate windows7-32 opt e10s stylo 6,164.16 -> 5,664.97 8% displaylist_mutate windows10-64 opt e10s stylo4,665.46 -> 4,306.19 6% displaylist_mutate windows10-64 opt e10s stylo4,310.93 -> 4,035.51 6% displaylist_mutate windows10-64 pgo e10s stylo3,708.77 -> 3,504.33 5% displaylist_mutate windows7-32 pgo e10s stylo 4,311.43 -> 4,100.26 3% displaylist_mutate linux64 pgo e10s stylo 3,063.73 -> 2,974.92 For up to date results, see: https://treeherder.mozilla.org/perf.html#/alerts?id=12878