title: Golang: why using goroutines to parallelize calls ends up being slower?
body: <p>I have two versions of merge sort implementation. The first is a "normal" version and the second uses <code>goroutines</code> that parallelize the work being done on each subset of the slice in each step of the recursion. </p>
  
  <p>One would assume that being able to parallelize this work would make the concurrent implementation faster: if I need to work on slice A and slice B, then working on them concurrently should be faster than doing so synchronously. </p>
  
  <p>Now I'm assuming something is wrong with either my implementation of my understanding, because my concurrent version ends up being 13-14x slower than the sync version. </p>
  
  <p>Can anyone point me in the right direction as to what I'm missing? </p>
  
  <p>"Normal" (synchronous implementation): </p>
  
  <pre><code>// MergeSort sorts the slice s using Merge Sort Algorithm
  func MergeSort(s []int) []int {
      if len(s) &lt;= 1 {
          return s
      }
  
      n := len(s) / 2
  
      var l []int
      var r []int
  
      l = MergeSort(s[:n])
      r = MergeSort(s[n:])
  
      return merge(l, r)
  }
  </code></pre>
  
  <p>"Concurrent" version:</p>
  
  <pre><code>// MergeSortMulti sorts the slice s using Merge Sort Algorithm
  func MergeSortMulti(s []int) []int {
      if len(s) &lt;= 1 {
          return s
      }
  
      n := len(s) / 2
  
      wg := sync.WaitGroup{}
      wg.Add(2)
  
      var l []int
      var r []int
  
      go func() {
          l = MergeSortMulti(s[:n])
          wg.Done()
      }()
  
      go func() {
          r = MergeSortMulti(s[n:])
          wg.Done()
      }()
  
      wg.Wait()
      return merge(l, r)
  }
  </code></pre>
  
  <p>Both use the same <code>merge</code> function:</p>
  
  <pre><code>func merge(l, r []int) []int {
      ret := make([]int, 0, len(l)+len(r))
      for len(l) &gt; 0 || len(r) &gt; 0 {
          if len(l) == 0 {
              return append(ret, r...)
          }
          if len(r) == 0 {
              return append(ret, l...)
          }
          if l[0] &lt;= r[0] {
              ret = append(ret, l[0])
              l = l[1:]
          } else {
              ret = append(ret, r[0])
              r = r[1:]
          }
      }
      return ret
  }
  </code></pre>
  
  <p>This is my benchmarking code:</p>
  
  <pre><code>package msort
  
  import "testing"
  
  var a []int
  
  func init() {
      for i := 0; i &lt; 1000000; i++ {
          a = append(a, i)
      }
  }
  func BenchmarkMergeSortMulti(b *testing.B) {
      for n := 0; n &lt; b.N; n++ {
          MergeSortMulti(a)
      }
  }
  
  func BenchmarkMergeSort(b *testing.B) {
      for n := 0; n &lt; b.N; n++ {
          MergeSort(a)
      }
  }
  </code></pre>
  
  <p>It reveals that the concurrent version is a lot slower than the normal synchronous version:</p>
  
  <pre><code>BenchmarkMergeSortMulti-8              1    1711428093 ns/op
  BenchmarkMergeSort-8                  10     131232885 ns/op
  </code></pre>