1867249 - View Source is slow on specific markdown page on Github

Status: RESOLVED FIXED

(Core :: DOM: Selection, defect)

Description

This issue is extracted from Bug 1866161 comment 1 and still persists after landing the fix for the mentioned bug.

STR:

• Go to This markdown page
• Select one of the code markup boxes
• Right-Click and hit "view source for selection"

Loading the source takes several minutes. Here's a current profile (from today's Nightly, after landing bug 1866161). Time is spent in layout reflow, which calls into Selection code (therefore I'm putting this into DOM::Selection instead of Layout).

FWIW, once the view-source page is open, scrolling horizontally is also pretty laggy.

(Again, asking :smaug for opinion what would be good steps to make this faster)

Comment 1

[Olli Pettay [:smaug][[e-mail]]]

There are some other older bugs about selection being slow, at least https://bugzilla.mozilla.org/show_bug.cgi?id=1518052
The profile hints that we should cache in nsIFrame whether it is selected.
And some kind of caching for nsFrameSelection::LookUpSelection too, or perhaps some caching should happen on the caller side.

Comment 2

[Jan Jaeschke [:jjaschke]]

After some offline discussion with :smaug, there are a few thoughts:

Problem description:

Each frame needs to determine if it is selected or not. This calls into nsINode::IsSelected(), which does a lot of point comparisons in here (each node is compared against range start and range end if I understand correctly). During that, the index of the node has to be determined, which is expensive.

Potential approaches

Approach 1: Move "isSelected" information to a global-ish hashmap

Add a Hashmap which contains nsINode* as key and enum IsSelected {Partially, Fully} as value and which lives somewhere "global" (Document, Selection,.. something like that).
Each time selection changes, all nodes that are added to the selection are added to the map, all nodes that are removed from the selection are removed from the map.
During reflow, each Frame only has to do one hashmap lookup to determine if its node is selected or not.

Pros:

• Reflow will likely be pretty fast.

Cons:

• Updating the Selection will be more expensive because of insertion/removal of all nodes that are now part of or not part of the selection, which translates to a traversal of the (sub) DOM Tree. Worst case would be CTRL-A that would have to traverse the whole document.

Approach 2: Reduce calls to nsINode::ComputeIndexOf() by checking the node's parent's IsSelected state

Currently, each node is compared to the start/end point of the range to determine if it is selected. This includes computing the node's index in its parent. Computing the index is an O(n) operation as nodes are stored as linked list.
However, this may not be necessary in all cases. If we can determine that the node's parent node is selected and parent's previous and next siblings are also selected (by the same range), we know that the node has to be selected as well. This should save a lot of work. Additionally, this could be combined with a local cache that persists only for the current reflow (maybe longer?), in which the information is stored if a node is selected partially or completely (as in approach 1). This should again save index computation.
If a (direct) parent is only partially selected, more detailed computation needs to take place (i.e. computing indices).

Pros:

• Fewer expensive computations necessary to determine if a node is in a range
• No additional overhead when updating selection
• Fewer changes to the code, no introduction of a fundamentally new mechanism

Cons:

• Potential overhead from building the cache (I assume that's negligible)
• Reflow will likely be not as fast as approach 1

With current state of information, approach 2 seems more sensible.

Comment 3

[Emilio Cobos Álvarez (:emilio)]

The only reason "view selection source" is slow while selecting is not slow on the page is presumably that the markdown box basically is a span for each code token, with a class, so <span class="pl-c1">54</span> for example. And that as I understand becomes as follows in view-source:

<span>&lt;<span class="start-tag">span</span> <span class="attribute-name">class</span>="<a class="attribute-value">pl-c1</a>"&gt;</span><span>54</span><span>&lt;/<span class="end-tag">span</span>&gt;</span>

So this is kind of a worst case scenario where the dom basically becomes one order of magnitude more complex than it was.

At a glance tho, it seems approach 2 could work, but I'd note that IsSelected is only half of the time in the profile. The other time is LookupSelectionDetails, which is also similarly expensive (ComparePoints taking most of the time there).

I'd note that this code doesn't use the pre-existing aParent1Cache argument to ComparePoints, and it seems in this case that could be a big win?

Comment 4

[Jan Jaeschke [:jjaschke]]

Attachment: WIP: Bug 1867249, part 1: Implemented new cache to determine selected nodes.

Comment 5

[Jan Jaeschke [:jjaschke]]

Attachment: Bug 1867249, part 0: Replaced hash set with array for performance reasons. r=sefeng!,#dom-core

In the given code, all selections of all common inclusive ancestors are collected.
Typically, this will be only one.
In this case, looking up if a Selection pointer is already in the array boils down to one pointer comparison, which is much faster than inserting the pointer into the hashtable.
Since this is very hot code, changing the hashtable to an array already has a relatively significant influence.

Comment 6

[Jan Jaeschke [:jjaschke]]

Attachment: WIP: Bug 1867249, part 2: Integrate `RangeNodeCache` also into painting.

Comment 7

[Jan Jaeschke [:jjaschke]]

It seems that the same issue as described above can encounter with text fragments.

STR:

• Enable dom.text_fragments.enabled
• Go to https://en.wikipedia.org/wiki/Nuclear_power#:~:text=up-,Most,reactors
• Go to view-source
• Loading the view-source page can take minutes

As a matter of fact, it seems that the expensive reflow can even be triggered on the page itself, I have not found out how. But it seems that going to another tab and then back triggers this? The page itself freezes while the reflow freezes the view-source tab.

Comment 8

[Jan Jaeschke [:jjaschke]]

Attachment: Bug 1867249, part 1: Implemented new cache to determine selected nodes. r=sefeng!,#dom-core

Determining if a node is selected is a super-hot code path, which at times introduces jank both in Reflow and Painting. This is due to each node comparing its position to the range's start and end point, which even happens several times (nsINode::IsSelected() and Selection::LookupSelection()). In worst cases, this can lead to reflow which takes several minutes.

This patch introduces a cache which contains all nodes selected in a selection, and lives throughout one PresShell::DoReflow() call.
Collecting all selected nodes of a selection is very fast.
The selected nodes are then stored either in a hash set (if fully selected) or in an array of {node, startOffset, endOffset} if they are partially selected.
During reflow the check if a node is selected is therefore reduced to either a hashtable lookup, or an iteration of a small contiguous array.

Comment 9

[Jan Jaeschke [:jjaschke]]

Attachment: Bug 1867249, part 2: Enable `SelectionNodeCache` for painting. r=sefeng!,#dom-core

Comment 10

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/cb3c39200716
part 0: Replaced hash set with array for performance reasons. r=sefeng,dom-core
https://hg.mozilla.org/integration/autoland/rev/9612bdfa326b
part 1: Implemented new cache to determine selected nodes. r=sefeng,dom-core
https://hg.mozilla.org/integration/autoland/rev/2851081fbabf
part 2: Enable `SelectionNodeCache` for painting. r=sefeng,dom-core,emilio

Comment 11

[pstanciu]

https://hg.mozilla.org/mozilla-central/rev/cb3c39200716
https://hg.mozilla.org/mozilla-central/rev/9612bdfa326b
https://hg.mozilla.org/mozilla-central/rev/2851081fbabf

Comment 12

[Mayank Bansal]

Opening the view-source: https://share.firefox.dev/3yxlxdJ (15s on a laptop)
Selecting some text and dragging the scrollbar: https://share.firefox.dev/4dwOvJt