Open Bug 1825618 Opened 1 year ago Updated 4 months ago

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

Categories

(Core :: Disability Access APIs, defect)

Desktop
Windows
defect

Tracking

()

People

(Reporter: Jamie, Unassigned)

References

(Blocks 1 open bug)

Details

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.

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

Flags: needinfo?(asa)

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

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.

Flags: needinfo?(asa)
You need to log in before you can comment on or make changes to this bug.