Re: [go-nuts] Performance of quick sort written with go-routines

[andrey mirtchovski]

start here: http://golang.org/doc/faq#Why_GOMAXPROCS

On Thu, Jan 24, 2013 at 5:39 AM, Felix Löft
<thechos...@googlemail.com> wrote:
> Hello everybody,
>
> I'm new to Google Go and I hope, my question is not too stupid. For personal
> interest I want to compare the performance of several implementations of
> quick sort in different languages (e.g. C, Java, Go). For this I have
> written the following code: http://play.golang.org/p/hqd1i-KprX
>
> In comparison to my code, that doesn't use go-routines, this one is very
> much slower. I wonder, how this could be (maybe I have misunderstood
> something). I would be very thankful, if anybody would help me. And sorry
> for my poor English :P
>
> Best regards
> Felix
>
> --
>
>

[David DENG]

The overhead if too large. Some suggestions:

1) Only set the runtime.GOMAXPROCS to the number cores, no more

2) Try concurrent on large gradularity only. e.g. 

if index < 10000 {

    quickSort(data[:index-1], ...)

} else {

    go quickSort(data[:index-1], ...)

} // else

David

[Donovan Hide]

In comparison to my code, that doesn't use go-routines, this one is very much slower. I wonder, how this could be (maybe I have misunderstood something). I would be very thankful, if anybody would help me. And sorry for my poor English :P

Are you running your benchmarks on a multi-CPU machine or just the playground? The playground only has access to one CPU, as far as I can tell, due to running on Appengine, so you'll get much better results for >1 MAXPROCS on a local machine. Also try this as well:

runtime.GOMAXPROCS(runtime.NumCPU())

Also consider how much work you are doing in each goroutine. You are recursing all the way down to an array of length 1. This is far from optimal, due to creating many goroutines which only indicate that they are done. Try counting the number of entries into quicksort your code achieves and then read the standard library sort to see how this problem is reduced by using insertion sort:

http://golang.org/src/pkg/sort/sort.go

You only really want to create a goroutine to do some work that takes significantly longer than the time to create a goroutine :-)

Hope that helps,

Donovan.

 

 

[bryanturley]

On Thursday, January 24, 2013 10:28:16 AM UTC-6, Donovan wrote:

In comparison to my code, that doesn't use go-routines, this one is very much slower. I wonder, how this could be (maybe I have misunderstood something). I would be very thankful, if anybody would help me. And sorry for my poor English :P

Are you running your benchmarks on a multi-CPU machine or just the playground? The playground only has access to one CPU, as far as I can tell, due to running on Appengine, so you'll get much better results for >1 MAXPROCS on a local machine. Also try this as well:

 

Additionally it is shared with others and shouldn't be used for benchmarking (speed wise at least)


goroutines work better if you can do work that is unrelated or work that can be broken into sequential steps, each step being it's own goroutine.
Heavy I/O workloads work especially well with goroutines.

[Felix Löft]

Thanks so far for your answers. First of all, of course I was running that benchmarks on my local machine. The playground was just for you, so you can see my code.  As you said, the creation of so many go-routines was anything bit optimal. Now, I look every time which recursion depth I am in. Beyond a threshold I stop creating more go-routines. Together with using runtime.GOMAXPROCS(runtime.NumCPU())this lead to a significant increase of performance.

Again, thanks for your help and best regards

Felix

[Tong Sun]

On Thursday, January 24, 2013 3:18:12 PM UTC-5, Felix Löft wrote:

. . . As you said, the creation of so many go-routines was anything bit optimal. Now, I look every time which recursion depth I am in. Beyond a threshold I stop creating more go-routines. Together with using runtime.GOMAXPROCS(runtime.NumCPU())this lead to a significant increase of performance.

 

How much increase of performance was it? 

Further, could you post your finished code please? I'd like to test out myself as well. 

Thanks