Thanks Andrey. I did realize the overhead of goroutines, but I didn't realize it was this large.
Your version is better, but it can't output results sequentially, sorting it before output is easy anyway. One new thing I learned from your code is that channels can be reused. I thought every goroutine needs a new channel as you can see in my original code. On Tuesday, 17 April 2018 00:47:18 UTC+8, andrey mirtchovski wrote: > > In short, your concurrency is too fine-grained. Adding concurrency > primitives requires locking which is expensive, and creating a lot of > goroutines does consume resources, even if we consider it relatively > cheap. > > If you slice the problem slightly differently it can be made faster: > one goroutine per number, but each goroutine calculates its number the > "normal" way, without using concurrency: > > https://play.golang.org/p/lKYSbuK79sB > > $ time ./tt 20 > /dev/null # new code > > real 0m3.374s > user 0m5.129s > sys 0m0.016s > > $ time ./t 20 > /dev/null # your original non-concurrent program > > real 0m4.593s > user 0m4.538s > sys 0m0.019s > > > > On Mon, Apr 16, 2018 at 9:09 AM, Tashi Lu <dotsl...@gmail.com > <javascript:>> wrote: > > Hi all, > > > > As a newbie I tried to implement a simple program calculating the > Catalan > > numbers, which are the numbers satisfying the recursion equation c(1) = > 1; > > c(n) = c(n - 1) * c(1) + c(n - 2) * c(2) + ... c(1) * c(n). > > > > At first, I implemented it without channels: > > package main > > > > import ( > > "fmt" > > "os" > > "strconv" > > ) > > > > func catalan(n int) int { > > if n == 1 { > > return 1 > > } > > res := 0 > > for i := 1; i < n; i++ { > > res += catalan(n - i) * catalan(i) > > } > > return res > > } > > > > func main() { > > n, _ := strconv.Atoi(os.Args[1]) > > for i := 1; i <= n; i++ { > > fmt.Println(catalan(i)) > > } > > } > > > > > > Then I thought the calculation can be easily made concurrent, so I wrote > the > > version below: > > package main > > > > import ( > > "fmt" > > "os" > > "strconv" > > ) > > > > func catalan(n int, ch chan int) { > > if n == 1 { > > ch <- 1 > > return > > } > > res := 0 > > for i := 1; i < n; i++ { > > ch1 := make(chan int) > > ch2 := make(chan int) > > go catalan(n - i, ch1) > > go catalan(i, ch2) > > res += <-ch1 * <-ch2 > > close(ch1) > > close(ch2) > > } > > ch <- res > > } > > > > func main() { > > n, _ := strconv.Atoi(os.Args[1]) > > for i := 1; i <= n; i++ { > > q := make(chan int) > > go catalan(i, q) > > fmt.Println(<-q) > > close(q) > > } > > } > > > > > > But I found the second version was unexpectly slower than the first: > > go run catalan.go 15 0.07s user 0.66s system 257% cpu 0.281 total > > vs > > go run catalan-parallel.go 15 3.80s user 0.97s system 130% cpu 3.662 > total > > > > What's the reason behind this? How can I improve this concurrent version > to > > make it faster? > > > > -- > > 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 <javascript:>. > > 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.
