1825618 - [CTW] Retrieving many selections is slow (AKA massive jank when selecting many table cells with Windows Text Cursor Indicator enabled)

Status: RESOLVED FIXED

(Core :: Disability Access APIs, defect)

Description

[James Teh [:Jamie]]

This was discovered by Asa. I don't have real world steps to reproduce yet; I'll ask Asa to provide those. As I understand it, control clicking on many table cells to select them causes massive jank and potentially a full parent process hang. Asa provided this profile:
https://share.firefox.dev/40EMBA4

Steps to reproduce with the NVDA Python console:

1. Open this test case:

   data:text/html,
   <section>
     <table><tbody id="tbody"></tbody></table>
   </section>
   <script>
     let html = "";
     for (let r = 0; r < 500; ++r) {
       html += '<tr><td>a</td><td>b</td></tr>';
     }
     tbody.innerHTML = html;
     const selection = window.getSelection();
     for (const cell of document.querySelectorAll("td")) {
       const range = document.createRange();
       range.selectNode(cell);
       selection.addRange(range);
     }
   </script>
   

2. Use NVDA object navigation to get to the section beneath the document.
3. Open the NVDA Python console with NVDA+control+z.
4. Paste the following:
   for i in range(1000): s = nav.IAccessibleTextObject.selection(i)

This is quite slow at present.

When table cells are selected using control click, Gecko creates a separate range in the selection for each individual cell. It does this even if the cells are contiguous. So, if you select 1000 cells, you'll have 1000 selection ranges. The test case above simulates this, but selects them on load.

The profile shows a lot of time spent in a11y::TextRange::CommonParent due to TextRange::Crop. It seems that UIA (presumably triggered by Text Cursor Indicator) is asking for every selection. At present, that means we call CroppedSelectionRanges for each selection, which calls crop on every single range.

It's difficult to avoid calling CroppedSelectionRanges each time because we probably don't want to cache those for every Accessible, but we don't necessarily know when a client is going to repeatedly ask the same Accessible for all of its selections. I thought of caching CroppedSelectionRanges for just the most recent Accessible on which it was called, but there's no guarantee that will help. For example, the client might descend into embedded objects and query their sub-selections. It's also tricky to plumb that cache; CroppedSelectionRanges is in HyperTextAccessibleBase, but we probably want to cache on DocAccessibleParent. Nevertheless, I'm not discounting this possibility completely going forward.

Inspired by DOM, an easier win which we should implement regardless is to binary search the document's selection ranges, rather than calling Crop on every range. This should significantly improve performance because it shifts from linear to logarithmic time for the cropping part.

Finally, another possibility is to collapse contiguous selection ranges in the document, probably when DocAccessibleParent::SelectionRanges is first called for a new list of selections. However, this would make API exposure different between local and remote, though this is mostly going to be relevant for remote (real web content) anyway.

Comment 1

[James Teh [:Jamie]]

Asa, I just kicked off a try build with an improvement here. Can you take this for a spin when you get a chance and let me know if it helps sufficiently? I'm trying to work out how far I need to go here.
https://treeherder.mozilla.org/jobs?repo=try&revision=3aae52348591df2194fd0246731e367564ae4d3c

Comment 2

[James Teh [:Jamie]]

If performance isn't sufficiently improved, a profile would be super useful. Thanks.

Comment 3

[BugBot [:suhaib / :marco/ :calixte]]

Clear a needinfo that is pending on an inactive user.

Inactive users most likely will not respond; if the missing information is essential and cannot be collected another way, the bug maybe should be closed as INCOMPLETE.

For more information, please visit BugBot documentation.

Comment 4

[James Teh [:Jamie]]

When UIA queries text selection, it always fetches all selections at once, so we'll likely hit this again. It's probably worth dealing with this as part of the UIA text work.

Comment 5

[James Teh [:Jamie]]

Attachment: Bug 1825618: CroppedSelectionRanges: Binary search selection ranges instead of cropping every range.

Previously, we called Crop on every range.
Among other things, that has to calculate common parents, which gets very slow with lots of ranges.
Since the selection ranges are sorted by position in the document, we can binary search to find the overlapping ranges instead.

This required a fix to TextPoint::operator<, which previously returned an incorrect result when comparing a descendant point with an ancestor point.
This patch also pre-allocates the array in DocAccessibleParent::SelectionRanges, since we know roughly how big that will be based on the cache.

Comment 6

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/30b02cc2e792
CroppedSelectionRanges: Binary search selection ranges instead of cropping every range. r=nlapre

Comment 7

[agoloman]

https://hg.mozilla.org/mozilla-central/rev/30b02cc2e792