Profile in the middle of it: https://share.firefox.dev/3Ias7az
And at the end of it: https://share.firefox.dev/3yhM7TW

The content process only contained a 4MB plain text log file, on which I was using the find bar, and pressing Cmd+G / Cmd+shift+G repetitively to go quickly through find results.

The profile looks like the time is spent entirely in nsRange::Release, so I think that's more of a DOM issue. Maybe there's some quadratic behavior when many ranges are being destroyed at once?

The profiler's inline code view points to all the time being spent on this line: https://searchfox.org/mozilla-central/rev/3e1a721bce1da3ae04675539b39a4e95b25a046d/dom/base/nsRange.cpp#178

That's a macro that expands to more code; Markus, is there any way to know on which line(s) of actual code the time was spent?

Here's the profile with inline frames included: https://share.firefox.dev/3uuVa2N
(Unfortunately now the file paths are of the /builds/worker/... form so the profiler's source view doesn't work)

We can see that the time is actually spent inside nsINode::RemoveMutationObserver, specifically in nsTArray::RemoveElements.

I'm currently working on bug 1636194 which will give us this information in profiles from official builds by default.

Bug 1636194 is not needed to fix this layout bug, the profile in the previous comment contains all the necessary information.

It seems that the cost of removing from the array of mutation observer is required.

If somebody (e.g., Selection) different from the root node (typically Document) manage mutations for a group of ranges, the cost of removing from the array could be saved because of reducing the size of array. However, according to comment 0, most ranges must be the highlight ranges of the findbar. Therefore, even if we took the approach, new range in Selection for highliter could be too big. This means that once we implement the Highlight API, this performance issue could appear in specific web apps.

On the other hand, I don't understand why the ranges are not released immediately and cleaned up by the cycle collector.

From the profile, it looks like the last release is happening inside the deferred finalizer, which I think means that the nsRanges were being held alive by their respective JS reflectors, so they are going to be released in a big batch after we GC the reflectors. The find in page code is written in JS I believe so it makes sense they all get exposed there.

We should consider storing nsIMutationObservers as a linked list. That would make all the insertions and removals O(1) yet keep the ordering.
That should not be too hard even. Just make nsIMutationObserver extend LinkedListElement. Might be worth to hide that inheritance from the implementations of nsIMutationObserver though.

Attached reproducible testcase.

Reproducible testcase attached.

For the upcoming change of how nsIMutationObservers are stored inside of nsINodes it is necessary to make sure that an observer is only associated with one Node.
To acomplish this, a pseudo mutation observer is introduced that forwards all calls to and is owned by the actual observer.
The observer is then bound to the parent node, the NAC wrapper to the new NAC element.

Removal of elements in nsAutoTObserverArray was O(n^2), therefore leading to serious hang in case there are many nsRange objects
(each removal called IndexOf() which took a O(n) lookup).

Solves this by switching from nsAutoTObserverArray to plain AutoTArray.
Instead of removing elements while iterating, set elements to nullptr. This is made possible by the nsIMutationObserver instance keeping track of its own index inside of the node's mutation observer array, reducing the cost of removal to array[index] = nullptr;.
After finished operation, the observer list is cleaned up by removing all nullptr elements and adjusting the index property.

Depends on D155776

This is still a work in progress.

Depends on D155776

Replaced the nsAutoTObserverArray with a SafeDoublyLinkedList which reduces object deletion from O(n^2) to O(n).

Depends on D156487

Depends on D156488

Deletion of mutation observers from a list resulted in O(n^2) behavior and could lead to massive freezes.
This is resolved by using a LinkedList instead, reducing complexity to O(n).

A safely iterable doubly linked list was implemented based on mozilla::DoublyLinkedList,
allowing to insert and remove elements while iterating the list.

Due to the nature of mozilla::DoublyLinkedList, every Mutation Observer now inherits mozilla::DoublyLinkedListElement<T>.
This implies that a Mutation Observer can only be part of one DoublyLinkedList.
This conflicts with some Mutation Observers, which are being added to multiple nsINodes.
To continue supporting this, new MutationObserver base classes nsMultiMutationObserver and nsStubMultiMutationObserver are introduced,
which create MutationObserverWrapper objects each time they are added to a nsINode.
The wrapper objects forward every call to the actual observer.

https://hg.mozilla.org/mozilla-central/rev/67db0fafa463