使用Golang的協程竟然變慢了｜100萬個協程的歸并排序耗時分析

這篇文章將用三個版本的歸并排序，為大家分析使用協程排序的時間開銷（被排序的切片長度由128到1000w）

前言

這篇文章將用三個版本的歸并排序，為大家分析使用協程排序的時間開銷（被排序的切片長度由128到1000w）

本期demo地址：https://github.com/BaiZe1998/go-learning

往期視頻講解 ??：B站：白澤talk，公眾號：白澤talk

認為并發總是更快

• 線程：OS 調度的基本單位，用于調度到 CPU 上執行，線程的切換是一個高昂的操作，因為要求將當前 CPU 中運行態的線程上下文保存，切換到可執行態，同時調度一個可執行態的線程到 CPU 中執行。
• 協程：線程由 OS 上下文切換 CPU 內核，而 Goroutine 則由 Go 運行時上下文切換協程。Go 協程占用內存比線程少（2KB/2MB），協程的上下文切換比線程快80～90%。

?? GMP 模型：

• G：Goroutine
  • 執行態：被調度到 M 上執行
  • 可執行態：等待被調度
  • 等待態：因為一些原因被阻塞
• M：OS thread
• P：CPU core
  • 每個 P 有一個本地 G 隊列（任務隊列）
  • 所有 P 有一個公共 G 隊列（任務隊列）

協程調度規則：每一個 OS 線程（M）被調度到 P 上執行，然后每一個 G 運行在 M 上。

?? 上圖中展示了一個4核 CPU 的機器調度 Go 協程的場景：

此時 P2 正在閑置因為 M3 執行完畢釋放了對 P2 的占用，雖然 P2 的 Local queue 中已經空了，沒有 G 可以調度執行，但是每隔一定時間，Go runtime 會去 Global queue 和其他 P 的 local queue 偷取一些 G 用于調度執行（當前存在6個可執行的G）。

特別的，在 Go1.14 之前，Go 協程的調度是合作形式的，因此 Go 協程發生切換的只會因為阻塞等待（IO/channel/mutex等），但 Go1.14 之后，運行時間超過 10ms 的協程會被標記為可搶占，可以被其他協程搶占 P 的執行。

歸并案例

?? 為了印證有時候多協程并不一定會提高性能，這里以歸并排序為例舉三個例子：

主函數：

func main() {
	size := []int{128, 512, 1024, 2048, 100000, 1000000, 10000000}
	sortVersion := []struct {
		name string
		sort func([]int)
	}{
		{"Mergesort V1", SequentialMergesortV1},
		{"Mergesort V2", SequentialMergesortV2},
		{"Mergesort V3", SequentialMergesortV3},
	}
	for _, s := range size {
		fmt.Printf("Testing Size: %d\n", s)
		o := GenerateSlice(s)
		for _, v := range sortVersion {
			s := make([]int, len(o))
			copy(s, o)
			start := time.Now()
			v.sort(s)
			elapsed := time.Since(start)
			fmt.Printf("%s: %s\n", v.name, elapsed)
		}
		fmt.Println()
	}
}

v1的實現：

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) {
    // ...
}

v2的實現：

func SequentialMergesortV2(s []int) {
	if len(s) <= 1 {
		return
	}
	middle := len(s) / 2

	var wg sync.WaitGroup
	wg.Add(2)

	go func() {
		defer wg.Done()
		SequentialMergesortV2(s[:middle])
	}()
	go func() {
		defer wg.Done()
		SequentialMergesortV2(s[middle:])
	}()
	wg.Wait()
	Merge(s, middle)
}

v3的實現：

const max = 2048

func SequentialMergesortV3(s []int) {
	if len(s) <= 1 {
		return
	}
	if len(s) < max {
		SequentialMergesortV1(s)
	} else {
		middle := len(s) / 2

		var wg sync.WaitGroup
		wg.Add(2)

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

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

耗時對比：

Testing Size: 128
Mergesort V1: 10.583μs
Mergesort V2: 211.25μs
Mergesort V3: 7.5μs

Testing Size: 512
Mergesort V1: 34.208μs
Mergesort V2: 500.666μs
Mergesort V3: 60.291μs

Testing Size: 1024
Mergesort V1: 48.666μs
Mergesort V2: 643.583μs
Mergesort V3: 47.084μs

Testing Size: 2048
Mergesort V1: 94.666μs
Mergesort V2: 786.125μs
Mergesort V3: 77.667μs

Testing Size: 100000
Mergesort V1: 6.810917ms
Mergesort V2: 58.148291ms
Mergesort V3: 4.219375ms

Testing Size: 1000000
Mergesort V1: 62.053875ms
Mergesort V2: 558.586458ms
Mergesort V3: 37.99375ms

Testing Size: 10000000
Mergesort V1: 632.3875ms
Mergesort V2: 5.764997041s
Mergesort V3: 388.343584ms

由于創建協程和調度協程本身也有開銷，第二種情況無論多少個元素都使用協程去進行并行排序，導致歸并很少的元素也需要創建協程和調度，開銷比排序更多，導致性能還比不上第一種順序歸并。

特別在切片長度為1000w的時候，基于v2創建的協程數量共計百萬。

而在本臺電腦上，經過調試第三種方式可以獲得比第一種方式更優的性能，因為它在元素大于2048個的時候，選擇并行排序，而少于則使用順序排序。但是2048是一個魔法數，不同電腦上可能不同。這里這是為了證明，完全依賴并發/并行的機制，并不一定會提高性能，需要注意協程本身的開銷。

小結

可以克隆項目之后，使用協程池寫一個歸并排序，進一步比較內存消耗。