1301829 - limit number of mutation events under same accessible

Status: NEW

(Core :: Disability Access APIs, enhancement, P3)

Description

[alexander :surkov (:asurkov)]

Attachment: patch

Comment 1

[alexander :surkov (:asurkov)]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=ac63aec25291

Comment 2

[alexander :surkov (:asurkov)]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=84ed96f034e0

Comment 3

[Yura Zenevich [:yzen] (please use "needinfo")]

Comment on attachment 8789962 [details] [diff] [review]
patch

Review of attachment 8789962 [details] [diff] [review]:
-----------------------------------------------------------------

looks reasonable with some naming concerns.. Also, I would ask an additional set of eyes, as I'm not entirely sure how parent recreation stuff could affect anything such as AT's.

::: accessible/base/EventTree.cpp
@@ +189,5 @@
> +      *node = Move((*node)->mNext);
> +      break;
> +    }
> +    node = &(*node)->mNext;
> +  }    

nit: whitespace

::: accessible/base/EventTree.h
@@ +86,5 @@
> +   * inserts its parent node into the event tree, if not yet there.
> +   *
> +   * Return true if the node object is destroyed.
> +   */
> +  bool DieIfHaveTo();

It doesn't really kill it since we hide and then show the tree. I think we should have a better name for this:
something with "rebuild", also these conditional procedures seem to be named Maybe... more often so maybe we can stick to that?

::: accessible/tests/mochitest/events/test_coalescence.html
@@ +536,5 @@
> +
> +      this.invoke = function shrinkShowEvents_invoke()
> +      {
> +        for (var i = 0; i <= 512; i++) {
> +          var tn = document.createTextNode(`${i};`);

nit tn name and var->let

Comment 4

[alexander :surkov (:asurkov)]

(In reply to Yura Zenevich [:yzen] from comment #3)
> Comment on attachment 8789962 [details] [diff] [review]
> patch
> 
> Review of attachment 8789962 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> looks reasonable with some naming concerns.. Also, I would ask an additional
> set of eyes, as I'm not entirely sure how parent recreation stuff could
> affect anything such as AT's.

you mean general kind of eyes, somebody like Marco or Jamie? 

AT will update the buffer, and that's it. All I can think of the tree mutations may affect on performance (both us and AT), but in this particular case, since we have many mutation events under a node, then at some point it should be faster to re render the whole parent, instead of processing all events.

> ::: accessible/base/EventTree.h
> @@ +86,5 @@
> > +   * inserts its parent node into the event tree, if not yet there.
> > +   *
> > +   * Return true if the node object is destroyed.
> > +   */
> > +  bool DieIfHaveTo();
> 
> It doesn't really kill it since we hide and then show the tree.

it literally kills the node, if a node is not referred by anyone, then it is destroyed

> I think we
> should have a better name for this:
> something with "rebuild", also these conditional procedures seem to be named
> Maybe... more often so maybe we can stick to that?

I'm good with MaybeDie if you like it more. IfHaveTo sounds more pathetical imo :)

Comment 5

[James Teh [:Jamie]]

I don't really understand exactly what this change does. However:

(In reply to alexander :surkov from comment #4)
> > I'm not entirely sure how parent recreation stuff could
> > affect anything such as AT's.
> AT will update the buffer, and that's it. All I can think of the tree
> mutations may affect on performance (both us and AT), but in this particular
> case, since we have many mutation events under a node, then at some point it
> should be faster to re render the whole parent, instead of processing all
> events.

If I understand you correctly, what you're trying to do here is coalesce many mutation events under the same tree into one event on the parent. That is, if the majority of a subtree is mutating, just rebuild the entire subtree. If so, I guess that makes sense. One thing that concerns me, though, is the mention of "parent recreation". I'm unclear as to exactly how these events are being coalesced. If you recreate the root of the tree, I'm concerned this will actually mean that this root gets removed and then reinserted into the parent above it. In NVDA's case, that will cause the parent above to be re-rendered, which is actually much worse than handling lots of events. Let's use an example:

body {
  node1 {
    node1a
    node1b
  }
  node2
}

Let's say node1a and node1b mutate and that causes us to hit the limit for node1. That means node1 will get re-created. That in turn fires a textRemoved and textInserted on body. NVDA will thus re-render body, which will render not only node1, but node2 as well.

Is this what's proposed? or is it something else?

Comment 6

[alexander :surkov (:asurkov)]

right, that was the idea, node1 gets hide and show events, reorder event on body, no text remove/inserted I think as text has not been changed. Are there other approaches? The more events we have, the more they bit us, at some point it has to be cheaper to rebuild the whole subtree instead of processing thousands of events. I'm not yet sure what numbers are, but I assume it's likely two different numbers for browser and for screen readers.

Comment 7

[James Teh [:Jamie]]

(In reply to alexander :surkov from comment #6)
> right, that was the idea, node1 gets hide and show events, reorder event on
> body, no text remove/inserted I think as text has not been changed.

If there's a reorder on body, that suggests a child was added or removed. I would have thought that would be accompanied by textInserted/Removed for the same reason. Does node1 actually get a new accessible (i.e. different unique id and old node1 references die)?

The problem with this approach is that the whole of body has to be invalidated by ATs (and for NVDA this means a re-render), even though only node1's subtree actually changed.

> Are
> there other approaches?

Fire reorder on node1, not body. That suggests that node1's subtree has changed, not the whole of body. The accessible for node1 must remain the same, even though its descendants might change.

Comment 8

[alexander :surkov (:asurkov)]

(In reply to James Teh [:Jamie] from comment #7)
> (In reply to alexander :surkov from comment #6)
> > right, that was the idea, node1 gets hide and show events, reorder event on
> > body, no text remove/inserted I think as text has not been changed.
> 
> If there's a reorder on body, that suggests a child was added or removed. I
> would have thought that would be accompanied by textInserted/Removed for the
> same reason.

I think Firefox sometimes makes some text change events coalescence, for example, if a continuous sequence of children was removed, then only one text removed event is fired. For that reason, if no text has been changed, then I would argue no text events should be fired.

> Does node1 actually get a new accessible (i.e. different unique
> id and old node1 references die)?

it's not changed, hide/show events are fake events in this case

> The problem with this approach is that the whole of body has to be
> invalidated by ATs (and for NVDA this means a re-render), even though only
> node1's subtree actually changed.

is there any AT perf differences between processing thousands of events vs re-rendering thousands of nodes? is event delivering is fast enough comparing to fetching IAccessible children?

> > Are
> > there other approaches?
> 
> Fire reorder on node1, not body. That suggests that node1's subtree has
> changed, not the whole of body. The accessible for node1 must remain the
> same, even though its descendants might change.

what about show/hide events?

Comment 9

[alexander :surkov (:asurkov)]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=c25454605f8e

Comment 10

[alexander :surkov (:asurkov)]

Marco, can you run the build for a while [1], whether it feels slower or faster than nightly one?

[1] https://archive.mozilla.org/pub/firefox/try-builds/[e-mail]-c25454605f8eece77e2573ff9cd5d2c6d975c0a1/

Comment 11

[James Teh [:Jamie]]

(In reply to alexander :surkov from comment #8)
> > If there's a reorder on body, that suggests a child was added or removed. I
> > would have thought that would be accompanied by textInserted/Removed for the
> > same reason.
> I think Firefox sometimes makes some text change events coalescence, for
> example, if a continuous sequence of children was removed, then only one
> text removed event is fired. For that reason, if no text has been changed,
> then I would argue no text events should be fired.

I guess this node's children haven't actually changed; in this example, node1 is still the same node and it stayed where it was. However, that's also why I don't think reorder is appropriate on this parent node (body in this example).

> is there any AT perf differences between processing thousands of events vs
> re-rendering thousands of nodes? is event delivering is fast enough
> comparing to fetching IAccessible children?

NVDA's buffer actually coalesces most events itself, processing at 100 ms intervals. We did this precisely to avoid excessive rendering due to many events. You're right: too many events is definitely a bad thing, especially for out-proc. That said, rendering thousands of nodes is also very bad, especially when most of them haven't even changed.

> > Fire reorder on node1, not body. That suggests that node1's subtree has
> > changed, not the whole of body.
> what about show/hide events?
A hide event requires us to remove the node and a show event requires us to add the node. The problem with this is that adding a node next to other siblings is difficult. We'd need to figure out where to place it, plus we might actually choose to render something very different based on an ancestor (e.g. aria-label overriding). Our coalescence makes this even harder. Therefore, we always re-render subtrees, never add/remove individual nodes.

Regardless of our own implementation, I think reorder on node1 (in this example) is more appropriate. You're saying "some stuff changed in node1", which is a signal to ATs to re-evaluate the subtree. Hide/show suggests "node1 itself went invisible/was removed", then "node1 became visible/was added". But it's the same node1 accessible, so actually, it didn't get removed or added; it (and its subtree) just changed.

Comment 12

[Marco Zehe (:MarcoZ)]

I ran with this try build all morning, and didn't see anything bad. I think I did see a bit of performance gain here and there, and no performance losses. Facebook was also quite OK, which is always my benchmark for a complex and usually pretty laggy web app.

Comment 13

[alexander :surkov (:asurkov)]

event coalescence screw us, we have some of o^2 processing, which is hard to remove. One way to resolve it is to keep our event tree small, which I tried to make by this patch. Another option is to remove coalescence at all, but that might emit thousands of events, and may be bad for AT who doesn't coalesce events on their own. There's a 3d option to improve existing algorithms to process trees fast, but that needs some hard work, and I'm not sure if this can that successful in performance as small trees.

I'm good with reorder on node1, that seems logical to me. However I'm not certain where show/hide should go. Should we do not emit them at all? I'm curious if there are any ATs who ignore reorder, but it is based on show/hide notifications instead.

Comment 14

[alexander :surkov (:asurkov)]

I'm not yet confident about how to proceed it. If we fired show/hide/reorder on same node, then would it make the things any better, since AT don't usually rely on both show/hide and reorder. Jamie, your insight is welcome.

Comment 15

[James Teh [:Jamie]]

(In reply to alexander :surkov from comment #13)
> I'm
> curious if there are any ATs who ignore reorder, but it is based on
> show/hide notifications instead.

Honestly, I'm not sure. You'd need to ask the other AT vendors.

(In reply to alexander :surkov from comment #14)
> I'm not yet confident about how to proceed it. If we fired show/hide/reorder
> on same node, then would it make the things any better, since AT don't
> usually rely on both show/hide and reorder. Jamie, your insight is welcome.

I can only speak for NVDA here.
* For browse mode, we never use show and hide, so this wouldn't hurt us.
* We do use show to handle content added to a live region that does not have a text parent; e.g. a row added to a table. So, if this happened on a table row where the table was a live region, that would cause us to report that entire row. However, that is probably the best experience we can hope for in this case anyway.
* In conclusion, I would suggest you fire hide, then show, then reorder. But I disclaim all liability for any unintended consequences. :) :)

Comment 16

[alexander :surkov (:asurkov)]

I've got some more data on it, it seems hide/show/reorder may work. I'll prepare though a try server build and a test case for manual check, just in case.

Comment 17

[David Bolter [:davidb] (NeedInfo me for attention)]

Setting wontfix 57 since I can't see us adding risk to hotpaths this late.

Comment 18

[alexander :surkov (:asurkov)]

assigning it to myself to investigate the issue further.

Comment 19

[David Bolter [:davidb] (NeedInfo me for attention)]

Might be a good time to revisit this?

Comment 20

[alexander :surkov (:asurkov)]

(In reply to David Bolter [:davidb] (NeedInfo me for attention) from comment #19)
> Might be a good time to revisit this?

I'm on it as part of bug 1368784, looking for a possible ways to implement this idea.

Comment 21

[Sylvestre Ledru [:Sylvestre]]

Moving to p3 because no activity for at least 24 weeks.

Comment 22

[BugBot [:suhaib / :marco/ :calixte]]

The bug assignee is inactive on Bugzilla, so the assignee is being reset.