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

Question

注意:"Go-lang parallel 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次

非平行平均值 - 1866ms

平行平均值 - 2437ms

任何解释将不胜感激.我知道goroutines可能不是最好的这种并行性,但我试图理解其中的原因.

先感谢您.

Answer 1

一般的答案是线程间协调具有成本,因此如果任务至少具有一定的大小,则将任务发送到另一个goroutine只能加快速度.所以不要发送单品.

对于像quicksort这样的分而治之算法,并行化的方法可能很有趣.通常:当你递归时,如果它足够大,你可以在goroutine中开始"对阵列的一半"任务."如果它足够大"部分是你如何减少协调开销.

更详细地说,看起来像:

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

2. 更改qsort为可选地接受*sync.WaitGroup我们将要求wg发出信号的信号.if wg != nil { wg.Done() }在每个returns 之前添加.

3. 在qsortrecurses中,让它检查它要分类的数据的一半是否是大的(比如,超过500个项目？),以及

   • 如果它很大,则启动另一项任务: wg.Add(1); go qsort(half, wg)
   • 如果不是,请在此处排序: qsort(half, nil)

4. 包裹qsort在隐藏来自用户的并行机械:喜欢,都quicksort(data)做wg := new(sync.WaitGroup),做一个初步wg.Add(1),通话qsort(data, wg),并做wg.Wait()等待所有的背景各种各样的完成.

这不是一种最佳策略,因为即使在有足够的任务来保持核心忙碌之后,它也会继续分离新的goroutine.关于如何将某些任务交给后台,可以做很多调整.但重要的是,使用另一个线程仅用于大型子任务是一种并行化快速排序的方法,而不会受到协调开销的影响.

这是一个带有令人尴尬的slapdash快速排序的演示(你已经在本地运行以获得时间) - 很有可能出现错误,绝对是已排序数据的二次方; 关键是要实现并行分治的想法.

还有一个自下而上的策略 - 排序然后合并 - 例如,用于此并行排序包.但是,包使用的就地合并代码很棘手.

(如果你还没有设置GOMAXPROCS,请设置类似runtime.GOMAXPROCS(runtime.NumCPU())的内容main.)

最后,看看Go的排序包.有很多代码,但它很清楚,一旦你得到它,你可以用"真正的",充实的排序实现做你的实验.