WebKit Bugzilla
New
Browse
Log In
×
Sign in with GitHub
or
Remember my login
Create Account
·
Forgot Password
Forgotten password account recovery
RESOLVED FIXED
106497
AX: memoize expensive computation during blocks where tree doesn't change
https://bugs.webkit.org/show_bug.cgi?id=106497
Summary
AX: memoize expensive computation during blocks where tree doesn't change
Dominic Mazzoni
Reported
2013-01-09 15:10:04 PST
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.
Attachments
Patch
(7.55 KB, patch)
2013-01-09 15:40 PST
,
Dominic Mazzoni
no flags
Details
Formatted Diff
Diff
Patch
(23.50 KB, patch)
2013-01-11 11:34 PST
,
Dominic Mazzoni
no flags
Details
Formatted Diff
Diff
Patch
(26.08 KB, patch)
2013-01-11 13:49 PST
,
Dominic Mazzoni
no flags
Details
Formatted Diff
Diff
Patch
(26.73 KB, patch)
2013-01-11 15:03 PST
,
Dominic Mazzoni
no flags
Details
Formatted Diff
Diff
Patch
(27.51 KB, patch)
2013-01-12 00:36 PST
,
Dominic Mazzoni
no flags
Details
Formatted Diff
Diff
Patch
(27.57 KB, patch)
2013-01-12 00:56 PST
,
Dominic Mazzoni
no flags
Details
Formatted Diff
Diff
Patch
(28.18 KB, patch)
2013-01-24 00:37 PST
,
Dominic Mazzoni
no flags
Details
Formatted Diff
Diff
Patch
(14.82 KB, patch)
2013-01-25 02:09 PST
,
Dominic Mazzoni
no flags
Details
Formatted Diff
Diff
Patch
(14.82 KB, patch)
2013-01-25 07:51 PST
,
Dominic Mazzoni
no flags
Details
Formatted Diff
Diff
Patch
(14.83 KB, patch)
2013-01-25 11:07 PST
,
Dominic Mazzoni
no flags
Details
Formatted Diff
Diff
Patch
(15.09 KB, patch)
2013-01-25 15:55 PST
,
Dominic Mazzoni
no flags
Details
Formatted Diff
Diff
Patch for landing
(15.34 KB, patch)
2013-02-01 13:35 PST
,
Dominic Mazzoni
no flags
Details
Formatted Diff
Diff
Show Obsolete
(11)
View All
Add attachment
proposed patch, testcase, etc.
Dominic Mazzoni
Comment 1
2013-01-09 15:40:02 PST
Created
attachment 181999
[details]
Patch
Dominic Mazzoni
Comment 2
2013-01-09 15:40:53 PST
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
Comment 3
2013-01-10 14:26:41 PST
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
Comment 4
2013-01-10 15:41:08 PST
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
Comment 5
2013-01-11 11:34:14 PST
Created
attachment 182384
[details]
Patch
WebKit Review Bot
Comment 6
2013-01-11 11:39:37 PST
Please wait for approval from
abarth@webkit.org
,
dglazkov@chromium.org
,
fishd@chromium.org
,
jamesr@chromium.org
or
tkent@chromium.org
before submitting, as this patch contains changes to the Chromium public API. See also
https://trac.webkit.org/wiki/ChromiumWebKitAPI
.
chris fleizach
Comment 7
2013-01-11 11:43:50 PST
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 8
2013-01-11 11:51:30 PST
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 9
2013-01-11 12:23:24 PST
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 10
2013-01-11 13:48:35 PST
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
Comment 11
2013-01-11 13:49:12 PST
Created
attachment 182411
[details]
Patch
Build Bot
Comment 12
2013-01-11 14:57:45 PST
Comment on
attachment 182411
[details]
Patch
Attachment 182411
[details]
did not pass mac-ews (mac): Output:
http://queues.webkit.org/results/15833022
Dominic Mazzoni
Comment 13
2013-01-11 15:03:29 PST
Created
attachment 182425
[details]
Patch
chris fleizach
Comment 14
2013-01-11 15:37:33 PST
looks good. lets just wait to make sure it builds
Peter Beverloo (cr-android ews)
Comment 15
2013-01-11 16:56:19 PST
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
Comment 16
2013-01-12 00:36:52 PST
Created
attachment 182461
[details]
Patch
Early Warning System Bot
Comment 17
2013-01-12 00:43:01 PST
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 18
2013-01-12 00:49:57 PST
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
Comment 19
2013-01-12 00:56:21 PST
Created
attachment 182462
[details]
Patch
Dominic Mazzoni
Comment 20
2013-01-13 23:03:55 PST
(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
Comment 21
2013-01-14 00:04:55 PST
(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
Comment 22
2013-01-14 14:04:59 PST
(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
Comment 23
2013-01-14 14:13:24 PST
(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
Comment 24
2013-01-14 14:22:18 PST
(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
Comment 25
2013-01-24 00:37:18 PST
Created
attachment 184425
[details]
Patch
Dominic Mazzoni
Comment 26
2013-01-24 00:52:53 PST
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 27
2013-01-24 01:10:26 PST
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 28
2013-01-24 13:53:33 PST
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
Comment 29
2013-01-24 14:09:52 PST
(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
Comment 30
2013-01-24 14:33:42 PST
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
Comment 31
2013-01-24 15:44:37 PST
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
Comment 32
2013-01-24 15:47:10 PST
(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
Comment 33
2013-01-24 15:50:17 PST
(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
Comment 34
2013-01-24 16:01:05 PST
(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
Comment 35
2013-01-24 16:14:53 PST
(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
Comment 36
2013-01-24 16:20:44 PST
(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
Comment 37
2013-01-25 02:09:21 PST
Created
attachment 184705
[details]
Patch
Early Warning System Bot
Comment 38
2013-01-25 02:18:41 PST
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 39
2013-01-25 02:30:01 PST
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 40
2013-01-25 04:39:12 PST
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
Comment 41
2013-01-25 07:51:03 PST
Created
attachment 184753
[details]
Patch
Ryosuke Niwa
Comment 42
2013-01-25 10:45:53 PST
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
Comment 43
2013-01-25 11:07:20 PST
(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
Comment 44
2013-01-25 11:07:31 PST
Created
attachment 184776
[details]
Patch
Ryosuke Niwa
Comment 45
2013-01-25 11:55:52 PST
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 46
2013-01-25 15:53:48 PST
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
Comment 47
2013-01-25 15:55:08 PST
Created
attachment 184830
[details]
Patch
Ryosuke Niwa
Comment 48
2013-01-25 16:04:42 PST
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
Comment 49
2013-01-25 16:19:05 PST
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 50
2013-01-25 22:57:42 PST
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
Comment 51
2013-01-29 15:17:03 PST
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
Comment 52
2013-02-01 09:28:49 PST
OK, will land later today if there's no more feedback.
Dominic Mazzoni
Comment 53
2013-02-01 13:35:48 PST
Created
attachment 186126
[details]
Patch for landing
WebKit Review Bot
Comment 54
2013-02-01 15:52:15 PST
Comment on
attachment 186126
[details]
Patch for landing Clearing flags on attachment: 186126 Committed
r141655
: <
http://trac.webkit.org/changeset/141655
>
WebKit Review Bot
Comment 55
2013-02-01 15:52:23 PST
All reviewed patches have been landed. Closing bug.
Csaba Osztrogonác
Comment 56
2013-02-02 02:01:36 PST
(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
Comment 57
2013-02-02 07:37:25 PST
(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
Note
You need to
log in
before you can comment on or make changes to this bug.
Top of Page
Format For Printing
XML
Clone This Bug