Apart from practical concerns about how to implement determinism, the specification of randomness exists for a reason: It prevents programs from depending on any specific choice for correctness.
(Which is why I asked above what the actual problem is if select isn't perfectly uniform but just "pretty darn close to. It would seem to me, that a program depending on uniformity is probably broken) On Sun, Oct 29, 2017 at 7:38 AM, John Souvestre <j...@souvestre.com> wrote: > Ø So a goroutine has storage for every possible select in the program? > If you do it statically, that's a lot of storage. If you do it > dynamically, then you have a dynamic select -> nextcase map you have to > maintain. > > Ø You can put that storage on the stack, but just barely: it has to live > as long as the goroutine does, so it has to be at the very top. > > > > Dynamic sounds like the better way. How do you think the run-time > overhead would compare to the current random method? > > > > John > > John Souvestre - New Orleans LA > > > > *From:* golang-nuts@googlegroups.com [mailto:golang-nuts@googlegroups.com] > *On Behalf Of *keith.rand...@gmail.com > *Sent:* 2017 October 29, Sun 01:23 > > *To:* golang-nuts > *Subject:* Re: [go-nuts] Re: select is still a little unfair if there are > more than 4 cases? > > > > > > On Saturday, October 28, 2017 at 11:11:02 PM UTC-7, John Souvestre wrote: > > Ø Round robin isn't implementable. There's no place to store the state > for an individual select. > > > > Couldn’t a place be allocated? Since it would be local to a goroutine, > put it on the stack. > > > > Ø I'm not sure how you would even define round robin. What's the unit > that's being round-robined? An individual select statement across all > goroutines? A select statement and goroutine pair? A select statement + > function instance pair? > > > > An individual select in a goroutine. > > > > > > So a goroutine has storage for every possible select in the program? If > you do it statically, that's a lot of storage. If you do it dynamically, > then you have a dynamic select -> nextcase map you have to maintain. > > You can put that storage on the stack, but just barely: it has to live as > long as the goroutine does, so it has to be at the very top. > > > > John > > John Souvestre - New Orleans LA > > > > *From:* golan...@googlegroups.com [mailto:golan...@googlegroups.com] *On > Behalf Of *keith....@gmail.com > *Sent:* 2017 October 28, Sat 18:38 > *To:* golang-nuts > *Subject:* Re: [go-nuts] Re: select is still a little unfair if there are > more than 4 cases? > > > > On Saturday, October 28, 2017 at 2:59:53 PM UTC-7, John Souvestre wrote: > > Ø I don't think it needs to be uniformly fair. It just needs to prevent > starvation of a channel for infinity. Any proof would have progress covered > if we pick every channel once in a while, even under a heavily unfair > weighting. You have to balance out the overhead of rolling a fair dice and > the speed at which you can select on channels. > > > > If it were uniformly fair then you couldn’t guarantee picking every > channel once in a while. Statistically it would be become more and more > probable, but never 100%. > > > > Why not just use round-robin? That would guarantee it and it’s a faster > algorithm, I would think. Also, it would sometimes save checking all cases > since you could check them in order, stopping when (if) you found one ready. > > > > Are there situations where it is better for it to be random or is there > some implementation advantage (not having to save state for the select)? > > > > > > Round robin isn't implementable. There's no place to store the state for > an individual select. And you can't store the state in the G (goroutine) > or M (os thread) because then: > > for { > > select { > > case <-x: > > case <-y: > } > > select { > > case <-y: > > case <-x: > } > } > > > > would never read from y (or x, depending on the initial state). > > > > I'm not sure how you would even define round robin. What's the unit > that's being round-robined? An individual select statement across all > goroutines? A select statement and goroutine pair? A select statement + > function instance pair? > > (The last one is actually implementable - but then select statements > behave differently if you wrap them in a function.) > > > > John > > John Souvestre - New Orleans LA > > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > > -- > You received this message because you are subscribed to the Google Groups > "golang-nuts" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to golang-nuts+unsubscr...@googlegroups.com. > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "golang-nuts" group. To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/d/optout.
