"Next task" optimization

[notgull]

In many actor systems (most notable Erlang), executors are optimized by having a "next task" slot in each executor queue. Whenever a new Runnable is scheduled, the future is first pushed to a slot separate from the normal queue. If a Runnable is already in this slot, it is pushed to the back of the queue. When it comes time to read from this queue, the slot is checked and popped from before the normal queue is.

This is optimal because if a task wakes another task to be immediately executed, the second task will be queued up immediately, which can emulate sequential computations very well.

[nullchinchilla]

An important issue about this slot is that it's unstealable from other workers, which can cause issues in scenarios where correctness directly depends on stealing. The most obvious example is something like this:

block_on(spawn(async { block_on(spawn(async{1}))}))

Here, if spawn does thread-local scheduling, then all the tasks start on the same thread. But the interior task cannot make progress until the outside task ends (because the outside task has no await points), but the outside task cannot end unless the interior task makes progress.

This admittedly pathological scenario only makes progress if some other thread can come in and steal away the inner task.

[nullchinchilla]

See geph-official/smolscale#2