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.
On Sat, Oct 28, 2017 at 12:54 AM Michael Jones <michael.jo...@gmail.com> wrote: > the bias of %n would not be detectable in this situation...but if you > wanted it right...the perfect thing is not hard. > > On Fri, Oct 27, 2017 at 3:44 PM, T L <tapir....@gmail.com> wrote: > >> Yes, the problem is fixed totally on tip. >> The tip is using the normal mod operation "fastrand() % n". >> >> >> On Friday, October 27, 2017 at 5:17:53 PM UTC-4, Axel Wagner wrote: >>> >>> It turns out that, apparently, at least on tip (what I linked to) the >>> fastrand implementation itself is actually pretty good. You might want to >>> re-run the test on tip. fastrandn will still be somewhat biased. >>> >>> On Fri, Oct 27, 2017 at 11:05 PM, Axel Wagner <axel.wa...@googlemail.com >>> > wrote: >>> >>>> Neither. fastrand is not a perfect PRNG, as that doesn't exist (much >>>> less in…fast) and the reduction is biased (necessarily, unless you are >>>> going to resort to rejection sampling, which is slow). >>>> >>>> On Fri, Oct 27, 2017 at 11:00 PM, T L <tapi...@gmail.com> wrote: >>>> >>>>> >>>>> >>>>> On Friday, October 27, 2017 at 4:57:46 PM UTC-4, T L wrote: >>>>>> >>>>>> >>>>>> >>>>>> On Friday, October 27, 2017 at 4:51:15 PM UTC-4, Axel Wagner wrote: >>>>>>> >>>>>>> Yes. The random number generator employed (right above from what I >>>>>>> linked to; the fastrand function), apparently, is unsurprisingly >>>>>>> imperfect. >>>>>>> >>>>>> >>>>>> Why not to maintain a global start index for each goroutine? >>>>>> The value of the start index is the number of executed select blocks >>>>>> in a goroutine. >>>>>> So that we can change the fastrandn implementation to >>>>>> "return uint32(uint64(fastrand() + current_g.numExecutedSelects) * >>>>>> uint64(n) >> 32)" >>>>>> >>>>> >>>>> Aha, which function is unfair, fastrand or fastrandn? >>>>> If fastrandn is unfair, then the above trick doesn't work. >>>>> >>>>>> >>>>>> >>>>>>> >>>>>>> On Fri, Oct 27, 2017 at 10:47 PM, T L <tapi...@gmail.com> wrote: >>>>>>> >>>>>>>> It is also not uniform for powers of two. >>>>>>>> If there a 8 cases, the sixth one will only get a 80% chance of the >>>>>>>> first one. >>>>>>>> >>>>>>>> On Friday, October 27, 2017 at 4:33:47 PM UTC-4, Axel Wagner wrote: >>>>>>>>> >>>>>>>>> The code suggests, that select is indeed not fair: >>>>>>>>> >>>>>>>>> https://github.com/golang/go/blob/a4d03a9bf7604b727abd0a1ebfb118ff6366ee50/src/runtime/stubs.go#L109 >>>>>>>>> Which seems fine to me. A fair, uniform PRNG for ranges that are >>>>>>>>> not powers of two gets a fair bit of overhead and no program should >>>>>>>>> depend >>>>>>>>> on uniformity of select for correctness anyway. >>>>>>>>> >>>>>>>>> On Fri, Oct 27, 2017 at 10:28 PM, T L <tapi...@gmail.com> wrote: >>>>>>>>> >>>>>>>>>> It looks the distribution of the RNG results depends on the >>>>>>>>>> number of cases. >>>>>>>>>> The third case only gets the lowest possibility of there are 6 >>>>>>>>>> cases, >>>>>>>>>> >>>>>>>>>> >>>>>>>>>> On Friday, October 27, 2017 at 4:21:12 PM UTC-4, T L wrote: >>>>>>>>>>> >>>>>>>>>>> A better example to show the inhomogeneity of the selected >>>>>>>>>>> possibilities of each case. >>>>>>>>>>> >>>>>>>>>>> package main >>>>>>>>>>> >>>>>>>>>>> import "fmt" >>>>>>>>>>> >>>>>>>>>>> func main() { >>>>>>>>>>> foo := make(chan struct{}) >>>>>>>>>>> close(foo) >>>>>>>>>>> var a, b, c, d, e, f, g float64 >>>>>>>>>>> fa := func(){a++} >>>>>>>>>>> fb := func(){b++} >>>>>>>>>>> fc := func(){c++} >>>>>>>>>>> fd := func(){d++} >>>>>>>>>>> fe := func(){e++} >>>>>>>>>>> ff := func(){f++} >>>>>>>>>>> fg := func(){g++} >>>>>>>>>>> for i := 0; i < 1000000; i++ { >>>>>>>>>>> select { >>>>>>>>>>> case <-foo: fa() >>>>>>>>>>> case <-foo: fb() >>>>>>>>>>> case <-foo: fc() >>>>>>>>>>> case <-foo: fd() >>>>>>>>>>> case <-foo: fe() >>>>>>>>>>> case <-foo: ff() >>>>>>>>>>> case <-foo: fg() >>>>>>>>>>> } >>>>>>>>>>> } >>>>>>>>>>> fmt.Println(a/a) >>>>>>>>>>> fmt.Println(b/a) >>>>>>>>>>> fmt.Println(c/a) >>>>>>>>>>> fmt.Println(d/a) >>>>>>>>>>> fmt.Println(e/a) >>>>>>>>>>> fmt.Println(f/a) >>>>>>>>>>> fmt.Println(g/a) >>>>>>>>>>> } >>>>>>>>>>> >>>>>>>>>>> result: >>>>>>>>>>> >>>>>>>>>>> 1 >>>>>>>>>>> 0.9999052991869258 >>>>>>>>>>> 0.9015652691532394 >>>>>>>>>>> 0.9691884140319548 >>>>>>>>>>> 0.966320332264567 >>>>>>>>>>> 0.9669020658305938 >>>>>>>>>>> 0.9604624105415533 >>>>>>>>>>> >>>>>>>>>>> On Friday, October 27, 2017 at 4:08:39 PM UTC-4, T L wrote: >>>>>>>>>>>> >>>>>>>>>>>> The following program constantly prints a value larger than 1.02 >>>>>>>>>>>> >>>>>>>>>>>> package main >>>>>>>>>>>> >>>>>>>>>>>> import "fmt" >>>>>>>>>>>> >>>>>>>>>>>> func main() { >>>>>>>>>>>> foo, bar := make(chan struct{}), make(chan struct{}) >>>>>>>>>>>> close(foo) >>>>>>>>>>>> close(bar) >>>>>>>>>>>> x, y := 0.0, 0.0 >>>>>>>>>>>> f := func(){x++} >>>>>>>>>>>> g := func(){y++} >>>>>>>>>>>> for i := 0; i < 1000000; i++ { >>>>>>>>>>>> select { >>>>>>>>>>>> case <-bar: g() >>>>>>>>>>>> case <-foo: f() >>>>>>>>>>>> case <-bar: g() >>>>>>>>>>>> case <-foo: f() >>>>>>>>>>>> case <-bar: g() >>>>>>>>>>>> case <-foo: f() >>>>>>>>>>>> } >>>>>>>>>>>> } >>>>>>>>>>>> fmt.Println(x/y) >>>>>>>>>>>> } >>>>>>>>>>>> >>>>>>>>>>>> if the last two cases are removed, then it becomes quit fair. >>>>>>>>>>>> >>>>>>>>>>> -- >>>>>>>>>> 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...@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...@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. >> > > > > -- > Michael T. Jones > michael.jo...@gmail.com > > -- > 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.
