七爪源码:Go 中的并发并不总是更快

要成为一名熟练的开发人员，您必须承认并发并不总是更快。涉及最小工作负载并行化的解决方案不一定比顺序实现更快。对顺序解决方案与并发解决方案进行基准测试应该是验证假设的方法。

许多开发人员的一个误解是认为并发解决方案总是比顺序解决方案更快。这再错不过了。解决方案的整体性能取决于许多因素，例如我们的代码结构（并发）的效率、可以并行处理的部分以及计算单元之间的竞争程度。这篇文章提醒了我们一些关于 Go 并发的基础知识；然后我们将看到一个具体的例子，其中并发解决方案不一定更快。

Go 调度

线程是操作系统可以执行的最小处理单元。如果一个进程想要同时执行多个动作，它会启动多个线程。这些线程可以是：

• 并发 - 两个或更多线程可以在重叠的时间段内启动、运行和完成。
• 并行 - 同一个任务可以一次执行多次。

操作系统负责以最佳方式调度线程的进程，以便：

• 所有线程都可以消耗 CPU 周期而不会饿死太多时间。
• 工作负载尽可能均匀地分布在不同的 CPU 内核之间。

注意：线程一词在 CPU 级别上也可以有不同的含义。每个物理核可以由多个逻辑核（超线程的概念）组成，一个逻辑核也称为线程。在这篇文章中，当我们使用线程这个词时，我们指的是处理单元，而不是逻辑核心。

CPU 内核执行不同的线程。当它从一个线程切换到另一个线程时，它会执行一个称为上下文切换的操作。消耗 CPU 周期的活动线程处于执行状态并进入可运行状态，这意味着它已准备好等待可用内核执行。上下文切换被认为是一项代价高昂的操作，因为操作系统需要在切换之前保存线程的当前执行状态（例如当前寄存器值）。

作为 Go 开发者，我们不能直接创建线程，但是可以创建 goroutine，可以认为是应用级线程。然而，OS 线程由 OS 上下文切换打开和关闭 CPU 内核，而 goroutine 由 Go 运行时上下文切换打开和关闭 OS 线程。此外，与 OS 线程相比，goroutine 的内存占用更小：Go 1.4 的 goroutines 占用 2 KB。操作系统线程取决于操作系统，但是，例如，在 Linux/x86–32 上，默认大小为 2 MB。较小的尺寸使上下文切换更快。

注意：上下文切换 goroutine 与线程的速度大约快 80% 到 90%，具体取决于架构。

现在让我们讨论一下 Go 调度程序是如何工作的，以概述 goroutine 的处理方式。在内部，Go 调度程序使用以下术语（参见 proc.go）：

• G - 协程
• M - OS 线程（代表机器）
• P - CPU核心（代表处理器）

每个 OS 线程 (M) 由 OS 调度程序分配给一个 CPU 内核 (P)。然后，每个 goroutine (G) 在一个 M 上运行。 GOMAXPROCS 变量定义了负责同时执行用户级代码的 Ms 的限制。但是如果一个线程在系统调用中被阻塞（例如，I/O），调度器可以启动更多的 Ms。从 Go 1.5 开始，GOMAXPROCS 默认等于可用 CPU 内核的数量。

goroutine 的生命周期比 OS 线程更简单。它可以执行以下操作之一：

• Executing - goroutine 被调度在一个 M 上并执行它的指令。
• Runnable - goroutine 正在等待处于执行状态。
• Waiting - goroutine 被停止并等待完成的事情，例如系统调用或同步操作（例如获取互斥锁）。

关于 Go 调度的实现还有最后一个阶段要理解：当一个 goroutine 被创建但还不能执行时；例如，所有其他 Ms 已经在执行 G。在这种情况下，Go 运行时将如何处理它？答案是排队。 Go 运行时处理两种队列：每个 P 的一个本地队列和所有 P 共享的全局队列。

图 1 显示了 GOMAXPROCS 等于 4 的四核机器上的给定调度情况。这些部分是逻辑核 (Ps)、goroutine (Gs)、OS 线程 (Ms)、本地队列和全局队列：

首先，我们可以看到 5 个 Ms，而 GOMAXPROCS 设置为 4。但正如我们所提到的，如果需要，Go 运行时可以创建比 GOMAXPROCS 值更多的 OS 线程。

P0、P1 和 P3 目前正忙于执行 Go 运行时线程。但是 P2 目前处于空闲状态，因为 M3 关闭了 P2，并且没有要执行的 goroutine。这不是一个好的情况，因为六个可运行的 goroutine 正在等待执行，一些在全局队列中，一些在其他本地队列中。 Go 运行时将如何处理这种情况？这是伪代码中的调度实现（参见 proc.go）：

runtime.schedule() {
    // Only 1/61 of the time, check the global runnable queue for a G.
    // If not found, check the local queue.
    // If not found,
    //     Try to steal from other Ps.
    //     If not, check the global runnable queue.
    //     If not found, poll network.
}

每执行 60 次，Go 调度程序将检查全局队列中的 goroutine 是否可用。如果没有，它将检查其本地队列。同时，如果全局队列和本地队列都为空，则 Go 调度程序可以从其他本地队列中提取 goroutine。这种调度原则称为工作窃取，它允许未充分利用的处理器主动寻找另一个处理器的 goroutine 并窃取一些。

最后要提到的一件重要的事情：在 Go 1.14 之前，调度程序是协作的，这意味着 goroutine 只能在特定的阻塞情况下（例如，通道发送或接收、I/O、等待获取互斥体）。从 Go 1.14 开始，Go 调度程序现在是抢占式的：当一个 goroutine 运行特定的时间量（10 毫秒）时，它将被标记为可抢占的，并且可以通过上下文切换被另一个 goroutine 替换。这允许强制长时间运行的作业共享 CPU 时间。

现在我们了解了 Go 中调度的基础知识，让我们看一个具体的例子：以并行方式实现归并排序。

并行合并排序

首先，让我们简要回顾一下归并排序算法的工作原理。然后我们将实现一个并行版本。请注意，目标不是实现最有效的版本，而是支持一个具体的示例，说明为什么并发并不总是更快。

合并排序算法的工作原理是将一个列表重复分成两个子列表，直到每个子列表包含一个元素，然后合并这些子列表，从而得到一个排序列表（见图 2）。每个拆分操作将列表拆分为两个子列表，而合并操作将两个子列表合并为一个排序列表。

这是该算法的顺序实现。 我们不包含所有代码，因为这不是本文的重点：

func sequentialMergesort(s []int) {
    if len(s) <= 1 {
        return
    }

    middle := len(s) / 2
    sequentialMergesort(s[:middle]) // First half
    sequentialMergesort(s[middle:]) // Second half
    merge(s, middle) // Merges the two halves
}

func merge(s []int, middle int) {
    // ...
}

该算法具有使其对并发开放的结构。 实际上，由于每个sequentialMergesort 操作都在不需要完全复制的独立数据集上工作（这里是使用切片的底层数组的独立视图），我们可以通过旋转每个sequentialMergesort 在CPU 内核之间分配这个工作负载 在不同的 goroutine 中操作。 让我们编写第一个并行实现：

func parallelMergesortV1(s []int) {
    if len(s) <= 1 {
        return
    }

    middle := len(s) / 2

    var wg sync.WaitGroup
    wg.Add(2)

    go func() { // Spins up the first half of the work in a goroutine
        defer wg.Done()
        parallelMergesortV1(s[:middle])
    }()

    go func() { // Spins up the second half of the work in a goroutine
        defer wg.Done()
        parallelMergesortV1(s[middle:])
    }()

    wg.Wait()
    merge(s, middle) // Merges the halves
}

在这个版本中，工作负载的每一半都在一个单独的 goroutine 中处理。 父 goroutine 使用 sync.WaitGroup 等待这两个部分。 因此，我们在合并操作之前调用 Wait 方法。

我们现在有了合并排序算法的并行版本。 因此，如果我们运行一个基准来比较这个版本和顺序版本，并行版本应该更快，对吗？ 让我们在具有 10,000 个元素的四核机器上运行它：

Benchmark_sequentialMergesort-4 2278993555 ns/op

Benchmark_parallelMergesortV1-4 17525998709 ns/op

令人惊讶的是，并行版本几乎慢了一个数量级。我们如何解释这个结果？跨四个内核分配工作负载的并行版本怎么可能比在单台机器上运行的顺序版本慢？我们来分析一下问题。

如果我们有一个切片，比如 1,024 个元素，父 goroutine 将启动两个 goroutine，每个负责处理由 512 个元素组成的一半。这些 goroutine 中的每一个都会启动两个新的 goroutine，负责处理 256 个元素，然后是 128 个，依此类推，直到我们启动一个 goroutine 来计算单个元素。

如果我们想要并行化的工作负载太小，这意味着我们将计算它太快，那么跨内核分配作业的好处就被破坏了：创建一个 goroutine 并让调度程序执行它所花费的时间很长与直接合并当前 goroutine 中的少量项目相比太高了。尽管 goroutine 比线程轻量级且启动速度更快，但我们仍然会遇到工作负载太小的情况。

那么我们可以从这个结果中得出什么结论呢？这是否意味着合并排序算法不能并行化？等等，没那么快。

让我们尝试另一种方法。因为在一个新的 goroutine 中合并少量元素效率不高，让我们定义一个阈值。该阈值将表示一半应包含多少元素才能以并行方式处理。如果一半的元素个数小于这个值，我们会依次处理。这是一个新版本：

const max = 2048 // Defines the threshold

func parallelMergesortV2(s []int) {
    if len(s) <= 1 {
        return
    }

    if len(s) <= max {
        sequentialMergesort(s) // Calls our initial sequential version
    } else { // If bigger than the threshold, keeps the parallel version
        middle := len(s) / 2

        var wg sync.WaitGroup
        wg.Add(2)

        go func() {
            defer wg.Done()
            parallelMergesortV2(s[:middle])
        }()

        go func() {
            defer wg.Done()
            parallelMergesortV2(s[middle:])
        }()

        wg.Wait()
        merge(s, middle)
    }
}

如果 s 切片中的元素个数小于最大值，我们称为顺序版本。否则，我们继续调用我们的并行实现。这种方法会影响结果吗？是的，它确实：

Benchmark_sequentialMergesort-4 2278993555 ns/op

Benchmark_parallelMergesortV1-4 17525998709 ns/op

Benchmark_parallelMergesortV2-4 1313010260 ns/op

我们的 v2 并行实现比顺序实现快 40% 以上，这要归功于定义阈值以指示何时并行应该比顺序更有效的想法。

注意：为什么我将阈值设置为 2,048？因为它是我机器上这个特定工作负载的最佳值。通常，应该使用基准（在类似于生产的执行环境中运行）仔细定义此类魔法值。值得注意的是，在没有实现 goroutine 概念的编程语言中运行相同的算法会对值产生影响，这也很有趣。例如，使用线程在 Java 中运行相同的示例意味着接近 8,192 的最佳值。这往往说明 goroutines 比线程更有效。

结论

我们在这篇文章中看到了 Go 中调度的基本概念：线程和 goroutine 之间的区别以及 Go 运行时如何调度 goroutine。同时，使用并行归并排序示例，我们说明了并发性不一定总是更快。正如我们所见，启动 goroutine 以处理最小的工作负载（仅合并一小部分元素）破坏了我们可以从并行性中获得的好处。

那么，我们应该从这里去哪里呢？我们必须记住，并发并不总是更快，不应该被认为是解决所有问题的默认方法。首先，它使事情变得更加复杂。此外，现代 CPU 在执行顺序代码和可预测代码方面变得非常高效。例如，超标量处理器可以在单核上高效地并行执行指令。

这是否意味着我们不应该使用并发？当然不是。但是，必须牢记这些结论。

关注七爪网，获取更多APP/小程序/网站源码资源！