使用 goroutines 进行合并排序与普通 Mergesort

Question

我在 Go 中编写了两个版本的归并排序。一个有goroutines，另一个没有。我正在比较每个人的表现，我一直在看https://github.com/denniss/goplayground/blob/master/src/example/sort.go#L69那就是使用 goroutines 的那个。这是一个没有https://github.com/denniss/goplayground/blob/master/src/example/sort.go#L8我一直在试图弄清楚为什么 goroutine 实现的性能比没有的要差得多。这是我在当地看到的数字 go run src/main.go[5 4 3 2 1]Normal Mergesort[1 2 3 4 5]Time:  724Mergesort with Goroutines[1 2 3 4 5]Time:  26690然而，我仍然无法弄清楚为什么。想知道你们是否可以给我关于做什么/看什么的建议或想法。在我看来，goroutines 的实现至少应该表现得更好一些。我这么说主要是因为以下几行go MergeSortAsync(numbers[0:m], lchan)go MergeSortAsync(numbers[m:l], rchan)

Answer 1

使用并发并不一定会使算法运行得更快。事实上，除非算法本质上是并行的，否则它会减慢执行速度。

处理器 (CPU) 一次只能做一件事，即使对我们来说，它似乎同时做两件事。两个 goroutine 的指令可能会交错，但这并不会使它们运行得比单个 goroutine 快。在任何给定时刻都只执行来自一个 goroutine 的一条指令（有一些非常低级别的异常，具体取决于硬件特性）——除非您的程序在多个内核上运行。

据我所知，标准归并排序算法本质上并不是并行的；需要进行一些修改以优化它以在多个处理器上并行执行。即使您使用多个处理器，也需要针对它优化算法。

这些优化通常与通道的使用有关。我不同意“写入通道有很大的开销”本身（Go 使它非常高效），但是，它确实引入了 goroutine 阻塞的可能性。显着减慢程序速度的不是对通道的实际写入，而是调度/同步：等待和唤醒 goroutine 以从通道写入或读取可能是瓶颈。

为了补充 Not_a_Golfer 的回答，我同意 goroutine 在执行 I/O 操作时肯定会发光——即使在单个内核上——因为这些发生在远离 CPU 的地方。当一个 goroutine 正在等待 I/O 时，调度程序可以调度另一个受 CPU 限制的 goroutine 在此期间运行。然而，当跨多个处理器/内核部署时，goroutines 也适用于 CPU 密集型操作。

Answer 2

正如其他人所解释的，并行是有代价的。您需要看到足够的收益来补偿该成本。这仅在工作单元大于制作通道和 goroutine 接收结果的成本时才会发生。

您可以通过试验来确定工作单元应该是什么。假设工作单元对 1000 个元素进行排序。在这种情况下，您可以非常轻松地更改代码，如下所示：

func MergeSortAsync(numbers [] int, resultChan chan []int)  {

    l := len(numbers)

    if l <= 1000 {

            resultChan <- Mergesort(numbers)

            return

    }

换句话说，一旦工作单元太小而无法证明使用 goroutines 和通道是合理的，那么使用你的 simpleMergesort没有这些成本。

Answer 3

有两个主要原因：

1. 写入通道有很大的开销。作为参考 - 我尝试使用通道和 goroutines 作为迭代器。它们比重复调用方法慢约 100 倍。当然，如果通过管道传输的操作需要很长时间才能执行（例如抓取网页），则这种差异可以忽略不计。

2. Goroutines 在基于 IO 的并发性方面非常出色，而在 CPU 并行性方面则不然。

考虑到这两个问题，您将需要大量 CPU 或更长时间，每个 goroutine 的阻塞操作更少，以使其更快。