sorting - 使用 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 实现的性能比没有 goroutine 的要差得多。这是我在本地看到的号码

 go run src/main.go
[5 4 3 2 1]
Normal Mergesort
[1 2 3 4 5]
Time:  724
Mergesort 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 的一条指令(这有一些非常低级的异常(exception)，具体取决于硬件特性)——除非你的程序运行在多个内核上。

据我所知，标准归并排序算法本身并不是并行的； some modifications need to be made优化它以在多个处理器上并行执行。即使您使用多个处理器，也需要针对它优化算法。

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

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