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

Question

注意：“Go-lang 并行段运行速度比串行段慢”问题涉及竞争条件，这个问题还有另一个问题，所以恕我直言，它不是重复的。我试图找到对以下情况的解释：使用 go 例程完成后，运行并行快速排序会导致运行时间显着延长。基准在代码之后：package c9sortimport (    "time")var runInParllel boolfunc 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        }    } 500000 个整数随机烫发的基准：跑了100次非并行平均 - 1866ms并行平均 - 2437ms任何解释将不胜感激。我知道 goroutines 可能不适合这种并行性，但我试图理解原因。

Answer 1

一般的答案是线程间协调是有成本的，因此将任务发送到另一个 goroutine 只能在任务至少达到特定大小时加快速度。所以不要寄单件。

对于像快速排序这样的分而治之的算法，并行化的方法可能很有趣。通常：当您递归时，如果它足够大，您可以在 goroutine 中启动“对数组的一半进行排序”任务。“如果它足够大”部分是如何减少协调开销。

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

1. 写一个非平行 qsort(data []int)

2. 更改qsort为可选地采用*sync.WaitGroup我们将调用wg的信号，表明它已完成。if wg != nil { wg.Done() }在它return的每个s之前添加。

3. 哪里qsort递归，让它检查它要排序的数据的一半是否很大（比如，超过 500 个项目？），和

• 如果它很大，请开始另一个任务： wg.Add(1); go qsort(half, wg)

• 如果不是，请在这里和现在排序： qsort(half, nil)

4. 换行qsort以对用户隐藏并行机制：like、have quicksort(data)do wg := new(sync.WaitGroup)、do an initial wg.Add(1)、callqsort(data, wg)和 dowg.Wait()以等待所有后台排序完成。

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

这是一个带有令人尴尬的草率快速排序的演示（您已在本地运行它以获取时间）-错误的可能性很大，绝对是已排序数据的二次方；关键是要理解并行分而治之的想法。

还有一种自下而上的策略——先对片段进行排序，然后再合并——例如，在这个并行排序包中使用。但是，包使用的就地合并代码很棘手。

（如果您还没有设置 GOMAXPROCS，请使用类似runtime.GOMAXPROCS(runtime.NumCPU())in 的内容进行设置main。）

最后看一下 Go 的 sort 包。有很多代码，但很清楚，一旦你得到它，你就可以用一个“真实的”、充实的排序实现来做你的实验。

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