Bug 22296 - Microtask model refactoring
Microtask model refactoring
Status: RESOLVED FIXED
Product: WHATWG
Classification: Unclassified
Component: HTML
unspecified
PC All
: P2 critical
: Unsorted
Assigned To: Ian 'Hixie' Hickson
contributor
:
Depends on: 22185
Blocks: 20821 22409 24724
  Show dependency treegraph
 
Reported: 2013-06-06 10:24 UTC by Anne
Modified: 2014-02-25 19:04 UTC (History)
16 users (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description Anne 2013-06-06 10:24:36 UTC
This is a follow-up of sorts to bug 22185.

Yehuda suggested turning the microtask processing into a loop where we keep emptying the queue for mutation observers and promises repeatedly until both are depleted. (Note that promises currently queue a task, but we want a hook for this kind of model instead.)
Comment 1 Ian 'Hixie' Hickson 2013-06-10 23:14:40 UTC
You should do this directly in the "invoke MutationObserver objects" algorithm in DOM core, right?
Comment 2 Anne 2013-06-11 06:38:52 UTC
So what Yehuda suggested was to remove step 3 from http://dom.spec.whatwg.org/#mutation-observers and instead have microtasks as a loop. The effect would be that promises and mutation observers run after each other until each queue is fully depleted (rather than mutation observers depleting itself in a tighter loop).
Comment 3 Ian 'Hixie' Hickson 2013-06-14 22:34:06 UTC
I recommend you just have DOM core have a single algorithm that does all the magic you want done between each task, whether that be mutation observers or some future stuff or whatever, and I just invoke that, once per iteration of the event loop.

(Futures don't do anything but queue tasks, right? They're not a way to jump ahead of the queue? If that's the case, it might be even better for futures to just use the "stable state" mechanism.)
Comment 4 Anne 2013-06-19 06:19:39 UTC
For promises (new name of futures) we want to use the same mechanism as mutation observers. The task queuing that happens now is a temporary hack. Basically there's a queue of promise notifications that needs to happen which is emptied each "turn" in a loop as just as with mutation observers more might happen. So we need to generalize that mechanism somehow.
Comment 5 Anne 2013-06-19 06:20:20 UTC
Object.observe() from ECMAScript 7 is something else that will want to participate in this down the road as I understand it.
Comment 6 Rafael Weinstein 2013-06-19 22:58:13 UTC
FWIW, Mark Miller and I plan to bang our heads together and come up with a strawman of what might work both for DOM and for near-future ECMAScript uses.

(Looking at the "needs abstracting" part of https://www.w3.org/Bugs/Public/show_bug.cgi?id=22185)
Comment 7 Rafael Weinstein 2013-07-01 15:14:22 UTC
Strawman Proposal:

Generalizing Microtasks => The Microtask Work Queue

In order to allow multiple types of work to take place at the timing currently described as a microtask checkpoint:

1) Replace the construct of "performing a microtask checkpoint" with "emptying the microtask work queue". Emptying the microtask work queue will process all pending items in FIFO order until there are none remaining:

while (!microtaskWorkQueue.empty()) {
  let microtask = microtaskWorkQueue.takeFirst();
  microtask.run();
}

2) Introduce the ability to "queue a microtask". Queuing a microtask appends a microtask to the end of the microtask work queue, and is allowed at any time.


Notes:

-Modifying the microtask delivery phase in this way means that the ordering which DOM Mutation Observers requires cannot naively be implemented by repeatedly queueing microtasks. Instead, DOM Mutation Observers will need to define a single microtask which is responsible for delivering to multiple observers when it is run, and for ensuring that it is always scheduled when there are pending mutation records to deliver to observers. It is likely that other microtask delivery types will need their own ordering (for example, present drafts of HTML Custom Element requires a specific order of delivery for lifecycle callbacks based on the structure of the DOM Tree).

-"Emptying the microtask work queue" will take place at the same three times that the microtask checkpoint is currently run:

-Immediately after every Buttom-most Script Entry Point exits.
-Immediately before every Task completes.
-When the HTML5 parser encounters a </script> (end script token).
Comment 8 Ian 'Hixie' Hickson 2013-07-02 22:07:05 UTC
What's the expected behaviour when one of these microtasks spins the event loop?
Comment 9 Ian 'Hixie' Hickson 2013-07-02 22:07:27 UTC
(see bug 20821 for background)
Comment 10 Domenic Denicola 2013-07-09 16:17:07 UTC
What is the expected behavior when one of these microtasks throws an exception?
Comment 11 Rafael Weinstein 2013-07-09 18:52:50 UTC
So I kind of feel like Mozilla should say what the right spec behavior is here since (I think, anyway) they have a more "real" implementation of showModalDialog.

In Blink, showModalDialog is pretty busted anyway, and our preference would be to disallow its use in any new contexts (i.e. it just throws if called inside a microtask). Possibly sync XHR as well (though it's event loop shouldn't have observable effects).

(In reply to comment #8)
> What's the expected behaviour when one of these microtasks spins the event
> loop?
Comment 12 Olli Pettay 2013-07-12 18:27:01 UTC
Note, also parsing may spin the event loop.

So, right now in Gecko all the scheduled (== have some records) MutationObservers are put into a list A and at the end of a microtask the
contents of that are moved to list B and A is now empty.
Then we iterate through B and call callbacks.
If one of the callbacks spins event loop, the rest of B need to wait until the
spinning ends. This may lead to postponing callback handling significantly.
However the order of MutationRecords per MutationObserver stays correct, since
even if the modalDialog causes new MutationRecords to be created in the main window, the scheduled, but not yet handled MutationObservers just queue
the records.

If modalDialog ends up using its own MutationObservers, they should work just fine, since they end up to list A, and then they are handled after copying to
list B'.

I think this is reasonable good behavior for MutationObservers (but should be
still ok to change if needed. The reason for the current behavior comes mostly 
from Gecko's sync XHR handling). This all would map easily to comment 7's
queue. MutationObservers form a separate unit within microtask delivery.


If Promises end up just queuing µts and MutationObservers use a separate subqueue
within the queue, the result is somewhat unexpected, since the ordering can be odd.
That can be actually issue even without nested event loop spinning.

(I don't know why Promises should use µts. Sounds a bit odd to me.)



/me continues thinking this issue...
Comment 13 Olli Pettay 2013-07-12 19:39:45 UTC
Anne explained the reasons for using µt (pretty much the same reasons as with MutationObserver)
Comment 14 Rafael Weinstein 2013-07-15 19:38:13 UTC
Yehuda commented in email:

Ideally, you want all mutation observers to run at the same time, not interleaved through other work. So if you resolve a promise that queues another promise resolution and mutates the DOM, you want the second promise to resolve so that if it too mutates the DOM you will only get a singe pass at handling mutation observers.

Similarly, you want to handle all O.o work together, and if a promise schedules another promise AND mutates an object, you want to wait until the other promise resolves so you handle object mutations together.

This is based on our experience with Ember, which began with a lot of interleaving, and broke a lot of coalescing optimizations we were attempting to make. It's not so much about priority, but about keeping the handling of observers together so that they can be coalesced.

"Priority" comes into it because doing mutation observers first and then promises would have a lot more interleaving.
Comment 15 Rafael Weinstein 2013-07-15 19:38:35 UTC
And I responded: 

I'm very nervous about making this work queue priority based. I feel
like what you've described here boils down to: you might be able to
get some perf gains by better coalescing types of work. This seems
like kind of a weak justification.

Prioritizing one type of work over another is going to allow for
better coalescing for the higher priority work and worse for the
lower-priority work. It's not obvious to me that one type will be
"lighter weight" than another because the real cost is what the
callback does.

Also, FIFO semantics means that if I want to go to the end of the line
(for whatever reason -- coalescing, etc...), it's simple.
Priority-queue means I have to know the priorities and be careful to
schedule myself after the right *type* of work.

To be clear: I have a nagging worry that Yehuda's mental model is
right: that we should have this kind of priority-based approach, I
just feel like we need a sound justification for more complex
semantics.

I'm not sure this is really a sound justification, but it's
interesting to note: Of the types of work we're yet aware of, we have:

-Promises
-Object.observe
-Custom Element callbacks
-MutationObservers

Of these, only the first is free of wanting a special ordering
*within* it's type of work. For FIFO semantics, this means that

(a) Each Promise would be a Microtask
(b) The later three would all have a "meta"-microtask that runs
something like this:
   (1) Make a copy of all pending callbacks
   (2) Clear pending callbacks
   (3) Order callbacks (this varies by type of work)
   (4) Deliver to all
   (5) Yield to the outer queue


As Mark observed when we discussed this with Adam, this, in effect,
creates *another* inner loop for these types which is a priority
queue.
Comment 16 Yehuda Katz 2013-07-16 19:48:43 UTC
(In reply to comment #15)
> And I responded: 
> 
> I'm very nervous about making this work queue priority based. I feel
> like what you've described here boils down to: you might be able to
> get some perf gains by better coalescing types of work. This seems
> like kind of a weak justification.

This is something we struggled with a lot in Ember. We initially had a staged queue that looked something like this:

* callbacks in Ember's equivalent of setImmediate
* Object observation callbacks
* DOM mutations
* Finalizers for explicitly destroyed objects

If any of the callbacks scheduled additional work, that work would be scheduled in another queue, to be run once the first one was completed.

This means that if an object observer triggered another object observer, the DOM mutations and finalizers would get called first, and then the next observer.

This is similar to the semantics you would expect from a simple FIFO queue.

As a practical matter, this was disastrous for us. Work that would be naturally coalesced (chained changes to objects, for example) got interspersed with work that touched the DOM, causing multiple DOM mutations when a single one would do.

In practice, there is a natural order of operations:

* Async I/O resolution (a.k.a promise resolution)
* Object mutations
* DOM mutations

To get the best performance, it is important for things to happen in this order where possible. If an object mutation triggers another promise resolution, which triggers another object mutation, you want ALL of these things to happen before you react to DOM mutations.

The reverse (DOM mutations triggering promise resolution) is far, far less common, and the opposite of the normal, expected data flow.

> 
> Prioritizing one type of work over another is going to allow for
> better coalescing for the higher priority work and worse for the
> lower-priority work. It's not obvious to me that one type will be
> "lighter weight" than another because the real cost is what the
> callback does.

See above. Data flows in a natural direction, and ordering the queues in that order produces coalescing benefits. This optimization was massive for us in practice.

> 
> Also, FIFO semantics means that if I want to go to the end of the line
> (for whatever reason -- coalescing, etc...), it's simple.
> Priority-queue means I have to know the priorities and be careful to
> schedule myself after the right *type* of work.
> 
> To be clear: I have a nagging worry that Yehuda's mental model is
> right: that we should have this kind of priority-based approach, I
> just feel like we need a sound justification for more complex
> semantics.
> 
> I'm not sure this is really a sound justification, but it's
> interesting to note: Of the types of work we're yet aware of, we have:
> 
> -Promises
> -Object.observe
> -Custom Element callbacks
> -MutationObservers
> 
> Of these, only the first is free of wanting a special ordering
> *within* it's type of work. For FIFO semantics, this means that

I think that Promise fast-forwarding means that promises also may want to be a meta-task, but I'm not 100% sure about that.

> 
> (a) Each Promise would be a Microtask
> (b) The later three would all have a "meta"-microtask that runs
> something like this:
>    (1) Make a copy of all pending callbacks
>    (2) Clear pending callbacks
>    (3) Order callbacks (this varies by type of work)
>    (4) Deliver to all
>    (5) Yield to the outer queue
> 
> 
> As Mark observed when we discussed this with Adam, this, in effect,
> creates *another* inner loop for these types which is a priority
> queue.
Comment 17 Rafael Weinstein 2013-07-18 17:44:25 UTC
@Yehuda,

I actually *want* to agree with you, but I'm not there.

I feel like you're just restating what you said before which is: we found this ordering to have perf benefits in practice.

The central problem I have with this view is that is rooted in an experience of being the only actor in the system. In your Ember implementation, there were different types of work, but only one Ember -- no other decoupled mechanism was at work.

Specifying this as a platform feature means that we must assume multiple *entirely* decoupled concerns operating via multiple types of work in the same work queue.

Not only do I believe that Ember found this processing ordering expedient, I know from experience (via MDV) that it is expedient for data-binding frameworks. My problem my lack of belief that the only kinds of actors in this system will be data-binding frameworks and that other kinds of actors have the same needs.

Lacking a robust justification to prioritize one actor vs another or one type of work vs another, I think the default behavior should be the simpler one, which is the FIFP queue.
Comment 18 Rafael Weinstein 2013-07-18 17:45:28 UTC
Sorry. FIFO queue.
Comment 19 Yehuda Katz 2013-07-18 17:58:38 UTC
You say "default behavior". Do you have in mind a mechanism for switching into the mode that is expedient for data binding?

I would also point out that several of these features (O.o, mutation observers) are designed for data binding, so the practical difference only occurs when data binding induces a data flow like the one I described in my previous comment.

Do you have any reason to believe that the approach I described would be WORSE for non-data binding cases that still made heavy use of promises and other end-of-microtask operations?

(In reply to comment #17)
> @Yehuda,
> 
> I actually *want* to agree with you, but I'm not there.
> 
> I feel like you're just restating what you said before which is: we found
> this ordering to have perf benefits in practice.
> 
> The central problem I have with this view is that is rooted in an experience
> of being the only actor in the system. In your Ember implementation, there
> were different types of work, but only one Ember -- no other decoupled
> mechanism was at work.
> 
> Specifying this as a platform feature means that we must assume multiple
> *entirely* decoupled concerns operating via multiple types of work in the
> same work queue.
> 
> Not only do I believe that Ember found this processing ordering expedient, I
> know from experience (via MDV) that it is expedient for data-binding
> frameworks. My problem my lack of belief that the only kinds of actors in
> this system will be data-binding frameworks and that other kinds of actors
> have the same needs.
> 
> Lacking a robust justification to prioritize one actor vs another or one
> type of work vs another, I think the default behavior should be the simpler
> one, which is the FIFP queue.
Comment 20 Rafael Weinstein 2013-07-18 19:06:41 UTC
(In reply to comment #19)
> You say "default behavior". Do you have in mind a mechanism for switching
> into the mode that is expedient for data binding?

Sorry, no. I wasn't meaning to imply switchable behavior. I should have said "our default position" should be to choose the simpler and more egalitarian approach.

> 
> I would also point out that several of these features (O.o, mutation
> observers) are designed for data binding, so the practical difference only
> occurs when data binding induces a data flow like the one I described in my
> previous comment.
> 
> Do you have any reason to believe that the approach I described would be
> WORSE for non-data binding cases that still made heavy use of promises and
> other end-of-microtask operations?

No. I have no basis for believing anything about non-databinding use cases.

> 
> (In reply to comment #17)
> > @Yehuda,
> > 
> > I actually *want* to agree with you, but I'm not there.
> > 
> > I feel like you're just restating what you said before which is: we found
> > this ordering to have perf benefits in practice.
> > 
> > The central problem I have with this view is that is rooted in an experience
> > of being the only actor in the system. In your Ember implementation, there
> > were different types of work, but only one Ember -- no other decoupled
> > mechanism was at work.
> > 
> > Specifying this as a platform feature means that we must assume multiple
> > *entirely* decoupled concerns operating via multiple types of work in the
> > same work queue.
> > 
> > Not only do I believe that Ember found this processing ordering expedient, I
> > know from experience (via MDV) that it is expedient for data-binding
> > frameworks. My problem my lack of belief that the only kinds of actors in
> > this system will be data-binding frameworks and that other kinds of actors
> > have the same needs.
> > 
> > Lacking a robust justification to prioritize one actor vs another or one
> > type of work vs another, I think the default behavior should be the simpler
> > one, which is the FIFP queue.
Comment 21 Yehuda Katz 2013-07-19 04:13:54 UTC
(In reply to comment #20)
> (In reply to comment #19)
> > You say "default behavior". Do you have in mind a mechanism for switching
> > into the mode that is expedient for data binding?
> 
> Sorry, no. I wasn't meaning to imply switchable behavior. I should have said
> "our default position" should be to choose the simpler and more egalitarian
> approach.

That means that for the case that requires interleaving-avoidance to get good performance (i.e. sophisticated cases), we're basically out of luck.

I'm going to continue to push back on this because interleaving was a very serious performance issue in our experience, and the only way to restore get good performance as the amount of scheduled events increased was to eliminate the interleaving.

> 
> > 
> > I would also point out that several of these features (O.o, mutation
> > observers) are designed for data binding, so the practical difference only
> > occurs when data binding induces a data flow like the one I described in my
> > previous comment.
> > 
> > Do you have any reason to believe that the approach I described would be
> > WORSE for non-data binding cases that still made heavy use of promises and
> > other end-of-microtask operations?
> 
> No. I have no basis for believing anything about non-databinding use cases.

I don't believe that simpler cases would be damaged by a bucketed approach, and it would significantly benefit applications that scheduled a large number of asynchronous events.

The use-case I'm describing is not just data binding, but any case where earlier buckets in my proposal tend to schedule asynchronous callbacks in later buckets. I believe that this will be, by far, the dominant case.

If you have any reason to believe that the order may often be different than my expectation, I'm all ears.

> 
> > 
> > (In reply to comment #17)
> > > @Yehuda,
> > > 
> > > I actually *want* to agree with you, but I'm not there.
> > > 
> > > I feel like you're just restating what you said before which is: we found
> > > this ordering to have perf benefits in practice.
> > > 
> > > The central problem I have with this view is that is rooted in an experience
> > > of being the only actor in the system. In your Ember implementation, there
> > > were different types of work, but only one Ember -- no other decoupled
> > > mechanism was at work.
> > > 
> > > Specifying this as a platform feature means that we must assume multiple
> > > *entirely* decoupled concerns operating via multiple types of work in the
> > > same work queue.
> > > 
> > > Not only do I believe that Ember found this processing ordering expedient, I
> > > know from experience (via MDV) that it is expedient for data-binding
> > > frameworks. My problem my lack of belief that the only kinds of actors in
> > > this system will be data-binding frameworks and that other kinds of actors
> > > have the same needs.
> > > 
> > > Lacking a robust justification to prioritize one actor vs another or one
> > > type of work vs another, I think the default behavior should be the simpler
> > > one, which is the FIFP queue.
Comment 22 Ian 'Hixie' Hickson 2013-09-03 17:34:07 UTC
(Please trim the quotes in your replies, if you must have quotes at all... this isn't GMail, there's no magic to hide trailing quotes and it makes reading your comments a lot more frustrating. Thanks!)
Comment 23 Rafael Weinstein 2013-10-30 19:45:21 UTC
FWIW, here's an issue the Polymer team ran into (which I *think* argues that work types should not be explicitly prioritized):

The hit a use case of an element wanting to observe an id property of a reference element. In this case the path was "myElement.id". DOM idl properties do not currently Object.getNotifier(obj).notify. However, it's possible to polyfil in this case by observing with MutationObservers -- which would effectively mean the "path" is being observed both by Object.observe and Mutation Observers -- for exactly the same concern (the value of a path changing).

It seems like it'd be surprising for the discovery of an element of this path changing having different prioritization based on what portion of the path changed.

In other words, this is an type of work which is dependent on JS and DOM data in the exactly the same way.
Comment 24 Ian 'Hixie' Hickson 2013-11-18 22:35:33 UTC
Ok so what do you want me to spec? I'm at a loss as to what people want here.
Comment 25 Rafael Weinstein 2014-01-16 00:12:40 UTC
Here's a high-level proposal for the general approach.

1) Microtask

A Microtask is task which is run during a microtask checkpoint. Microtasks are run-able (e.g. have a run() method).

2) Microtask Work Queue

The "Microtask Work Queue" is a FIFO queue of Microtasks which has two operations

-enqueueMicrotask(microtask); // append |microtask| to the end of the queue
-processAll(); // repeated select the first item from the queue and run() it, until the queue is empty

3) Simple work types enqueue one Microtask per work item

Example: ECMA promises

4) Complex work types (those which require specialized ordering) must ensure that as long as there is pending work, there is either a presently running or scheduled Microtask enqueued to process pending work.

Examples: Mutation Observers, Object.observe, Custom Element callbacks.

Issue: Each complex work type will face a choice of whether or not to yield before all work is completed, in the case where new work is scheduled during processing of existing work. I propose that a general rule of thumb is to process the set of work visible prior to the beginning of each work phase, but process new work in a subsequent Microtask.

Example: Processing of Mutation Observers (Object.observe will be analogous)

-Create a list of observers which have pending mutation records, ordered by observer creation time
-One by one, deliver to each observer any & all pending records.
-Upon completion, if any observers have pending records, schedule a new Microtask to start a new delivery phase.

This means that it's possible to deliver records created during a delivery phase to observers, but it's not possible to schedule new delivery to an observer beyond when a delivery phase has begun.
Comment 26 Rafael Weinstein 2014-01-31 01:53:43 UTC
Yehuda and I discussed this at length at this week's TC-39 and I believe we're both on the same page now.

Yehuda, correct me if I'm misremembering, but here's my summary:

-Yehuda's concern is about wanting to schedule inexpensive work before expensive work.
-We agreed that because these mechanisms simply trigger callback, at the platform level, we can assume nothing about the work they will actually do
-Thus the FIFO ordering makes sense (see my previous explanations)
-For apps or frameworks which to control scheduling, the likely pattern is implementing a priority queue in user-space which simply ensures that a promise is scheduled to run whenever there is work to do.

I believe Yehuda may also have ideas about formalizing the later mechanism as platform APIs, but I'll let him describe those.

Thus, I'm going to move forward with landing patches in blink & V8 which implement the FIFO microtask queue.
Comment 27 Anne 2014-01-31 01:58:30 UTC
Does that make mutation observers more straightforward too then?
Comment 28 Rafael Weinstein 2014-01-31 02:04:53 UTC
Mutation Observers are specified to deliver in creation-time order. We can't change that.

The MutationObservers *system* will behave as a single actor within the FIFO queue, ensuring that a Microtask is scheduled if any observers are pending delivery of mutations.

The blink patch that paves the way for the Microtask Queue (https://codereview.chromium.org/142193004/) does just this.
Comment 29 Anne 2014-01-31 02:11:43 UTC
Ah right, each time we queue a mutation record we add it to a queue and then provide a callback with the entire queue. Oh well. Thanks!
Comment 30 Yehuda Katz 2014-01-31 03:39:49 UTC
(In reply to Rafael Weinstein from comment #26)
> Yehuda and I discussed this at length at this week's TC-39 and I believe
> we're both on the same page now.

I think we're both on the same page that the opacity of the callbacks makes inferring the relative cost of the work in the callback difficult (if not impossible).

> 
> Yehuda, correct me if I'm misremembering, but here's my summary:
> 
> -Yehuda's concern is about wanting to schedule inexpensive work before
> expensive work.
> -We agreed that because these mechanisms simply trigger callback, at the
> platform level, we can assume nothing about the work they will actually do
> -Thus the FIFO ordering makes sense (see my previous explanations)
> -For apps or frameworks which to control scheduling, the likely pattern is
> implementing a priority queue in user-space which simply ensures that a
> promise is scheduled to run whenever there is work to do.

I don't agree with this characterization of my position; see below.

> 
> I believe Yehuda may also have ideas about formalizing the later mechanism
> as platform APIs, but I'll let him describe those.

The basic idea is that programs that want to defer work (even relatively simple programs), will want the ability to defer work at different priority levels.

On of the simplest and most common work-deferral strategies is to defer "work that mutates the DOM" and "other kinds of work".

One reason to defer work that mutates the DOM is that the DOM mutations may become irrelevant by the end of the turn. For example, consider an application with a hide-able sidebar. If, during the course of a single turn, the contents of the sidebar are manipulated (possibly via data bindings) and the sidebar itself is hidden, deferring both pieces of work allows the work related to the contents of the sidebar to be optimized away. This is just a specific example of a very general kind of optimization that can be applied to UI work, and a kind of optimization that the browser does itself.

A similar kind of optimization can be done with JavaScript objects. For example, imagine a Person object with a memoized `name` property that is composed of a number of components (`salutation`, `firstName` and `lastName`). Ideally, if all three properties change within a single turn, the application would like to recompute the `name` only a single time, so deferring the recomputation allows them to coalesce into a single computation.

In applications that make use of even simple deferred work strategies, it is useful to be able to schedule very expensive kinds of work (like DOM mutations) to happen after other kinds of deferred work.

Raf made the correct observation that we cannot use the source of the callback to order the work. He also made the correct observation that it is possible to implement a system that supports multiple priority levels in user-space, as long as it is possible to schedule microtask callbacks.

However, this means that libraries that want to schedule async work meaningfully must work within the context of specific user-land abstractions that provide these queues, and libraries written for different abstractions won't be able to interoperate meaningfully. Especially in the context of web components, where people will be writing very generic abstractions that are meant to interoperate across many of these abstractions, it would be very helpful to define a high-level API for scheduling.

Here is a basic straw-man:

// some example named queues
window.addSchedulingQueue('render');
window.addSchedulingQueue('actions', { before: 'render' });
window.addSchedulingQueue('post-mortem', { after: 'render' });
window.addSchedulingQueue('repaint-canvas', { after: 'render', before: 'post-mortem'});

document.find('h1').on('click', function(e) {
  window.schedule('render', function() {
    // coalescing logic, then...
    e.target.nextElement.style.display = 'block';
  });
});

This would still require some level of coordination around which queue names to  use, but that level of coordination is far easier than coordination around which user-land libraries to use.

This means that if Ember, Angular and React all agree to schedule deferred DOM work to happen in a queue named "render", a data binding library that wants to make sure that it has propagated its work before any DOM work can be guaranteed to be able to do so. Additionally, web component libraries could use a conventional named queue like 'render'. This would allow more decoupling between data binding libraries, routing/navigation libraries and web component libraries.

The specific API names are obviously wide open for bikeshedding. The semantics are relatively simple: scheduled work is guaranteed to run before work scheduled in a lower-priority queue. The queues themselves are FIFO.

> 
> Thus, I'm going to move forward with landing patches in blink & V8 which
> implement the FIFO microtask queue.

I hope that you will work with me to move forward on a more extensible scheduling system. Good work getting us here!
Comment 31 Yehuda Katz 2014-01-31 04:11:08 UTC
Here's an example of the optimization, using just DOM and ES6 APIs (no data binding libraries).

HTML:

<h1 id="greeting"></h1>

JS:

var user = { first: "Yehuda", last: "Katz" };
var appConfig = { salutation: "Greetings!" };
var updatingGreeting = false;

function scheduleUpdateGreeting() {
  if (updatingGreeting) return;
  schedule('render', updateGreeting);
}

function updateGreeting() {
  document.find('#greeting').innerHTML = greeting();
  updatingGreeting = false;
}

function greeting() {
  return [appConfig.salutation, user.first, user.last].join(" ");
}

Object.observe(user, scheduleUpdateGreeting);
Object.observe(appConfig, scheduleUpdateGreeting);

---

This is a very simple example. A couple of observations:

* Ember's system has a `scheduleOnce`, which keeps a Set of callbacks and won't schedule the identical callback twice in the same queue in the same turn.
* This example only makes use of a single named queue, assuming that any intervening Object.observe calls will run before the render queue. This essentially assumes that built-in microtask queues are at a high priority, so callbacks from built-in scheduling can always be re-scheduled to a lower, user-defined priority.
* Hopefully you can see that as the number of decoupled Object.observe calls in the system scales up, naive optimization strategies would rapidly become impossible to reason about, but that this deferral approach to optimizing would continue to work (assuming a bit more library or platform glue so that managing the state of things like updatingGreeting was not necessary)
Comment 32 Yehuda Katz 2014-01-31 04:14:10 UTC
One final thing before I board to go back to Portland: The best optimizations that use this technique do things like avoid mutating the inside of a sidebar if the sidebar was already scheduled to be removed. Those approaches require framework-level coordination, which would be built on top of this system.

Even with that kind of coordination in play, the ability for a data binding framework to schedule work to happen before a conventionally named "render" queue would be a big win.
Comment 33 Ian 'Hixie' Hickson 2014-02-04 21:12:23 UTC
So... what are the conclusions here? What do you want the HTML spec to say?
Comment 34 Rafael Weinstein 2014-02-04 21:15:38 UTC
I think a good start would be creating spec text for steps 1 & 2 in comment 25. From there we can open separate bugs to refactor the various microtask users (Mutation Observers, Custom Elements, etc...) to use this new construct (i.e. "enqueue microtask"
Comment 35 Ian 'Hixie' Hickson 2014-02-04 21:48:58 UTC
This would be one queue per event loop, and we flush the entire queue each time, even if new things are added while we're flushing it? (What are we going to do to avoid starving the event loop by recursively added microtasks?)

Should we _only_ allow microtasks to be handled by this queue, or should it be possible for the "perform a microtask" algorithm to also do things explicitly, e.g. the way that it now first does custom elements, then sorts tables, then does mutation observers? I don't like the idea of a mutation observer on a table mutating the table, causing it to sort, causing it to fire mutation observers, causing it to sort, etc. I'd much rather we first sorted, then did mutation observers, then span the event loop.
Comment 36 Domenic Denicola 2014-02-04 22:02:01 UTC
While all this interesting discussion is going on let me transcribe some of my findings regarding the ES microtask stuff from IRC into a slightly more permanent and structured form. The section I am summarizing is at

https://people.mozilla.org/~jorendorff/es6-draft.html#sec-tasks-and-task-queues

plus some of its usage in the Promise parts of the spec.

ES uses "tasks" to mean what we all refer to as "microtasks." This is silly.

The ES spec and algorithms are leaving a lot to the implementation (i.e. to HTML), with very few requirements and lots of implementation-defined behavior.


The main relevant pieces of the ES spec are:

- Queueing: EnqueueTask

- Beginning of microtask phase: "When there is no running execution context and the execution context stack is empty, the ECMAScript implementation removes the first PendingTask from a Task Queue and uses the information contained in it to create an execution context and starts execution of associated Task abstraction operation."

- Middle: NextTask (moves to next task in queue, if there is one)

- End: "An implementation must define what occurs when there are no running execution context and all Task Queues are empty."

ES's task queue model allows for multiple task queues and lets the implementation define interleaving order of any kind to be implemented by customizations to NextTask. Within a task queue the order must be FIFO though.

The only task queue defined in the ES spec right now is "PromiseTasks".

The spec takes care of setting up the execution context and realm for a task's algorithm (although I do not know if it does so in a web-realistic manner).
Comment 37 Ian 'Hixie' Hickson 2014-02-04 22:08:13 UTC
So how do we get PromiseTasks to be the same queue as where mutation observers et al get queued? Is that possible? (Is that what we want?)

BTW we should consider the word "job" rather than "microtask" (or ES "task"), if we want new terminology here.
Comment 38 Rafael Weinstein 2014-02-04 22:15:20 UTC
You've raised on number of issues here:

1. There should be one microtask per event loop

2. processAll on a microtask queue must run all microtasks in the queue until there are none left.

3. We're not going to do anything to prevent the event loop from being starved. We've already crossed that bridge. Mutation Observers, Custom Elements, Object.observe all already have this property. What we are doing is specifying the scheduling of these types of work relative to each other.

4. Semantically, table sorting is really just a mutation observer that you've hard coded into the spec. It observers that content of table cells and mutates the table according to some algorithm. If you specify it to go first and some mutation observer mutates the table so that it needs re-sorting, don't you want it to re-sort before the page re-paints? Conversely, if a mutation observer is decorating the table based on it's current sort order, should it get to go after table sorting takes place (in case you were thinking of having it *last*).

So, yes, in my opinion, unless some very special type of work arises which is essentially unobservable by the page, I think all microtask work should be scheduled in this queue.
Comment 39 Rafael Weinstein 2014-02-04 22:18:24 UTC
Re: ES spec. We discussed this last week at the TC-39 meeting. The current spec text is incomplete and needs alignment with what where this bug is going.
Comment 40 Rafael Weinstein 2014-02-04 22:27:39 UTC
ES is going to need to schedule work for the embedder. In particular,

-Promises and Object.observe will need to schedule microtasks, and
-Modules will need to schedule tasks (which will resolve as a result of external I/O).

I'm not sure what the right mechanism is to align the specs. I figured the best thing to do was to get clarity on the semantics and then figure out how to describe it.

In my mind, the ES spec would describe in general assumptions about it's "host environment", and that it needs an ability to schedule Task work and Microtask Queue. It would also probably have some normative text enforcing some invariants (all Microtask work is done before a new Task is processed, all Microtasks and Tasks are run on an empty stack, etc...)
Comment 41 Ian 'Hixie' Hickson 2014-02-05 00:23:07 UTC
As far as the ES thing goes, best thing is for whoever is editing this on the ES side to reach out to be by e-mail so we can coordinate.

As far as this bug goes, let me have a crack at speccing what's been described here now that I have a better idea of what we're trying to do...
Comment 42 Mark S. Miller 2014-02-05 00:23:58 UTC
Since dom specs use both "task" and "microtask" to means turns at specific priority levels meaningful only to that hosting environment, a host independent spec should choose another term for the host-and-priority independent concept. I suggest "turn". "Turn" already has exactly the right definition -- it executes from an empty user-stack state to the next empty user-stack state.
Comment 43 Mark S. Miller 2014-02-05 00:25:49 UTC
I hit a so-called mid-air collision in submitting my last comment. I responded by hitting the wrong button, possibly wiping out someone else's comment. If you just submitted a comment in the last few minutes, please check that it is really there.

Apologies.
Comment 44 Ian 'Hixie' Hickson 2014-02-05 00:36:48 UTC
So, I started speccing this, and immediately ran into bug 20821. Do we have an answer for how we want that to work yet? See bug 20821 comment 6 in particular.

(Mark, don't worry, you can't blow away other people's comments on Bugzilla.)
Comment 45 contributor 2014-02-05 01:00:09 UTC
Checked in as WHATWG revision r8463.
Check-in comment: First attempt at speccing the generic microtask queue idea.
http://html5.org/tools/web-apps-tracker?from=8462&to=8463
Comment 46 Ian 'Hixie' Hickson 2014-02-05 01:00:27 UTC
Ok, take a look at my attempt at speccing this. I haven't yet converted the table sorting model to this, but if it looks ok, I can do that as the first client, as a proof of concept. (Note: this also fixes bug 20821.)

What all this means for mutation observers is that there shouldn't be a mutation observer queue any more, each observer callback should be queued separately, so that it all operates with the right order relative to other microtasks like table sorting, custom elements, etc.
Comment 47 Rafael Weinstein 2014-02-05 01:02:17 UTC
Thanks. Will have a look...

Re: Mutation Observers: No. See Part 4 of comment 25.
Comment 48 Ian 'Hixie' Hickson 2014-02-05 21:00:35 UTC
If we want to have just one microtask to do bulk callback, then my solution for bug 20821 won't work here, and we'll need to have anyone who wants to do more clever work have a bunch of logic for handling spinning the event loop. That seems like a really bad idea. I don't really understand part 4 of comment 25, though.
Comment 49 Rafael Weinstein 2014-02-05 22:22:22 UTC
So for mutation observers, basically it would work like this:

-Mutation Observers maintains an isMicrotaskScheduled flag, initially false.

-Whenever a record is enqueued to an observer for delivery
  -If isMicrotaskScheduled is false, enqueue the mutationObserverMicrotask to the microtask queue and set isMicrotaskScheduled to true.

-the mutationObserverMicrotask does roughly this:

a) set isMicrotaskScheduled to false
b) create a list of the observers with records to deliver
c) order that list by observer creation time
d) deliver to each observer in the list from beginning to end

Notice that, if any new observed mutations take place during this phase, the mutationObserverMicrotask will be rescheduled -- and that at the end of the list created in (b), mutation observers essentially yields back to the microtask queue.

This behavior is actually already committed to blink: https://src.chromium.org/viewvc/blink/trunk/Source/core/dom/MutationObserver.cpp?revision=166252 (see line 189)
Comment 50 Ian 'Hixie' Hickson 2014-02-06 00:34:53 UTC
The complexity is in step d, which has to be something that calls back into the HTML spec so that the HTML spec can correctly set the "current task" so that if the scripts spin the event loop, we only defer that specific mutation observer, not the next ones. That's the part that makes this less desirable.
Comment 51 Rafael Weinstein 2014-02-20 00:02:18 UTC
Can I restate this question as:

Does each event loop need it's own microtask queue (and, by implication, set of mutation observers which are pending delivery)?
Comment 52 Ian 'Hixie' Hickson 2014-02-20 19:04:45 UTC
The answer to that question is yes, definitely, but that doesn't have anything to do with the ability to spin the event loop from within a microtask callback.

What I don't understand is why if, in a microtask callback, you cause both a table to want to get sorted, and then a mutation observer to be queued, in that order, you would want the mutation observer to be processed first, but if the microtask related to component initialisation were to cause both a table to want to get sorted, and then a mutation observer to be queued, in that order, the table would want to be sorted first.

That's the author-visible implication of the "no" in comment 47. The spec-visible impact is that it makes everything harder to spec because we have to wrap each individual callback in something that can handle spinning the event loop, instead of small microtasks all being queued and there just being one big queue for all microtasks and so there only needing to be one place with spin-the-event-loop handling logic, but that's just an issue for Anne, me, and Dimitri, probably.
Comment 53 Ian 'Hixie' Hickson 2014-02-20 20:25:28 UTC
Based on IRC discussion, I think we're going to need two ways to do microtasks. One like today's spec prose which is used for trivial microtasks with at most one callback, and one for more elaborate ones with multiple callbacks.
Comment 54 Ian 'Hixie' Hickson 2014-02-25 03:53:08 UTC
Ok, I specced that out. I think the original premise of this bug is fixed now.

There's four things that need doing still:

 1. Converting mutation observers to use this.
 2. Converting Web components to use this.
 3. Converting table sorting to use this.
 4. Converting "stable state" to use this. (bug 24724)
Comment 55 contributor 2014-02-25 03:53:26 UTC
Checked in as WHATWG revision r8510.
Check-in comment: Lay the groundwork for interruptible microtasks, mutation-observer style.
http://html5.org/tools/web-apps-tracker?from=8509&to=8510
Comment 56 Ian 'Hixie' Hickson 2014-02-25 18:57:40 UTC
Filed bug 24809 for table sorting.
Reopened and reassigned bug 22409 for Web components.
Filed bug 24810 for mutation observers.

I'm closing this bug. Please open a new one if there's more to do (though do put a pointer here, in case people cc'ed here want to know about it).