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>
diff --git a/src/runtime/select.go b/src/runtime/select.go
index 5e5047b..63d436a 100644
--- a/src/runtime/select.go
+++ b/src/runtime/select.go
@@ -389,6 +389,7 @@
k.releasetime = sglist.releasetime
}
if sg == sglist {
+ // sg has already been dequeued by the G that woke us up.
cas = k
} else {
c = k._chan
@@ -624,23 +625,36 @@
return
}
-func (q *waitq) dequeueSudoG(s *sudog) {
- var prevsgp *sudog
- l := &q.first
- for {
- sgp := *l
- if sgp == nil {
+func (q *waitq) dequeueSudoG(sgp *sudog) {
+ x := sgp.prev
+ y := sgp.next
+ if x != nil {
+ if y != nil {
+ // middle of queue
+ x.next = y
+ y.prev = x
+ sgp.next = nil
+ sgp.prev = nil
return
}
- if sgp == s {
- *l = sgp.next
- if q.last == sgp {
- q.last = prevsgp
- }
- s.next = nil
- return
- }
- l = &sgp.next
- prevsgp = sgp
+ // end of queue
+ x.next = nil
+ q.last = x
+ sgp.prev = nil
+ return
+ }
+ if y != nil {
+ // start of queue
+ y.prev = nil
+ q.first = y
+ sgp.next = nil
+ return
+ }
+
+ // x==y==nil. Either sgp is the only element in the queue,
+ // or it has already been removed. Use q.first to disambiguate.
+ if q.first == sgp {
+ q.first = nil
+ q.last = nil
}
}
