Go : channel is necessary in this case?

Question

http://play.golang.org/p/Xn3Qw7xAi3

It is hard to make sense of channel.

Here I have

func main() {
  in := make(chan int)
  out := make(chan int)
  go QuickSort(in, out)

  for i := 0; i < 100; i++ {
    in <- rand.Intn(1000)
  }
  close(in)

  for i := range out {
    fmt.Println(i)
  }
}

This makes two channels named in, out and goroutine the function Quicksort.

1. How QuickSort take in and out as arguments? Does it receive from the line below?

  in <- rand.Intn(1000)

2. Is this case optimal using channel? It looks pretty neat receiving values dynamically... What would be different just sorting without channel? This case is faster?

Answer 1

I wrote the original version of that!

My original write-up answers your second question I think...

Just for fun - a channel based quicksort.

Interesting that you can make a quicksort without being able to index your input. It may be O(n log n) for comparisons but it is O(n) for channels and go routines so perhaps not the most efficient quicksort ever ;-)

It also has the worst case complexity O(n²) if you feed it sorted input, so don't do that!

It is a bit of fun really - but it uses an awful lot of channels and goroutines which will make it slower and use more memory than a traditional quicksort.

Answer 2

1. How QuickSort take in and out as arguments? Does it receive from the line below?

This code pushes 100 random into into the channel called "in". You previously passed a reference to this channel to the quicksort function. This is the same idea as if I pass a function a thread-safe stack, and then from the callers context push a new element onto that stack.

  for i := 0; i < 100; i++ {
    in <- rand.Intn(1000)
  }
  close(in)

2. Is this case optimal using channel? It looks pretty neat receiving values dynamically... What would be different just sorting without channel? This case is faster?

I would consider this a cool toy example of how flexibly channels can be used (and a streaming sort). In most common cases, it is usually going to be much faster/easier to take a slice and call sort.Sort on it. Its also worth noting in most real world cases you will get better throughput by creating a channel with a buffer, as this will reduce the scheduler switching between goroutines. Channels are very fast, but they still have overhead and if you are not actually processing in parallel that overhead isn't buying you anything.

If you want to be processing in parallel don't forgot to set GOMAXPROCS > 1 and use buffered channels.

Answer 3

The answer to question 1 is yes. The QuickSort in the example expects two channels as arguements, one to read ints from and one to write ints to after they are sorted. It's very similar to using sort on the unix command line with stdin and stdout.

As to the answer to question 2, this is just an example of using Go Channels and go routines to solve a standard problem. It would only be faster if you had some other work to do while waiting for the sort to return.

The real speed up possible in this code is the use of channels and goroutines inside the QuickSort function. If your underlying hardware has sufficient cores to allow you to multi-thread the program this could be significantly faster than a single threaded version.

The point of go channels and threads is to allow you to easily take advantage of the underlying hardware w/o the difficulties of writing threaded code. For comparision look at this version of a pthread based quicksort and compare it to the go code.

http://sc12.supercomputing.org/hpceducator/PythonForParallelism/codes/parallelQuicksort.c