概要

以前の記事で

christina04.hatenablog.com

golangはスレッドよりはるかに軽量なgoroutineでC10K問題を解決する、という話をしましたが、goroutineが軽量なのはなぜか？という理由を深掘りしたことがなかったのでしてみました。

環境

golang 1.11.1
Darwin 17.7.0

軽量と呼ばれる理由は２つ

大きく分けると以下の２つのポイントがあります

スレッドに比べてメモリ使用量が低い
スイッチングコストが低い

それぞれ説明していきます。

goroutineがスレッドに比べてメモリ使用量が低いのはなぜか

スタックとヒープのメモリの使い方を理解すると分かります。

ヒープはメモリの下層、プログラムコードのすぐ上にあり、上に向かって成長します。一方スタックは仮想アドレス空間の一番上にあり、徐々に下に成長していきます。

f:id:quoll00:20181022010421p:plain

ref: イベントループなしでのハイパフォーマンス – C10K問題へのGoの回答 | POSTD

ただしヒープとスタックがお互いに上書きしないよう、ガードページと呼ばれるアクセスできないメモリ空間（数メガバイト）を用意します。

スレッドの場合はプロセスの中でメモリを共有しているので、マルチプロセスよりは省コストと言えますが

スタックがどれくらいか分からないため多めに確保する
各スレッド毎にガードページが有る

のでメモリを非常に食うという問題があります。

f:id:quoll00:20181022031927p:plain

ref: イベントループなしでのハイパフォーマンス – C10K問題へのGoの回答 | POSTD

一方goroutineのスタックはガードページを使いません。 Goのコンパイラはガードページの代わりに、実行させる関数にとって十分なスタックがあるかどうかのチェックを挿入します。このチェックによってどれくらい確保すればよいのかが分かり、スレッドスタックのようなオーバーヘッドを避けることが可能になっています。

f:id:quoll00:20181022011009p:plain

ref: イベントループなしでのハイパフォーマンス – C10K問題へのGoの回答 | POSTD

スタックの初期サイズは2kですが、それでは足りない場合ランタイムはヒープに対してより大きなスタックセグメントを割り当て、現在のスタックの内容を新しいセグメントにコピーし、古いセグメントを解放しそれから関数呼び出しを再開します。

このように

最初のスタックサイズを小さくできる
ガードページが不要

といった点で、メモリにおける軽量さを実現しています。

スイッチングが低コストなのはなぜか

限られたCPU上でマルチプロセス・マルチスレッドを実現するためにはコンテキストスイッチが発生します。
なのでそのコストを下げることは並行処理を効率化することになります。

コンテキストスイッチ

以下の時にコンテキストスイッチが起きます。

マルチタスキング
割り込み処理
ユーザーモードとカーネルモードの切り替え

詳細はwikipediaをどうぞ

スレッドのモデル

スレッドには大きく分けて以下の３つがあります。

参考：Thread (computing) - Wikipedia

1:1（カーネルレベルスレッディング）

１つのユーザ・スレッドに対して、 1 つのカーネル・スレッドをマップします。

特徴	説明
メリット	シンプル。マシンのコアを全て利用できる
デメリット	各スレッドによるマルチタスキングでのコンテキストスイッチが必要なので遅い

N:1（ユーザレベルスレッディング）

複数のユーザ・スレッドに対して、 1 つのカーネル・スレッドをマップします。

特徴	説明
メリット	マルチタスキングによるコンテキストスイッチが無くなるので高速
デメリット	マルチコアの恩恵を受けられない。また、あるスレッドがカーネル内でIOでブロックされると全スレッドがブロックされる

M:N（ハイブリッドスレッディング）

複数のユーザ・スレッドに対して、複数のカーネル・スレッドをマップします。
前述の２つを組み合わせた形です。

特徴	説明
メリット	マルチコアが活用でき、マルチタスキングによるコンテキストスイッチが抑えられるので1:1モデルよりも高速
デメリット	スケジューラが複雑になる

golangはこの中で最後のM:Nモデルを採用しており、スイッチングコストを最小限に抑えていることが分かります。
またデメリットとなる複雑なスケジューラ部分を言語側で吸収してくれています。

スケジューラの動き方

Golangのスケジューラあたりの話

を読めばとても良く分かります。勉強のため自分でもまとめます。

G, P, M

スケジューラを話す上で３つの登場人物がいます

人物	役割
M	OSスレッド。Machineの略
G	goroutine
P	スケジューリングのコンテキスト。Processorの略

通常の動き

例えばOSスレッド（＝M）とGOMAXPROCSがともに２つの場合、以下のようになります。

f:id:quoll00:20181022172716j:plain

ref: The Go scheduler - Morsing's blog

PはGOMAXPROCSを設定した分存在します。デフォルトはCPUのコア数ですね。
一方Mは基本的にPより＋２程度多く存在しました（もしかしたらDarwinだけ？）。
余分なうちの１つはsysmonという関数を実行する特別なMで、これはnetpollのチェック・実行時間の長いGのプリエンプト・必要があればGC用のGをグローバルキューに追加などを行います。

基本的にPがGをMに紐付けます。Pの役割として

各PはローカルキューにGを持つ
Pは紐付いているMに対し、Gを渡していく
自分のローカルキューが無くなるとグローバルキューをみてキューを補充する
グローバルキューにもなかったら他のPからキューを半分盗む

と言う形でgoroutineを処理していきます。

work stealing

下の図では右のPのローカルキューがなくなったため、隣のPから半分Gを盗んでいますね。

f:id:quoll00:20181022173432j:plain

ref: The Go scheduler - Morsing's blog

syscallによるPの移動

syscallなどコンテキストスイッチが発生して時間がかかるような処理では、PはMにそのGを処理させたまま、別のMへ移動してスケジューリングを行います。
その時idleなMがあればそこへ移動し、もしなければMを新しく生成して移動します。

f:id:quoll00:20181022173618j:plain

ref: The Go scheduler - Morsing's blog

この図ではM0でsyscallが発生したのでPはM1に移動し、残りのGを処理させようとします。

このことから分かるように、仮にGOMAXPROCSが１であっても複数のM（＝OSスレッド）を使う、つまりマルチコアを使用することになります。

具体的な挙動

golangでは実行時にGODEBUG=scheddetail=1,schedtrace=1000といったオプションを付けることで、スケジューラの挙動を確認することが可能です。
適当なサンプルで試してみましょう

サンプルコード

func main() {
    runtime.GOMAXPROCS(1)
    for i := 0; i < 100; i++ {
        goroutine()
    }
    time.Sleep(100 * time.Second)
}

func goroutine() {
    go func() {
        var counter int64
        for {
            counter++
        }
    }()
}

GOMAXPROCS=1の時

$ GODEBUG=scheddetail=1,schedtrace=1000 ./scheduler
...
SCHED 1006ms: gomaxprocs=1 idleprocs=0 threads=6 spinningthreads=0 idlethreads=3 runqueue=0 gcwaiting=0 nmidlelocked=0 stopwait=0 sysmonwait=0
  P0: status=1 schedtick=2 syscalltick=1 m=5 runqsize=99 gfreecnt=0
  M5: p=0 curg=4 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M4: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=true lockedg=-1
  M3: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=true lockedg=-1
  M2: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=true lockedg=-1
  M1: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=1 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M0: p=-1 curg=104 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=true lockedg=-1
  G1: status=4(sleep) m=-1 lockedm=-1
  G2: status=4(force gc (idle)) m=-1 lockedm=-1
  G3: status=4(GC sweep wait) m=-1 lockedm=-1
  G4: status=2() m=5 lockedm=-1
  G5: status=1() m=-1 lockedm=-1
  G6: status=1() m=-1 lockedm=-1
  G7: status=1() m=-1 lockedm=-1
  G8: status=1() m=-1 lockedm=-1
  G9: status=1() m=-1 lockedm=-1

人物	数
P	1
M	6
G	100

という結果になりました。
Pが１つに限定されていてもMは思ったより多く用意されていました。おそらくCPUの数が関係ありそうです。

GOMAXPROCS=6の時

SCHED 2007ms: gomaxprocs=6 idleprocs=0 threads=8 spinningthreads=0 idlethreads=0 runqueue=0 gcwaiting=0 nmidlelocked=0 stopwait=0 sysmonwait=0
  P0: status=1 schedtick=2 syscalltick=1 m=7 runqsize=89 gfreecnt=0
  P1: status=1 schedtick=2 syscalltick=0 m=4 runqsize=0 gfreecnt=0
  P2: status=1 schedtick=1 syscalltick=0 m=5 runqsize=0 gfreecnt=0
  P3: status=1 schedtick=1 syscalltick=0 m=3 runqsize=4 gfreecnt=0
  P4: status=1 schedtick=1 syscalltick=0 m=2 runqsize=1 gfreecnt=0
  P5: status=1 schedtick=1 syscalltick=0 m=6 runqsize=0 gfreecnt=0
  M7: p=0 curg=14 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M6: p=5 curg=11 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M5: p=2 curg=4 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M4: p=1 curg=5 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M3: p=3 curg=10 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M2: p=4 curg=13 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M1: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=1 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M0: p=-1 curg=104 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=true lockedg=-1
  G1: status=4(sleep) m=-1 lockedm=-1
  G2: status=4(force gc (idle)) m=-1 lockedm=-1
  G3: status=4(GC sweep wait) m=-1 lockedm=-1
  G4: status=2() m=5 lockedm=-1
  G5: status=2() m=4 lockedm=-1
  G6: status=1() m=-1 lockedm=-1
  G7: status=1() m=-1 lockedm=-1
  G8: status=1() m=-1 lockedm=-1

人物	数
P	6
M	8
G	100

先に述べたようにMはPよりも+2分用意されました。
各PのrunqsizeでローカルキューのGの数が分かりますが、処理によっては偏りが出るようですね。

GOMAXPROCS=100の時

SCHED 3023ms: gomaxprocs=100 idleprocs=0 threads=102 spinningthreads=0 idlethreads=0 runqueue=0 gcwaiting=0 nmidlelocked=0 stopwait=0 sysmonwait=0
  P0: status=1 schedtick=1 syscalltick=0 m=4 runqsize=0 gfreecnt=0
  P1: status=1 schedtick=4 syscalltick=1 m=8 runqsize=0 gfreecnt=0
  P2: status=1 schedtick=1 syscalltick=0 m=2 runqsize=0 gfreecnt=0
  P3: status=1 schedtick=1 syscalltick=0 m=3 runqsize=0 gfreecnt=0
...
  P96: status=1 schedtick=1 syscalltick=0 m=98 runqsize=0 gfreecnt=0
  P97: status=1 schedtick=1 syscalltick=0 m=99 runqsize=0 gfreecnt=0
  P98: status=1 schedtick=1 syscalltick=0 m=100 runqsize=0 gfreecnt=0
  P99: status=1 schedtick=1 syscalltick=0 m=101 runqsize=0 gfreecnt=0
  M101: p=99 curg=95 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M100: p=98 curg=53 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M99: p=97 curg=56 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M98: p=96 curg=98 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
...
  M4: p=0 curg=19 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M3: p=3 curg=20 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M2: p=2 curg=21 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M1: p=-1 curg=-1 mallocing=0 throwing=0 preemptoff= locks=1 dying=0 helpgc=0 spinning=false blocked=false lockedg=-1
  M0: p=-1 curg=117 mallocing=0 throwing=0 preemptoff= locks=0 dying=0 helpgc=0 spinning=false blocked=true lockedg=-1
  G1: status=4(sleep) m=-1 lockedm=-1
  G2: status=4(force gc (idle)) m=-1 lockedm=-1
  G3: status=4(GC sweep wait) m=-1 lockedm=-1
  G17: status=2() m=5 lockedm=-1
  G18: status=2() m=6 lockedm=-1

人物	数
P	100
M	102
G	100

生成するgoroutine分GOMAXPROCSを用意すると、各Pが１つのGをMに割り当てるようになっていました。

GOMAXPROCSは増やした方がいいのか？

さて、上記の実験からGOMAXPROCSを増やすとPだけでなくM（＝OSスレッド）も増えることが分かります。
OSスレッドが増えるということはCPUはそのマルチスレッドをコンテキストスイッチによって切り替えて実行する必要があり、スイッチングコストが掛かってしまします。

本来goroutineはOSスレッドによるコンテキストスイッチを減らすことで軽量なスレッドを実現していたのに、これでは台無しです。
したがってGOMAXPROCSはCPU数程度が良い、と言われるわけですね。

まとめ

goroutineは

スレッドに比べてメモリ使用量が低い
M:Nモデルを採用することでスイッチングコストが低い

といった点から、軽量スレッドと呼ばれることが分かりました。

Carpe Diem

備忘録

goroutineはなぜ軽量なのか

概要

環境

軽量と呼ばれる理由は２つ

goroutineがスレッドに比べてメモリ使用量が低いのはなぜか

スイッチングが低コストなのはなぜか

コンテキストスイッチ

スレッドのモデル

1:1（カーネルレベルスレッディング）

N:1（ユーザレベルスレッディング）

M:N（ハイブリッドスレッディング）

スケジューラの動き方

G, P, M

通常の動き

work stealing

syscallによるPの移動

具体的な挙動

サンプルコード

GOMAXPROCS=1の時

GOMAXPROCS=6の時

GOMAXPROCS=100の時

GOMAXPROCSは増やした方がいいのか？

まとめ

ソース