Parallel Merge Sort in Go

  • A thread pool to limit the number of threads
  • A work-stealing strategy in order to optimize the distribution of the workload

Sequential Implementation

benchSequential              avgt    129.8    ms/op

Parallel Implementation

Pseudocode

mergesort(s []int) {
if len(s) > 1 {
middle := len(s) / 2
// Create two sub-tasks
createTask -> mergesort(s[:middle])
createTask -> mergesort(s[middle:])
merge(s, middle)
}
}

Concurrency/Parallelism in Go

  • Cooperative system: a goroutine is context-switched off an OS thread purposely
  • The Go runtime is based on a work-stealing strategy to optimize the distribution of the goroutines

First version

benchSequential              avgt    129.8    ms/op
benchParallelv1 avgt 438.8 ms/op
go trace on a one millisecond time range (v1)
  • Scheduler wait time: the time awaited by a goroutine to be scheduled
  • GC pause time: the time spent in performing GC operations
Goroutines analysis
Scheduler wait time (func1 and func2): avg 156.7 ms
GC pause time: avg 792.3 ms

Second version

benchSequential              avgt    129.8    ms/op
benchParallelv1 avgt 438.8 ms/op
benchParallelv2 avgt 47.3 ms/op
go trace on a one millisecond time range (v2)
  • The first line showing the goroutines execution
  • The second line showing the GC operations (the purple rectangles)
// v1
Scheduler wait time (func1 and func2): avg 156.7 ms
GC pause time: avg 792.3 ms
// v2
Scheduler wait time (func1): avg 4 ms
Scheduler wait time (func2): avg 1.3 ms
GC pause time: avg 30.9 ms
  • The average scheduler wait time is drastically smaller meaning that the goroutines are spending way less time in waiting for being scheduled
  • Scheduling the second call (func2) is 3 times faster than the first call
  • The GC pause time is also drastically smaller which is the direct consequence of creating way fewer goroutines

Third version

benchSequential              avgt    129.8    ms/op
benchParallelv1 avgt 438.8 ms/op
benchParallelv2 avgt 47.3 ms/op
benchParallelv3 avgt 45.7 ms/op
go trace on a one millisecond time range (v3)
// v1
Scheduler wait time (func1 and func2): avg 156.7 ms
GC pause time: avg 792.3 ms
// v2
Scheduler wait time (func1): avg 4 ms
Scheduler wait time (func2): avg 1.3 ms
GC pause time: avg 30.9 ms
// v3
Scheduler wait time (func1 only): avg 4 ms
GC pause time: avg 19.9 ms

Conclusion

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Teiva Harsanyi

Teiva Harsanyi

3.5K Followers

Software Engineer @Docker 🐳 | 📖 100 Go Mistakes author | 改善