{"action":"created","issue":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/13763","labels_url":"https://api.github.com/repos/JuliaLang/julia/issues/13763/labels{/name}","comments_url":"https://api.github.com/repos/JuliaLang/julia/issues/13763/comments","events_url":"https://api.github.com/repos/JuliaLang/julia/issues/13763/events","html_url":"https://github.com/JuliaLang/julia/issues/13763","id":113263792,"number":13763,"title":"julep: a @select statement","user":{"login":"malmaud","id":987837,"avatar_url":"https://avatars.githubusercontent.com/u/987837?v=3","gravatar_id":"","url":"https://api.github.com/users/malmaud","html_url":"https://github.com/malmaud","followers_url":"https://api.github.com/users/malmaud/followers","following_url":"https://api.github.com/users/malmaud/following{/other_user}","gists_url":"https://api.github.com/users/malmaud/gists{/gist_id}","starred_url":"https://api.github.com/users/malmaud/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/malmaud/subscriptions","organizations_url":"https://api.github.com/users/malmaud/orgs","repos_url":"https://api.github.com/users/malmaud/repos","events_url":"https://api.github.com/users/malmaud/events{/privacy}","received_events_url":"https://api.github.com/users/malmaud/received_events","type":"User","site_admin":false},"labels":[{"url":"https://api.github.com/repos/JuliaLang/julia/labels/julep","name":"julep","color":"F4F0CB"},{"url":"https://api.github.com/repos/JuliaLang/julia/labels/parallel","name":"parallel","color":"f7e102"}],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":18,"created_at":"2015-10-26T00:11:17Z","updated_at":"2015-10-29T20:52:13Z","closed_at":null,"body":"Motivation\r\n===\r\nNow that we have channels, the utility for a [mechanism to wait on multiple events](https://github.com/JuliaLang/julia/issues/6563) 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](https://tour.golang.org/concurrency/5) 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. \r\n\r\nSyntax\r\n===\r\nI propose taking inspiration from Go's syntax:\r\n\r\n```julia\r\n    @select begin\r\n        if c1 |> x\r\n            \"Got $x from c1\"\r\n        elseif c2\r\n            \"Got a message from c2\"\r\n        elseif c3 <| :write_test\r\n            \"Wrote to c3\"\r\n        elseif task |> z\r\n            \"Task finished and returned $z\"\r\n        end\r\n    end\r\n```\r\n\r\nThis 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).\r\n\r\nA 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. \r\n\r\nA clause has three possible forms:\r\n\r\n1) `event |> value` (a \"take\" clause kind)\r\n\r\nIf `event` is an `AbstractChannel`, wait for a value to become available in the channel and assign `take!(event)` to `value`.\r\nif `event` is a `Task`, wait for the task to complete and assign `value` the return value of the task.\r\n\r\n2) `event |< value` (a \"put\" clause kind)\r\n\r\nOnly supported for `AbstractChannel`s. Wait for the channel to have capacity to store an element, and then call `put!(event, value)`.\r\n\r\n3) `event` (\"a \"wait\" clause kind)\r\n\r\nCalls `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.)\r\n\r\nA 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.\r\n\r\nImplementation\r\n====\r\n\r\nIn https://github.com/JuliaLang/julia/pull/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. \r\n\r\nNon-blocking case\r\n---\r\nThis 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\". \r\n\r\nBlocking case\r\n---\r\nOne task is scheduled for each clause (this set is called the \"waiters\"):\r\n\r\n1) 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 call `wait` on the event.\r\n\r\n2) 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. \r\n\r\nIf 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.\r\n\r\nFor 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. \r\n\r\nThis 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. \r\n"},"comment":{"url":"https://api.github.com/repos/JuliaLang/julia/issues/comments/152318777","html_url":"https://github.com/JuliaLang/julia/issues/13763#issuecomment-152318777","issue_url":"https://api.github.com/repos/JuliaLang/julia/issues/13763","id":152318777,"user":{"login":"malmaud","id":987837,"avatar_url":"https://avatars.githubusercontent.com/u/987837?v=3","gravatar_id":"","url":"https://api.github.com/users/malmaud","html_url":"https://github.com/malmaud","followers_url":"https://api.github.com/users/malmaud/followers","following_url":"https://api.github.com/users/malmaud/following{/other_user}","gists_url":"https://api.github.com/users/malmaud/gists{/gist_id}","starred_url":"https://api.github.com/users/malmaud/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/malmaud/subscriptions","organizations_url":"https://api.github.com/users/malmaud/orgs","repos_url":"https://api.github.com/users/malmaud/repos","events_url":"https://api.github.com/users/malmaud/events{/privacy}","received_events_url":"https://api.github.com/users/malmaud/received_events","type":"User","site_admin":false},"created_at":"2015-10-29T20:52:13Z","updated_at":"2015-10-29T20:52:13Z","body":"I think this is vulnerable to a race condition where if you're waiting for a channel to have a value for taking, it might notify the waiter waiting for it but by the time the `take!` statement is executed, another task has already taken the value before the body executed. That's what motivated this design in the first place."}}