Simple Factorial?
dylan m
concurrently.
When I ran this program in the Go playground, I was surprised that the
result was wrong.
When I run it on my computer, it is sometimes right and sometimes
wrong.
Why isn't this deterministic? What am I missing?
--------------------------------------------------------------------------
package main
import "fmt"
func gen(ch chan int64, n int64) {
for i := int64(2); i<=n; i++ {
fmt.Println("in <- ", i)
ch <- i
}
close(ch)
}
func mul(in chan int64, out chan int64) {
var fact int64 = 1
for t := range in {
fmt.Println("in -> ", t)
fact *= t
}
out <- fact
}
func main() {
var n int64 = 10
var p int = 4
in := make(chan int64)
go gen(in, n)
out := make(chan int64)
for i := 0; i < p; i++ {
go mul(in, out)
}
var fact int64 = 1
for i := 0; i < p; i++ {
fact *= <-out
}
fmt.Println(fact)
}
--------------------------------------------------------------------------
andrey mirtchovski
on it more clearly. What's happening is that, contrary to the spec
(NB: the spec actually says "any values are read", not "all values are
read", so perhaps this should be clarified by those who wrote it), if
you call close() on a channel with multiple readers, then the last
value written to the channel will sometimes not be read by any of the
readers.
I've made a smaller sample out of your code by removing all the
factorial stuff and printing out all the values read/written. the last
value before closed() is called is 9, but more often than not, the
last value read by any of the readers is 8:
$ ./6.out
generated: 0
generated: 1
consumed: 0
generated: 2
consumed: 1
generated: 3
consumed: 2
generated: 4
consumed: 3
generated: 5
consumed: 4
generated: 6
consumed: 5
generated: 7
consumed: 6
generated: 8
consumed: 7
generated: 9
consumed: 8
<- 1
<- 1
<- 1
<- 1
<- 1
if you run the code long enough occasionally the 9 will be read, which
gives you your correct result:
$ while true; do ./6.out | egrep 'consumed: [89]'; done | egrep -n
'consumed: 9'
180:consumed: 9
356:consumed: 9
569:consumed: 9
984:consumed: 9
989:consumed: 9
2166:consumed: 9
2235:consumed: 9
2295:consumed: 9
2350:consumed: 9
2929:consumed: 9
3039:consumed: 9
issue #1183, with hopes that i'm not misinterpreting the spec.
as for your solution to the factorial problem, you're better off
splitting the generation function (and therefore the input space) into
as many multiplication routines as you've got. that way you won't have
to wait on the generator on multicore systems.
HTH
andrey
peterGo
Here's a result that's in error, which reads all the values from the
channel.
in <- 2
in <- 3
in <- 4
in <- 5
in -> 2
in -> 4
in <- 6
in <- 7
in -> 6
in <- 8
in -> 3
in -> 7
in <- 9
in -> 8
in <- 10
in -> 9
in -> 10
725760
This occured with GOMAXPROCS(4). With GOMAXPROCS(1), the result always
seemed to be right.
Peter
> < 1KViewDownload
andrey mirtchovski
prematurely before all the values from the channel are read. In my
testing I tried tagging the different multiplication goroutines and
waiting to see what happens. I didn't run it with GOMAXPROCS>1, but
now that you mention it here's what I get:
play-by-play: the first go mul() sees '2', then '3', then '7', then
goroutines 1 and 2 see '4' and '5' respectively, the channel is closed
after '8' and '9' are sent; goroutine 0 now sees the '8', which
corresponds to the 'any value read from closed channel' in the spec,
and sends everything it's seen out as 336, which is correct;
goroutines 1 and 2 send out their respectively read values (4 and 5)
and goroutine 3 returns not having read anything from the channel...
now, where's '6'???
in <- 2
0 in -> 2
in <- 3
in <- 4
in <- 5
in <- 6
in <- 7
0 in -> 3
0 in -> 7
1 in -> 4
2 in -> 5
in <- 8
in <- 9
in <- 10
closing
0 in -> 8
0 out <- 336
1 out <- 4
2 out <- 5
main sees: 336
main sees: 4
main sees: 5
3 out <- 1
main sees: 1
6720
Anthony Martin
> in <- 2
> in <- 3
> in <- 4
> in <- 5
> in -> 2
> in -> 4
> in <- 6
> in <- 7
> in -> 6
> in <- 8
> in -> 3
> in -> 7
> in <- 9
> in -> 8
> in <- 10
> in -> 9
> in -> 10
> 725760
The value 5 is never received here.
andrey mirtchovski
this issue has been dealt with before (see this thread:
http://groups.google.com/group/golang-nuts/browse_thread/thread/a87b2c54c8448538/2f783ad5725c0d7a)
the problem is that the range loop is equivalent to this:
for {
x := <-c
if closed(c) {
break
}
body of loop
}
closed() returns true when one value has been read from the channel
after close() has been called. when there are several readers,
this means that the following sequence can happen:
reader1: read value from c
writer: close(c)
reader2: read final value from c
reader1: closed(c) -> true
thus causing reader1 to discard a legitimately sent value.
for now, a quick workaround is to avoid using range
loops when using multiple readers, and instead use the
zero value to signify eof.
a proper solution would involve a way to both read
a value from the channel and find out whether it has
been closed simultaneously (for instance by changing
the semantics of the multiple-result receive operator,
as discussed in that mailing list thread)
dylan m
As suggested, removing the use of the range clause fixed the problem.
I know to be more careful with multiple readers now.
On Oct 9, 8:44 am, andrey mirtchovski <mirtchov...@gmail.com> wrote:
> explanation from the issue tracker by Roger Peppe:
>