code review 112990043: runtime: fine-grained locking in select

runtime: fine-grained locking in select
Never lock more than one channel at a time.
Also makes lockorder and channel sorting unnecessary.
Details of the algorithm are in comments.

benchmark                            old ns/op     new ns/op     delta
BenchmarkSelectUncontended           213           188           -11.74%
BenchmarkSelectUncontended-2         110           97.2          -11.64%
BenchmarkSelectUncontended-4         56.2          49.5          -11.92%
BenchmarkSelectUncontended-8         29.7          25.9          -12.79%
BenchmarkSelectUncontended-16        17.3          16.4          -5.20%
BenchmarkSelectUncontended-32        13.7          11.4          -16.79%
BenchmarkSelectSyncContended         795           710           -10.69%
BenchmarkSelectSyncContended-2       946           710           -24.95%
BenchmarkSelectSyncContended-4       1791          1187          -33.72%
BenchmarkSelectSyncContended-8       1749          637           -63.58%
BenchmarkSelectSyncContended-16      2109          563           -73.30%
BenchmarkSelectSyncContended-32      3165          1172          -62.97%
BenchmarkSelectAsyncContended        231           208           -9.96%
BenchmarkSelectAsyncContended-2      671           209           -68.85%
BenchmarkSelectAsyncContended-4      395           215           -45.57%
BenchmarkSelectAsyncContended-8      451           240           -46.78%
BenchmarkSelectAsyncContended-16     486           233           -52.06%
BenchmarkSelectAsyncContended-32     861           395           -54.12%
BenchmarkSelectNonblock              126           36.0          -71.43%
BenchmarkSelectNonblock-2            155           17.6          -88.65%
BenchmarkSelectNonblock-4            285           8.45          -97.04%
BenchmarkSelectNonblock-8            212           4.41          -97.92%
BenchmarkSelectNonblock-16           180           2.44          -98.64%
BenchmarkSelectNonblock-32           395           1.63          -99.59%
BenchmarkSelectProdCons              1140          926           -18.77%
BenchmarkSelectProdCons-2            653           545           -16.54%
BenchmarkSelectProdCons-4            519           352           -32.18%
BenchmarkSelectProdCons-8            667           372           -44.23%
BenchmarkSelectProdCons-16           751           431           -42.61%
BenchmarkSelectProdCons-32           1142          583           -48.95%

[dvyukov, 2014-07-14 12:00:24]

Hello golang-codereviews@googlegroups.com,

I'd like you to review this change to
https://dvyukov%40google.com@code.google.com/p/go/

[rsc, 2014-07-16 11:42:37]

not reviewing until the other CL is worked out

[dvyukov, 2014-08-25 14:07:25]

On 2014/07/16 11:42:37, rsc wrote:
> not reviewing until the other CL is worked out

The other CL is submitted.
I've updated this CL. PTAL.

[dvyukov, 2014-08-25 14:09:03]

Quick benchmarking shows that the win still holds:

benchmark                         old ns/op     new ns/op     delta
BenchmarkSelectUncontended        188           137           -27.13%
BenchmarkSelectSyncContended      687           558           -18.78%
BenchmarkSelectAsyncContended     179           140           -21.79%
BenchmarkSelectProdCons           996           819           -17.77%

[josharian, 2014-08-26 20:35:42]

This no longer applies cleanly to tip.

[dvyukov, 2014-08-30 13:04:50]

On Wed, Aug 27, 2014 at 12:35 AM,  <josharian@gmail.com> wrote:
> This no longer applies cleanly to tip.

It will get rotten every other hour now, I will update it before submit.

[gobot, 2014-12-19 05:10:33]

R=close

To the author of this CL:

The Go project has moved to Gerrit Code Review.

If this CL should be continued, please see the latest version of
https://golang.org/doc/contribute.html for instructions on
how to set up Git and the Go project's Gerrit codereview plugin,
and then create a new change with your current code.

If there has been discussion on this CL, please give a link to it
(golang.org/cl/112990043 is best) in the description in your
new CL.

Thanks very much.