It's odd to half-define inter-document callback ordering, but not fully define it

[bzbarsky]

The fact that inter-document ordering is half-defined and half-arbitrary is a bit weird. Specifically, if I have two documents, A and B, and each schedules two idle callbacks (A1, A2, B1, B2) then I think per this spec the only allowable execution orders are "A1, B1, A2, B2" and "B1, A1, B2, A2", but either one of those two is ok. That's assuming those 4 idle callbacks fit inside a single idle period. If the idle period ends after the first two have run, then "A1, B1, B2, A2" and "B1, A1, A2, B2" also become possible orders, and if the idle period ends after every callback then the other orderings that keep A1 before A2 and B1 before B2 also become possible.

Given that, I'm not sure why a UA is required to interleave things in a particular way inside a single idle period; it seems like an accident of the way the processing model is defined, and allows direct observation of when idle periods start/end in a UA, and I think it would be better to not overconstrain things in that way.

[rmcilroy]

Right, I don't think it matters which order the callbacks of different documents interleave, all that matters is that the callbacks for a particular document happen in-posting-order (e.g, all orderings are valid as long as A1 is before A2 and B1 is before B2).

I'm not quite sure how to rewrite the spec to avoid this constraint - my intention with the "For every document in docs, in any order" was to allow callbacks from different documents to run in any order, but I now realize that the way the "invoke idle callbacks" tasks get queued up on the idle-task task source forces the ordering you are mentioning here. Any thoughts on how to rework this?

[bzbarsky]

One option would be to do rephrase to something like this:

While docs is not empty, select any document in docs, remove the first callback from its list, put it in the queue, if its list is now empty remove it from docs.

[igrigorik]

The fact that inter-document ordering is half-defined and half-arbitrary is a bit weird. Specifically, if I have two documents, A and B, and each schedules two idle callbacks (A1, A2, B1, B2) then I think per this spec the only allowable execution orders are "A1, B1, A2, B2" and "B1, A1, B2, A2", but either one of those two is ok.

@bzbarsky I'm trying to wrap my head around the above.. Can you explain how you arrived at this ordering?

• each document has a runlist
• when in an idle period starts we iterate over all the docs and:
  • update their runlists
  • queue a task to process each runlist that, in turn, processes a single callback and queues another task to repeat the same steps

Conceptually, I think this allows any interleaving order between documents, while preserving 'posting-order' for a single document. Is that not the case? I'm probably missing something obvious here.

[bzbarsky]

Conceptually, I think this allows any interleaving order between documents

It does not. Say you have two docs A and B. When an idle period starts, you iterate over them. The iteration will be either A first then B, or B first then A. If it's A first then B, then you will queue the task to process A's runlist, then the task to process B's runlist. When the first task runs it will queue another task to keep processing A's runlist. But that will of course run after the already-queued task to process B's runlist. So you get the "A1, B1, A2, B2" order. If your original iteration processes B first, you get "B1, A1, B2, A2". No other orders are possible.

Again, this is assuming all four callbacks fit within a single idle period. If they don't, you can get other orders.

[igrigorik]

Got it, think I'm with you now -- thank you.

While docs is not empty, select any document in docs, remove the first callback from its list, put it in the queue, if its list is now empty remove it from docs.

What did you have in mind for "queue" in this instance? Some global callback list that's shared by all documents?

[bzbarsky]

What did you have in mind for "queue" in this instance?

Hmm. I guess what I meant is that instead of having a task per document in flight we'd just have one task in flight that closes over all the runlists (or documents, equivalently). When the task runs, it would pick one of the runlists, run the first thing in it, forget the runlist if it's now empty, and then repost itself.

Basically, yes, a single queue but allowing dynamic prioritization as you go instead of requiring the order across documents to be fixed at the point when things are moved to runlists.

[igrigorik]

Hmm, how about something like this...

...(processing section starting at step 6)...
(6) Let docs be the list of fully active Document objects associated with the event loop in question.
(7) For every document in docs, in any order, perform the following steps:

1. Let doclist be document's list of idle request callbacks.
2. Let runlist be document's list of runnable idle callbacks.
3. Append all entries from doclist into runlist preserving order.
4. Clear doclist.

(8) Queue a task which performs the steps defined in the invoke idle callbacks algorithm with deadline as parameter.
(9) Save deadline as the last idle period deadline associated with the current event loop.

The invoke idle callbacks algorithm:
(1) Let docs be the list of fully active Document objects with non-empty runlist's.
(2) Let now be the current time
(3) If now is less than deadline:

1. Select any doc from docs and pop callback from doc's runlist.
2. Remove doc from docs if doc's runlist is now empty.
3. (snip call callback steps) ...
4. If docs is not empty, the user agent should queue a task which performs the steps in invoke idle callback algorithm with deadline as parameter.

Would that do the trick? /cc @rmcilroy

[bzbarsky]

That seems about right to me, yes.

[rmcilroy]

Yes that works for me too. Thanks to you both!