Re: [go-nuts] Why does the parallel version of a program runs slower?

[Tashi Lu]

Hi Lee,

Thanks for pointing out my misuse of words. 
I've actually borne in mind that parallelism and concurrency are different 
things, but I made a slip. 
I'll try to be more careful next time.

On Tuesday, 17 April 2018 04:09:06 UTC+8, Lee Painton wrote:
>
> Also, as Rob Pike has stressed in the past, concurrency is not 
> parallelism.  Concurrency is a design principle that enables parallelism, 
> but goroutines are concurrency constructs and do not automatically run in 
> parallel.
>
> On Monday, April 16, 2018 at 12:47:18 PM UTC-4, 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  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. 
>> > 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.

Re: [go-nuts] Why does the parallel version of a program runs slower?

[Tashi Lu]

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  > 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 . 
> > 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.

Re: [go-nuts] Why does the parallel version of a program runs slower?

[Lee Painton]

Also, as Rob Pike has stressed in the past, concurrency is not 
parallelism.  Concurrency is a design principle that enables parallelism, 
but goroutines are concurrency constructs and do not automatically run in 
parallel.

On Monday, April 16, 2018 at 12:47:18 PM UTC-4, 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  > 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 . 
> > 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.

Re: [go-nuts] Why does the parallel version of a program runs slower?

[andrey mirtchovski]

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  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+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.

[go-nuts] Why does the parallel version of a program runs slower?

[Tashi Lu]

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+unsubscr...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.