STR (with CTW enabled and NVDA running):

1. Open a Treeherder push; e.g. https://treeherder.mozilla.org/jobs?repo=try&revision=60713f21da425c6188bf3d16a091b2469dd82e21
2. Open the actions dropdown and choose: Add new jobs (Search)
   • Expected: Should be usable within a few seconds.
   • Actual: Browser hangs for over 30 seconds.

Getting a decent profile for this was really tricky, but I eventually managed it:
https://share.firefox.dev/3evr5LH

The profile is quite enlightening:

1. We spend a lot of time trying to get the index of RemoteAccessible children, since IndexInParent is not cached for them.
2. This is happening due to an Accessible::Level call triggered by RemoteAccessibleBase::Attributes queried in response to a show win event. This is probably NVDA's in-process code checking if the show event is for a live region.
   • This would explain why exiting NVDA or switching windows stops the hang. When you switch windows, the Accessibles get the off-screen state and NVDA ignores off-screen Accessibles in its live region code.
3. I didn't verify this, but the list of items might be populated gradually (rather than showing the entire list once its built), which means there are probably a lot of show events.

Accessible::Level contains this loop:

        for (Accessible* child = parent->FirstChild(); child;
             child = child->NextSibling()) {

That is ridiculously expensive for large lists, since NextSibling calls IndexInParent and IndexInParent has to linear walk the children array. We're looking at O(n^2) there. If we're firing a lot of show events, that's O(n^3)!

On one hand, we could fix this by fixing bug 1768396 and caching IndexInParent, for RemoteAccessibles which will probably help other things. On the other hand, the NextSibling loop in Accessible::Level could very easily be rewritten to use ChildAt, which would still be more efficient even if IndexInParent were cached since it avoids hash lookups.

NextSibling uses IndexInParent, which is currently slow for RemoteAccessible.
Even if IndexInParent were faster, we're iterating all children here, so doing it this way is more efficient regardless.
This results in a significant performance improvement (> 25x) with NVDA when thousands of HTML select options are shown.

The above patch improves things majorly, but I'm still seeing IndexInParent in a profile due to SelectedItems, which uses Pivot, which uses NextSibling. It's very reasonable for Pivot to use NextSibling, since it searches from an arbitrary point in the tree, so we'll need bug 1768396 to address that.

https://hg.mozilla.org/mozilla-central/rev/613d6cf07e5e