Uniform fairness was my goal, not ordering the selection. A hard real-time
program would require the deterministic latency this would provide.
I agree that any program requiring an ordered selection probably is broken.
Perhaps another method could be used to detect such code.
John
John Souvestre - New Orleans LA
From: Axel Wagner [mailto:axel.wagner...@googlemail.com]
Sent: 2017 October 29, Sun 02:18
To: John Souvestre
Cc: golang-nuts
Subject: Re: [go-nuts] Re: select is still a little unfair if there are more
than 4 cases?
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.
