Recursive orDone — goroutine leaks and infinite recursion with three channels

Contents

  1. 1. Goroutine leak
  2. 2. Infinite recursion

While fixing benchmarks for “two ways to implement orDone”, I found bugs in the binary-recursive version — mainly goroutine leaks. See also learning orDone the hard way.

Goroutine leak

1
2
3
4
5
6
7
8
9
10
11
12
13
14
orDone := make(chan interface{})
go func() {
defer close(orDone)
switch len(channels) {
case 2: // two inputs — special case
...
default: // more than two — binary split
m := len(channels) / 2
select {
case <-or(channels[:m]...):
case <-or(channels[m:]...):
}
}
}()

The recursive branches never merged the parent orDone channel. After orDone closed, nested goroutines had no signal to exit.

Fix by appending orDone into each recursive call:

1
2
3
4
select {
case <-OrWithIssue(append(channels[:m:m], orDone)...):
case <-OrWithIssue(append(channels[m:], orDone)...):
}

Infinite recursion

With three channels, the old split still recursed forever. The reference post includes goroutine-count prints if you want to reproduce.

Recursion tree:

1
2
3
4
5
6
7
// with 3 channels, unbounded recursion:
f(3)
f(2) f(3)
f(2) f(3)
f(2) f(3)
...

Treat n == 3 as its own case.

Final version:

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
33
34
35
36
func OrRecur(channels ...<-chan interface{}) <-chan interface{} {
// special cases: 0 or 1 channel
switch len(channels) {
case 0:
return nil
case 1:
return channels[0]
}

orDone := make(chan interface{})
go func() {
defer close(orDone)

switch len(channels) {
case 2:
select {
case <-channels[0]:
case <-channels[1]:
}
case 3:
select {
case <-channels[0]:
case <-channels[1]:
case <-channels[2]:
}
default:
m := len(channels) / 2
select {
case <-OrRecur(append(channels[:m:m], orDone)...):
case <-OrRecur(append(channels[m:], orDone)...):
}
}
}()

return orDone
}

After the fix, benchmarks favored binary recursion over reflection on time. Memory profiles looked similar.

Wall time comparison for orDone implementations
Allocation comparison for orDone implementations

Benchmark source: Dig101-Go orDone

The orDone pattern looks simple; channels still reward careful shutdown and edge cases.

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