proposal: Go 2: hierarchical select

[MirceaS]

Author background

• Would you consider yourself a novice, intermediate, or experienced Go programmer?
• I'm pretty new to Go but I've used it to implement some reasonably complex, non-trivial networking protocols.
• What other languages do you have experience with?
• C++, C, Haskell, Java, Python

Related proposals

• Has this idea, or one like it, been proposed before?
• Not as far as I can tell. If it has been, I apologise.
  • If so, how does this proposal differ?
• Does this affect error handling?
• No
  • If so, how does this differ from previous error handling proposals?
• Is this about generics?
• No
  • If so, how does this relate to the accepted design and other generics proposals?

Proposal

• What is the proposed change?

At the moment, when writing a select statement in Go I would write something like:

select {
        case x := <-c1:
            ...
        case x := <-c2:
            ...
        }

where if both c1 and c2 have pending entries, one of them will be selected uniformly at random.
I quite often, however, found myself wishing to write some program logic that would require the select statement to prioritize consuming from a specific channel rather than another, if both are populated.
As far as I am aware there is no mechanism in Go to do this. There are some workarounds that can be implemented, presented here but they all suffer from either not implementing the exact logic required, being very convoluted or being really inefficient (because they effectively end up acting as spin locks).
I know there are good reasons for having the nondeterministic choice be the default but I believe my proposal would be fully backwards compatible, preserving this behavior, while incorporating a new mechanism for prioritizing one or more channels.
My proposal would be the introduction of a new token that can go inside select statements (on the same level as default). For the rest of this document, I will assume that this token is called or: but I have no strong feelings for what it should be called. This token will partition the select statement into blocks separated by or::

select {
        case x := <-c1:
            ...
        case x := <-c2:
            ...
        or:
        case x := <-c3:
            ...
        default:
            ...
        }

If one or more channels from a given block has a pending value in it, it i guaranteed that the select statement will not choose to read from a channel in a succeeding block. default: will still work the same way, regardless of which block it belongs to (though it should be common practice to add it in the last one).
This language feature would be fully backwards compatible since a statement with a single block will act like a normal select statement in current Go, but it will offer a very easy and intuitive way for people to work with hierarchical select statements and implement more complex and safe logic. The number of views on the Stack Exchange page that I liked earlier seems to suggest that there are a fair amount of people interested in a feature like this.

I don't have data to back this up, but I feel like there must be a fair amount of users trying to achieve this very thing using suboptimal solutions, so why not make it a language feature?

Costs

• Would this change make Go easier or harder to learn, and why?
• I think it would make it more expressive and thus more fun to work with, especially to a beginner
• What is the cost of this proposal? (Every language change has a cost).
• I guess the main cost would be engineering this feature into the language but I don't think it would have a recurrent cost after that.
• How many tools (such as vet, gopls, gofmt, goimports, etc.) would be affected?
• I don't know.
• What is the compile time cost?
• Possibly slightly slower? Though if a user chooses to not use this feature then things should remain the same.
• What is the run time cost?
• I don't expect there to be a significant runtime cost
• Can you describe a possible implementation?
• Not with my current knowledge of the internals of Go compilation
• Do you have a prototype? (This is not required.)
• No

[seankhliao]

see also recent discussion: https://groups.google.com/g/golang-nuts/c/I9cbvCB86MA/m/GCKIJbzPAAAJ

[ianlancetaylor]

It seems to me that instead of or one could write

        select {
        case x := <-c1:
            ...
        case x := <-c2:
            ...
        default:
                select {
                        case x := <-c3:
                            ...
                        default:
                            ...
                }
        }

[MirceaS]

It seems to me that instead of or one could write

        select {
        case x := <-c1:
            ...
        case x := <-c2:
            ...
        default:
                select {
                        case x := <-c3:
                            ...
                        default:
                            ...
                }
        }

@ianlancetaylor

I suppose that if you have a default in your select statement, then these are almost equivalent. But consider the case where you don't want to have a default:

        select {
        case x := <-c1:
            ...
        case x := <-c2:
            ...
        default:
                select {
                        case x := <-c3:
                            ...
                }
        }

If c1 and c2 are empty then we will move on to the next select statement that only waits on c3. If then something comes up on c1, then we won't be reading from that. So the behavior of this construct is different from my suggestion. In my proposal, c1 would still be read from if nothing comes up on c3.

[jfesler]

I too would like to see a deterministic select (vs random), at least as an option. Syntax, I'm not married to any particular ideas.

Right now I have this, which .. is on the racey side.

select {
    case x := <-c1:
        ...
        default:
                select {
                        case x := <-c1:
                            ...
                        case x := <-c2:
                            ...
                }
        }
 }

If I don't have C1 immediately ready, and then both C1/C2 show up "simultaneously", it's random which one of C1/C2 will get the flow. And happens enough to make unit tests flakey.

In reality, I'm actually doing 3 channels, with "best effort priority", but the code for that is really nasty. If this, then that. Otherwise, if those, do those. Otherwise, do all 3. With too much duplication, in a loop that's already expensive.

I've also had to learn (and re-learn at least once more) the hard way that selects are non-deterministic. But that's on me, the docs are clear, even when the behavior is non-intuitive.

[DeedleFake]

It seems to me that the ordering of select is not the best way to deal with the ordering of elements. It seems better to create a priority-queued channel intermediary, which is fairly easy to do now that generics are available. For example:

Playground Link

type PriorityChanQueue[T any] struct {
	q   pqueue[T]
	out chan<- T
	add chan item[T]
}

func NewPriorityChanQueue[T any](out chan<- T) *PriorityChanQueue[T] {
	pcq := PriorityChanQueue[T]{
		out: out,
		add: make(chan item[T]),
	}
	go pcq.loop()
	return &pcq
}

func (pcq PriorityChanQueue[T]) Stop() {
	close(pcq.add)
}

func (pcq PriorityChanQueue[T]) Add(p int, v T) {
	pcq.add <- item[T]{p: p, v: v}
}

func (pcq PriorityChanQueue[T]) C(p int, c <-chan T) {
	go func() {
		for v := range c {
			pcq.add <- item[T]{p: p, v: v}
		}
	}()
}

func (pcq *PriorityChanQueue[T]) loop() {
	defer close(pcq.out)

	var out chan<- T
	add := pcq.add
	for {
		select {
		case out <- pcq.q.Peek():
			pcq.q.Pop()
			if len(pcq.q) == 0 {
				if add == nil {
					return
				}
				out = nil
			}

		case v, ok := <-add:
			if !ok {
				add = nil
				continue
			}

			pcq.q.Push(item[T]{p: v.p, v: v.v})
			out = pcq.out
		}
	}
}

Maybe something like this, but with more thought put into it than this really quick example, could be added to x/sync?

[rittneje]

If I don't have C1 immediately ready, and then both C1/C2 show up "simultaneously", it's random which one of C1/C2 will get the flow.

I would think that in practice it is extremely unlikely that two different channels could be unblocked literally simultaneously. And even if by shear luck they did, you wouldn't be able to prove it anyway. Consequently, I feel like this aspect of a priority select is ill-defined.

However, defining priority for the initial evaluation of the select cases, instead of simply randomly selecting among the available ones, is well-defined and very useful. As was mentioned, you can more or less get this behavior today with a bunch of selects with default cases, but it is quite cumbersome when you have multiple cases. So it would definitely help to be able to do something like this:

select first {
case <-c1:
   ...
case <-c2:
   ...
case <-c3:
  ...
...
}

[DeedleFake]

I would think that in practice it is extremely unlikely that two different channels could be unblocked literally simultaneously. And even if by shear luck they did, you wouldn't be able to prove it anyway. Consequently, I feel like this aspect of a priority select is ill-defined.

I'm not sure about this. For example, what if you have something like

for {
  select {
  case v := <-highPriority:
    longRunningThing(v)
  case v := <-lowPriority:
    otherLongRunningThing(v)
  }
}

Then several things send to each while one of those long-running things is running. By the time the loop comes around again, even with unbuffered channels, you could easily have multiple things queued up in each channel. In that case, the select will choose one randomly. What this proposal is asking for is the ability to guarantee that highPriority is completely drained before lowPriority.

I still think separate implementation is better, though. For example, if you have a select-like structure that's ordered, how do you tell it to allow stuff through from lowPriority sometimes if it's been blocked on highPriority for a while? With a priority queue, it can be tuned to whatever the client needs at the time, while select, like most language features, probably won't have too many nobs on it.

[rittneje]

@DeedleFake Yeah that's falls under the "initial evaluation" I was describing in the second paragraph. What I mean here is that once a select actually blocks the goroutine (meaning that none of the cases were available initially), then it is not really possible for more than one case to unblock simultaneously.

[rittneje]

For example, if you have a select-like structure that's ordered, how do you tell it to allow stuff through from lowPriority sometimes if it's been blocked on highPriority for a while? With a priority queue, it can be tuned to whatever the client needs at the time, while select, like most language features, probably won't have too many nobs on it.

If you actually need this level of complexity, then sure. But we generally don't. For example, it's fairly common for newcomers to write something like this:

for {
    select {
    case <-ctx.Done():
        return
    case x := <- c:
        // do something with x
    }
}

But then, there is non-determinism surrounding what happens when the context is canceled when the producer is "chatty". So then they have to rewrite it to this:

for {
    select {
    case <-ctx.Done():
        return
    default:
    }
    select {
    case <-ctx.Done():
        return
    case x := <- c:
        // do something with x
    }
}

[ianlancetaylor]

Here is an interesting example from Tailscale. This select statement wants to flush if none of the cases are true. This is done by repeating the entire select statement.

https://github.com/tailscale/tailscale/blob/main/derp/derp_server.go#L1374

I don't think this proposal handles this case. Which is not a mark against it. But it would be interesting if we could handle this somehow.

[ianlancetaylor]

@griesemer points out that a better choice than or would be else, since else is already a keyword.

[ianlancetaylor]

Based on the discussion above, and the emoji voting, there isn't strong interest in this proposal. It is always possible to write the code that one wants, with some additional verbosity; this proposal just permits some code to be written somewhat more tersely.

Therefore, this is a likely decline. Leaving open for four weeks for final comments.

[ianlancetaylor]

No further comments.