Go or-channel pattern — recursive select vs reflect.Select

Contents

  1. 1. Approach 1: recursion
  2. 2. Approach 2: reflection
  3. 3. Benchmarks

The or-channel pattern waits on several concurrent tasks and proceeds as soon as any one completes.

Two implementations:

Approach 1: recursion

Binary split: select on halves recursively. When the first underlying channel wins, close orDone so readers see completion.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
// given several channels, return orDone that closes when any input is ready
func Or(channels ...<-chan interface{}) <-chan interface{} {
switch len(channels) {
case 0:
// nil channel — receive blocks forever
return nil
case 1:
return channels[0]
}

orDone := make(chan interface{})
go func() {
// closing orDone broadcasts completion
defer close(orDone)

switch len(channels) {
case 2:
select {
case <-channels[0]:
case <-channels[1]:
}
default:
m := len(channels) / 2
select {
case <-Or(channels[:m]...):
case <-Or(channels[m:]...):
}
}
}()

return orDone
}

Approach 2: reflection

reflect.SelectCase describes one select arm (send or recv):

1
2
3
4
5
type SelectCase struct {
Dir SelectDir // direction of case
Chan Value // channel to use (for send or receive)
Send Value // value to send (for send)
}

Build a slice of receive cases and call reflect.Select:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func OrInReflect(channels ...<-chan interface{}) <-chan interface{} {
switch len(channels) {
case 0:
return nil
case 1:
return channels[0]
}

orDone := make(chan interface{})
go func() {
defer close(orDone)
var cases []reflect.SelectCase
for _, c := range channels {
cases = append(cases, reflect.SelectCase{
Dir: reflect.SelectRecv,
Chan: reflect.ValueOf(c),
})
}

reflect.Select(cases)
}()

return orDone
}

Benchmarks

Both scale to many channels; recursion vs reflection is not obvious on paper.

Helper stream:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func AsStream(done <-chan struct{}, values ...interface{}) <-chan interface{} {
s := make(chan interface{})
go func() {
defer close(s)
for _, v := range values {
select {
case <-done:
return
case s <- v:
}
}
}()
return s
}

Benchmark harness:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var funcs = []struct {
name string
f func(...<-chan interface{}) <-chan interface{}
}{
{"reflection", OrInReflect},
{"recursion", OrRecur},
}
func BenchmarkOr(b *testing.B) {
for _, f := range funcs {
for n := 8; n <= 1024; n *= 2 {
b.Run(fmt.Sprintf("%s/%d", f.name, n), func(b *testing.B) {
for i := 0; i < b.N; i++ {
b.StopTimer()
done := make(chan struct{})
defer close(done)
streams := make([]<-chan interface{}, n)
for i := range streams {
streams[i] = AsStream(done, []interface{}{1})
}
b.StartTimer()
<-f.f(streams...)
}
})
}
}
}

Sample results (darwin/amd64, i7-8750H):

1
2
3
4
5
BenchmarkOr/reflection/8-12                    60044             22924 ns/op
...
BenchmarkOr/recursion/8-12 186949 6770 ns/op
...
BenchmarkOr/recursion/1024-12 3112 645105 ns/op

Chart:

Or-channel benchmark: recursion vs reflection

With many channels, the recursive version was faster in these runs.

Questions? Leave a comment below or email: newbvirgil@gmail.com