Ordering constraints on indices returned by wasi:io/poll/poll?

[tschneidereit]

The wasi:io/poll/poll function returns a list of indices into the list of pollables that was passed in to indicate readiness for them. Currently it's not documented which order these indices should appear in, so e.g. [3,1,0,2] would seemingly be a valid response.

Can we document the required order, and can we ideally require that the indices should be in ascending order? That'd make it more straight-forward to use the list of pollables as an event queue that is processed in first-in, first-(ready-)out order.

[sunfishcode]

Could you say more about why first-in-first-ready-out order would be useful? It's nondeterministic whether two events happening around the same time are reported in the same poll call or in consecutive poll calls. If they're reported in consecutive events, it's nondeterministic which order they're reported in. So it seems like users should be prepared to process events in arbitrary orders in any case.

Another subtlety is that it's currently possible to pass the same pollable multiple times to a single poll call, and at least some implementations coalesce them.

[tschneidereit]

Actually after discussing this with @elliottt I actually think that in-order-of-readiness is the right thing to do here, not ascending order. The latter can trivially be derived by sorting the list, whereas the former gives additional information.

@sunfishcode I of course agree that guests should be ready to process events in any order. The (now, based on the thought from the previous paragraph) question is can we give any additional useful information.

I think we potentially can, by including something like the following language in the definition:

Implementations SHOULD sort the list of indices in the order the indexed pollables became ready. If an implementation can't or doesn't want to do so, it SHOULD instead randomize the order.

Why would we do this? I can imagine situations in which two pollables have some implicit, unexpressed ordering constraint that means they always become ready in a specific order, and where that order is equally implicitly expected in the event loop processing the pollables.

I guess that'd argue for either turning the first SHOULD into a MUST or for requiring the randomization order, so as to force applications to not have these kinds of implicit dependencies.

But regardless of the outcome, I do think we should say something here, because I'm pretty sure this is one of those things where implementation-defined behavior will eventually come to bite us.

[tschneidereit]

Another subtlety is that it's currently possible to pass the same pollable multiple times to a single poll call, and at least some implementations coalesce them.

Ah, yet another thing that I think we should mandate some behavior. Coalescing makes sense to me, and if some implementations do so, we should either mandate or disallow it.

[sunfishcode]

Implementations based on Unix-style poll or similar won't have information about what order events that occur in the same call happen in, so it seems like it'd be difficult to require this additional information.

I can see the benefits to randomizing, in promoting portability and exposing subtle ordering bugs earlier. That said, requiring randomization would prevent poll from being usable in fully deterministic environments.

So, what if we added wording to the spec saying that the order of items returned by poll is non-deterministic, though it may be deterministic in a deterministic profile, and that implementations in non-deterministic profiles are encouraged to randomize the order?