「Rust の練習帳」で Rust に入門した 次のステップとして、「詳解 Rust アトミック操作とロック」 を読みました。 全体は 200 ページちょっとですが、かなり歯ごたえのある内容でした。
各章で学んだこと
1 章 Rust 並行性の基本
Rust でスレッドを生成する方法 (std::thread::spawn
や std::thread::scope
) を知りました。
所有権のある Rust では、スレッドに値の所有権を渡すこともあります。 値をドロップする責務がスレッドに渡るので、複数スレッドで値を共有し、共有データがきちんとドロップされることを保証するにはどうすればいいか?という課題が出てきます。
そこで登場するのが Rc や Arc といった参照カウント型です。 参照カウントは値と所有者数カウンタを持っており、clone/drop 時にカウンタのインクリメント/デクリメントが行われます。 所有者数がゼロになったときだけ値が drop されるという仕組みです。
参照カウント自体は不変参照ですが、内部のカウンタは可変になっています。 複数スレッドから不変参照として共有される場合でも、その参照は内部的に可変性を持っています。 この性質を内部可変性と呼びます。 内部可変性を持つものは Rc や Arc 以外に Cell, RefCell という型や、Mutex, RwLock, アトミック型などがあります。
ちなみに Rust の Mutex は Go とは全然違っており、ロックを取って操作したい値そのものを、Mutex が持つという構造になっています。 ロックを取ると、操作対象の値をラップしたガードが返ってきます。 そのガードを通じて排他アクセスを行い、ガードのドロップ時にアンロックされる仕組みです。 個人的には Go の Mutex のほうがわかりやすいですが、Rust の Mutex は所有権をうまく使ったライフサイクル設計だなと感心しました。
マルチスレッドの話として、他のスレッドからの通知を待機する方法の 1 つにスレッドパーキングがあります。 スレッドは自分自身をパークすることで休止し、CPU サイクルを消費しなくなります。 パークしたスレッドは、他のスレッドからアンパークして起こすことができます。 スレッドパーキングは無駄な CPU サイクルの消費を防げるため、単なる while ループを使った待機(ビジーループ)よりも効率的に思えますが、ごく短時間の待機であればビジーループの方がレイテンシが抑えられるので、場合によって使い分けるのが大事です。 スレッドパーキングという仕組みは(おそらく)初めて知り、勉強になりました。
2 章 アトミック操作
アトミックなロード操作とストア操作、読み込み更新 (fetch-and-modify) 操作、比較交換操作について学びました。
std::sync::atomic
で提供されているアトミック型を使い、各種のアトミック操作をどのように行うかが具体的なコードで示されています。
ところで、今までプログラミングしてきてアトミック操作を使ったことはほとんどありませんでした。
もし ISUCON で Go を使ってインクリメンタルな ID 採番をやるとしたら、Mutex でロックを取って採番する場合と、アトミック操作で採番する場合とで、どのくらいパフォーマンスに差が出るのか気になりました。
アトミック操作のほうが、Mutex でロックを取るオーバーヘッドがなくなるぶん速くなるはずです。
せっかくなので Copilot にサクッとコード生成してもらい、go test -bench=. -cpu=XXX
で並列数を指定してベンチマークを取ってみました。
package main
import (
"sync"
"sync/atomic"
"testing"
)
type MutexIDGen struct {
mu sync.Mutex
id int64
}
func (g *MutexIDGen) Next() int64 {
g.mu.Lock()
defer g.mu.Unlock()
g.id++
return g.id
}
type AtomicIDGen struct {
id int64
}
func (g *AtomicIDGen) Next() int64 {
return atomic.AddInt64(&g.id, 1)
}
func BenchmarkMutexIDGen(b *testing.B) {
gen := &MutexIDGen{}
b.RunParallel(func(pb *testing.PB) {
for pb.Next() {
_ = gen.Next()
}
})
}
func BenchmarkAtomicIDGen(b *testing.B) {
gen := &AtomicIDGen{}
b.RunParallel(func(pb *testing.PB) {
for pb.Next() {
_ = gen.Next()
}
})
}
並列数 | MutexIDGen (ns/op) | AtomicIDGen (ns/op) |
---|---|---|
1 | 23.3 | 9.7 |
10 | 81.7 | 30.1 |
100 | 118.7 | 28.6 |
1000 | 117.0 | 23.3 |
10000 | 142.6 | 29.8 |
100000 | 186.3 | 47.4 |
Mutex バージョンだと並列数が上がるほどロック競合によって実行時間が長くなる傾向がありますが、対してアトミック操作バージョンは性能の劣化が抑えられています。 どのみち 1 回あたり数十〜百 ns レベルならボトルネックにならない気もしますが、これまでの ISUCON の経験上、CPU プロファイリングしてみると Mutex が意外と CPU 時間を食っていたりすることもあるので、Mutex の代わりにアトミック操作が使えるところでは使ったほうが良いかもしれません。
若干話が逸れたので戻ります。
3 章 メモリオーダリング
プロセッサは最適化(高速化)のためにアウトオブオーダで実行する可能性があります。 シングルスレッドの場合、アウトオブオーダ実行によってプログラムの結果が変わることはありません。 しかしそのような最適化はスレッド間の相互作用を考慮していないため、マルチスレッドで共有データのロードとストアを(順序指定なしで)行うと、最適化によってプログラムの結果が変わるかもしれません。 Rust のアトミック操作では、オーダリングを正しく指定することで、その不整合を防止することができます。
オーダリングを考えるにあたり、先行発生関係という概念を抑えておく必要があります。 たとえば共有データのストアの後にそのデータのロードが起こるというように、操作の起こる順序が保証されるとき、それらの操作は先行発生関係を結ぶ(あるいは作る)といいます。 自分の理解では、プログラマが個々の操作を細かく順序付けするというよりは、プログラム実行時にある操作 A と B を観測したとき、「操作 A よりも操作 B が先に起こった」ことを保証するのが先行発生関係です。
オーダリングはいくつか種類がありますが、この本では Relaxed オーダリングと Release/Acquire オーダリングが特に重要な位置付けになっています。 Relaxed オーダリングでアトミック操作を行う場合、先行発生関係を作りませんが、1 つのアトミック変数に対するすべての変更はすべてのスレッドから見て同じ順序で行われることになります。 最も緩いオーダリングです。 一方 Release/Acquire オーダリングは、「Release オーダリングでのストア → Acquire オーダリングでのロード」の順で操作が行われたときに、ストア操作(およびストアに先行するすべて)とロード操作(およびロードに後続するすべて)が先行発生関係を作ります。
3 章時点で Release/Acquire オーダリングを理解するのは難しいので、とりあえず「Release ストア → Acquire ロード」の順だけ覚えて読み進めても良いと思います。
4 章以降
3 章でようやく前置きが一区切りついたところです。
この本はオーダリングと先行発生関係がキモで、以降の章では先行発生関係を考慮しながら安全なロックやチャネル、Arc を実装していくことになります。 それぞれミニマム実装から始まり、その実装でどんな問題が起きるかが説明され、その対処や最適化のために実装を改良していく流れです。
スクラッチ実装する経験ができて面白かったですし、「Rust の練習帳」で CLI ツール作成しかやったことがない 自分にとっては Rust の勉強にもなりました(ジェネリクスの書き方や、drop に合わせて何かをやりたいときの Drop トレイトの実装など)。
(コードのリポジトリ:https://github.com/Fukkatsuso/rust-atomics-and-locks)
また 7 章(プロセッサを理解する)の p.137 では、昔 「プログラマーのための CPU 入門」 を読んだときにどうやって実装するのか謎のままだった「値を別々のキャッシュラインに乗せる」を Rust で実験しており、1 年越しに具体例を知ることができたのでスッキリしました。
全体を通じて
全 10 章のうち 1〜3 章しか感想を書いていないようなものですが、本の内容は全体的にかなり濃かったです。
一度読んだだけで納得するのは難しく、読み終えた今でもロックなどの実装を自力で再現するのは正直不可能です。 繰り返し読むことで消化できる本だと思います。 それでも、この本を一通り読み切ったことで達成感と少しの自信が付きました。
また Rust か Go でニッチな内容の本があれば、読んで見識を広げたいと思います。