这台机器上最有效的 goroutines 数量

Question

所以我确实有一个由我编写的并发快速排序实现。它看起来像这样：

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缓冲通道，我用它来限制goroutines的数量运行ning（如果它达到那个数字，我不设置另一个goroutine，我只是做正常的子数组上的快速排序）。首先，我从 100 开始，然后改为 50、20。基准测试会稍微好一些。但是切换到 10 之后，它开始倒退，时间开始变大。所以有一些任意数字，至少对于我的硬件来说，使算法运行最有效。

当我实现这个时，我实际上看到了一些关于最好的 goroutines 数量的问题，但现在我找不到它（愚蠢的 Chrome 历史实际上并没有保存所有访问过的站点）。你知道如何计算这样的东西吗？如果我不必硬编码，那将是最好的，让程序自己完成。

P.S 我有非并发快速排序，运行比这慢 1.7 倍。正如您在我的代码中看到的，当运行ning goroutines 的数量超过我之前设置的数量时，我会执行 Quicksort。我想过使用 ConcurrentQuicksort 怎么样，而不是用 go 关键字调用它，只是简单地调用它，也许如果其他 goroutines 完成他们的工作，我调用的 ConcurrentQuicksort 就会开始启动 goroutines，加快进程（因为你可以看到 Quicksort 只会启动递归快速排序，没有 goroutines）。我这样做了，实际上时间比常规 Quicksort 慢了 10%。你知道为什么会这样吗？

Answer 1

你必须对这些东西进行一些试验，但我认为主要关注的不是goroutines 运行一次。正如@reticentroot 链接到的答案所说，it's not necessarily a problem to run a lot of simultaneous goroutines.

我认为您主要关心的应该是goroutine 启动总数。目前的实现理论上可以启动一个 goroutine 来对一些项目进行排序，并且该 goroutine 在 startup/coordination 上花费的时间比实际排序要多得多。

理想情况是您只启动所需数量的 goroutine 以充分利用所有 CPU。如果您的工作项大小相同并且您的核心也同样繁忙，那么每个核心开始一个任务是完美的。

这里，任务的大小不均匀，因此您可以将排序分成稍微比[=76]更多的任务=]s 并分发它们。（在生产中，您通常会使用 worker pool 来分配工作，而无需为每个任务启动一个新的 goroutine，但我认为我们可以在这里跳过它。）

要获得可行数量的任务——足以让所有核心保持忙碌，但又不会多到造成大量开销——你可以设置最小大小（初始数组 size/100 或其他） , 并且只拆分比这更大的数组。

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

每个 goroutine launch 花一点时间设置堆栈并进行调度程序簿记
每个任务切换在调度器中花费一些时间，当两个goroutines查看不同的代码或数据时可能会cache misses
您自己的协调代码（通道发送和sync ops）需要时间

其他因素可能会阻止理想的加速发生：您可能会达到系统范围的限制，例如正如 Volker 指出的那样，内存带宽，一些同步成本会随着您添加内核而增加，有时您可以运行变为 various trickier issues。但是设置、切换和协调成本是一个很好的起点。

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

我认为，但还没有测试，你在 50 个 goroutines 上的问题是 1) 你很久以前就已经接近完全利用，所以添加更多的任务会增加更多的协调工作而不会让事情变得更快，并且 2)您正在为 tiny 排序创建 goroutine，这可能比他们实际进行排序花费更多的时间来设置和协调。在 10 个 goroutines 时，您的问题可能是您不再实现完全 CPU 利用率。

如果你愿意，你可以通过计算在不同 goroutine 限制下（在 an atomic global counter 中）启动的 goroutine 总数并测量在不同限制下的 CPU 利用率来测试这些理论（例如运行在 Linux/UNIX time 实用程序下安装您的程序。

对于像这样的分而治之的问题，我建议的方法是只为足够大的子问题分叉一个 goroutine（对于快速排序，这意味着足够大的子数组).您可以尝试不同的限制：也许您只为超过原始数组的 1/64 的部分或超过某个静态阈值的部分（如 1000 项）启动 goroutines。

我怀疑您的意思是将这种排序例程作为一种练习，但是您可以做很多事情来使您的排序更快或更稳健地应对奇怪的输入。 The standard libary sort 回退到小子数组的插入排序，并使用堆排序来处理导致快速排序问题的异常数据模式。

您还可以查看其他算法，例如用于全部或部分排序的基数排序，which I played with. That sorting library is also parallel. I wound up using a minimum cutoff of 127 items before I'd hand a subarray off for other goroutines to sort, and I used an arrangement with a fixed pool of goroutines and a buffered chan to pass tasks between them。这在当时产生了不错的实际加速，尽管它可能不是当时最好的方法，而且我几乎可以肯定它不在今天的 Go 调度程序中。实验很有趣！

Answer 2

如果操作是CPU有界，我的实验表明最优是CPUs的数量。

template

这台机器上最有效的 goroutines 数量

Most efficient number of goroutines on this machine

concurrency

go

goroutine