runtime: use doubly-linked lists for channel send/recv queues.

Avoids a potential O(n^2) performance problem when dequeueing
from very popular channels.

benchmark                old ns/op     new ns/op     delta
BenchmarkChanPopular     2563782       627201        -75.54%

Change-Id: I231aaeafea0ecd93d27b268a0b2128530df3ddd6
Reviewed-on: https://go-review.googlesource.com/1200
Reviewed-by: Russ Cox <rsc@golang.org>

1 files changed, 23 insertions, 0 deletions

diff --git a/src/runtime/chan_test.go b/src/runtime/chan_test.go
index e689ceaed1..8a357c1f23 100644
--- a/src/runtime/chan_test.go
+++ b/src/runtime/chan_test.go
@@ -818,3 +818,26 @@ func BenchmarkChanSem(b *testing.B) {
 		}
 	})
 }
+
+func BenchmarkChanPopular(b *testing.B) {
+	const n = 1000
+	c := make(chan bool)
+	var a []chan bool
+	for j := 0; j < n; j++ {
+		d := make(chan bool)
+		a = append(a, d)
+		go func() {
+			for i := 0; i < b.N; i++ {
+				select {
+				case <-c:
+				case <-d:
+				}
+			}
+		}()
+	}
+	for i := 0; i < b.N; i++ {
+		for _, d := range a {
+			d <- true
+		}
+	}
+}