waiting on dynamic set of channels?

[Watson Ladd]

Hello,

Suppose I have a single socket, and I want to split messages coming into it according to some rule and send them to goroutines that are created dynamically.

Then it is easy enough to have a a map[key] channel [whatever]. However, if I want to do the reverse it appears there is no easy way to do so: waiting on all

channels in a list isn't possible. In Concurrent ML it is. This is a problem if I want to multiplex a socket, and have flow control.

Sincerely,

Watson Ladd

[Kevin Gillette]

There's no syntactic support, but there is runtime support in tip, via reflect: <http://tip.golang.org/pkg/reflect/#Select>. You are correct, though -- there's currently no 'easy' way to do this.

[Rémy Oudompheng]

It seems more appropriate that all goroutines send their response to a
single channel.

Rémy.

[bryanturley]

Make a small protocol using structs?
Inside the struct is a unique to the sender return channel.
Send the struct over the request channel.

Single request channel, N return channels.

[John Nagle]

On 2/16/2013 5:02 PM, Kevin Gillette wrote:
> There's no syntactic support, but there is runtime support in tip, via
> reflect: <http://tip.golang.org/pkg/reflect/#Select>. You are correct,
> though -- there's currently no 'easy' way to do this.

OK, so the runtime engine knows how to do this; it's just not
exported to the source language level.

The documentation doesn't say, but I expect that, like
"select" at the language level, the first channel mentioned
with traffic wins. This differs from the BSD/Linux "select"
call, which is FIFO.

This matters. If you write a server using this
approach, the channels near the beginning of the list
have priority over the ones further down. On a
busy server, the ones at the end will be starved out.

If you feed all the incoming events into a single
queue, it's FIFO. This is OK if senders have to wait for
a reply before they can send again. If they can send as
much as they want, the one that sends most wins. In
that case, fair queuing may be necessary.

John Nagle

[Ian Lance Taylor]

On Sun, Feb 17, 2013 at 10:38 AM, John Nagle <na...@animats.com> wrote:
> The documentation doesn't say, but I expect that, like
> "select" at the language level, the first channel mentioned
> with traffic wins. This differs from the BSD/Linux "select"
> call, which is FIFO.

I'm not sure quite what you mean here, but, to be clear, in the Go
select clause and in the reflect.Select function, the order in which
the channels are listed is entirely irrelevant.

Ian

[minux]

On Mon, Feb 18, 2013 at 2:38 AM, John Nagle <na...@animats.com> wrote:

On 2/16/2013 5:02 PM, Kevin Gillette wrote:
> There's no syntactic support, but there is runtime support in tip, via
> reflect: <http://tip.golang.org/pkg/reflect/#Select>. You are correct,
> though -- there's currently no 'easy' way to do this.

    OK, so the runtime engine knows how to do this; it's just not
exported to the source language level.

    The documentation doesn't say, but I expect that, like
"select" at the language level, the first channel mentioned
with traffic wins.  This differs from the BSD/Linux "select"
call, which is FIFO.

Please don't guess the behavior of "select".

Please read the language spec.

http://golang.org/ref/spec#Select_statements

[John Nagle]

On 2/17/2013 10:45 AM, minux wrote:
> Please don't guess the behavior of "select".
> Please read the language spec.
> http://golang.org/ref/spec#Select_statements

That's the spec for the "select" statement at the language level.
The documentation for the "Select" function in the reflection package
reads:

http://tip.golang.org/pkg/reflect/#Select

"Select executes a select operation described by the list of cases. Like
the Go select statement, it blocks until one of the cases can proceed
and then executes that case. It returns the index of the chosen case
and, if that case was a receive operation, the value received and a
boolean indicating whether the value corresponds to a send on the
channel (as opposed to a zero value received because the channel is
closed)."

So the documentation does not explicitly guarantee random selection
for the reflection package version. Implementations may provide it,
but are not required to do so.

John Nagle

[bryanturley]

I think the word random is used here because it has a more positive sound than undefined which is usually reserved for negative things.
Leaving which case gets called first undefined leaves the background implementation more flexible.
In either situation you shouldn't count on any case happening before another one.

[John Nagle]

On 2/17/2013 11:30 AM, bryanturley wrote:

> I think the word random is used here because it has a more positive sound
> than undefined which is usually reserved for negative things.
> Leaving which case gets called first undefined leaves the background
> implementation more flexible.
> In either situation you shouldn't count on any case happening before
> another one.

For the statement version of "select", the spec reads:

"If multiple cases can proceed, a uniform pseudo-random choice is made
to decide which single communication will execute."

That's a strong statement, and one right way to do it. (It's borrowed
from Dijkstra's classic paper "Guarded commands. non-determinacy and a
calculus for the derivation of programs":
"http://www.cs.utexas.edu/~EWD/transcriptions/EWD04xx/EWD418.html"
where it was used for case statements. Randomizing guarded case
statements when more than one case is true never really caught on,
but for multiple-input asynchronous reads, it provides load
balancing.)

The question here is whether the "Select()" call in the reflection
package also works that way, or whether the randomization occurs in
the language implementation at the compiler level.

John Nagle

[Dan Kortschak]

The answer to that question is in chan.c

http://tip.golang.org/src/pkg/runtime/chan.c?h=rselect#L1113

[Kevin Gillette]

Your initial premise of "the first channel mentioned with traffic wins" is invalidated by the spec:

"If multiple cases can proceed, a uniform pseudo-random choice is made to decide which single communication will execute."

Although some room for interpretation exists of the reflect.Select documentation, unlike the spec (in which all documentation serves to define the nature of the implementation), all package documentation, unless explicitly stated otherwise, exists to describe current behavior (if the package docs disagree with the behavior, the docs must change). The reflect.Select function is not an implementation of the selection algorithm: it is a wrapper around the same part of the runtime that facilitates the select statement.

Beyond that, having "first win" preference in the selection algorithm would produce thoroughly undesirable behavior: in many scenarios, all but the first few channels (if not just the first) would be starved out; I doubt any implementor would choose to not implement random selection available channels. Giving preference to certain operations can easily be achieved, however, by providing several select statements (or reflect.Select calls) in a row (all but the last having default clauses), so that the prioritized operations are listed in each statement/call, and low-priority operations are gradually added (the lowest priority ops would only exist in the last statement/call).

[Kevin Gillette]

On Sunday, February 17, 2013 1:06:43 PM UTC-7, John Nagle wrote:

The question here is whether the "Select()" call in the reflection
package also works that way, or whether the randomization occurs in
the language implementation at the compiler level.

All communication is facilitated by the runtime, be it for select statements or reflect.Select calls. If a hypothetical implementation had a forking multi-process model to handle goroutines, then it may make sense to handle this sort of thing at compile time, though since all current implementations use a threaded model with an internal scheduler, and since communication is a scheduling operation (a very good thing -- current kernels can't get enough information to make that efficient themselves), there's much less benefit to doing compile-time specialization. Beyond which, the amount of channel use in many programs is such that inlining more than a little of this wouldn't be worth the bloat/cache-overload tradeoff.

[John Nagle]

That's a good read. The comments note that the compiler
doesn't call the general case code for select statements
with only 1 case plus a default. But if you use the
"Select()" function, you grind through the general case,
which is quite elaborate.

I'd wondered how they did that. The answer is that it works
in the obvious, but slow way. It creates a selection object,
fills it in with all the possible selections, randomizes the order
of the selections, tests them in sequence, picks the first winner,
and goes with that.

If there's no winner and the select has to block, it hangs
an event that references the select on each involved channel
and parks to await further developments. When something happens
on a relevant channel, this code wakes up and another pass is
made through the selection algorithm.

The randomizer is at

http://tip.golang.org/src/pkg/runtime/chan.c?h=rselect#L866

It generates a random number for each case in the select, then
does a bubble sort on the results, then tests all the cases in
the permuted sequence. It's thus O(n^2). Selects on hundreds
or thousands of channels are probably not a good idea unless
somebody speeds up that code.

The C code looks retro. There are many "goto" statements,
going up, down, and sideways. All variable declarations are at the
beginning of each function. Very few comments. It's like reading
the source code for early UNIX tools from the K&R era. Nostalgic.

John Nagle

[Dan Kortschak]

I think Jan said something along the lines of, "Select by reflection. Not even even wrong."

[bryanturley]

Yay another paper to read, some day I will be as smart as John Nagle........... <facepalm>

[Ian Lance Taylor]

On Sun, Feb 17, 2013 at 1:12 PM, John Nagle <na...@animats.com> wrote:
>
> The randomizer is at
>
> http://tip.golang.org/src/pkg/runtime/chan.c?h=rselect#L866
>
> It generates a random number for each case in the select, then
> does a bubble sort on the results, then tests all the cases in
> the permuted sequence. It's thus O(n^2). Selects on hundreds
> or thousands of channels are probably not a good idea unless
> somebody speeds up that code.

To be clear the sorting is for the order in which the channels are
locked, it doesn't really have anything to do with the random numbers
or which channel is selected. Locking the channels in sorted order
avoids deadlock. That sort can be replaced by a quicksort easily
enough. That would probably be a good idea given the existence of
runtime.Select.

> The C code looks retro. There are many "goto" statements,
> going up, down, and sideways. All variable declarations are at the
> beginning of each function. Very few comments. It's like reading
> the source code for early UNIX tools from the K&R era. Nostalgic.

It was indeed written by Ken Thompson.

Ian

[Cory Kolbeck (cbeck)]

This has probably been talked about before, but I'm curious what issues would arise with allowing something like:

channels := make([]chan int, n)

//...

select {

    case i := <-channels:

         //...

}

Obviously, it makes the language slightly more complex by allowing a recv on an array type in that situation but not others, but it seems like it'd be useful enough that it'd be worth supporting.

I'm also very willing to believe that there are terrible issues I'm just not seeing.

[Nigel Tao]

On Mon, Feb 18, 2013 at 2:16 PM, Cory Kolbeck (cbeck)
<ckol...@cs.pdx.edu> wrote:
> Obviously, it makes the language slightly more complex by allowing a recv on
> an array type in that situation but not others, but it seems like it'd be
> useful enough that it'd be worth supporting.

https://groups.google.com/d/msg/golang-nuts/9jvHMT6VHfg/zFdZ4zHu9w4J

[Cory Kolbeck (cbeck)]

I'll trust rsc's word over my vague intuitions any day. Perhaps a note about this in Effective Go would be worthwhile.

[Kevin Gillette]

Aside from the expensiveness, it's syntactically and semantically awkward unless you severly limit what can be done:

In your example, it appears you just want to get the received value -- in those cases, you really do want a single, shared channel. In real-world use-cases, you'd want a two-part assignment, indicating the index of the channel that communication occurred on, and the value received. This also leads to the need for a three-part assignment, so that it can be determined if the channel is closed. This also assumes that the channels all have the same type and direction; the reflect option has the maximum flexibility by allowing a slice of channels of arbitrary type and direction, though it's very inconvenient.

[John Nagle]

On 2/17/2013 2:11 PM, Ian Lance Taylor wrote:
> On Sun, Feb 17, 2013 at 1:12 PM, John Nagle <na...@animats.com> wrote:
>>
>> The randomizer is at
>>
>> http://tip.golang.org/src/pkg/runtime/chan.c?h=rselect#L866

...

> To be clear the sorting is for the order in which the channels are
> locked, it doesn't really have anything to do with the random numbers
> or which channel is selected. Locking the channels in sorted order
> avoids deadlock.

Oh, right. That trick is common for file locks and database locks,
where you sometimes lock in alphabetical order to avoid deadlock.

> That sort can be replaced by a quicksort easily
> enough. That would probably be a good idea given the existence of
> runtime.Select.

Really big selects also involve a lot of lock operations for each
pass through the select. Probably good to warn users that big
select lists are inefficient. There are ways that this could
be sped up, but it's probably not worth the trouble. Someone
coding huge select lists is probably doing it wrong anyway.

In practice, this might come up when someone builds a server
which has one channel per connection, some sequential process
listening to all of them, and, in normal operation, a small number
of connections. If the server gets badly overloaded, the O(N^2)
overhead starts to dominate. Like when a botnet hits your mailer.

John Nagle

[Russ Cox]

Regarding the semantics of reflect.Select, they are, like the rest of reflect, intended to mirror the semantics of the Go language. In particular reflect.Select guarantees the same non-deterministic selection that the select statement does.

Regarding array select, I will repeat what Nigel found me saying earlier: "we intentionally left array select out. It's an expensive operation and can often be avoided by arranging for the various senders to send on a shared channel instead."

Regarding the O(N²) sort, I agree with Ian that we probably need to fix that for completeness. In practice, though, if you are using a select statement or reflect.Select with enough cases for the square to start hurting, you're already doing it wrong. Each select is already O(N), and presumably you care about all the channels so you're running it in a loop that will execute at least N or so times. So you're already at O(N²), and we're just making it O(N³) by using a crummy sort. It's hard to get excited about the difference.

Russ

[jonathan...@gmail.com]

Responding to a very old thread here, but the bit about intentionally leaving out an array select and instead use a channel of channels (or structs with a channel in them), would be a great thing for the FAQ.

[Dmitri Shuralyov]

> the bit about intentionally leaving out an array select and instead use a channel of channels (or structs with a channel in them), would be a great thing for the FAQ.

I strongly agree. I just learned today via a tweet (https://twitter.com/zbobet2012/status/621440185226665984) and this would be absolutely fantastic to know in advance.

[Dmitri Shuralyov]

To clarify, I'm referring to this comment by Russ:

> "we intentionally left array select out. It's an expensive operation and can often be avoided by arranging for the various senders to send on a shared channel instead."

I did not know it was intentionally left out due to performance reasons (rather than "didn't get around to it/to keep language simpler") and I should write my program in another way. That is very helpful to know.