本机上最有效的goroutine数

Question

所以我确实有一个并发的quicksort实现。看起来像这样：

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)
    }
}

我有一个sem缓冲通道，用于限制正在运行的goroutine的数量（如果达到该数量，则不设置另一个goroutine，我只对子数组执行常规的quicksort）。首先，我从100开始，然后又变为50、20。基准会稍微好一些。但是切换到10后，它开始倒退，时间开始变大。因此，至少对于我的硬件而言，有一些任意数字可使算法运行效率最高。

在实施此功能时，实际上我看到了一些关于最佳goroutine数量的问题，但现在找不到了（愚蠢的Chrome历史记录实际上并未保存所有访问过的网站）。你知道如何计算这样的事情吗？如果我不必对其进行硬编码，那将是最好的，只需让程序自己执行即可。

PS我有非并行Quicksort，它的运行速度比此慢1.7倍。如您在我的代码中看到的Quicksort，当正在运行的goroutine的数量超过我之前设置的数量时，我会这样做。我想过要使用a ConcurrentQuicksort，但不使用go关键字来调用它，而只是简单地调用它，也许其他的goroutine完成他们的工作，ConcurrentQuicksort我调用的它将开始启动goroutine，从而加快了处理速度（如您所见Quicksort，仅启动递归快速排序，而无需goroutines）。我这样做了，实际上时间比常规的Quicksort慢了10％。你知道为什么会这样吗？

Answer 1

您必须对这些东西进行一些试验，但是我认为主要关注点不是goroutines立即运行。正如@reticentroot链接的答案所言，同时运行许多goroutine不一定是问题。

我认为您主要关心的是goroutine发射的总数。从理论上讲，当前的实现可以启动一个goroutine来仅排序一些项目，并且该goroutine在启动/协调上花费的时间比实际排序要多得多。

理想的情况是，您只需要启动所需的所有goroutine，以充分利用所有CPU。如果您的工作项目大小相等，而您的核心也同样繁忙，那么每个核心启动一个任务就很完美。

在这里，任务不是大小均匀，所以你可能排序分成几分比你有更多的CPU任务和分发。（在生产中，您通常会使用工作池来分配工作，而不必为每个任务启动新的goroutine，但是我认为我们可以跳过这里。）

要获得可行的任务数量-足以使所有内核保持忙碌，但又不至于造成太多内核开销，则可以设置最小大小（初始数组大小为100或其他任何值），并且只能将大于此的数组。

稍微详细一点，每次将任务发送到后台时都会花费一些成本。对于初学者：

• 每次goroutine 启动都会花费一些时间来设置堆栈并进行调度程序簿记
• 每个任务切换都会在调度程序中花费一些时间，并且当两个goroutine正在查看不同的代码或数据时可能会导致高速缓存未命中
• 您自己的协调代码（频道发送和sync操作）需要时间

其他事情可能会阻止理想的加速发生：您可能会在系统范围内达到极限，例如Volker指出的内存带宽；随着添加内核的增加，某些同步成本可能会增加；有时还会遇到各种棘手的问题。但是设置，交换和协调成本是一个不错的起点。

当然，可以抵消协调成本的好处是，其他CPU在闲置时可以完成工作。

我认为但尚未经过测试，您使用50个goroutine时遇到的问题是：1）您很早就已经达到了几乎完全的利用率，因此添加更多任务会增加更多的协调工作，而又不会使事情进展得更快； 2）您正在创建goroutine。对于微小的排序，可能比他们实际进行的排序花费更多的时间进行设置和协调。在使用10个goroutine时，您的问题可能是您不再获得完全的CPU利用率。

如果需要，您可以通过计算各种goroutine限制（在atomic全局计数器中）发出的 goroutine启动总数，以及测量各种限制（例如通过在Linux / UNIX time实用程序下运行程序）来测量CPU利用率，来测试这些理论。

我建议的解决此类问题的方法只是为足够大的子问题（对于quicksort，这意味着足够大的子数组）派出了goroutine。您可以尝试不同的限制：也许您只为大于原始数组的1/64的片段或高于某个静态阈值（例如1000项）的片段启动goroutine。

我怀疑您的意思是将这种排序例程作为一种练习，但是您可以采取多种措施来使您的排序针对怪异的输入更快或更稳定。标准的库排序可以归结为小型子数组的插入排序，而将堆排序用于引起快速排序问题的异常数据模式。

您还可以查看其他算法，例如对所有或部分排序进行基数排序的算法，我都曾使用过。该排序库也是并行的。在将子数组交给其他goroutine进行排序之前，我使用了至少127个项目的截止值，并且我使用了带有固定goroutine库和缓冲chan的安排，以在它们之间传递任务。尽管当时这可能不是最好的方法，但在当时确实产生了不错的实际提速，而且我几乎可以肯定，今天的Go调度程序中没有这种方法。实验很有趣！