1914833 - View Source of a single word is very slow on specific markdown page on Github (Followup from bug 1867249)

Status: NEW

(Core :: DOM: Selection, defect)

Description

[Mayank Bansal]

STR:
Go to This markdown page
Inside of the first markup box, select only the the first word (That word is "function")
Right-Click and hit "view source for selection"

AR: https://share.firefox.dev/470Rh7L (truncated. I got bored after 1.5 minutes)
ER: Maybe we should be better

Comment 1

[Mayank Bansal]

Attachment: about:support

Comment 2

[Mayank Bansal]

Patch from bug 1503581 does make the operation complete in ~20s: https://share.firefox.dev/3XfRWiq

Comment 3

[Jan Jaeschke [:jjaschke]]

Thanks for that use case. I think that if we can manage to land the change in bug 1503581 it could even make the change in bug 1867249 obsolete, as the cache in bug 1503581 essentially does something similar, but has a longer lifetime.

Explanation:

The slowness happens because view-source is essentially one parent node with lots (thousands) of direct child nodes. The rendering code needs to determine for each of these child nodes if they are selected. To do this, the node needs to be compared to the selection range's start and end point. For this it is necessary to determine the index of the node inside of its parent. The node can't know the index for various reasons, therefore it has to be computed every time. Since nodes are stored as linked list, the time complexity is O(n), and becomes very slow for large lists. Since this check is done (apparently even multiple times) for each node, this results in quadratic (or worse) behavior, which leads to rendering taking several minutes.

Bug 1867249 introduces a cache which contains all fully-selected nodes per Selection as a hash set. This cache only lives throughout one reflow / paint iteration, where no script is allowed to run (hence the Selection can't change). The cache does not contain partially selected nodes. The original test case in bug 1867249 selected all of the text in the markdown code, which utilizes the cache and reduces the selection reflow to <1 second (overall rendering still at ~22s). This test case however seems to only have partially selected nodes, hence it can't use the cache and runs the slow code path.

Bug 1503581 uses a more general approach, as computing the index of a node in a parent with many child nodes shows up as bottleneck in other places as well.
Instead of caching the selected nodes and invalidating the cache after reach render, the indices of the nodes are cached instead. When the index of a node is requested, the index is computed by traversing the childlist back to the beginning, and then every node/index combination is stored in a hashmap. In a consecutive call to computing an index of a node which has the same parent, the cost for computing the index can be greatly reduced because it's only necessary to traverse back until there is a cache hit. In the optimal case where an index is requested which is already cached, computing the index is reduced to one hashtable lookup. Also note that this cache introduces hashtable lookups as overhead. Therefore it is only active if the parent node has many children (currently >1k), because otherwise traversing the linked list to determine the index is faster.

Since this cache is not depending on Selection, it can have a longer lifetime -- it is valid until there is a DOM mutation which might have changed the indices. Unfortunately, landing is blocked currently because the editor code allows to run legacy mutation events for each inserted node when pasting html code, each time invalidating the cache.