Merge sort with goroutines vs normal Mergesort

I am wrote two versions of mergesort in Go. One with goroutines and the other one without. I am comparing the performance of each and I keep seeing

https://github.com/denniss/goplayground/blob/master/src/example/sort.go#L69

That's the one using goroutines. And this is the one without

https://github.com/denniss/goplayground/blob/master/src/example/sort.go#L8

I have been trying to figure out why the goroutine implementation performs much worse than the one without. This is the number that I see locally

 go run src/main.go
[5 4 3 2 1]
Normal Mergesort
[1 2 3 4 5]
Time:  724
Mergesort with Goroutines
[1 2 3 4 5]
Time:  26690

Yet I still have not been able to figure out why. Wondering if you guys can give me suggestions or ideas on what to do/look at. It seems to me that the implementation with goroutines should perform at least somewhat better. I say so mainly, because of the following lines

go MergeSortAsync(numbers[0:m], lchan)
go MergeSortAsync(numbers[m:l], rchan)

Using concurrency does not necessarily make an algorithm run faster. In fact, unless the algorithm is inherently parallel, it can slow down the execution.

A processor (CPU) can only do one thing at a time even if, to us, it seems to be doing two things at once. The instructions of two goroutines may be interleaved, but that does not make them run any faster than a single goroutine. A single instruction from only one of the goroutines is ever being executed at any given moment (there are some very low-level exceptions to this, depending on hardware features) -- unless your program is running on more than one core.

As far as I know, the standard merge sort algorithm isn't inherently parallel; some modifications need to be made to optimize it for parallel execution on multiple processors. Even if you're using multiple processors, the algorithm needs to be optimized for it.

These optimizations usually relate to the use of channels. I wouldn't agree that "writing to channels has a big overhead" of itself (Go makes it very performant), however, it does introduce the likely possibility that a goroutine will block. It's not the actual writing to a channel that slows down the program significantly, it's scheduling/synchronizing: the waiting and waking of either goroutine to write or read from the channel is probably the bottleneck.

To complement Not_a_Golfer's answer, I will agree that goroutines definitely shine when executing I/O operations--even on a single core--since these occur far away from the CPU. While one goroutine is waiting on I/O, the scheduler can dispatch another CPU-bound goroutine to run in the meantime. However, goroutines also shine for CPU-intensive operations when deployed across multiple processors/cores.

As others have explained, there is a cost of parallelism. You need to see enough benefit to compensate for that cost. This only happens when the unit of work is larger than the cost of making channels and goroutines receiving the results.

You can experiment to determine what the unit of work should be. Suppose the unit of work is sorting 1000 elements. In that case, you can change your code very easily like so:

func MergeSortAsync(numbers [] int, resultChan chan []int)  {
    l := len(numbers)
    if l <= 1000 {
            resultChan <- Mergesort(numbers)
            return
    }

In other words, once the unit of work is too small to justify using goroutines and channels, use your simple Mergesort without those costs.

There are two main reasons:

1. Writing to channels has a big overhead. Just as a reference - I tried using channels and goroutines as iterators. They were ~100 times slower than calling methods repeatedly. Of course if the operation that is being piped via the channel takes a long time to perform (say crawling a web page), that difference is negligible.

2. Goroutines really shine for IO based concurrency, and less so for CPU parallelism.

Considering these 2 issues, you'll need a lot of CPUs or longer, less blocking operations per goroutine, to make this faster.