Interesting "select" examples

[Nigel Tao]

I'm working on a multi-threaded C++ project. We have the equivalent of
Go's channels, and are considering whether we also need to implement
the equivalent of Go's select.

Does anyone have interesting, non-trivial examples of a Go select
statement in real code?

By non-trivial, I mean that a lot of the selects that I've seen have
exactly two cases, one of them doing "real work" and the other being
either (1) "default" or (2) a timeout/cancel channel (e.g.
ctx.Done()).

In our C++ API, our channel send/recv methods already have
try_send/try_recv equivalents for (1) and a timeout/cancel mechanism
for (2).

bcmills' "Rethinking Classical
Concurrency Patterns"
(https://drive.google.com/file/d/1nPdvhB0PutEJzdCq5ms6UI58dp50fcAN/view)
uses select to implement higher level ResourcePool / WorkerPool APIs
but select is arguably a private implementation detail. While it might
not be as beautiful under the hood, I think we can already present
similar APIs using C++'s std::counting_semaphore.

r's "A Concurrent Window System"
(https://swtch.com/~rsc/thread/cws.pdf) discusses select'ing from
separate window, keyboard and mouse channels but this could arguably
instead be a single channel of heterogenous elements (e.g. in C++, a
std::variant).

It's more interesting to select over both input and output channels,
and output channels may become "ready to communicate" without new
input. But again, it may be possible to work around that by downstream
actors sending "I'm ready to receive" events onto the upstream actor's
heterogenous input channel.

The most interesting selects I have so far is the
golang.org/x/net/http2 source code, whose internals have a bit of a
learning curve. If anyone has other examples, please share.

[Konstantin Kulikov]

Below is an example of code that does some work even after timeout.
In a perfect world it would be simple "return FetchLinks(user)", but
unfortunately 3rd-party service is unreliable, so we did some caching
and timeouts.

The idea is as follows:
User sends a request, we try to fetch data from a 3rd-party, if that
fails or response doesn't come in 2 seconds, then we stop waiting and
serve data from the local DB.
If request takes longer than 2 secs, we don't want to throw it away,
we still want to write its data into the local DB.

ctx, cancel := context.WithTimeout(ctx, 2*time.Second)
defer cancel()

linksCh := make(chan []*Link)
go func() {
links, err := FetchLinks(user)
if err != nil {
logger.WithError(err).Error("fetch links error")
cancel()
return
}

select {
case <-ctx.Done():
case linksCh <- links:
}

if err := SyncLinks(user, links); err != nil {
logger.WithError(err).Error("sync links error")
return
}
}()

select {
case l := <-linksCh:
return l, nil
case <-ctx.Done():
return nil, ctx.Err()

> --
> You received this message because you are subscribed to the Google Groups "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAOeFMNWBtuEci9oPUFNa0v0gDC%3DV6Xb0N05Jyxo%3DxN2ywJALGA%40mail.gmail.com.

[Rob Pike]

Here's an excerpt from a piece of concurrent code I like, an unpublished interactive game of life. The select near the bottom has only two cases but it is perhaps instructive. I leave its analysis to the reader.

-rob

   var kbdC chan of rune = ... // events from keyboard

   var ticker = time.NewTicker(*deltaTFlag)

...

    pauseC := make(chan int)
    go func() {
        for {
            switch <-kbdC {
            case 'q':
                os.Exit(0)
            case ' ':
                pauseC <- 1
            }
        }
    }()

    gen := 0
    for gen = 1; ; gen++ {
        b.draw(display, *cellSizeFlag)
        changed := b.step()
        if !changed {
            break
        }
        select {
        case <-ticker.C:
        case <-pauseC:
            <-pauseC
        }
    }
    fmt.Fprintln(os.Stderr, "stable after", gen, "generations")
    select {}
}

[burak serdar]

Below is part of a generic ordered fan-in for data pipelines. It works by reading data from multiple channels using one goroutine for each channel, sending that data element to another goroutine that does the actual ordering, but in the mean time, pauses the pipeline stage until all out-of-order data elements are sent.

func orderedFanIn[T sequenced](done <-chan struct{}, channels ...<-chan T) <-chan T {
  fanInCh := make(chan fanInRecord[T])
  wg := sync.WaitGroup{}
  for i := range channels {
    pauseCh := make(chan struct{})
    wg.Add(1)

    // Create one goroutine for each incoming channel
    go func(index int, pause chan struct{}) {
      defer wg.Done()
      for {
        var ok bool
        var data T
        select {
        case data, ok = <-channels[index]:
          if !ok {
            return
          }

          // Send data to the ordering goroutine with the pause channel
          fanInCh <- fanInRecord[T]{
            index: index,
            data:  data,
            pause: pause,
          }
        case <-done:
        return
    }

    // Pause the pipeline stage until the ordering goroutine writes to the pause channel
    select {
      case <-pause:
      case <-done:
        return
    }
 }
}(i, pauseCh)
}

[Skip Tavakkolian]

I think this qualifies:
mux9p, Fazlul Shahriar's port of Russ' 9pserve (plan9port)
https://github.com/fhs/mux9p/search?q=clientIO

I've used this dispatcher pattern:
func dispatcher(commands chan Cmd, reporting chan Stats, worker Worker) {
control = make(chan ...)
counts = make(chan ...)
timer = time.Tick( ... )
go worker.Work(control, counts)
for {
select {
case v, ok := <- counts:
// collect samples
case reporting <- Stats{ stats }:
case <-timer:
// calculate stats from samples
case cmd, ok := <-commands:
// reset counters, restart worker, exit, etc.

[Skip Tavakkolian]

Nice pause/resume. I'll need to remember this.

> --
> You received this message because you are subscribed to the Google Groups "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAOXNBZS11bKz%2B95gUXstgHHrgDRFoTWdm5kmNBriDpoxNz%3DWXQ%40mail.gmail.com.

[Ian Lance Taylor]

On Sun, Apr 2, 2023 at 8:44 PM Nigel Tao <nige...@golang.org> wrote:
>

> Does anyone have interesting, non-trivial examples of a Go select
> statement in real code?

Some of the select statements in net/http/transport.go are non-trivial.

Ian

[Nigel Tao]

On Mon, Apr 3, 2023 at 3:40 PM Konstantin Kulikov <k.kul...@gmail.com> wrote:
> select {
> case <-ctx.Done():
> case linksCh <- links:
> }

On Tue, Apr 4, 2023 at 1:15 AM burak serdar <bse...@computer.org> wrote:
> select {
> case <-pause:
> case <-done:
> return
> }

Thanks, but I think both of these fall under: By non-trivial, I mean

that a lot of the selects that I've seen have exactly two cases, one
of them doing "real work" and the other being either (1) "default" or
(2) a timeout/cancel channel (e.g. ctx.Done()).

Even if you do some work after a timeout, the select itself is still
collapsable to a single cancellable recv.

[Nigel Tao]

On Mon, Apr 3, 2023 at 8:14 PM Rob Pike <r...@golang.org> wrote:
> select {
> case <-ticker.C:
> case <-pauseC:
> <-pauseC
> }

This one is more interesting. You can't combine the ticker.C and the
pauseC into a single heterogenous channel because you want to wait for
the second pause event (a resumption) without dropping or buffering
arbitrarily many other ticker events.

I take the general point that sometimes you're waiting on only a
subset of incoming events.

For this particular code, though, I think you could structure it a
different way. Instead of two channels with (ticker) events and
(pause, resume) events, you could have two channels with heterogenous
(ticker, pause) events and (resume) events. Yes, the `time.NewTicker`
API equivalent would have to be passed a channel instead of returning
a channel. The `case ' ': pauseC <- 1` code would have to alternate
which channel it sent on. But we could eliminate the select.

To be clear, it's not that the code is better / simpler / cleaner if
we eliminate selects. It's that, outside of Go, if we don't have
selects, what becomes unworkably complicated enough that it's worth
implementing selects.

[Robert Engels]

I think it is as simple as looking at kselect/poll in posix. Each descriptor can be viewed as an independent channel of info/objects.

Select with Go channels works similarly and has similar usefulness.

> On Apr 3, 2023, at 7:00 PM, Nigel Tao <nige...@golang.org> wrote:

> --
> You received this message because you are subscribed to the Google Groups "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

> To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAOeFMNVZcoj8kp%3DDeaVqs55FiNcJrbPGPAUuLOLj0gUWqCRJKg%40mail.gmail.com.

[Nigel Tao]

On Tue, Apr 4, 2023 at 7:56 AM Skip Tavakkolian
<skip.tav...@gmail.com> wrote:
> mux9p, Fazlul Shahriar's port of Russ' 9pserve (plan9port)
> https://github.com/fhs/mux9p/search?q=clientIO
>

> ...

>
> select {
> case v, ok := <- counts:
> // collect samples
> case reporting <- Stats{ stats }:
> case <-timer:
> // calculate stats from samples
> case cmd, ok := <-commands:
> // reset counters, restart worker, exit, etc.
> }

I'd have to study mux9p for longer, but its select chooses between two
receives, so it could possibly collapse to a single heterogenous
channel. Indeed, both its channels are already heterogenous in some
sense. Both its processTx and processRx methods say "switch
m.tx.Type".

Your second suggestion, mixing both sends (on the reporting channel)
and receives, is interesting. Would it be possible to move the
`reporting <- Stats{ stats }` case inside the `case <-timer: //
calculate stats from samples` body, though?

[Nigel Tao]

On Tue, Apr 4, 2023 at 8:06 AM Ian Lance Taylor <ia...@golang.org> wrote:
> Some of the select statements in net/http/transport.go are non-trivial.

Yeah, net/http (and its transport.go) is probably equally good an
example of selects as golang.org/x/net/http2 (and its transport.go).
But that's not really surprising, in hindsight. Thanks for the tip.

[Nigel Tao]

On Tue, Apr 4, 2023 at 10:13 AM Robert Engels <ren...@ix.netcom.com> wrote:
> I think it is as simple as looking at kselect/poll in posix. Each descriptor can be viewed as an independent channel of info/objects.
>
> Select with Go channels works similarly and has similar usefulness.

But would any problems be easier/harder if kselect/poll instead
presented a 'channel' of ready file descriptors - a "single,
heterogenous input channel"?

[Robert Engels]

Tbh I’m not sure but I am uncertain how you would get a system with 1000+ independent channels coalesced into a single channel - seems that would become highly contended/bottleneck. More importantly, I think the processing often involves subsequent stages operating on a subset of the original channels based on the earlier. If the channels were already merged into a heterogeneous queue seems that would be more difficult.

Also, with descriptors/Go channels each can be independently buffered. Not saying your C++ impl couldn’t allow similar behavior.



> On Apr 3, 2023, at 7:49 PM, Nigel Tao <nige...@golang.org> wrote:

[Nigel Tao]

Perhaps another way to look at it: in an alternative universe where
io_uring was invented first, would there be any reason to invent
select / poll / epoll (ignoring the difference between readiness and
completion)?

[Nigel Tao]

On Tue, Apr 4, 2023 at 11:22 AM Robert Engels <ren...@ix.netcom.com> wrote:
> the processing often involves subsequent stages operating on a subset of the original channels based on the earlier.

I get that, in theory. Rob's pause channel is a simple example of
that. Do you have any other concrete examples?

[Robert Engels]

Nothing concrete but I envision a system where the super set is all the request channels - when a request is received a routine is spawned/called with the related request response and status channels - a subset of all channels.

Contrived but just thinking out loud.

> On Apr 3, 2023, at 8:28 PM, Nigel Tao <nige...@golang.org> wrote:

[Skip Tavakkolian]

On Mon, Apr 3, 2023 at 5:22 PM Nigel Tao <nige...@golang.org> wrote:
>
> On Tue, Apr 4, 2023 at 7:56 AM Skip Tavakkolian
> <skip.tav...@gmail.com> wrote:
> > mux9p, Fazlul Shahriar's port of Russ' 9pserve (plan9port)
> > https://github.com/fhs/mux9p/search?q=clientIO
> >
> > ...
> >
> > select {
> > case v, ok := <- counts:
> > // collect samples
> > case reporting <- Stats{ stats }:
> > case <-timer:
> > // calculate stats from samples
> > case cmd, ok := <-commands:
> > // reset counters, restart worker, exit, etc.
> > }
>
> I'd have to study mux9p for longer, but its select chooses between two
> receives, so it could possibly collapse to a single heterogenous
> channel. Indeed, both its channels are already heterogenous in some
> sense. Both its processTx and processRx methods say "switch
> m.tx.Type".

One side serializes the Fcall to 9P packet and the other decodes the
packet into Fcall (there is a check m.tx.Type+1 == m.rx.Type; by 9P
convention).

>
> Your second suggestion, mixing both sends (on the reporting channel)
> and receives, is interesting. Would it be possible to move the
> `reporting <- Stats{ stats }` case inside the `case <-timer: //
> calculate stats from samples` body, though?

Yes, but you'd have to have another select if you don't want to block
on reporting. I have an old piece of code that does that:
https://github.com/9nut/tcpmeter/search?q=Dispatch

I don't know if you're looking for ideas on potential API's for C
implementation, but Plan 9's (and P9P) C API for chan/select is easy
to understand and use (https://9p.io/magic/man2html/2/thread).

[Robert Engels]

Interesting - that page has “ Thread stacks are allocated in shared memory, making it valid to pass pointers to stack variables between threads and procs.”

That seems very difficult to pull off safely.

On Apr 3, 2023, at 9:46 PM, Skip Tavakkolian <skip.tav...@gmail.com> wrote:

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.

To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/CAJSxfm%2BheUJBAWd3fub-9JD2%3DovPR_oqfxWT0Dpnpg8aq5jvFw%40mail.gmail.com.

[Gaal Yahas]

https://github.com/gaal/prolix-go/blob/master/prolix.go#L521 selects on several channels. This was written as an exercise when I was learning the language and may be buggy.

The application is an interactive console filter.

[Jesper Louis Andersen]

On Tue, Apr 4, 2023 at 2:22 AM Nigel Tao <nige...@golang.org> wrote:

I'd have to study mux9p for longer, but its select chooses between two
receives, so it could possibly collapse to a single heterogenous
channel. Indeed, both its channels are already heterogenous in some
sense. Both its processTx and processRx methods say "switch
m.tx.Type".

If you crank that idea to the max, you can get away with a single mailbox for a goroutine, much like in the sense Erlang is doing it. This approach, however, sacrifices type information which is currently being upheld by the ability to select on multiple channels, each of which have different types. In my experience, the concurrency primitives are malleable in many programming languages, and you can implement one model with another, albeit at a heavy efficiency penalty due to translation.

I wouldn't be surprised if you find that a simpler model will work in 95% of all cases, and that you can find workarounds for the remaining 5% to the point where you are going to ask "what's the point?" I think the answer is "elegance and simplicity".

A view: a select statement is a synchronization of an event. A channel read or a channel write is an event. The select statement is an algebraic concat operation, in the sense it takes an array of such events and produces a new event. We often think of these events as being either "we receive something" or "we send something". But select-statements also allow for their combination of "we either send or receive something". Sometimes, serializing those events into a "send, then receive" or "receive, then send" pattern is fairly easy. Sometimes, it is exceedingly hard to pull off, and the parallel send/recv pattern is just that much more elegant and clearer. The key problem is that sends and/or receives can block, thus obstructing the other event from being processed. You can alleviate this by tasting each channel through a poll. But those solutions often end up being convoluted.

To hammer it in even more: a select statement is more than just a single concat. It also contains a body for each event. That body allows you to mediate between different event types, so even if the type of the channel varies, the rest of the code doesn't have to deal with the variance.

If you want a model which works locally, non-distributed, and cranks the above ideas even more, you should look at Concurrent ML. In that language, events are first-class values which can be manipulated by programs. There's no select, but you have lower level primitives which allows you to construct one when you need it. The key difference to something like Go is that you can dynamically build up a select as you go and then synchronize it. In Go, such statements are static in the program, and you have to resort to tricks where you disable channels by setting their variables to nil. The perhaps most interesting part of CML is the `withNACK` construction. It allows you to carry out an action if *another* event ends up being chosen. If you squint your eyes---it has to be really really hard, admittedly---it's a vast generalization of Go's `defer`. Where defer cleans up on aborts in functions, withNACK cleans up after aborted events (under a select).

--

J.

[Dan Kortschak]

On Mon, 2023-04-03 at 14:59 -0700, Skip Tavakkolian wrote:
> Nice pause/resume. I'll need to remember this.
>
> On Mon, Apr 3, 2023 at 3:14 AM Rob Pike <r...@golang.org> wrote:
> >
> > Here's an excerpt from a piece of concurrent code I like, an
> > unpublished interactive game of life. The select near the bottom
> > has only two cases but it is perhaps instructive. I leave its
> > analysis to the reader.
> >
> > -rob

I needed something just like this recently for pausing/un-pausing
graphic animation to swap out animated graphics while keeping frame
position, and allowing cancellation.

It doesn't use a single channel of events to drive the pause behaviour
because pause is not a toggle in this system (for safety), so it's less
elegant in that sense, but it does require the consideration of the
hold, release and the context.Done chans.


https://go.dev/play/p/uyuP94Tvi50

[p...@morth.org]

Sarama's producer might qualify as interesting. https://pkg.go.dev/github.com/Shopify/sarama#example-AsyncProducer-Select

You're supposed to produce messages on a channel while simultaneously listening for acks (optional) and errors (mandatory) in the same select loop.

Regards,

Per Johansson

[Bakul Shah]

On Apr 4, 2023, at 6:20 AM, Jesper Louis Andersen <jesper.lou...@gmail.com> wrote:

On Tue, Apr 4, 2023 at 2:22 AM Nigel Tao <nige...@golang.org> wrote:

I'd have to study mux9p for longer, but its select chooses between two
receives, so it could possibly collapse to a single heterogenous
channel. Indeed, both its channels are already heterogenous in some
sense. Both its processTx and processRx methods say "switch
m.tx.Type".

If you crank that idea to the max, you can get away with a single mailbox for a goroutine, much like in the sense Erlang is doing it. This approach, however, sacrifices type information which is currently being upheld by the ability to select on multiple channels, each of which have different types. In my experience, the concurrency primitives are malleable in many programming languages, and you can implement one model with another, albeit at a heavy efficiency penalty due to translation.

Note that in Erlang (as well as Hewitt's pure Actor Model) a send never blocks.

This means an Erlang process mailbox can grow unbounded (or bounded only

by available memory) and you need app specific ways to deal with that. In Go

a channel is bounded; which implies a send can block.

Nigel Tao wrote in his original message

it may be possible to work around that by downstream
actors sending "I'm ready to receive" events onto the upstream actor's
heterogenous input channel.

Which made me wonder if the actors he is talked about are actors in the sense

of the Actor Model or Erlang (not the same but close) or if he was using it more

generically -- an entity carrying out some action.

I wouldn't be surprised if you find that a simpler model will work in 95% of all cases, and that you can find workarounds for the remaining 5% to the point where you are going to ask "what's the point?" I think the answer is "elegance and simplicity".

I would think it is more a question of which model he wants to implement (as why) as Go is based on Hoare's CSP model which is quite different from the Actor concurrency model....

A view: a select statement is a synchronization of an event. A channel read or a channel write is an event. The select statement is an algebraic concat operation, in the sense it takes an array of such events and produces a new event. We often think of these events as being either "we receive something" or "we send something". But select-statements also allow for their combination of "we either send or receive something". Sometimes, serializing those events into a "send, then receive" or "receive, then send" pattern is fairly easy. Sometimes, it is exceedingly hard to pull off, and the parallel send/recv pattern is just that much more elegant and clearer. The key problem is that sends and/or receives can block, thus obstructing the other event from being processed. You can alleviate this by tasting each channel through a poll. But those solutions often end up being convoluted.

You can always add more goroutines to avoid selecting over more than one channel!

[Andrew Harris]

I was surprised looking through old code that I didn't have much in the way of "interesting, non-trivial" selects - in every case where I remember doing something interesting through a select statement, later versions had moved to less interesting selects, more interesting messages from channels in the select arms. Non-deterministic selection between a flat list of edges is very clear to reason about. Channels of (some carefully composed type of functions and channels and tokens etc.) are possible, so messages can be pretty interesting.

Generally I think each example could be motivated as a scheduling gadget ... I briefly looked at some job queueing libraries (temporal.io, asynq) to see if they had "interesting" selects, they also looked like they were going more towards interesting messages.