Description
openedon Oct 26, 2015
Motivation
Now that we have channels, the utility for a mechanism to wait on multiple events is especially high. Go has proven that the combination of channels and select
is a strong unifying mechanism for asynchronous programming such as fine-grained synchronization and building complex parallel pipelines. Here's one simple demonstration of how select
works in Go and the kinds of program it enabled; I won't fully go into the utlity of select
here since so much is already generally available.
Syntax
I propose taking inspiration from Go's syntax:
@select begin
if c1 |> x
"Got $x from c1"
elseif c2
"Got a message from c2"
elseif c3 <| :write_test
"Wrote to c3"
elseif task |> z
"Task finished and returned $z"
end
end
This will wait for a value to be on available on channel c1
or c2
, or capacity for a value to be available on channel c3
, or for task task
to complete. Whichever completes first will then go on to execute its corresponding body. I'll call statements such as c3 <: :write_test
a "clause". I call the actual values that will be waited-upon (like "c3") an "event" (I'm not attached to this nomenclature at all).
A complimentary non-blocking form is available by providing a default else
block to @select
, which will execute immediately if none of the clauses are immediately available.
A clause has three possible forms:
event |> value
(a "take" clause kind)
If event
is an AbstractChannel
, wait for a value to become available in the channel and assign take!(event)
to value
.
if event
is a Task
, wait for the task to complete and assign value
the return value of the task.
event |< value
(a "put" clause kind)
Only supported for AbstractChannel
s. Wait for the channel to have capacity to store an element, and then call put!(event, value)
.
event
("a "wait" clause kind)
Calls wait
on event
, discarding the return value. Usable on any "waitable" events", which include with a wait method defined (most commonly, channels, tasks,
Condition` objects, and processes.)
A functional form of the macro, select
, will be provided as well in the case that the number of clauses is not known statically. However, as in go, the macro variant is the preferred style whenever feasible.
Implementation
In #13661, I provide a simple but functional and reasonably performant implementation. I suspect that this implementation will go through rounds of optimization and gain support for multithreading before Julia 1.0, but it gets the ball rolling.
Non-blocking case
This case is simpler: a function _isready
is defined that decides if a clause is immediately available for execution. For abstract channels, it will check if it has a value that is ready to be taken for a "take" clause kind; or ready to have a value put into it for a "put" clause type; for tasks, it will check if the task is done. No other event types are supported. This is a limitation of wait
being edge-triggered: for general objects with wait
defined, there isn't a pre-defined notion of what it means to have a value "available".
Blocking case
One task is scheduled for each clause (this set is called the "waiters"):
-
Each task calls
_wait
on its event within a try-catch block._wait
called on channel events will wait for the channel to have a value available for taking or putting, depending on the clause type._wait
for a task will wait for the task to finish, returning the tasks return value. Otherwise,_wait
will just callwait
on the event. -
When a task gets past its
_wait
(and hence becomes the "winner"), it signals to all its "rival" tasks (all other waiters) to terminate before modifying the state of their events. To signal the blocked tasks, it throws to the rival a custom error type that interrupts the riva's_wait
statement, and also passes to the rival a reference to the winner task. The rival processes the error in a "catch" block, returns control to the winner, and then exists.
If the rival hasn't yet been scheduled, it is deleted from the workqueue. This scheme ensures only one waiter will end up manipulating the state of its event, no matter how the waiters are scheduled or what other tasks happen to be scheduled.
For channels, it is important that between the call to _wait
and the call to take!
or put!
, no other task manipulates the channel. In this scheme, the scheduler is never run between those calls: all that happens is a sequence of yieldto
calls amongst the waiters.
This correctness is with respect to Julia's current cooperative multitasking; additional locking will have to be done to be thread-safe. As the complexity of go's select implementation shows, getting correct and high-performant select
functionality in the presence of preemptive multithreading is a subtle problem that I don't think should block us from a reasonable @select
implementation that works in Julia today.