十一月 8, 2018

在 Golang 中使用 Goroutine 进行平行运算

在 Golang 中要开一个 goroutine 非常简单,只要一行 go task() 就可以了,也因为这样可以很轻易写出并发的程序

而这篇文章要讲的正是如何使用 goroutine 进行平行运算,把 CPU 的效能发挥(一ㄚㄓㄚˋ)到极致

何谓「平行运算」

根据维基百科上的定义:

平行计算(英语:parallel computing)一般是指许多指令得以同时进行的计算模式。在同时进行的前提下,可以将计算的过程分解成小部份,之后以并行方式来加以解决

简单来说就是把一个大任务拆成多个小任务,然后用并行(parallel)的方式处理他们

今天的大任务:把一个 slice 的数字加总

你可能想说:「把一个 slice 中的数字加总有什麽难?这种程度的问题连我阿嬷都会」,于是轻轻松松就写出了一个 Sum 函数,跑个循环把里面的数字都加起来

func Sum(numbers []int) int {
	total := 0
	for _, n := range numbers {
		total += n
	}
	return total
}

实测一下把一百万个数字加总只花了 50 万奈秒,速度非常之快

注:一秒 = 十亿奈秒

> go test -bench=^BenchmarkSum$
goos: darwin
goarch: amd64
BenchmarkSum-8 3000 502660 ns/op

但因为 Sum 终究是单线程(Single Thread)的,执行时只会用到一个 CPU,如果你的电脑有两个以上的 CPU,那可以想办法让他们分工合作

双核心改良版

为了让大任务可以被平行运算,必须先将它拆成多个小任务

以这个的例子来说,如果可以把 slice 切成左右两半,左半边交给 cpu1 加总、右半边则交给 cpu2,等他们各自加总完再相加,这样应该会比较快吧?

照这个想法去实作会写出这样的代码,把左半边跟右半边交给不同的 goroutine 去加总,加总完再透过 channel 传回来相加

func SumTwoParallel(numbers []int) int {
	mid := len(numbers) / 2

	ch := make(chan int)
	go func() { ch <- Sum(numbers[:mid]) }()
	go func() { ch <- Sum(numbers[mid:]) }()

	total := <-ch + <-ch
	return total
}

实测一下,这次只花了 30 万奈秒,速度快了不少

> go test -bench=^BenchmarkSumTwoParallel$
goos: darwin
goarch: amd64
BenchmarkSumTwoParallel-8        5000     300351 ns/op

多核心通用版

刚刚的「双核心改良版」只把 slice 切割成左右两边,但如果有更多 CPU 就可以切成更多块交给不同的 CPU

先使用 runtime.NumCPU() 取得 CPU 的数量,再把 slice 切割成 N 等份给不同的 goroutine 去加总,最后再统合到 total,这样不管跑这段程式的电脑有几个 CPU 都可以均匀分配

func SumMaxParallel(numbers []int) int {
	nCPU := runtime.NumCPU()
	nNum := len(numbers)

	ch := make(chan int)
	for i := 0; i < nCPU; i++ {
		from := i * nNum / nCPU
		to := (i + 1) * nNum / nCPU
		go func() { ch <- Sum(numbers[from:to]) }()
	}

	total := 0
	for i := 0; i < nCPU; i++ {
		total += <-ch
	}
	return total
}

在我的电脑上(八核心)实测大概可以跑到 16 万奈秒,跟一开始的 50 万奈秒比起来大概是三倍快

> go test -bench=^BenchmarkSumMaxParallel$
goos: darwin
goarch: amd64
BenchmarkSumMaxParallel-8       10000     163897 ns/op

为什麽只有三倍快?

有人可能会说:「以八核心的电脑来说,把任务拆成八份平行处理应该要接近八倍快才对阿,为什麽只有三倍快?」

关于这点我也很疑惑,于是就 trace 了一下各个 goroutine 的执行状况,发现了两个最主要的原因:

1. 等待 Thread 启动的时间太久

如下图,因为程式一开始只有一个 main thread,但开了八个 goroutine 之后系统也需要一些时间再启动七个 thread,没办法在 go func(){…}() 的当下马上就开始加总,所以就延迟了一些

但这不是 goroutine 的错,goroutine 本身启动还是很快的,如果可以有个 thread pool 先开好 thread 就可以解决这个问题

2. 任务太过简单

若单纯看 Thread 启动的延迟应该不会导致速度差好几倍,另外一方面也是因为这个任务(slice 加总)太过简单,任务本身执行得太快,所以只要启动 Thread 时稍有延迟 benchmark 出来的结果就会差很多

下图中 goroutine 15 总共花了约 35 万奈秒,但其中有 23 万奈秒都在等待被 scheduler 排进去,大概三分之二的时间都在等?,跑出来结果自然很慢

如果换做是非常複杂的任务要执行很久,那 Thread 启动的延迟虽然还是有但相较之下就小得多,Benchmark 测出来的也会更有参考价值

总结

这次用一个很简单的小例子示范如何把大任务切割给多个 CPU 平行处理,但这只是一个范例,除非你服务的核心功能就是帮人把数字加总XD,不然真的不需要写成这样

平行运算在很多地方像是 merge sort、矩阵乘法、map reduce 等等都可以用上,虽然这次讲的例子好像很简单,但概念上都是一样的,下次要处理複杂的任务时不妨先想想看,能不能把它拆解成多个小任务分别处理

文章中的程式码都放在 Github repo,欢迎 clone 到自己的电脑上跑跑看 benchmark,其实还有方法可以更快,只是原理比较複杂留著以后再说,大家也可以先自己想想看

本文永久链接:https://mrcpp.com/?p=98429,转载请注明出处

-- EOF --

相关文章 »