Bug 106497 – AX: memoize expensive computation during blocks where tree doesn't change

• Component: Accessibility
• Status: RESOLVED FIXED

[Dominic Mazzoni]

I'd like to speed up the time to build the accessibility tree for the whole document. This happens in Chromium whenever the document first loads, but I'm pretty sure we could speed up operations like findMatchingObjects in Safari, too - basically anytime a lot of accessibility objects will be queried from a block that doesn't mutate the tree.

A lot of the time is spent computing accessibilityIsIgnored, but it's hard to optimize it for a single object. Originally I thought we should avoid going up the parent chain more than once (bug 101370), but an even better speedup is to just memoize the value of accessibilityIsIgnored whenever you can be confident that it won't change.

I don't think it would make sense to mark an AccessibilityObject as dirty every time its ignored state might change. Changing an attribute of a single element could conceivably result in hundreds of elements in its subtree changing their ignored state.

Instead, I think it's easier to try to identify blocks where the tree doesn't change and memoize the ignored state for each node as long as we're within that block. It may also be useful to memoize other values, too, but the ignored state is the biggest win.

I think this could eliminate the need for bug 101370 (Only walk up the parent tree one time in accessibilityIsIgnored).

I have a proposed patch. If the overall design looks good, I'll write a test by adding a method to DRT that allows you to explicitly turn on memoization, and then test that accessibilityIsIgnored does *not* update when memoization is on.

[Dominic Mazzoni]

Created attachment 181999 [details]
Patch

[Dominic Mazzoni]

Comment on attachment 181999 [details]
Patch

Not for review yet, please give me thoughts on the approach - and in particular the name of methods / data structures (to save me time rewriting tests later)

[chris fleizach]

I like ideas like this that can cache certain values for a short time. Have you identified any blocks that could use this? my primary concern is how many regressions we'd introduce by having data out of date. maybe there are portions of accessibilityIsIgnored() that could be cached as well instead of the whole thing...

[Dominic Mazzoni]

The two places where I'm sure it could be used:

1. In Chromium, inside our accessibility notification handler, where we query potentially a large number of accessibility objects. The tree won't change within that context, so it's safe to create a cache and then delete it. I've benchmarked this and it makes building the whole ax tree for a large page almost twice as fast.

2. In findMatchingObjects, I think we could enable the cache just before the search.

3. With a bit more work, I think we could use it in addChildren. Every child added ends up traversing up the same parent chain! 

To clarify, I want to use it only in small blocks, like this:

AXObjectCache->startMemoizing
call expensive method, e.g. findMatchingObjects, addChildren
AXObjectCache->stopMemoizing

There's no way the DOM/render tree will change inside of findMatchingObjects, right? So this just means that as it scans a large number of nodes, it can avoid repeating the same computation over and over again. As soon as that code block ends, we throw the cache away so there's no chance of regressions.

[Dominic Mazzoni]

Created attachment 182384 [details]
Patch

[WebKit Review Bot]

Please wait for approval from [e-mail], [e-mail], [e-mail], [e-mail] or [e-mail] before submitting, as this patch contains changes to the Chromium public API. See also https://trac.webkit.org/wiki/ChromiumWebKitAPI.

[chris fleizach]

Comment on attachment 182384 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=182384&action=review

> Source/WebCore/accessibility/AXObjectCache.cpp:809
> +    for (HashMap<AXID, MemoizedAccessibilityObjectData*>::iterator it = m_memoizedData->begin(); it != m_memoizedData->end(); ++it)

can you make MemoizedAccessibilityObjectData  a RefPtr, so you don't have to iterate everything to delete it?

> Source/WebCore/accessibility/AXObjectCache.cpp:831
> +        return (*it).value;

can you call getMemoizedData() directly here and use that

> LayoutTests/ChangeLog:12
> +        * platform/chromium/accessibility/memoize-isignored-expected.txt: Added.

can you make this test go in accessibility/
I'll implement the Mac methods for it and we can skip on the other platforms in the meantime

[Build Bot]

Comment on attachment 182384 [details]
Patch

Attachment 182384 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/15805487

[Peter Beverloo (cr-android ews)]

Comment on attachment 182384 [details]
Patch

Attachment 182384 [details] did not pass cr-android-ews (chromium-android):
Output: http://queues.webkit.org/results/15806472

[Dominic Mazzoni]

Comment on attachment 182384 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=182384&action=review

>> Source/WebCore/accessibility/AXObjectCache.cpp:809
>> +    for (HashMap<AXID, MemoizedAccessibilityObjectData*>::iterator it = m_memoizedData->begin(); it != m_memoizedData->end(); ++it)
> 
> can you make MemoizedAccessibilityObjectData  a RefPtr, so you don't have to iterate everything to delete it?

Sure

>> Source/WebCore/accessibility/AXObjectCache.cpp:831
>> +        return (*it).value;
> 
> can you call getMemoizedData() directly here and use that

Good idea

>> LayoutTests/ChangeLog:12
>> +        * platform/chromium/accessibility/memoize-isignored-expected.txt: Added.
> 
> can you make this test go in accessibility/
> I'll implement the Mac methods for it and we can skip on the other platforms in the meantime

OK. I guess you'll have to add a hidden API or something? I got the impression it wasn't easy to call WebCore methods from WKTR in particular if you don't want to expose them in the public interface.

[Dominic Mazzoni]

Created attachment 182411 [details]
Patch

[Build Bot]

Comment on attachment 182411 [details]
Patch

Attachment 182411 [details] did not pass mac-ews (mac):
Output: http://queues.webkit.org/results/15833022

[Dominic Mazzoni]

Created attachment 182425 [details]
Patch

[chris fleizach]

looks good. lets just wait to make sure it builds

[Peter Beverloo (cr-android ews)]

Comment on attachment 182425 [details]
Patch

Attachment 182425 [details] did not pass cr-android-ews (chromium-android):
Output: http://queues.webkit.org/results/15827091

[Dominic Mazzoni]

Created attachment 182461 [details]
Patch

[Early Warning System Bot]

Comment on attachment 182461 [details]
Patch

Attachment 182461 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/15828225

[Ryosuke Niwa]

Comment on attachment 182461 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=182461&action=review

> Source/WebCore/accessibility/AccessibilityObject.cpp:454
> +    // Turn on memoization to minimize redundant computation during the duration of this
> +    // method, where we can guarantee the tree won't change.
> +    axObjectCache()->startMemoizing();
> +

Please create a RAII object to do this instead. Also, why don't we cache things inside a RAII instead of adding member variables to AXObjectCache?

[Dominic Mazzoni]

Created attachment 182462 [details]
Patch

[Dominic Mazzoni]

(In reply to comment #18)
> (From update of attachment 182461 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=182461&action=review
> 
> > Source/WebCore/accessibility/AccessibilityObject.cpp:454
> > +    // Turn on memoization to minimize redundant computation during the duration of this
> > +    // method, where we can guarantee the tree won't change.
> > +    axObjectCache()->startMemoizing();
> > +
> 
> Please create a RAII object to do this instead.

That's a great pattern within WebCore, but I also need it to be possible to enable/disable the cache from the WebKit API, and from layout tests. What do you think about leaving this as the low-level interface but adding a RAII wrapper?

If RAII was the only way to control the cache, that would make the layout test much hairier.

> Also, why don't we cache things inside a RAII instead of adding member variables to AXObjectCache?

Then how would a particular AccessibilityObject find the cache? We'd still need a pointer from the AXObjectCache to the class that owns the cache. Note that AXObjectCache is not a singleton.

[Ryosuke Niwa]

(In reply to comment #20)
> (In reply to comment #18)
> > (From update of attachment 182461 [details] [details])
> > View in context: https://bugs.webkit.org/attachment.cgi?id=182461&action=review
> > 
> > > Source/WebCore/accessibility/AccessibilityObject.cpp:454
> > > +    // Turn on memoization to minimize redundant computation during the duration of this
> > > +    // method, where we can guarantee the tree won't change.
> > > +    axObjectCache()->startMemoizing();
> > > +
> > 
> > Please create a RAII object to do this instead.
> 
> That's a great pattern within WebCore, but I also need it to be possible to enable/disable the cache from the WebKit API, and from layout tests. What do you think about leaving this as the low-level interface but adding a RAII wrapper?

Why? What’s the use case for that? Sounds like this will be a very fragile API because enable/disable need to be called at the right time. In the world where we already have an open security vulnerability (e.g. the bug 106106), I don’t think we should be adding an API like this.

> If RAII was the only way to control the cache, that would make the layout test much hairier.

While being able to test something is good, we shouldn’t be choosing a worse design just so that we can test it.

> > Also, why don't we cache things inside a RAII instead of adding member variables to AXObjectCache?
> 
> Then how would a particular AccessibilityObject find the cache? We'd still need a pointer from the AXObjectCache to the class that owns the cache. Note that AXObjectCache is not a singleton.

There is no need. Given that at most one instance of this RAII object exists  (assuming that the current patch doesn’t have a bug), AccessibilityObject can find the cache via the RAII object’s interface since the RAII object is effectively a singleton.

[Dominic Mazzoni]

(In reply to comment #21)
> > That's a great pattern within WebCore, but I also need it to be possible to enable/disable the cache from the WebKit API, and from layout tests. What do you think about leaving this as the low-level interface but adding a RAII wrapper?
> 
> Why? What’s the use case for that? Sounds like this will be a very fragile API because enable/disable need to be called at the right time. In the world where we already have an open security vulnerability (e.g. the bug 106106), I don’t think we should be adding an API like this.

SerializeAccessibilityNode is the main place where Chromium calls into WebKit accessibility:

  http://code.google.com/searchframe#OAMlx_jo-ck/src/content/renderer/accessibility_node_serializer.cc

I can get a substantial speedup on some Chromium benchmarks when accessibility is enabled, just by enabling memoization for the duration of this method call.

[Ryosuke Niwa]

(In reply to comment #22)
>
> SerializeAccessibilityNode is the main place where Chromium calls into WebKit accessibility:
> 
>   http://code.google.com/searchframe#OAMlx_jo-ck/src/content/renderer/accessibility_node_serializer.cc
> 
> I can get a substantial speedup on some Chromium benchmarks when accessibility is enabled, just by enabling memoization for the duration of this method call.

I see. I still don't think adding enable/disable public API is a good idea. We need to figure out some other way to improve the performance here.

[Abhishek Arya]

(In reply to comment #23)
> (In reply to comment #22)
> >
> > SerializeAccessibilityNode is the main place where Chromium calls into WebKit accessibility:
> > 
> >   http://code.google.com/searchframe#OAMlx_jo-ck/src/content/renderer/accessibility_node_serializer.cc
> > 
> > I can get a substantial speedup on some Chromium benchmarks when accessibility is enabled, just by enabling memoization for the duration of this method call.
> 
> I see. I still don't think adding enable/disable public API is a good idea. We need to figure out some other way to improve the performance here.

Dominic, why are we compromising on security here ? We shouldn't be going with a design that is causing more use-after-frees than we can manage. Can you please explain the assumptions that you think would prevent it from happening.

[Dominic Mazzoni]

Created attachment 184425 [details]
Patch

[Dominic Mazzoni]

New approach. Needs a bit of clean up and some better names, but this is a snapshot to see if people like the direction this is going.

@rniwa: It's now an RAII object, the new name emphasizes that this is just a way to group together a bunch of read-only operations. I'm open to suggestions for the name of the class, since "Transaction" usually implies read and write operations, not a batch of atomic read-only operations.

Are you at all happier with exposing it in the WebKit API like this? I'm convinced this gives us the most opportunity for optimization, since we can know for certain the tree isn't changing between two calls, rather than trying to build fragile mechanisms to keep track of potential changes. WebKit accessibility is basically only accessed from one place on the Chromium side; I don't see any reason to worry the API could be abused.

@inferno: I designed this to be safe from a security perspective (and also I hope we are in better shape with respect to heap-use-after-free bugs now). The cache is deliberately a map from axID (integer) to a struct of POD (currently just one bool, but perhaps one or two strings in the future). If a bug causes the tree to change while the cache is active, the worst case is that it will return bad values.

Thanks.

[Ryosuke Niwa]

Comment on attachment 184425 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=184425&action=review

> Source/WebCore/accessibility/AXObjectCache.cpp:91
> +    if (s_instanceCount == 0)

Nit: should be !s_instanceCount instead.

> Source/WebCore/accessibility/AXObjectCache.cpp:99
> +    if (s_instanceCount == 0)

Ditto.

> Source/WebCore/accessibility/AXObjectCache.cpp:106
> +    return it != m_memoizedData.end() ? (*it).value.get() : 0;

Why not it->value.get()?

> Source/WebCore/accessibility/AXObjectCache.h:60
> +// Create an instance of this class on the stack to temporarily enable
> +// internal caching of accessibility data, to speed up a series of read-only
> +// operations on the accessibility tree. There's no security risk if the
> +// tree changes during the scope of a transaction due to a bug, because the
> +// cache is simply a map from axObjectID to simple data types - the worst
> +// case is that stale results could be returned. Nested instances are fine.

We need to give the class a more descriptive name so that we can get rid of this comment.

> Source/WebCore/accessibility/AXObjectCache.h:61
> +class ReadOnlyAXTransaction {

We normally use "Scope" for RAII object so how about something like AXRenderTreeDependentCacheScope or AXRenderTreeStateCacheScope?

> Source/WebCore/accessibility/AXObjectCache.h:74
> +    // Methods to be used only by AccessibilityRenderObject (or in the
> +    // future, any AccessibilityObject subset).

This comment repeats exactly what the code says right beneath it. Please remove it.

> Source/WebCore/accessibility/AXObjectCache.h:78
> +    friend class AccessibilityRenderObject;
> +    static ReadOnlyAXTransaction* instance() { return s_instance; }
> +    MemoizedData* getMemoizedData(AXID) const;
> +    MemoizedData* getOrCreateMemoizedData(AXID);

I don't really see a point if making these methods private and then making AccessibilityRenderObject a friend of this class.
It would have been better if they were all static functions and public.

> Source/WebCore/accessibility/AXObjectCache.h:82
> +    static ReadOnlyAXTransaction* s_instance;
> +    static int s_instanceCount;
> +    HashMap<AXID, RefPtr<MemoizedData> > m_memoizedData;

I don't quite understand the point of making m_memoizedData an instance variable. Why don't we make everything static?
(note, we can have OwnPtr<HashMap<AXID, RefPtr<MemoizedData> > > if you're worried about the initialization cost.

> Source/WebCore/accessibility/AccessibilityRenderObject.cpp:1135
> +        if (ReadOnlyAXTransaction::MemoizedData* memoizedData = transaction->getMemoizedData(axObjectID())) {
> +            if (memoizedData->ignored == IgnoreObject)
> +                return true;
> +            if (memoizedData->ignored == IncludeObject)
> +                return false;

I wouldn't have exposed MemoizedData like this if I were you. I would have added a static method specifically for computeAccessibilityIsIgnored so that MemoizedData could stay private to the scoping object.

> Source/WebKit/chromium/public/WebAccessibilityObject.h:62
> +// Create an instance of this class on the stack to temporarily enable
> +// internal caching of accessibility data, to speed up a series of read-only
> +// operations on the accessibility tree.

Again, we shouldn't be needing a comment like this.
i.e. the class name should convey all of this information by its name.

> Source/WebKit/chromium/public/WebAccessibilityObject.h:70
> +class WebReadOnlyAccessibilityTransaction {
> +public:
> +    WEBKIT_EXPORT WebReadOnlyAccessibilityTransaction();
> +    WEBKIT_EXPORT ~WebReadOnlyAccessibilityTransaction();
> +
> +private:
> +    WebPrivateOwnPtr<WebCore::ReadOnlyAXTransaction> m_private;
> +};

Ideally, we don't want to expose this outside of WebKit. One thing you can do is to move more code from Chromium to WebKit such that all expensive operations are done inside Source/WebKit/chromium.

> Tools/DumpRenderTree/chromium/TestRunner/src/AccessibilityControllerChromium.cpp:214
> +void AccessibilityController::startMemoizingCallback(const CppArgumentList& arguments, CppVariant* result)
> +{
> +    result->setNull();
> +    m_transaction = new WebReadOnlyAccessibilityTransaction();
> +}
> +
> +void AccessibilityController::stopMemoizingCallback(const CppArgumentList& arguments, CppVariant* result)
> +{
> +    result->setNull();
> +    delete m_transaction;
> +    m_transaction = 0;
> +}
> +

I don't think we should be exposing such an implementation detail in DRT. I don't think we need a test for this optimization.

> LayoutTests/accessibility/memoize-isignored.html:1
> +<html>

Missing DOCTYPE

[Dominic Mazzoni]

Comment on attachment 184425 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=184425&action=review

Happy to take all other feedback - will upload a new patch soon, but meanwhile just two points left to discuss:

>> Source/WebCore/accessibility/AXObjectCache.h:61
>> +class ReadOnlyAXTransaction {
> 
> We normally use "Scope" for RAII object so how about something like AXRenderTreeDependentCacheScope or AXRenderTreeStateCacheScope?

I like the direction. Note that "state" has a specific meaning in accessibility, I want to avoid an ambiguous term. I'd like to convey that it's attributes of AX objects that are cached, not the tree - how about CacheAXObjectMethodResultsScope or AXObjectMemoizationEnabledScope?

>> Source/WebKit/chromium/public/WebAccessibilityObject.h:70
>> +};
> 
> Ideally, we don't want to expose this outside of WebKit. One thing you can do is to move more code from Chromium to WebKit such that all expensive operations are done inside Source/WebKit/chromium.

That's what all of the other ports do. Chromium's multi-process architecture constrains our design. In a nutshell, operating-system native accessibility interfaces that Chromium implements are all synchronous, and need to respond in the browser process with low latency. So Chromium's render process serializes WebKit's accessibility tree and sends the data to the browser process, where we implement all of the native interfaces based on the serialized tree. (It's not that different than how Chromium's software rendering works; the render process asks WebKit to redraw the bitmap when it changes, then the browser process blits the most recent bitmap to the screen on-demand.) The majority of the time spent in the render process is in responding to each accessibility notification from WebKit and serializing the information about what nodes changed.

We couldn't easily move the relatively small amount of code from Chromium's content/renderer/*accessibility* to WebKit, because changes to the serializable data structure would frequently require simultaneous changes to both WebKit and Chromium code (IPC macros, for example). With the current design, landing two-sided patches is pretty easy, as I can temporarily expose a new API from WebKit, switch Chromium to serialize the result of the new method and unserialize it on the other end in one step, then delete the old method in WebKit third.

Other ideas that I considered:

* WebKit calls back to Chromium whenever there's an accessibility notification; it could require that Chromium not change the tree within that notification callback, and that would allow the cache to be enabled within that scope. However, this doesn't address a few cases where Chromium wants to grab the accessibility tree not in response to a notification (when switching tabs, for example), and this constraint would be far less explicit in the code, it'd be easier for someone to accidentally violate later.

* AccessibilityRenderObject could call a platform method (see accessibilityIsIgnored for one example where we're already doing this) and that platform method could implement the caching. That would give us most of the optimization I want in Chromium, but it'd mean that we couldn't make use of this optimization on other platforms (and I think it is worthwhile for a few operations in Safari).

So I still think that letting Chromium tell WebKit when it's in a read-only scope is the simplest.

[Ryosuke Niwa]

(In reply to comment #28)
> (From update of attachment 184425 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=184425&action=review
> 
> Happy to take all other feedback - will upload a new patch soon, but meanwhile just two points left to discuss:
> 
> >> Source/WebCore/accessibility/AXObjectCache.h:61
> >> +class ReadOnlyAXTransaction {
> > 
> > We normally use "Scope" for RAII object so how about something like AXRenderTreeDependentCacheScope or AXRenderTreeStateCacheScope?
> 
> I like the direction. Note that "state" has a specific meaning in accessibility, I want to avoid an ambiguous term. I'd like to convey that it's attributes of AX objects that are cached, not the tree - how about CacheAXObjectMethodResultsScope or AXObjectMemoizationEnabledScope?

"Method" isn't a C++ term. MemoizationEnabled doesn't really tell us what we're caching. We definitely need to communicate the fact this cache is dependent on the render tree since we can cache things indefinitely otherwise, and that's the whole point of making this RAII object.

Among all these options, I like AXRenderTreeDependentCacheScope best. Maybe Chris has an opinion on this?

> >> Source/WebKit/chromium/public/WebAccessibilityObject.h:70
> >> +};
> > 
> > Ideally, we don't want to expose this outside of WebKit. One thing you can do is to move more code from Chromium to WebKit such that all expensive operations are done inside Source/WebKit/chromium.
> 
> That's what all of the other ports do.

This sentence makes it clear that's what Chromium port should do. I'm fine with temporarily exposing this API in Chromium but it shouldn't be a long term solution. Trusting the Chromium code to do the right thing for WebCore is almost never a good idea because most of people working on Chromium codebase doesn't know how WebCore works and all the complexity and constraints we have. Using a RAII object mitigates it to some extent, but not completely. The point of Source/WebKit is to avoid decouple browser code and WebCore. In principle, we shouldn't be exposing any implementation details like how caching of accessibility code works to the browser code.

[James Robinson]

I don't think anything in the WebKit API layer can promise that WebCore will not mutate the DOM or render tree.  If you want to have some cache that is only valid until, say, layout happens then I think the right way to factor it would be to (optionally) have some call in the WebKit API that says "please build this cache / start caching this" and then have WebCore be responsible for invalidating the cache whenever layout/whatever happen.  You can also have a WebKit API call to say "please discard this cache if you have it".

[Dominic Mazzoni]

That could work, with the caveat that even changes to the DOM tree that don't affect rendering might affect the accessibility tree. Luckily the accessibility layer is already notified whenever there's a change to the DOM tree, so we could leverage that existing code to know when there's been a mutation.

Note that I don't think it would be a good idea to just clear the cache every time there's a tree mutation. A sequence of tree mutations would likely result in adding data to the cache and then clearing it again for every operation, which would just hurt performance. The cache should be off while the tree is changing.

So, how about this:

* Public WebKit API that says "please turn on the cache until the tree changes".
* WebCore automatically turns off the cache at the next tree mutation - it doesn't just clear it, it turns off caching until it's explicitly enabled again.

That way, turning on the cache is just a *hint* that says "I'm probably going to do a bunch of read-only operations that would be faster with caching enabled", and there's no need to turn it off.

[Ryosuke Niwa]

(In reply to comment #31)
> * Public WebKit API that says "please turn on the cache until the tree changes".
> * WebCore automatically turns off the cache at the next tree mutation - it doesn't just clear it, it turns off caching until it's explicitly enabled again.
> 
> That way, turning on the cache is just a *hint* that says "I'm probably going to do a bunch of read-only operations that would be faster with caching enabled", and there's no need to turn it off.

That sounds like a great solution given the constraints.

[James Robinson]

(In reply to comment #31)
> That could work, with the caveat that even changes to the DOM tree that don't affect rendering might affect the accessibility tree. Luckily the accessibility layer is already notified whenever there's a change to the DOM tree, so we could leverage that existing code to know when there's been a mutation.
> 
> Note that I don't think it would be a good idea to just clear the cache every time there's a tree mutation. A sequence of tree mutations would likely result in adding data to the cache and then clearing it again for every operation, which would just hurt performance. The cache should be off while the tree is changing.
> 
> So, how about this:
> 
> * Public WebKit API that says "please turn on the cache until the tree changes".
> * WebCore automatically turns off the cache at the next tree mutation - it doesn't just clear it, it turns off caching until it's explicitly enabled again.

Does this mean the cache can be rebuilt from a partially-invalid state the next time it's enabled?

> 
> That way, turning on the cache is just a *hint* that says "I'm probably going to do a bunch of read-only operations that would be faster with caching enabled", and there's no need to turn it off.

I think you should add a control to explicitly drop the cache if it's memory intensive and the caller (chromium/whomever) has a time at which they know they won't access it again.

[Dominic Mazzoni]

(In reply to comment #33)
> (In reply to comment #31)
> > That could work, with the caveat that even changes to the DOM tree that don't affect rendering might affect the accessibility tree. Luckily the accessibility layer is already notified whenever there's a change to the DOM tree, so we could leverage that existing code to know when there's been a mutation.
> > 
> > Note that I don't think it would be a good idea to just clear the cache every time there's a tree mutation. A sequence of tree mutations would likely result in adding data to the cache and then clearing it again for every operation, which would just hurt performance. The cache should be off while the tree is changing.
> > 
> > So, how about this:
> > 
> > * Public WebKit API that says "please turn on the cache until the tree changes".
> > * WebCore automatically turns off the cache at the next tree mutation - it doesn't just clear it, it turns off caching until it's explicitly enabled again.
> 
> Does this mean the cache can be rebuilt from a partially-invalid state the next time it's enabled?

No, once the tree mutates, the entire cache is invalid.

> > That way, turning on the cache is just a *hint* that says "I'm probably going to do a bunch of read-only operations that would be faster with caching enabled", and there's no need to turn it off.
> 
> I think you should add a control to explicitly drop the cache if it's memory intensive and the caller (chromium/whomever) has a time at which they know they won't access it again.

OK, so that sounds like I should go back to something closer to my previous approach without RAII (https://bugs.webkit.org/attachment.cgi?id=182462&action=review) and just add the code to automatically stop caching when the tree changes.

[James Robinson]

(In reply to comment #34)
> > > * WebCore automatically turns off the cache at the next tree mutation - it doesn't just clear it, it turns off caching until it's explicitly enabled again.
> > 
> > Does this mean the cache can be rebuilt from a partially-invalid state the next time it's enabled?
> 
> No, once the tree mutates, the entire cache is invalid.

Then why not clear the cache when the tree mutates?  I have no idea why we would want to keep an invalid cache around.

[Dominic Mazzoni]

(In reply to comment #35)
> Then why not clear the cache when the tree mutates?  I have no idea why we would want to keep an invalid cache around.

Sorry, I wasn't clear. Yes, I agree, clear the cache when the tree mutates - I was saying we should not only clear it, we should disable it (stop adding to it) until told to start caching again.

[Dominic Mazzoni]

Created attachment 184705 [details]
Patch

[Early Warning System Bot]

Comment on attachment 184705 [details]
Patch

Attachment 184705 [details] did not pass qt-ews (qt):
Output: http://queues.webkit.org/results/16119234

[Peter Beverloo (cr-android ews)]

Comment on attachment 184705 [details]
Patch

Attachment 184705 [details] did not pass cr-android-ews (chromium-android):
Output: http://queues.webkit.org/results/16121258

[Early Warning System Bot]

Comment on attachment 184705 [details]
Patch

Attachment 184705 [details] did not pass qt-wk2-ews (qt):
Output: http://queues.webkit.org/results/16111538

[Dominic Mazzoni]

Created attachment 184753 [details]
Patch

[Ryosuke Niwa]

Comment on attachment 184753 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=184753&action=review

Don't you need to call stopCachingComputedObjectAttributes() in Document::recalcStyle? I thought that was the whole point of this approach?

> Source/WebCore/accessibility/AXObjectCache.cpp:98
> +        CachedAXObjectAttributes* attributes = new CachedAXObjectAttributes();

Please adopt the pointer here instead.

[Dominic Mazzoni]

(In reply to comment #42)
> (From update of attachment 184753 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=184753&action=review
> 
> Don't you need to call stopCachingComputedObjectAttributes() in Document::recalcStyle? I thought that was the whole point of this approach?

Changes to the DOM or Render tree that affect the Accessibility tree already call AXObjectCache::postNotification (sometimes indirectly via another AXObjectCache method), which is why I added the calls to stopCachingComputedObjectAttributes there.

recalcStyle wouldn't be sufficient anyway - there are DOM mutations that can affect accessibility even if they don't affect rendering.

> > Source/WebCore/accessibility/AXObjectCache.cpp:98
> > +        CachedAXObjectAttributes* attributes = new CachedAXObjectAttributes();
> 
> Please adopt the pointer here instead.

Sure.

[Dominic Mazzoni]

Created attachment 184776 [details]
Patch

[Ryosuke Niwa]

Comment on attachment 184776 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=184776&action=review

> Source/WebCore/accessibility/AXObjectCache.cpp:98
> +        RefPtr<CachedAXObjectAttributes> attributes = adoptRef(new CachedAXObjectAttributes());

Please add create function to CachedAXObjectAttributes and call new there. Don't forget to make the constructor private.
I don't understand why this needs to be RefCounted though… this object appears to have exactly one owner: m_idMapping.

> Source/WebCore/accessibility/AXObjectCache.cpp:840
> +        m_computedObjectAttributeCache = new AXComputedObjectAttributeCache();

Please add a create function to AXComputedObjectAttributeCache and call new there. Also please make the constructor private
so that we don't forget to adoptPtr or adoptRef like we do here.

> Source/WebCore/accessibility/AXObjectCache.h:55
> +class AXComputedObjectAttributeCache : public RefCounted<AXComputedObjectAttributeCache> {

This class certainly doesn't need to be RefCounted, right?

> Source/WebCore/accessibility/AXObjectCache.h:61
> +    struct CachedAXObjectAttributes  : public RefCounted<CachedAXObjectAttributes> {

Is this object going to have multiple owners? If not, then please don't inherit from RefCounted and just use OwnPtr in HashMap below.
Also, do we even need to allocate this separately from the HashMap? Why can't we just have HashMap<AXID, CachedAXObjectAttributes> instead?

> Source/WebCore/accessibility/AXObjectCache.h:67
> +    HashMap<AXID, RefPtr<CachedAXObjectAttributes> > m_idMapping;

You could have stored OwnPtr<HashMap<AXID, RefPtr<CachedAXObjectAttributes> > > directly in AXObjectCache but it's your call.

> Source/WebCore/accessibility/AXObjectCache.h:200
> +    void cacheComputedObjectAttributesUntilTreeMutates();

Since the other method is called stopCachingComputedObjectAttributes, I would call this one startCachingComputedObjectAttributesUntilTreeMutates

> Source/WebCore/accessibility/AccessibilityRenderObject.cpp:1137
> +        AccessibilityObjectInclusion ignored = attributeCache->getIgnored(axObjectID());
> +        if (ignored == IgnoreObject)
> +            return true;
> +        if (ignored == IncludeObject)
> +            return false;

Why don't we just store the boolean? It'll make this code much simpler.
Also, if you're sticking with enum, we should be using switch here instead.

[Dominic Mazzoni]

Comment on attachment 184776 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=184776&action=review

>> Source/WebCore/accessibility/AXObjectCache.cpp:98
>> +        RefPtr<CachedAXObjectAttributes> attributes = adoptRef(new CachedAXObjectAttributes());
> 
> Please add create function to CachedAXObjectAttributes and call new there. Don't forget to make the constructor private.
> I don't understand why this needs to be RefCounted though… this object appears to have exactly one owner: m_idMapping.

Switched to OwnPtr.

>> Source/WebCore/accessibility/AXObjectCache.cpp:840
>> +        m_computedObjectAttributeCache = new AXComputedObjectAttributeCache();
> 
> Please add a create function to AXComputedObjectAttributeCache and call new there. Also please make the constructor private
> so that we don't forget to adoptPtr or adoptRef like we do here.

Done.

>> Source/WebCore/accessibility/AXObjectCache.h:61
>> +    struct CachedAXObjectAttributes  : public RefCounted<CachedAXObjectAttributes> {
> 
> Is this object going to have multiple owners? If not, then please don't inherit from RefCounted and just use OwnPtr in HashMap below.
> Also, do we even need to allocate this separately from the HashMap? Why can't we just have HashMap<AXID, CachedAXObjectAttributes> instead?

If this struct grew larger, is there a way to avoid a copy when you add to it? For example:

CachedAXObjectAttributes attributes;
... initialize several members
m_idMapping.set(id, attributes);  <-- this requires copying

It doesn't matter for now, so let's go with the simpler design.

>> Source/WebCore/accessibility/AXObjectCache.h:67
>> +    HashMap<AXID, RefPtr<CachedAXObjectAttributes> > m_idMapping;
> 
> You could have stored OwnPtr<HashMap<AXID, RefPtr<CachedAXObjectAttributes> > > directly in AXObjectCache but it's your call.

I expect to add a few more attributes to CachedAXObjectAttributes. If each one will have its own getter and setter, I'd prefer a separate class.

>> Source/WebCore/accessibility/AXObjectCache.h:200
>> +    void cacheComputedObjectAttributesUntilTreeMutates();
> 
> Since the other method is called stopCachingComputedObjectAttributes, I would call this one startCachingComputedObjectAttributesUntilTreeMutates

Done

>> Source/WebCore/accessibility/AccessibilityRenderObject.cpp:1137
>> +            return false;
> 
> Why don't we just store the boolean? It'll make this code much simpler.
> Also, if you're sticking with enum, we should be using switch here instead.

We can't use a boolean once there's more than one attribute in CachedAXObjectAttributes; it may be that another attribute is cached but |ignored| is still unknown.

Another approach would be to require that all of the values of CachedAXObjectAttributes must be valid or none of them are; I'll re-evaluate when I add the next attribute. I made it a switch for now.

[Dominic Mazzoni]

Created attachment 184830 [details]
Patch

[Ryosuke Niwa]

Comment on attachment 184830 [details]
Patch

Please add an assertion in Document::styleRecalc and other places where the cache must have been disabled so that we may detect any bugs should we introduce them in the future.

[Dominic Mazzoni]

Thanks. I think that the end of style recalc calls postNotification with a LayoutComplete notification, but I'll double-check that and add an assert if needed.

Chris, I'd appreciate it if you could take another look too. In particular, please check the places where I'm clearing the cache and let me know if you think anything's missing.

[chris fleizach]

Comment on attachment 184830 [details]
Patch

are you stopping caching when 
childrenChanged() is called or handleAriaRoleChanged() is called, or labelChanged()?
i suspect all of those could change isIgnored values

also, how does this interact with AccessibilityObject::cachedIsIgnoredValue()? are there now two cached isIgnored values?

[Dominic Mazzoni]

I put the call to stopCachingComputedObjectAttributes at
the top of postNotification because by design, any change that
should affect the accessibility tree should already call
postNotification. On Win, GTK, and Chromium, it's a bug if
the accessibility tree changes and postNotification isn't
called.

I checked these specific cases to be sure:

(In reply to comment #48)
> (From update of attachment 184830 [details])
> Please add an assertion in Document::styleRecalc and other places where the cache must have been disabled so that we may detect any bugs should we introduce them in the future.

When Document::recalcStyle is called, that calls FrameView::layout if
there were any changes to any styles, and that will call
AXObjectCache::postNotification, which stops this cache.
Since there are a few cases that layout without a style change
but not vice-versa, it seems reasonable to stop the cache on
layout.

(In reply to comment #50)
> (From update of attachment 184830 [details])
> are you stopping caching when 
> childrenChanged() is called or handleAriaRoleChanged() is called, or labelChanged()?
> i suspect all of those could change isIgnored values

childrenChanged calls postNotification.

labelChanged() calls postNotification on the corresponding
control, which will have the same effect.

handleAriaRoleChanged() calls postNotification only if the
ignored value changed - but, that's the only case that
affects the cache anyway. To be more future-proof, I could call stopCachingComputedObjectAttributes() at the top of
handleAriaRoleChanged anyway.

I checked all of the cases handled in
AXObjectCache::handleAttributeChanged - all of them call
postNotification if there were any changes to the accessibility
tree.

> also, how does this interact with AccessibilityObject::cachedIsIgnoredValue()? are there now two cached isIgnored values?

Yes. They serve very different purposes. I suggest we rename cachedIsIgnoredValue to lastKnownIsIgnoredValue, that will make
the difference more clear. Here's the
difference between the two:

* AXComputedObjectAttributeCache::getIgnored is the current value of accessibilityIsIgnored, if known to be current. It's thrown out as soon as the tree is mutated in any way, because a change to any one node can have far-reaching effects on isIgnored. It's used so we don't have to keep recomputing it over and over on the same object when the tree hasn't changed.

* AXObject::cachedIsIgnoredValue is the last known value of accessibilityIsIgnored. It's used so that when an object goes from ignored to not ignored or vice-versa, a ChildrenChanged notification can be fired on its parent - this is important because from the point of view of AT, a node in the accessibility tree was *created* or *destroyed*.

I filed https://bugs.webkit.org/show_bug.cgi?id=108238 for the rename idea.

[Dominic Mazzoni]

OK, will land later today if there's no more feedback.

[Dominic Mazzoni]

Created attachment 186126 [details]
Patch for landing

[WebKit Review Bot]

Comment on attachment 186126 [details]
Patch for landing

Clearing flags on attachment: 186126

Committed r141655: <http://trac.webkit.org/changeset/141655>

[WebKit Review Bot]

All reviewed patches have been landed.  Closing bug.

[Csaba Osztrogonác]

(In reply to comment #54)
> (From update of attachment 186126 [details])
> Clearing flags on attachment: 186126
> 
> Committed r141655: <http://trac.webkit.org/changeset/141655>

It broke the Qt build with the folloeing error:
/ramdisk/qt-linux-release/build/WebKitBuild/Release/lib/libQt5WebKit.so: undefined reference to `WebCore::AXObjectCache::startCachingComputedObjectAttributesUntilTreeMutates()'
collect2: ld returned 1 exit status
make[4]: *** [tst_qobjectbridge] Error 1

It seems there is a serious build system bug somewhere in Qt project files,
because EWS didn't notice this error and only revealed by a clean build.
I don't have any time for this bug, CC Qt developers, who can fix this bug.
(Now all Qt buildbots and EWS bots are red because of this bug and unable
to catch any build/layout regression.)

[Simon Hausmann]

(In reply to comment #56)
> (In reply to comment #54)
> > (From update of attachment 186126 [details] [details])
> > Clearing flags on attachment: 186126
> > 
> > Committed r141655: <http://trac.webkit.org/changeset/141655>
> 
> It broke the Qt build with the folloeing error:
> /ramdisk/qt-linux-release/build/WebKitBuild/Release/lib/libQt5WebKit.so: undefined reference to `WebCore::AXObjectCache::startCachingComputedObjectAttributesUntilTreeMutates()'
> collect2: ld returned 1 exit status
> make[4]: *** [tst_qobjectbridge] Error 1
> 
> It seems there is a serious build system bug somewhere in Qt project files,
> because EWS didn't notice this error and only revealed by a clean build.
> I don't have any time for this bug, CC Qt developers, who can fix this bug.
> (Now all Qt buildbots and EWS bots are red because of this bug and unable
> to catch any build/layout regression.)

Fixed a17n disabled build in http://trac.webkit.org/changeset/141694