Go语言中常见100问题-#56 Concurrency isn’t always faster

并发并不一定是最快的

许多开发人员犯的一个误解是认为并发的处理方法应该总是比顺序的处理方法更快，这是大错特错的。处理方法的整体性能取决于很多因素。例如程序结构的效率（并发性），可以并行处理的部分以及计算单元之间的竞争程度。在本节中，我们将学习一些Go并发的基础知识，并通过一个具体的例子说明并发的处理方法并不是最快的。

Go调度

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

• 并发的，当两个或以上线程在重叠的时间段内启动、运行和完成时。例如Go语言中常见100问题-#55 Mixing concurrency and parallelism中的服务员线程和咖啡机线程。
• 并行的，当同一个任务可以同时执行多次时，例如Go语言中常见100问题-#55 Mixing concurrency and parallelism中的多个服务员线程。

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

• 所有的线程都可以使用CPU周期而不会饿死很长时间
• 工作负载尽可能的均匀分布在不同的CPU内核上

NOTE: 在CPU级别上来看，线程具有不同的含义。每个物理核可以有多个逻辑核（超线程的概念），一个逻辑核也可以称为线程。在本节内容中，当说线程一词时，它指的不是逻辑核，而是处理单元的概念。

CPU内核执行不同的线程，当它从一个线程切换到另一个线程执行时，会执行一个上下文切换的操作。正在使用CPU的活动线程从处于执行状态变为可运行状态。可运行状态意味着线程已准备好执行但在等待CPU. 上下文切换是一项有代价的操作，在进行切换之前，操作系统需要保存线程的当前执行状态，例如当前寄存器的值。

在Go语言开发中，我们不能直接创建线程，但是可以创建goroutine，可以把goroutine当做应用级线程。如果说线程的上下文切换是由操作系统内核管理的，那么goroutine在一个线程上的上下文切换是由Go运行时管理的。与线程相比，goroutine占用的内存更小。Go1.4中一个goroutine占用的内存为2KB，线程的大小取决于操作系统，例如在Linux/x86-32上，线程的默认大小为2MB. goroutine因为占用的内存更小，所以在上下文切换时也更快。

NOTE: goroutine的上下文切换比线程的上下文切换大约快80%到90%，实际情况取决于系统架构。

下面开始深入研究Go程序调度的工作原理，以及goroutine的处理方式。Go调度即为GMP工作原理，G/M/P的含义如下:

• G:goroutine
• M:OS thread, 操作系统线程
• P:CPU core, 处理器

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

goroutine的生命周期比OS线程的更简单，它位于下面状态之一：

• 执行状态：goroutine被调度在一个M上并执行它的指令
• 可运行状态：goroutine等待被调度到M上执行状态
• 等待状态：停止并等待完成某些事情，例如操作系统调用或同步调用，例如互斥锁

最后一个需要理解的Go调度策略是：当一个goroutine被创建但还不能执行时，例如，其他所有的M都在执行G. 在这种情况下，处理方法是进行排队。Go运行时处理两种队列，每个P有一个本地队列，还有一个全局队列，全局队列在所有的P中是共享的。

在4核机器上Go程序的调度情况如下图所示，GOMAXPROCS等于4，有程序逻辑处理器（P),程序并发执行单元goroutine, OS线程（M),本地队列以及全局队列。

上图中有5个M(M0-M4),然而GOMAXPROCS设置的为4.正如我们所提到的的，在需要时运行时可以创建比GOMAXPROCS更多的操作系统线程。P0，P1和P3正在忙着执行G. P2却处于空闲状态，因为M3解除了与P2的关联，并且没有要执行的goroutine. 这种情况很糟糕，因为总共有6个可运行的goroutine正在等待被执行。3个在全局队列中，2个在P0的本地队列1个在P3的本地队列中。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.
}

每执行61次调度，调度程序将检查全局队列中中是否有可被执行的goroutine. 如果没有，将检查本地队列是否有可运行的G. 如果全局队列和本地队列都为空，则会从其他本地队列中偷取G,这种调度原则称为工作窃取，它允许未充分利用的处理器主动寻找其他处理器的G并窃取过来执行。

在Go1.14之前，goroutine调度是协作式的，意味着goroutine只能在特定阻塞的情况下才能切换。向通道中发送或从通道中接收数据，等待I/O，等待互斥。从Go1.14开始，Go的调度是抢占式的，意味着当一个goroutine运行一定的时间(10毫秒)时，它将被标记为可抢占的，并且可以上下文切换到另一个goroutine运行，允许强制长时间运行的任务共享CPU时间。

通过上面的介绍我们已经了解了Go调度的基础知识，下面通过并行方法实现归并排序这个具体例子加深理解。

并行排序

首先，我们来回顾一下归并排序算法的工作原理。然后，我们将实现一个并行的版本，需要注意的是下面代码不是追求实现最高效的版本，而是通过这个例子来说明并发不是最快的实例。

归并排序算法的工作原理是将一个数组重复分解为两个子数组，直到每个子数组中包含一个元素，然后按顺序合并这些子数组，从而得到一个排序的数组。

每次split操作将一个数组分割为两个子数组，merge操作将两个子数组合并为一个有序的数组。下面是归并排序的顺序实现版本，这里只贴了关键的代码，完整的代码实现我上传到github（https://github.com/ThomasMing0915/100-go-mistakes-code/tree/main/56）。

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

        middle := len(s) / 2
        sequentialMergesort(s[:middle])
        sequentialMergesort(s[middle:])
        merge(s, middle)
}

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

归并排序在结构上也容易通过并发进行实现，由于每个sequentialMergesort操作不需要对原s切片进行拷贝操作，共享s只是操作的s的不同位置的数据。我们可以将单个sequentialMergesort操作在一个goroutine上执行，多个sequentialMergesort操作分配在所有的CPU核上进行，下面是一个并行归并排序实现。

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

        middle := len(s) / 2

        var wg sync.WaitGroup
        wg.Add(2)

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

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

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

在上述版本中，工作任务的每一半都在一个单独的goroutine上执行，父goroutine使用sync.WaitGroup等待两个子goroutine完成各个子数组的排序之后，再将它们合并为一个有序的数组。

现在我们已经实现了一个串行版本和一个并行版本的归并排序算法，下面通过性能测试benchmark进行验证，那么一定是并行版本更快吗？下面对一个有1万个元素的切片在我的4核机器上的测试结果。

goos: darwin
goarch: amd64
pkg: mergesort
cpu: Intel(R) Core(TM) i5-7360U CPU @ 2.30GHz
BenchmarkParallelMergesortV1-4               156           7015025 ns/op
BenchmarkSequentialMergesort-4              1197            932941 ns/op
PASS
ok      mergesort       4.321s

让人感到震惊的是并行版本比串行版本慢了一个数量级。为什么会是这样呢？利用4个核分配工作任务的并行版本怎么可能比串行的版本慢呢？下面开始分析原因：

如果我们有一个1024大小元素的切片，父goroutine将启动两个goroutine,每个负责处理一般的元素排序，即处理512个。然后，这些goroutine中的每一个都会启动两个新的goroutine来处理256个元素，接着是128个，依此类推，直到最后启动一个goroutine来处理单个元素。

如果让每部分处理任务变得更小，那么小任务处理的更快，但是这样会破坏跨核分配任务的好处。与直接合并当前goroutine中元素相比，创建goroutine并调度它们所 花费的时间太长了。尽管goroutine比线程轻量并且启动速度更快，但是在工作任务太小的情况下，我们还是会遇到上述问题，即花在非处理工作任务的时间超过了真正要执行任务的时间，这是得不偿失的。

那怎样解决上面的问题呢？难道是说归并排序算法不能并行化？等等，并不是这样。下面尝试另一种方法，因为在一个goroutine中合并少量元素的效率不高，我们定义一个阈值，这个阈值表示以并行方式处理的元素大小，如果低于这个值，将按顺序处理。代码如下：

const max = 2048

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

        if len(s) <= max {
                sequentialMergesort(s)
        } else {
                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)
        }
}

当切片的大小比max小时，直接走顺序处理，否则进行并行处理。现在再来进行benmark测试，测试结果如下，V2版本的并行实现比顺序实现快了20%以上，这主要归功于定义了阈值，用于指导在何时并行应该比顺序更高效。

goos: darwin
goarch: amd64
pkg: mergesort
cpu: Intel(R) Core(TM) i5-7360U CPU @ 2.30GHz
BenchmarkParallelMergesortV1-4               174           6794052 ns/op
BenchmarkParallelMergesortV2-4              1545            709677 ns/op
BenchmarkSequentialMergesort-4              1218            932325 ns/op
PASS
ok      mergesort       5.433s

NOTE：为什么将阈值设置为2048，而不是其他值，这个值是在我的机器上进行工作负载的最佳值，通常可以设置一系列值进行基准测试，从而得到一个最佳值。

在本章中我们学习了Go调度的基本概念，线程和goroutine之间的区别，以及Go运行时是如何调度goroutine的。同时举了归并排序的例子进行说明，验证了并发并不一定总是更快。正如前面的实验，当启动goroutine处理更少量元素的工作时，从并行程序中获取的优势正在丢失。

那在工作中实现的时候，选择并行还是串行的呢？我们需要记住，并发并不总是更快，不应该视为解决所有问题的默认方法。一方面是因为并行的程序写起来更复杂，另一方面是现在的CPU在执行顺序代码和可预测代码方面已经非常高效。例如，超标量处理器可以在单个核上以高效率并行执行指令。

这是说我们不应该使用并发吗？当然不是，记住下面这个原则。如果我们不能确定并行版本是否更快，正确的做法是从一个简单的顺序版本开始，然后作为基准，再实现并发的版本，通过benchmark测试，验证哪种方法是最佳的。