So I do have a concurrent quicksort implementation written by me. It looks like this:
func Partition(A []int, p int, r int) int {
index := MedianOf3(A, p, r)
swapArray(A, index, r)
x := A[r]
j := p - 1
i := p
for i < r {
if A[i] <= x {
j++
tmp := A[j]
A[j] = A[i]
A[i] = tmp
}
i++
}
swapArray(A, j+1, r)
return j + 1
}
func ConcurrentQuicksort(A []int, p int, r int) {
wg := sync.WaitGroup{}
if p < r {
q := Partition(A, p, r)
select {
case sem <- true:
wg.Add(1)
go func() {
ConcurrentQuicksort(A, p, q-1)
<-sem
wg.Done()
}()
default:
Quicksort(A, p, q-1)
}
select {
case sem <- true:
wg.Add(1)
go func() {
ConcurrentQuicksort(A, q+1, r)
<-sem
wg.Done()
}()
default:
Quicksort(A, q+1, r)
}
}
wg.Wait()
}
func Quicksort(A []int, p int, r int) {
if p < r {
q := Partition(A, p, r)
Quicksort(A, p, q-1)
Quicksort(A, q+1, r)
}
}
I have a sem
buffered channel, which I use to limit the number of goroutines running (if its reaches that number, I dont set up another goroutine, I just do the normal quicksort on the subarray). First I started with 100, then I've changed to 50, 20. The benchmarks would get slightly better. But after switching to 10, it started to go back, times started to get bigger. So there is some arbitrary number, at least for my hardware, that makes the algorithm run most efficient.
When I was implementing this, I actually saw some SO question about the number of goroutines that would be the best and now I cannot find it (stupid Chrome history actually saves not all visited sites). Do you know how to calculate such a things? And it would be the best if I didn't have to hardcode it, just let the program do it itself.
P.S I have nonconcurrent Quicksort, which runs about 1.7x slower than this. As you can see in my code, I do Quicksort
, when the number of running goroutines exceeds the number I've set up earlier. I thought what about using a ConcurrentQuicksort
, but not calling it with go
keyword, just simply calling it, and maybe if other goroutines finish their job, the ConcurrentQuicksort
which I called would start to launch up goroutines, speeding up the process (cuz as you can see Quicksort
would only launch recursive quicksorts, without goroutines). I did that, and actually the time was like 10% slower than the regular Quicksort. Do you know why would that happen?