1419992 - [e10s a11y] Improve performance of UIA tree walking/caching

Status: RESOLVED FIXED

(Core :: Disability Access APIs, enhancement)

Description

[James Teh [:Jamie]]

Some software appears to be using UIA to search the accessibility tree and/or cache subtrees. We suspect this is the case for RealPlayer; see bug 1418535. Jim posted an mscom log in bug 1418535 that is quite enlightening:
https://bugzilla.mozilla.org/attachment.cgi?id=8930903

I need to investigate this more, but here are some initial notes:

1. UIA is doing a QueryService for IAccessibleEx on every node. That makes sense, but it's wasteful for us.
Possible mitigation: Whether or not we have IAccessibleEx, we should cache appropriately (leveraging the work done in bug 1416986). That is, whether we return the interface or E_NOINTERFACE, this should not be a cross-process call.

2. IEnumVARIANT is used rather inefficiently:
* QI, Clone and Reset all get called.
* Rather than retrieving all children in a single call to Next, Next gets called to retrieve accessibles one by one.
Possible mitigation: We should implement IEnumVARIANT in the handler. When Next is first called on a reset instance, we should fetch all children in one call and cache them.
Risk: If a client doesn't end up wanting all children, we've just wasted a lot of work. However, if IEnumVARIANT is being used, I think it's reasonable that a client may very well end up visiting all children.
Question: Should we fetch children for each reset instance of IEnumVARIANT or just keep the cache and keep using it for any future instances? Stale cache is a risk here, but I think we can rely on the reorder event here. Memory wastage is another concern, but hopefully, clients release the parent accessible once they're done with it, at which point we can clean up.

Comment 1

[James Teh [:Jamie]]

Aaron, I'd love your thoughts/opinions here.

Comment 2

[alexander :surkov (:asurkov)]

Guys, what about returning IRawElementProviderSimple from WM_GETOBJECT when UIA is detected, and then implementing IRawElementProviderSimple and its friends. In that case I suppose UIA doesn't want to query IAccessibleEx and use IEnumVARIANT, since it should stick with native UIA navigation. 

If this approach is workable in theory, then it shouldn't be hard to implement it. We have starter implementation for IRawElementProviderSimple already. I guess it shouldn't be too hard to support its friends like IRawElementProviderFragment. Also we probably don't need to implement UIA in full, since our most consumers need some basic features only.

Comment 3

[James Teh [:Jamie]]

(In reply to alexander :surkov from comment #2)
> Guys, what about returning IRawElementProviderSimple from WM_GETOBJECT when
> UIA is detected, and then implementing IRawElementProviderSimple and its
> friends. In that case I suppose UIA doesn't want to query IAccessibleEx and
> use IEnumVARIANT, since it should stick with native UIA navigation.

There are two reasons I don't think we want to do this:

1. If you support UIA natively (via WM_GETOBJECT), UIAHasServerSideProvider will return true. That will tell NVDA that we should be using UIA in preference to IAccessible. We do have a blacklist in NVDA, but that would need to be updated for Mozilla.
2. Even if we use native UIA navigation, the accessibility tree is still in the content process. So, when UIA walks the tree, we'll still be going cross-process for every element. In fact, this might be worse because UIA doesn't have an IEnumVARIANT equivalent; its Navigate method returns a single element at a time, so it'd be difficult to make caching guesses. We'd also have to separately cache UIA properties in the handler, which means a whole lot of extra caching work.

Comment 4

[James Teh [:Jamie]]

Here's a quick way to reproduce UIA tree walking ugliness with the NVDA Python console:

1. Start NVDA and Firefox.
2. Open Gmail and ensure it's focused.
3. Press NVDA+control+z to open the NVDA Python console.
4. Paste this snippet as one line:
import UIAHandler; doc = UIAHandler.handler.clientObject.ElementFromIAccessible(nav.treeInterceptor.rootNVDAObject.IAccessibleObject, 0); cond = UIAHandler.handler.clientObject.CreatePropertyCondition(UIAHandler.UIA_NamePropertyId, "Conversations"); doc.FindFirst(UIAHandler.TreeScope_Descendants, cond).CurrentName

This searches for the "Conversations" heading (an off-screen heading just above the table of threads). On my system, that takes about 5 seconds... and that heading is not particularly far through the document. Searching for something at the end of the document hangs for about 15 seconds and then seems to give up and fail. In contrast, rendering a buffer with NVDA for the same page takes just under a second. So, we can definitely do better than this for UIA.

Comment 5

[James Teh [:Jamie]]

Here's another one to cache the names of all elements in a document:

import UIAHandler; doc = UIAHandler.handler.clientObject.ElementFromIAccessible(nav.treeInterceptor.rootNVDAObject.IAccessibleObject, 0); creq = UIAHandler.handler.clientObject.CreateCacheRequest(); creq.AddProperty(UIAHandler.UIA_NamePropertyId); creq.TreeScope = UIAHandler.TreeScope_Subtree; doc.BuildUpdatedCache(creq)

Just doing that on this Bugzilla bug takes 8 seconds (rendering an NVDA buffer takes < 1).

Comment 6

[(No longer employed by Mozilla) Aaron Klotz]

(In reply to James Teh [:Jamie] from comment #1)
> Aaron, I'd love your thoughts/opinions here.

(In reply to James Teh [:Jamie] from comment #0)
> 1. UIA is doing a QueryService for IAccessibleEx on every node. That makes
> sense, but it's wasteful for us.
> Possible mitigation: Whether or not we have IAccessibleEx, we should cache
> appropriately (leveraging the work done in bug 1416986). That is, whether we
> return the interface or E_NOINTERFACE, this should not be a cross-process
> call.

Yes, I've been wanting this for quite some time now.

> 2. IEnumVARIANT is used rather inefficiently:
> * QI, Clone and Reset all get called.
> * Rather than retrieving all children in a single call to Next, Next gets
> called to retrieve accessibles one by one.
> Possible mitigation: We should implement IEnumVARIANT in the handler. When
> Next is first called on a reset instance, we should fetch all children in
> one call and cache them.
> Risk: If a client doesn't end up wanting all children, we've just wasted a
> lot of work. However, if IEnumVARIANT is being used, I think it's reasonable
> that a client may very well end up visiting all children.

I think we should do this. In practice I don't believe it will be too expensive in terms of memory, but when in doubt, measure.

One caveat to point out: each child accessible that we cache would itself be accompanied by a cache of its own. We need to be careful about how we do this so that we don't inadvertently cache the world. As you have proposed, by lazily resolving the child cache upon the first call to IEnumVARIANT::Next, we can hopefully avoid that.

Perhaps another optimization that we could make is to only cache children if the call to IEnumVARIANT::Next requests retrieval of a single result? That way there's no cache penalty for well-written ATs.

> Question: Should we fetch children for each reset instance of IEnumVARIANT
> or just keep the cache and keep using it for any future instances? Stale
> cache is a risk here, but I think we can rely on the reorder event here.

Hopefully we can rely on the reorder event. I guess we still have the concern about caching the world, but I'd hope that the AT would eagerly Release the parent accessible once it has finished with it. Again, let's do it and measure the practicalities later. If we have to we could use some kind of compat flags to blacklist/whitelist which clients get this feature.

> Memory wastage is another concern, but hopefully, clients release the parent
> accessible once they're done with it, at which point we can clean up.

Yeah, I don't think we can worry about that until we have data.

Comment 7

[alexander :surkov (:asurkov)]

(In reply to James Teh [:Jamie] from comment #3)
> (In reply to alexander :surkov from comment #2)
> > Guys, what about returning IRawElementProviderSimple from WM_GETOBJECT when
> > UIA is detected, and then implementing IRawElementProviderSimple and its
> > friends. In that case I suppose UIA doesn't want to query IAccessibleEx and
> > use IEnumVARIANT, since it should stick with native UIA navigation.
> 
> There are two reasons I don't think we want to do this:
> 
> 1. If you support UIA natively (via WM_GETOBJECT), UIAHasServerSideProvider
> will return true. That will tell NVDA that we should be using UIA in
> preference to IAccessible. We do have a blacklist in NVDA, but that would
> need to be updated for Mozilla.

It is doable, so this probably shouldn't go for a reason #1 :)

> 2. Even if we use native UIA navigation, the accessibility tree is still in
> the content process. So, when UIA walks the tree, we'll still be going
> cross-process for every element. In fact, this might be worse because UIA
> doesn't have an IEnumVARIANT equivalent; its Navigate method returns a
> single element at a time, so it'd be difficult to make caching guesses. We'd
> also have to separately cache UIA properties in the handler, which means a
> whole lot of extra caching work.

It depends on implementation, right? If UI tree is separate, then we may keep a whole UI tree in parent process. This would require us to make caching for sure, but we are probably not expected to implement UI in whole at this stage, so caching stuff may be minimal.

Do you want me to file a new bug to explore the options here?

Comment 8

[James Teh [:Jamie]]

(In reply to alexander :surkov from comment #7)
> > 1. If you support UIA natively (via WM_GETOBJECT), UIAHasServerSideProvider
> > will return true. That will tell NVDA that we should be using UIA in
> > preference to IAccessible. We do have a blacklist in NVDA, but that would
> > need to be updated for Mozilla.
> It is doable, so this probably shouldn't go for a reason #1 :)

It's doable, yes, but it would involve closely coordinating releases and waiting until this was available in a stable NVDA release plus a bit of extra time for people to reasonably update. This would basically completely break NVDA users otherwise.

I also disagree with this from a philosophical perspective. If we implement it this way, we're essentially declaring that we have a native UIA implementation and that it should be used instead of our IAccessible implementation where possible. That's just not how things actually are; our IAccessible implementation is far richer and it's going to be that way for quite some time, possibly forever.

There's also not much advantage here. If you want to go down this path, you could just implement IAccessibleEx and IRawElementProviderFragment::Navigate, which would also force native UIA navigation instead of IEnumVARIANT.

> If UI tree is separate, then we may
> keep a whole UI tree in parent process. This would require us to make
> caching for sure, but we are probably not expected to implement UI in whole
> at this stage, so caching stuff may be minimal.

If we're keeping some of the tree in the parent process, it'd make sense to leverage that for IAccessible as well, and perhaps only hop to the child process for queries we can't answer from our parent cache. In other words, if we're going to cache, why not let IAccessible benefit as well? Either way, we have to solve the problem of keeping the cache in sync.

> Do you want me to file a new bug to explore the options here?

If you have solid ideas on how we can manage such a cache, sure! I think we need to keep all options on the table at this stage.

Comment 9

[James Teh [:Jamie]]

Damn. My tests in comment 4 and comment 5 are invalid. They rely on building a UIA element from an IAccessible, but the IAccessible came from the content process, so it can't actually try doing things in-proc.

To do these in-proc, we have to get a UIA element without going via a content IAccessible. The easiest way to do that for now is to do it using the HWND.

So, search for the Conversations heading:

import UIAHandler; root = UIAHandler.handler.clientObject.ElementFromHandle(nav.windowHandle); cond = UIAHandler.handler.clientObject.CreatePropertyCondition(UIAHandler.UIA_NamePropertyId, "Conversations"); root.FindFirst(UIAHandler.TreeScope_Descendants, cond).CurrentName

And cache the names of all elements:

import UIAHandler; root = UIAHandler.handler.clientObject.ElementFromHandle(nav.windowHandle); creq = UIAHandler.handler.clientObject.CreateCacheRequest(); creq.AddProperty(UIAHandler.UIA_NamePropertyId); creq.TreeScope = UIAHandler.TreeScope_Subtree; root.BuildUpdatedCache(creq)

Doing it this way, it's significantly faster without any additional patches, though still slower than NVDA rendering a buffer.

Interestingly, my patches to cache children for IEnumVARIANT don't seem to make much (if any) difference at all, which perplexes me a lot.

Comment 10

[James Teh [:Jamie]]

This should be largely resolved by Cache the World, which is enabled by default in Firefox 113. Any further performance issues here should be addressed in separate, specific bugs.