1892589 - Custom Highlight API: Speed up `Highlight::Add()`

Status: RESOLVED FIXED

(Core :: DOM: Selection, task)

Description

[Jan Jaeschke [:jjaschke]]

As pointed out in Bug 1892514, there are situations in which Highlight::Add() shows up in profiles prominently. This is due to the current situation described in Bug 1852908 that requires mirroring the maplike/setlike data structures in the DOM code using nsTArray<>s to be able to iterate its contents.

The elements in the mirrored array have to be sorted by insertion order and unique. Since SetlikeHelpers::Add() does not indicate if it actually inserts something, nsTArray::Contains() is used to determine if a new element needs to be inserted into the array. In the case of many highlighted ranges (such as the described test case in Bug 1892514), this can take up to a few seconds.

While waiting for the real solution of the underlying problem (-> Bug 1852908), removing the need of the mirrored array altogether, the nsTArray<>::Contains() calls can be replaced with SetlikeHelpers::Has(), which (presumably) has a better time complexity due to its underlying data structure.

Comment 1

[Jan Jaeschke [:jjaschke]]

As expected, implementing the proposed changes reduced the time spent in Highlight::Add() from ~1sec (test case above, on my machine) to ~300ms. The remaining time is mostly spent in NotifySelectionListener() now.

Try run for part 1.

Additionally, there was a small bug which caused NotifySelectionListener() to notify for eNormal selections even when triggered by highlight selections. This change reduced the Highlight::Add() call even further (~200ms now).

Try run for part 2.

Try run hopefully without build errors.

Comment 2

[Jan Jaeschke [:jjaschke]]

Attachment: Bug 1892589 - Custom Highlight API: Implemented speedup for `Highlight::Add()`. r=edgar!,#dom-core

To preserve uniqueness in the mirrored data structure for the JS-setlike object,
nsTArray::Contains() was used. This showed up in profiles due to its O(n) time complexity.
Performance could be improved by replacing it with SetlikeHelpers::Has(), which uses the more efficient version of the underlying data structure of the setlike.

The same idea has been applied to HighlightRegistry, which uses a maplike. However, this is mostly for consistency, since Highlight::Add() will likely be called more often and hence the bigger performance bottleneck.

Comment 3

[Jan Jaeschke [:jjaschke]]

Attachment: Bug 1892589, part 2 - Custom Highlight API: Call `NotifySelectionListener()` for the correct selection type. r=masayuki!,#dom-core

Before this patch, the AutoFrameSelectionBatcher helper class would always call NotifySelectionListeners() for SelectionType::eNormal.

Comment 4

[Jan Jaeschke [:jjaschke]]

(Fixing broken tests tomorrow)

Comment 5

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/6614f1cdc59b
Custom Highlight API: Implemented speedup for `Highlight::Add()`. r=edgar,dom-core

Comment 6

[Sandor Molnar[:smolnar]]

https://hg.mozilla.org/mozilla-central/rev/6614f1cdc59b

Comment 7

[Mayank Bansal]

Operation: Copy-paste text, Ctrl+A, delete text

Profile from couple of days back : https://share.firefox.dev/3xJ4kgR
Profile from latest Nightly: https://share.firefox.dev/3QfMxnI