Accessibility/EventCoalescing
Here we list rules to coalesce by. Given a queue of events to fire, which events can be filtered (removed/ignored)?
Events to coalesce
Some accessible events are subject of coalescence, i.e. events are filtered before delivery to AT. These events can be divided into groups.
Mutation events
There are show, hide and reorder accessible mutation events.
Show event
Show event is fired when accessible object should be created. The accessible object is created when its DOM node is appended to the DOM tree or is shown.
Hide event
Hide event is fired when accessible object is about to destroy. The accessible should be destroyed when its DOM node is removed from DOM or hidden.
Reorder event
Reorder event is fired for accessible which children were changed. Therefore reorder event is tightly related with show/hide events so that reorder event is created for every show/hide event.
However reorder event can be appended to the queue for coalescence without corresponding show event. It happens in the case when DOM node is appended (or shown) is not accessible but it might be accessible after timeout (because the DOM node frame is not created yet).
Text events
There are insert, remove and change text events. The insert event is fired when accessible text is inserted, remove when removed and change when portion of text is changed, i.e. when old text is replaced on new one.
The accessible text can be built from text nodes and DOM elements, for example, HTML br element is treated as caret return character, the same time arbitrary DOM elements within text container accessible are treated as special characters (called as embedded characters) of accessible text, so that, for example, HTML form controls can be a part of accessible text.
The text events are fired when data of text node is changed, text node or element are appended or removed. Text change events should be merged (coalesced) to prevent unnecessary AT processing of these events. For example, if children of HTML p element are removed
<p>text<h1>heading</h1>text</p>
then only one text remove event should be fired.
Other events
In general other events aren't subject of coalescence from the tree, usually dupe events (i.e. events for the same target) are removed. However no events are expected from the accessible subtree that is destroyed, therefore ideally events should be coalesced with the hide events.
Test area
Test list
- Lazy frame construction insertBefore, bug 570500 (original test, bug 568430).
- Lazy frame construction appendChild, bug 570500, (original test, bug 568430)
- JS Progressive Raytracer, see bug 565452
- Table mutation, see bug 522847
- bug 521973 in attachments (bz said the test is quick with a11y)
Results of tests
All tests are run on my local machine: Intel Core i5, 4Gb, Windows 7 Home extended. Some tests consist of two parts: sync processing and async processing. If "failed" instead a number then I was failed to get results after 2 minutes. Every test run three times, tables present average value. Windows 7 SDK Accessible Event Watcher (AEW) (watching in context events) tool was used as AT.
Additional tests with NVDA were run by Marco on an Intel Core2Duo 6.67 gHz, 3 B of RAM, Windows 7 X64 with NVDA 2010.1.
Reference values table (06 June, trunk)
Date/Test | AT? | LFC insertBefore | LFC appendChild | JS PR Basic | JS PR Full | Table mutation | Remove children |
---|---|---|---|---|---|---|---|
no a11y | 89/3 ms | 1195/1012 ms | 1045ms | 17971ms | 595/582 ms | n/a | |
a11y | no AT | 1422/10155 ms | 3400/12904 ms | 7984 ms | failed | 1801/946 ms | 52214 /221 ms |
AEW | 1490/14727 ms | 3470/18956 ms | 8056 ms | failed | 1862/998 ms | 52056 /3836 ms | |
NVDA | 1581/33760 ms | 2503/37310 ms | 79500 | failed | failed | ?/? | |
no coalescence | no AT | 141/8957 ms | 1287/11440 ms | 7114ms | failed | 941/881 ms | 37865 /333 ms |
AEW | 129/16268 ms | 1273/20006 ms | 7275 ms | failed | 3399/3346 ms | 38498/13970 ms | |
NVDA | 134/33403 ms | 9283/39093 ms | 71239 ms | failed | 297000/297000 ms | ?/? | |
Firefox 3.6.4 | No AT | ??? | ??? | ??? | ??? | ??? | ?/? |
AEW | ??? | ??? | ??? | ??? | ??? | ?/? | |
NVDA | 134/89000 ms | failed | 115709 MS | failed | 15602/15401 MS | ?/? |
Performance improvements tracking table
Date/Test | AT? | LFC insertBefore | LFC appendChild | JS PR Basic | JS PR Full | Table mutation | Remove children |
---|---|---|---|---|---|---|---|
a11y | no AT | 1422/10155 ms | 3400/12904 ms | 7984 ms | failed | 1801/946 ms | 52214 /221 ms |
AEW | 1490/14727 ms | 3470/18956 ms | 8056 ms | failed | 1862/998 ms | 52056 /3836 ms | |
NVDA | 1581/33760 ms | 2503/37310 ms | 79500 | failed | failed | ?/? | |
07 June, bug 570532 | no AT | 139/9292 ms | 1321/11538 ms | 7176 ms | failed | 731/681 ms | 43251/337 ms |
AEW | 148/16700 ms | 1355/20957 ms | 7278 ms | failed | 3818/3768 ms | 42358/13778 ms | |
NVDA | 130/28800 ms | 970/38500 ms | 72300 ms | failed | 286000/286000 ms | ?/? | |
08 June, bug 570710 | no AT | 149/4030 ms | 1328/5790 ms | 3717 ms | failed | 930/878 ms | 25901/331 |
AEW | 159/11830 ms | 1322/15374 ms | 4296 ms | failed | 5612/5561 ms | 25019/13211 ms | |
NVDA | ?/? ms | ?/? ms | ? ms | ? | ?/? ms | ?/? | |
27 June, many bugs | no AT | 114/115 ms | 1227/1001 ms | 1175 ms | 20478 ms | 977/945 ms | 3639/118 |
AEW | 135/8180 ms | 1235/9354 ms | 2261 ms | 25178 ms | 992/955 ms | 3688/5314 | |
NVDA | 124/14080 ms | 957/15003 ms | 17578 ms | failed | 108044/108017 ms | 1844/4155 ms |
Current implementation
Hidden priority
If a node N is hidden, then any events in the subtree denoted by N are filtered.
Ancestral priority
If a node N has been shown or hidden, then the event is filtered if there is another event in the queue for an ancestor node A that has been shown or hidden.
If a node N has been reordered, then the event is filtered if there is another event in the queue for an ancestor node A that has been reordered.
Siblings
Siblings have the same priority. This could mean for example, that if an event for a node N is to be filtered, then this decision is likely applicable to the same event for all siblings of N.
Bugs/ideas
General performance bugs
These bugs might be split into several bugs while fixing.
- bug 565452 - Lots of seemingly unnecessary text change events; very slow code to generate them (perf improvement done on
bug 575052) bug 568430- Perf of insertBefore testcase much much slower than test with appendChild- bug 522847 - Terrible accessibility performance on this testcase
Bugs tracking (what we did and do)
- General improvements, get rid unnecessary query interfaces,
bug 541618 - Ignore layout changes that haven't affect on accessible tree, bug 570275.
- CreateTextChangeEventForNode traverses array twice, bug and patch is coming
Ideas tracking (what we can do)
- DOMNodeToHyperTextOffset is not performant
- Coalesce events against the accessible tree.
- Coalesce reorder events by their related show/hide events.
- Map accessible tree to ordered set.
Raw brain dump section
Ignorable Cases: For a node N and a descendant node D, can a hide event for D ever come after a hide event for N in gecko?
Fire Hose detection: Would it be useful to detect when the events/time_delta ratio is too large to bother with; after which (when the ratio meets a certain threshold) we could fire the latest event of each type?