Benchmark aggregating channels vs. reflect.Select

dynamic_select_test.go

package scratch

import (
	"reflect"
	"sync"
	"testing"
)

/*

Results with Go1.5 on a 4 CPU 8 core Xeon E3-1245 v3 @ 3.40GHz

go test -bench=. -cpu=1,4 -benchtime=5s

BenchmarkGoSelectSetup       	  100000	     66270 ns/op	     604 B/op	       4 allocs/op
BenchmarkGoSelectSetup-4     	  300000	     24411 ns/op	     278 B/op	       2 allocs/op
BenchmarkReflectSelectSetup  	 1000000	     35488 ns/op	    6144 B/op	       1 allocs/op
BenchmarkReflectSelectSetup-4	 1000000	     29511 ns/op	    6144 B/op	       1 allocs/op
BenchmarkGoSelectOne         	20000000	       487 ns/op	       0 B/op	       0 allocs/op
BenchmarkGoSelectOne-4       	20000000	       392 ns/op	       0 B/op	       0 allocs/op
BenchmarkReflectSelectOne    	  500000	     59533 ns/op	    9206 B/op	      85 allocs/op
BenchmarkReflectSelectOne-4  	  500000	     55471 ns/op	   11089 B/op	     103 allocs/op
BenchmarkGoSelect            	     100	  50316049 ns/op	     193 B/op	       3 allocs/op
BenchmarkGoSelect-4          	     200	  39271425 ns/op	     117 B/op	       2 allocs/op
BenchmarkReflectSelect       	       2	4119766788 ns/op	622802656 B/op	 5833761 allocs/op
BenchmarkReflectSelect-4     	       1	5020789519 ns/op	1088873568 B/op	10112874 allocs/op

Comparing *GoSelect* to *ReflectSelect* benchmarks (here "old" is GoSelect, "new" is ReflectSetup):

benchmark                                    old ns/op     new ns/op      delta
Benchmark{GoSelect,ReflectSelect}Setup       66270         35488          -46.45%
Benchmark{GoSelect,ReflectSelect}Setup-4     24411         29511          +20.89%
Benchmark{GoSelect,ReflectSelect}One         487           59533          +12124.44%
Benchmark{GoSelect,ReflectSelect}One-4       392           55471          +14050.77%
Benchmark{GoSelect,ReflectSelect}            50316049      4119766788     +8087.78%
Benchmark{GoSelect,ReflectSelect}-4          39271425      5020789519     +12684.84%

benchmark                                    old allocs     new allocs     delta
Benchmark{GoSelect,ReflectSelect}Setup       4              1              -75.00%
Benchmark{GoSelect,ReflectSelect}Setup-4     2              1              -50.00%
Benchmark{GoSelect,ReflectSelect}One         0              85             +Inf%
Benchmark{GoSelect,ReflectSelect}One-4       0              103            +Inf%
Benchmark{GoSelect,ReflectSelect}            3              5833761        +194458600.00%
Benchmark{GoSelect,ReflectSelect}-4          2              10112874       +505643600.00%

benchmark                                    old bytes     new bytes      delta
Benchmark{GoSelect,ReflectSelect}Setup       604           6144           +917.22%
Benchmark{GoSelect,ReflectSelect}Setup-4     278           6144           +2110.07%
Benchmark{GoSelect,ReflectSelect}One         0             9206           +Inf%
Benchmark{GoSelect,ReflectSelect}One-4       0             11089          +Inf%
Benchmark{GoSelect,ReflectSelect}            193           622802656      +322695576.68%
Benchmark{GoSelect,ReflectSelect}-4          117           1088873568     +930661069.23%

The reflect code is more complex and the only place where it's faster is setup with GOMAXPROCS=1

A slightly fairer comparison might make both include information on
which channel was read from (trivial for reflect, requires the merged
channel to be a struct with that information added by the merging
goroutines).

The below code is still very ugly; it was just a quick hack to improve the original which wasn't
producing any useful results because it failed to use `b.N` within the benchmark code.

*/

// makeChannels returns `nc` channels each of which will be sent `ni`
// values and then closed.
func makeChannels(nc, ni int) []chan int {
	chans := make([]chan int, nc)
	for i := 0; i < nc; i++ {
		c := make(chan int)
		go func(c chan int, n int) {
			for i := 0; i < n; i++ {
				c <- i
			}
			close(c)
		}(c, ni)
		chans[i] = c
	}
	return chans
}

// SetupReflectSelect does setup for do a reflect.Select on a slice of channels.
// Seperated out for benchmarking setup separately if desired.
func SetupReflectSelect(channels []chan int) []reflect.SelectCase {
	cases := make([]reflect.SelectCase, len(channels))
	for i, c := range channels {
		cases[i] = reflect.SelectCase{
			Dir:  reflect.SelectRecv,
			Chan: reflect.ValueOf(c),
		}
	}
	return cases
}

func OneReflectSelect(p *[]reflect.SelectCase) int64 {
	cases := *p
	i, value, ok := reflect.Select(cases)
	if !ok {
		cases = append(cases[:i], cases[i+1:]...)
	}
	*p = cases
	return value.Int()
}

func DoReflectSelect(cases []reflect.SelectCase) int64 {
	var result int64 = 0

	for len(cases) > 0 {
		if i, value, ok := reflect.Select(cases); !ok {
			cases = append(cases[:i], cases[i+1:]...)
		} else {
			result += value.Int()
		}
	}
	return result
}

func SetupGoSelect(channels []chan int) <-chan int {
	m := make(chan int)
	var wg sync.WaitGroup
	wg.Add(len(channels))
	for _, c := range channels {
		go func(c chan int) {
			for v := range c {
				m <- v
			}
			wg.Done()
		}(c)
	}
	go func() {
		wg.Wait()
		close(m)
	}()
	return m
}

func OneGoSelect(m <-chan int) int64 {
	// We don't actually use select since all the channels
	// are merged into one
	return int64(<-m)
}

func DoGoSelect(m <-chan int) int64 {
	var result int64
	for v := range m {
		result += int64(v)
	}
	return result
}

const numProduce = 1000
const numChannels = 100
const expectedResult = numChannels * numProduce * (numProduce - 1) / 2

func BenchmarkGoSelectSetup(b *testing.B) {
	b.ReportAllocs()
	b.StopTimer()
	channels := makeChannels(numChannels, numProduce)
	b.StartTimer()
	for i := 0; i < b.N; i++ {
		_ = SetupGoSelect(channels)
	}
}

func BenchmarkReflectSelectSetup(b *testing.B) {
	b.ReportAllocs()
	b.StopTimer()
	channels := makeChannels(numChannels, numProduce)
	b.StartTimer()
	for i := 0; i < b.N; i++ {
		_ = SetupReflectSelect(channels)
	}
}

func BenchmarkGoSelectOne(b *testing.B) {
	b.ReportAllocs()
	n := 0
	var merged <-chan int
	for i := 0; i < b.N; i++ {
		if n <= 0 {
			b.StopTimer()
			channels := makeChannels(numChannels, numProduce)
			merged = SetupGoSelect(channels)
			n = numChannels * numProduce / 2
			b.StartTimer()
		}
		n--
		_ = OneGoSelect(merged)
	}
}

func BenchmarkReflectSelectOne(b *testing.B) {
	b.ReportAllocs()
	n := 0
	var cases []reflect.SelectCase
	for i := 0; i < b.N; i++ {
		if n <= 0 {
			b.StopTimer()
			channels := makeChannels(numChannels, numProduce)
			cases = SetupReflectSelect(channels)
			n = numChannels * numProduce / 2
			b.StartTimer()
		}
		n--
		_ = OneReflectSelect(&cases)
	}
}

func BenchmarkGoSelect(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		b.StopTimer()
		channels := makeChannels(numChannels, numProduce)
		b.StartTimer()
		merged := SetupGoSelect(channels)
		result := DoGoSelect(merged)
		checkResult(b, result)
	}
}

func BenchmarkReflectSelect(b *testing.B) {
	b.ReportAllocs()
	for i := 0; i < b.N; i++ {
		b.StopTimer()
		channels := makeChannels(numChannels, numProduce)
		b.StartTimer()
		cases := SetupReflectSelect(channels)
		result := DoReflectSelect(cases)
		checkResult(b, result)
	}
}

func TestGoSelect(t *testing.T) {
	channels := makeChannels(numChannels, numProduce)
	merged := SetupGoSelect(channels)
	result := DoGoSelect(merged)
	checkResult(t, result)
}

func TestReflectSelect(t *testing.T) {
	channels := makeChannels(numChannels, numProduce)
	cases := SetupReflectSelect(channels)
	result := DoReflectSelect(cases)
	checkResult(t, result)
}

func checkResult(tb testing.TB, result int64) {
	if result != expectedResult {
		tb.Fatalf("Fail! Expected %v but got %v", expectedResult, result)
	}
}