1768396 - [CTW] Consider caching RemoteAccessibleBase::IndexInParent

Status: NEW

(Core :: Disability Access APIs, enhancement)

Description

[James Teh [:Jamie]]

We cache IndexInParent for LocalAccessible already. This was never done for RemoteAccessible because it wasn't clear that it was necessary. However, this profile, taken when rendering an NVDA vbuf for view source on a Bugzilla bug, suggests that we could definitely benefit from caching this (or optimising it some other way if there is one).

While it doesn't show up in this profile, note that we also use IndexINParent in TextLeafPoint::operator<, which we'll probably start using more over time.

Comment 1

[James Teh [:Jamie]]

Even after the patch for bug 1794747, IndexInParent still shows up in profiles as a hot path for the repro steps in that bug. That's because SelectedItems uses Pivot, which uses NextSibling. Pivot is used in quite a few other places too.

Comment 2

[James Teh [:Jamie]]

I have a patch for this locally which caches parent indexes in a hash map on the doc. On my desktop, this speeds up NVDA vbuf rendering of view source for the Mozilla Wikipedia page from 2.11 sec to 0.76 sec, about a 2.7x increase. On the other hand, performing the Treeherder steps in bug 1794747 comment 0 takes about 14 sec with the patch and 7 sec without it. This is probably because I'm invalidating the whole map every time the document changes and caching the indexes for every child in the parent when IndexInParent is called. This can probably be optimised further, but we now know that the super naive caching approach actually makes things worse here for some cases.

Comment 3

[James Teh [:Jamie]]

Attachment: Bug 1768396 approach 1: Lazily cache IndexInParent for RemoteAccessibles using a hash map on the document.

When IndexInParent is queried, if there is no cached value, the indexes for all children of the parent are calculated and cached in a hash map on the document.
When the tree structure mutates, the entire hash map is cleared.
This way, we only calculate and store IndexInParent if a client actually requests it.

Comment 4

[James Teh [:Jamie]]

Attachment: Bug 1768396approach 2: Cache IndexInParent on RemoteAccessible.

Similar to LocalAccessible, IndexInParent is kept in an instance variable.
Upon insertion or removal, the index is updated on all impacted children.

Comment 5

[James Teh [:Jamie]]

(In reply to James Teh [:Jamie] from comment #2)

I have a patch for this locally which caches parent indexes in a hash map on the doc.

This is approach 1 (comment 3). It avoids calculation or using memory unless a client actually requests IndexInParent.

performing the Treeherder steps in bug 1794747 comment 0 takes about 14 sec with the patch and 7 sec without it.

Approach 2 (comment 4) doesn't suffer from this problem. On the flip side:

• It also means that if there is an insertion or a removal that isn't the last child, we have to adjust IndexInParent for all children after the inserted/removed child. If thousands of nodes were inserted in the middle of a large container, we'd update many indexes thousands of times.
• It always uses memory, even if a client doesn't request IndexInParent. That said, it almost certainly uses less memory than the hash map (approach 1) if a client does request IndexInParent.

Comment 6

[James Teh [:Jamie]]

Loading https://coreboot.org/status/board-status.html with NVDA really hurts here.
Profile: https://share.firefox.dev/3Mp2ANZ