Go中并行Quicksort的死锁

Question

As an exercise I'm trying to implement a parallel version of quicksort in Go. This is what I have so far:

func quicksort(nums []int, ch chan int, level int, threads int)  {
  level *= 2;
  if len(nums) == 1 {  ch<- nums[0]; close(ch); return }

  less := make([]int, 0)
  greater := make([]int,0)
  pivot := nums[0]
  nums = nums[1:]

  for _,i := range nums{
    switch{
    case i <= pivot:
      less = append(less,i)
    case i > pivot:
      greater = append(greater,i)
    }
  }

  ch1 := make(chan int, len(less))
  ch2 := make(chan int, len(greater))
  if(level <= threads){
    go quicksort(less, ch1, level, threads)
    go quicksort(greater,ch2, level, threads)
  }else{
    quicksort(less,ch1, level, threads)
    quicksort(greater,ch2, level, threads)
  }

  for i := range ch1{
    ch<-i;
  }
  ch<-pivot
  for i := range ch2{
    ch<-i;
  }
  close(ch)
  return
}

However, when I run it, I get an error claiming the program has deadlocked! I'm pretty stumped to what is causing this...

Thanks in advance,

Linus

Answer 1

The code has one problem, and at least one potential buggy usage case:

1. It is missing a base case. Consider what happens if quicksort is asked to sort the empty slice.
2. When calling quicksort for the first time, say in a main(), if you don't spawn the sorter in a separate goroutine, the main thread, running the toplevel sort, can block trying to write back to the channel (depending if the toplevel channel itself is buffered).

For example:

func main() {
    x := []int{3, 1, 4, 1, 5, 9, 2, 6}
    ch := make(chan int)
    quicksort(x, ch, 0, 0)    // buggy!
    for v := range(ch) {
        fmt.Println(v)
    }
}

This is buggy because this asks the main thread to do the sort, but it will inevitably block at this part of quicksort: it can't communicate with itself!

for i := range ch1{
    ch<-i;
}

and it's at the write to the toplevel channel here that the main thread will deadlock.

Contrast this with what happens if we do create a goroutine at toplevel:

func main() {
    x := []int{3, 1, 4, 1, 5, 9, 2, 6}
    ch := make(chan int)
    go quicksort(x, ch, 0, 0)
    for v := range(ch) {
        fmt.Println(v)
    }
}

and now we avoid that particular deadlock problem.