golang中如何利用并行高效的解决问题(附代码)

背景

一：并发与并行

这是一个老生常谈的问题了，随便搜索一下都能得到大量地回答，并发与并行的概念如下。

并发(concurency)：并发表示多个任务可以在同一时间段运行，但不代表能在同一时刻运行，比如在单核处理器上运行多个任务。
并行(parallelism)：并行代表任务可以同时运行，比如在多核处理器上运行多个任务(每个核在同一时间都在处理任务)。

在实际工作中，我们在遇到一个问题的时候，往往会先想到一个串行的解决问题的方案；然后才会进一步思考如何更快的解决问题，也就是利用并行解决问题，这里说并行不是并发是因为并发并不能加快解决问题的速度，只有并行才可以。

那么什么样的问题才能通过并行加速解决呢，我们一起来思考下面几个问题。

二：计算数组总和

问题：计算一个整形数组之和是多少？

根据问题我们很快能够写出代码如下：

func add(num []int) int64 {
	var sum int64 = 0
	for _, i := range num {
		sum += int64(i)
	}
	return sum
}

分析一下这个问题可不可以使用并行的方式来处理，答案当然是可以的，具体原因后面再说，读者可以自己先思考一下。使用并行的方式处理，需要用到多个goroutine一起来进行计算，把num数组拆为num1，num2，num3……numn等，然后每个goroutine计算自己的那份，最后加到一起，代码实现如下：

func addConcurrent(gNumber int, num []int) int64 {
	lenght := len(num) / gNumber

	wg := sync.WaitGroup{}
	wg.Add(gNumber)

	var answer int64 = 0
	for i := 0; i < gNumber; i++ {
		go func(index int) {
			defer wg.Done()

			start := index * lenght
			end := (index + 1) * lenght
			if index == gNumber - 1 {
				end = len(num)
			}

			var sum int64 = 0
			for i := start; i < end; i++ {
				sum += int64(num[i])
			}

			atomic.AddInt64(&answer, sum)
		}(i)
	}

	wg.Wait()
	return answer
}

那么理论上来说，addConcurrent函数的计算速度是要比add快的，我们来测试一下，首先需要生成一个数组，内容随机生成

func init() {
	rand.Seed(time.Now().UnixNano())
}

//生成长度为totalNumbers的数组
func generateList(totalNumbers int) []int {
	numbers := make([]int, totalNumbers)
	for i := 0; i < totalNumbers; i++ {
		numbers[i] = rand.Intn(totalNumbers)
	}
	return numbers
}

然后写性能测试文件main_test.go

//main_test.go
package main

import (
	"fmt"
	"runtime"
	"testing"
)

var num []int

func init() {
	num = generateList(1e7)
	fmt.Printf("cpu count=%+v\n", runtime.NumCPU())
}

func Benchmark1(b *testing.B) {
	for i := 0; i < b.N; i++ {
		add(num)
	}
}

func Benchmark2(b *testing.B) {
	for i := 0; i < b.N; i++ {
		addConcurrent(runtime.NumCPU(), num)
	}
}

main文件如下：

//main.go
package main

import (
	"fmt"
	"math/rand"
	"sync"
	"sync/atomic"
	"time"
)

func add(num []int) int64 {
	var sum int64 = 0
	for _, i := range num {
		sum += int64(i)
	}
	return sum
}

func addConcurrent(gNumber int, num []int) int64 {
	lenght := len(num) / gNumber

	wg := sync.WaitGroup{}
	wg.Add(gNumber)

	var answer int64 = 0
	for i := 0; i < gNumber; i++ {
		go func(index int) {
			defer wg.Done()

			start := index * lenght
			end := (index + 1) * lenght
			if index == gNumber - 1 {
				end = len(num)
			}

			var sum int64 = 0
			for i := start; i < end; i++ {
				sum += int64(num[i])
			}

			atomic.AddInt64(&answer, sum)
		}(i)
	}

	wg.Wait()
	return answer
}

func init() {
	rand.Seed(time.Now().UnixNano())
}


func generateList(totalNumbers int) []int {
	numbers := make([]int, totalNumbers)
	for i := 0; i < totalNumbers; i++ {
		numbers[i] = rand.Intn(totalNumbers)
	}
	return numbers
}


func main() {
}

接下来我们开始测试，执行如下命令

GOGC=off go test -cpu 1 -run none -bench . -benchtime 3s

然后得到结果

update_data git:(master) ✗ GOGC=off go test -cpu 1 -run none -bench . -benchtime 3s
cpu count=4
goos: darwin
goarch: amd64
pkg: update_data
Benchmark1           500           7539064 ns/op
Benchmark2           500           7989754 ns/op
PASS
ok      update_data     10.141s

结果竟然发现使用"并行"的方式竟然要比串行慢，这个主要是因为在进行测试的时候我们指定了CPU个数为1，那么其实我们虽然启动了4个goroutine去计算数据，但是其实还是一个CPU在进行工作，里面还包含了goroutine之间互相切换的时间，所以速度当然会慢了。
现在我们换个姿势，使用2个CPU来进行测试。
结果如下：

update_data git:(master) ✗ GOGC=off go test -cpu 2 -run none -bench . -benchtime 3s
cpu count=4
goos: darwin
goarch: amd64
pkg: update_data
Benchmark1-2         500           7671754 ns/op
Benchmark2-2        1000           5379842 ns/op
PASS
ok      update_data     11.571s

可以看到姿势正确了之后，速度一下子就上来了，并行去做计算大概能够提升30%，需要注意的是因为每个人的电脑都不一样，程序运行时是否有其他进程干扰，CPU型号等都会影响我们的数据结果。

但是还是不妨碍我们看到并行是可以更高效的帮助我们解决问题的。

三：冒泡排序

问题：实现一个冒泡排序
基本排序问题，相信读者们都不陌生了，直接上代码：

func bubbleSort(num []int) []int {
	if len(num) <= 1 {
		return num
	}

	for i := len(num); i > 0; i-- {
		for j := 0; j < i - 1; j++ {
			if num[j] > num[j+1] {
				num[j], num[j+1] = num[j+1], num[j]
			}
		}
	}

	return num
}

下面我们分析一下，冒泡排序可否用并行的方式来计算，比如将num拆分为多个数组，每个goroutine计算自己的部分，最后再将该部分数组合起来。但是相比你立马就发现问题了，即使之前每个goroutine计算完了自己的那一部分，但是最后还是要重新进行一遍。所以冒泡排序是无法使用并行计算的方式来加速的。

通过上面两个简单的例子，我们发现了使用并行加速计算的问题必须要具备一个很重要的特征：顺序无关性
比如求数组之和，无论我们怎么拆分数组，只要每个数都加过一遍，最后就可以得到结果，同样的还有数组连乘等问题。

像我们平常写工程代码的时候，经常要调用其他的接口，如果两个接口之间没有数据依赖(比如第二个接口的调用参数包含第一个接口的返回值，就是有数据依赖的，必须有序执行接口)，其实是可以使用并行的方式来加速计算的。

四：任务类型对并行的影响

我们一般会将任务分为CPU密集型和IO密集型，顾名思义，CPU密集型的任务就是需要CPU进行大量计算的，其中的瓶颈主要在于CPU的算力；IO密集型的任务主要消耗在于文件IO、网络IO等消耗上，CPU通常处于低负载状态。那么不同的任务类型对我们并行的解决问题是否有影响。

答案当然是肯定的。具体的代码就不举例了，留给读者们自己阅读文章，找到答案。

再贴一下原文的地址：https://www.ardanlabs.com/blog/2018/12/scheduling-in-go-part3.html