在并行快速排序实现中使用 go routines 时性能更差

Question

注意："Go-lang parallel segment runs slower than series segment" 问题处理竞争条件，这个问题有另一个问题，所以恕我直言，它不是重复的。

我正在尝试为以下情况寻找解释：运行使用 go 例程完成时，并行快速排序会显着延长运行时间。

基准在代码之后：

package c9sort

import (
    "time"
)

var runInParllel bool

func Quicksort(nums []int, parallel bool) ([]int, int) {
    started := time.Now()
    ch := make(chan int)
    runInParllel = parallel

    go quicksort(nums, ch)

    sorted := make([]int, len(nums))
    i := 0
    for next := range ch {
        sorted[i] = next
        i++
    }
    return sorted, int(time.Since(started).Nanoseconds() / 1000000)
}

func quicksort(nums []int, ch chan int) {

    // Choose first number as pivot
    pivot := nums[0]

    // Prepare secondary slices
    smallerThanPivot := make([]int, 0)
    largerThanPivot := make([]int, 0)

    // Slice except pivot
    nums = nums[1:]

    // Go over slice and sort
    for _, i := range nums {
        switch {
        case i <= pivot:
            smallerThanPivot = append(smallerThanPivot, i)
        case i > pivot:
            largerThanPivot = append(largerThanPivot, i)
        }
    }

    var ch1 chan int
    var ch2 chan int

    // Now do the same for the two slices
    if len(smallerThanPivot) > 1 {
        ch1 = make(chan int, len(smallerThanPivot))
        if runInParllel {
            go quicksort(smallerThanPivot, ch1)
        } else {
            quicksort(smallerThanPivot, ch1)
        }
    }
    if len(largerThanPivot) > 1 {
        ch2 = make(chan int, len(largerThanPivot))
        if runInParllel {
            go quicksort(largerThanPivot, ch2)
        } else {
            quicksort(largerThanPivot, ch2)
        }
    }

    // Wait until the sorting finishes for the smaller slice
    if len(smallerThanPivot) > 1 {
        for i := range ch1 {
            ch <- i
        }
    } else if len(smallerThanPivot) == 1 {
        ch <- smallerThanPivot[0]
    }
    ch <- pivot

    if len(largerThanPivot) > 1 {
        for i := range ch2 {
            ch <- i
        }
    } else if len(largerThanPivot) == 1 {
        ch <- largerThanPivot[0]
    }

    close(ch)
}

500000 个整数随机烫发的基准：

运行100次

非并行平均 - 1866 毫秒

并行平均 - 2437 毫秒

如有任何解释，我们将不胜感激。我知道 goroutines 可能不是这种并行性的最佳选择，但我正在尝试理解原因。

提前致谢。

Answer 1

一般的答案是线程间协调是有成本的，所以只有当任务至少达到一定规模时，将任务发送到另一个 goroutine 才能加快速度。所以不要发单品。

对于像快速排序这样的分而治之的算法，并行化的方式可能很有趣。通常：当你递归时，如果它足够大，你可以在 goroutine 中启动 "sort one half of the array" 任务。 "if it's large enough" 部分是如何减少协调开销。

更详细地说，它看起来像：

写一个非平行qsort(data []int)
更改 qsort 以选择性地使用 *sync.WaitGroup 我们将调用 wg 来表示它已完成。在每个 return 之前添加 if wg != nil { wg.Done() }。
其中 qsort 递归，让它检查它要排序的数据的一半是否很大（比如，超过 500 项？），并且
- 如果它很大，开始另一个任务：wg.Add(1); go qsort(half, wg)
- 如果不是，请立即排序：qsort(half, nil)
包裹qsort以对用户隐藏并行机器：比如，让quicksort(data)做wg := new(sync.WaitGroup)，做一个初始的wg.Add(1)，调用 qsort(data, wg)，然后执行 wg.Wait() 以等待所有后台排序完成。

这不是一个最佳策略，因为即使有足够多的任务让您的核心保持忙碌，它也会继续分叉新的 goroutines。并且可以围绕如何将一些任务移交给后台进行大量调整。但重要的是，使用另一个线程 仅用于大型子任务 是一种并行化快速排序的方法，而不会被协调开销破坏。

这是一个demo with an embarrassingly slapdash quicksort（你在本地有运行它来获取时间）——错误的可能性很大，绝对是已经排序的数据的二次方；重点是了解并行分而治之的想法。

还有一种自下而上的策略——对片段进行排序然后合并——例如在 this parallel sort package 中使用。不过，包使用的就地合并代码很棘手。

（如果您还没有设置 GOMAXPROCS，请在 main 中设置类似 runtime.GOMAXPROCS(runtime.NumCPU()) 的内容。）

最后，look at Go's sort package。代码很多，但很清楚，一旦你得到它，你就可以用 "real" 充实的排序实现来做你的实验。

Answer 2

原来很简单。因为我在一台新机器上，所以没有设置 GOMAXPROCS 变量。

正如预测的那样，新基准支持并行实现：设置成双核数：

Using 16 goroutines
Ran 100 times

Non parallel average - 1980
Parallel average - 1133

设置为核心数：

Using 8 goroutines
Ran 100 times

Non parallel average - 2004
Parallel average - 1197

顺便说一句，这是相当一致的。双核数量的平均值总是好一点。

更大集合 (1000000) 的基准：

Using 8 goroutines
Ran 100 times

Non parallel average - 3748
Parallel average - 2265

加倍：

Using 16 goroutines
Ran 100 times

Non parallel average - 3817
Parallel average - 2012

在并行快速排序实现中使用 go routines 时性能更差

Worse performance when using go routines in parallel quicksort implementation

concurrency

go

parallel-processing

quicksort

goroutine