Why is the select statement non-deterministic?

<p>From the specification on <code>select</code>:</p> <blockquote> <p>If one or more of the communications can proceed, a single one that can proceed is chosen via a uniform pseudo-random selection.</p> </blockquote> <p>How come <code>select</code> can&#39;t work like <code>switch</code>es (both expression and type), which prioritize the topmost cases?</p> <hr/>**评论：**<br/><br/>TheMerovius: <pre><p>The real reason is to prevent starvation. Say you would always pick the first communication that&#39;s possible, in source-order. Now, if you have a channel with a fast sender, you will always chose to read from the first channel and no other communications get a chance to proceed. This can easily lead to undesirable effects. Choosing one uniformly at random means, that sooner or later every value will be read, so you don&#39;t have starvation.</p></pre>danredux: <pre><p>This is exactly it. It has another benefit - programmers can&#39;t rely on the order being top-most-first, which allows for optimizations compiler-side (and other things). This is the same reason why map keys are returned in random order.</p> <p>I should also say this - the most &#34;sensible&#34; approach would be FIFO... Whichever channel had an element &#34;earliest&#34; should be returned first, which would be a deterministic way of preventing starvation. It has the benefit that each channel would be consumed in the order the elements were put in, which would lower worst-case wait time. This solution isn&#39;t practical in reality, of course, because tracking that information would slow down channel operations.</p></pre>Manbeardo: <pre><p>For people who really care about latency, select is already too slow. Making it slower would be back-breaking.</p></pre>danredux: <pre><p>I didn&#39;t know select was slow. I&#39;d love to see a benchmark or something. In fact I don&#39;t even know an alternative way to, say, time out some set of io operations. </p></pre>Manbeardo: <pre><p>I can&#39;t find it right now, but a friend of mine who works on AirMech did a write-up about it on Facebook a year or two ago. They were able to cut a sizeable chunk of latency off by replacing select with mutexes and manually scanning for new output. As implemented in the standard compiler, the select statement is ~600 lines of runtime go with several function calls.</p></pre>danredux: <pre><p>Okay thanks I&#39;ll do some benches on that! Awesome.</p></pre>TheMerovius: <pre><blockquote> <p>This solution isn&#39;t practical in reality, of course, because tracking that information would slow down channel operations.</p> </blockquote> <p>Yes, that was my conclusion also. It&#39;s also much more complicated to put into the spec. :)</p></pre>karaziox: <pre><p>This is an extension of the issue where no channel are ready when you start a select. Then, 2 goroutines can write on 2 channels that you are selecting. Unless you take measures to synchronize those two channels, you cannot know with certainty which one will be received first. The pseudo-random behavior serves as an extension to that uncertainty. It forces you to ensure the order of reception if you really need one, because you cannot trust in that order if you do not ensure it yourself, due to scheduling variation or other racy behaviors.</p> <p>Starting a select where you know that more than one channel is ready is an edge case of the select statement, it&#39;s not what it is usually used for. Enforcing a random selection ensures that people won&#39;t rely on a behavior that is only valid in that edge case, thus preventing potential bugs due to the racy nature of relying on channel timings.</p></pre>earthboundkid: <pre><p>A lot of times I find myself wishing I could prioritize a select statement and then I think about it more and realize that if I could it would just be a racing bug. </p></pre>RalphCorderoy: <pre><p>No, forcing programmers to not assume a priority is not the reason.</p></pre>tv64738: <pre><p><code>select</code> is inherently about communication between goroutines, and the timing of when a channel becomes ready is inherently not to be relied upon. The pseudo-randomness there is to enforce programming habits that acknowledge that reality; it&#39;s the same reasoning as why ranging a map intentionally scrambles the order.</p></pre>TheMerovius: <pre><p>You can tell that this is not the right answer, as the behavior of select is defined, whereas the iteration order in a map is undefined. It&#39;s an implementation detail of gc, that the iteration order is randomized, other implementations don&#39;t need to follow that (they could even choose to iterate over a map in sort-order if they wanted to). Select, on the other hand, must always be random, to prevent starvation.</p></pre>hegbork: <pre><blockquote> <p>the iteration order in a map is undefined.</p> </blockquote> <p>It&#39;s deliberately defined to be unpredictable.</p> <p>From Go 1 release notes: &#34;In Go 1, the order in which elements are visited when iterating over a map using a for range statement is defined to be unpredictable, even if the same loop is run multiple times with the same map. Code should not assume that the elements are visited in any particular order.&#34;</p> <blockquote> <p>It&#39;s an implementation detail of gc, that the iteration order is randomized</p> </blockquote> <p>It&#39;s not an implementation detail of gc. It&#39;s a deliberately added randomization.</p> <p><a href="https://golang.org/src/runtime/hashmap.go" rel="nofollow">See line 648 and forward</a></p> <p>Don&#39;t call someone out on &#34;not the right answer&#34; when you don&#39;t know yourself.</p></pre>TheMerovius: <pre><blockquote> <p>False. It&#39;s deliberately defined to be unpredictable.</p> </blockquote> <p>Let&#39;s look at the <a href="https://golang.org/ref/spec#For_statements">spec</a>, authoritative source for the language definition of go:</p> <blockquote> <p>The iteration order over maps is not specified and is not guaranteed to be the same from one iteration to the next.</p> </blockquote> <p>The segment you quoted is specific to the implementations provided by the go team. It&#39;s not part of the language spec. [edit: I even think that sentence just means it&#39;s defined to be unspecified - unpredictable doesn&#39;t mean randomized]</p> <blockquote> <p>It&#39;s not an implementation detail of gc. It&#39;s a deliberately added randomization.</p> </blockquote> <p>The two aren&#39;t mutually exclusive.</p> <blockquote> <p>Don&#39;t call someone out on &#34;not the right answer&#34; when you don&#39;t know what you&#39;re talking about.</p> </blockquote> <p>a) I do, and b) the answer is wrong <em>regardless</em> of the specification of the iteration order of maps.</p> <p>[edit] To prove my point: <a href="http://www.gopherjs.org/playground/#/hBSLA0oGWN">The iteration order of maps in GopherJS is deterministic</a>. Other implementations can choose any iteration order they like (that&#39;s pretty much the benefit of having it undefined)</p></pre>SportingSnow21: <pre><blockquote> <p>To prove my point: The iteration order of maps in GopherJS is deterministic. Other implementations can choose any iteration order they like (that&#39;s pretty much the benefit of having it undefined)</p> </blockquote> <p>You&#39;re attempting to prove your point about go&#39;s runtime by showing javascript&#39;s runtime?</p></pre>TheMerovius: <pre><p>No, by showing how a separate implementation of go does this. &#34;go&#39;s runtime&#34; is not a well-defined concept. Go has several runtimes (I can think of at least three or four) and one of them is built on the javascript runtime. So, this is not &#34;behavior of javascript&#39;s runtime&#34;, it&#39;s behavior of the one implementation of go that uses it. They were entirely free to implement whatever behavior they wish for maps (as it&#39;s undefined, that&#39;s the point), so they chose the one which is most convenient (that&#39;s <em>why</em> it&#39;s undefined, so implementors can chose the behavior that is best suited for their implementation).</p> <p>If you believe, that gopherjs&#39; behaviour is not in conformance with the spec, you should file a bug. It is, though.</p></pre>SportingSnow21: <pre><p>From the front page (GopherJS.org): </p> <blockquote> <p><strong>GopherJS - A compiler from Go to JavaScript</strong><br/> GopherJS compiles Go code (golang.org) to pure JavaScript code.</p> </blockquote> <p>GopherJS is not &#34;an implementation of go&#34;, it&#39;s a transpiler. That code is being converted to JavaScript and it&#39;s being executed as JavaScript. </p> <p>Edit: Also, &#34;undefined&#34; and &#34;unspecified&#34; are entirely different concepts. There is no sorting/ordering in place that someone can depend upon for map iterations (unspecified ordering). If iteration order was &#34;undefined&#34;, there would be no guarantee against repeating map entries. </p></pre>TheMerovius: <pre><blockquote> <p>GopherJS is not &#34;an implementation of go&#34;, it&#39;s a transpiler. </p> </blockquote> <p>The two aren&#39;t mutually exclusive. Indeed, one <em>implies</em> the other. By compiling go into <em>any</em> language, you are building an implementation of go.</p> <blockquote> <p>hat code is being converted to JavaScript and it&#39;s being executed as JavaScript.</p> </blockquote> <p>And gc implements go by transpiling it into ELF, which is then executed. Really, you are splitting hairs by trying to distinguish between compilers and transpilers to somehow support your point that GopherJS would not be an implementation of go. But it is. There is no practical difference between a transpiler and a compiler. GopherJS implements the go spec, as such it&#39;s an implementation of go. It&#39;s simple as that.</p> <blockquote> <p>Also, &#34;undefined&#34; and &#34;unspecified&#34; are entirely different concepts. There is no sorting/ordering in place that someone can depend upon for map iterations (unspecified ordering). If iteration order was &#34;undefined&#34;, there would be no guarantee against repeating map entries.</p> </blockquote> <p>I disagree with this distinction, but it&#39;s also irrelevant to the discussion.</p></pre>TheMerovius: <pre><p>As you&#39;ve not actually acknowledged that point, let me reiterate that GopherJS could have chosen to implement maps <em>however they like</em>. They could have built their own implementation of maps on top of javascript and use a randomized sort-order if they needed to. But they didn&#39;t have to, because javascript already gives a fast implementation of maps that modern javascript engines optimize to. And as <em>the spec doesn&#39;t define a map iteration order</em>, the fact that it uses sort-order is no reason not to just use it. </p></pre>