go - 这台机器上最有效的 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缓冲 channel ，我用它来限制运行的 goroutines 的数量(如果它达到这个数量，我不会设置另一个 goroutine，我只是在子数组上做普通的快速排序)。首先我从 100 开始，然后我更改为 50、20。基准会稍微好一点。但是在切换到 10 之后，它开始倒退，时间开始变大。因此，至少对于我的硬件而言，有一些任意数字可以使算法运行最高效。

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

P.S 我有非并发 Quicksort，它的运行速度比这慢 1.7 倍。正如你在我的代码中看到的，我做 Quicksort ，当运行的 goroutine 数量超过我之前设置的数量时。我想如何使用 ConcurrentQuicksort ，但不使用 go 调用它关键字，只需简单地调用它，也许如果其他 goroutine 完成它们的工作，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 会在启动/协调上花费比实际排序更多的时间。

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

在这里，任务的大小不均匀，因此您可以将排序拆分为比 CPU 多的任务并分配它们。 (在生产中，您通常会使用 worker pool 来分配工作，而无需为每个任务启动一个新的 goroutine，但我认为我们可以在这里跳过它。)

为了获得可行数量的任务——足以让所有核心保持忙碌，但又不会太多以至于你产生大量开销——你可以设置一个最小大小(初始数组大小/100 或其他)，并且只拆分比这更大的数组。

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

每个 goroutine 启动都会花费一些时间来设置堆栈并进行调度程序簿记

每个任务切换都会在调度程序中花费一些时间，并且可能会导致 cache misses当两个 goroutine 查看不同的代码或数据时

您自己的协调代码( channel 发送和 sync 操作)需要时间

其他事情可能会阻止理想的加速发生:您可能会达到系统范围的限制，例如正如 Volker 指出的那样，内存带宽会随着您添加内核而增加一些同步成本，并且您可能会遇到 various更棘手 issues有时。但是设置、切换和协调成本是一个很好的起点。

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

我认为，但尚未测试，您在 50 个 goroutine 上的问题是 1)您很久以前就已经达到了几乎完全利用的状态，因此添加更多任务会增加更多的协调工作而不会使事情变得更快，以及 2)您正在创建 goroutines对于微小的排序，它们可能花费更多的时间进行设置和协调，而不是实际进行排序。在 10 个 goroutine 时，您的问题可能是您不再实现 CPU 的充分利用。

如果您愿意，您可以通过计算在各种 goroutine 限制(在 an atomic global counter 中)启动的 goroutine 总数并测量各种限制下的 CPU 利用率(例如，通过在 Linux/UNIX time 实用程序下运行您的程序)来测试这些理论.

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

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

您还可以查看其他算法，例如用于全部或部分排序的基数排序，which I played with .那个排序库也是并行的。在我将子数组交给其他 goroutine 进行排序之前，我使用了 127 个项目的最小截止值，并且我使用了 an arrangement with a fixed pool of goroutines and a buffered chan to pass tasks between them .这在当时产生了不错的实际加速，尽管当时它可能不是最好的方法，而且我几乎可以肯定它不在今天的 Go 调度程序中。实验很有趣!