Custom Highlight API: Speed up `Highlight::Add()`
Categories
(Core :: DOM: Selection, task)
Tracking
()
| Tracking | Status | |
|---|---|---|
| firefox127 | --- | fixed |
People
(Reporter: jjaschke, Assigned: jjaschke)
References
(Blocks 2 open bugs)
Details
Attachments
(1 file, 1 obsolete file)
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.
| Assignee | ||
Comment 1•4 months ago
•
|
||
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.
| Assignee | ||
Comment 2•4 months ago
|
||
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.
| Assignee | ||
Comment 3•4 months ago
|
||
Before this patch, the AutoFrameSelectionBatcher helper class would always call NotifySelectionListeners() for SelectionType::eNormal.
| Assignee | ||
Comment 4•4 months ago
|
||
(Fixing broken tests tomorrow)
Updated•4 months ago
|
Updated•4 months ago
|
Updated•4 months ago
|
Updated•4 months ago
|
Pushed by jjaschke@mozilla.com: https://hg.mozilla.org/integration/autoland/rev/6614f1cdc59b Custom Highlight API: Implemented speedup for `Highlight::Add()`. r=edgar,dom-core
Comment 6•4 months ago
|
||
| bugherder | ||
Comment 7•4 months ago
|
||
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
Description
•