Goのcontext実装にお手本のようなDouble-Checked Lockingが利用されていた話

# `cancelCtx.done`の型変更
Goの標準ライブラリを読んだことがある人ならば、`context`パッケージを読んだことがある人が多いのではないだろうか。

自分もその一人で、`context.Context`の機能自体が好きなのもあるが、`context`パッケージの実装はGoらしさが詰まっていて、十分短い(600秒未満)のでサクッと読めてとても参考になる。

過去3回ほど読み直しているが久しぶりに読み直してみたら、「おっ」と思うような修正が入っていた。

以下の一年前のパッチである。
https://github.com/golang/go/commit/ae1fa08e4138c49c8e7fa10c3eadbfca0233842b

下がdiffの一部であるが、`cancelCtx.done`の型が `chan struct{}`から`atomic.Value`に変更されているではないか。

![スクリーンショット 2022-04-09 0.13.58.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/370237/7229e878-cbb7-fb6f-4a7d-8ce33034e66d.png)

issueを追っかけると、どうやら、複数のGoルーチンが同時に、同一コンテキストに対してキャンセルされたかをcheckする状況においてパフォーマンスが悪化するのが発覚し、`Done() <-chan struct{}`における排他ロックをDouble-Checked Locking（後述）に修正したらしい。

今回新規に追加された以下のベンチマークだと-96.74%の改善されたようだ。
Double-Checked Lockingの威力を感じる数字だ。

```go
func BenchmarkContextCancelDone(b *testing.B) {
	ctx, cancel := context.WithCancel(context.Background())
	defer cancel()

	b.RunParallel(func(pb *testing.PB) {
		for pb.Next() {
			select {
			case <-ctx.Done():
			default:
			}
		}
	})
}
```

```
name                 old time/op  new time/op  delta
ContextCancelDone-8  67.5ns ±10%   2.2ns ±11%  -96.74%  (p=0.000 n=30+28)
```

# Double-Checked Lockingとは
yamasa-sanのhttps://yamasa.hatenablog.jp/entry/20100128/1264693781 が良い。

ポイントを引用すると

> DCLとは、「ロック→条件判定」というロジックを「条件判定→ロック→(再度)条件判定」と書き換えるイディオムで、主に遅延初期化などの処理においてロックのオーバーヘッドを減らすために用いられます。

> このDCL実装の肝は、変数 p がatomic型として宣言されている点です。 C++0x のatomic型は、これまで繰り返し説明してきたように、操作がアトミック(不可分)に行われるだけでなく、メモリアクセスの順序付けを保証する効果(メモリバリア)も持っています。変数 p への読み書きの際にメモリバリア効果が発揮されるため、最初に挙げた「DCLの問題点」を解消できているのです。

今回のソースでいうと、修正前は、「`c.mu`にてlockして初期化済みか判定して必要であれば`c.done`を初期化」していた。

それが、`c.done`を `atomic.Value`として格納するよう修正した上で、「`c.done`にて初期化済みか判定して不要ならreturn、必要なら`c.mu`にてlockした後、再度判定して必要であれば`c.done`を初期化」している。

一番大事なのは、操作がアトミック(不可分)に行われるだけでなく、メモリバリア(メモリフェンスとも言う)効果が`c.done`の読み書きにあるのか？ということである。

c++だと、https://en.cppreference.com/w/cpp/atomic/memory_order にあるように保証され、なおかつさまざまな保証レベルを選択できる。

Goの場合はどうかというと常に`Sequentially-consistent`であることを保証してくれているようだ。

実は、2022年4月現在だと[GoのMemory Modelのドキュメント](https://go.dev/ref/mem)に`consistency`と言う単語が見つからず不安になるのだが、[documentに書くようrscが進めてくれているよう](https://github.com/golang/go/issues/50859)である。

また、rscが過去に

> Yes, I spent a while on this last winter but didn't get a chance to write it up properly yet. The short version is that I'm fairly certain the rules will be that Go's atomics guarantee sequential consistency among the atomic variables (behave like C/C++'s seqconst atomics), and that you shouldn't mix atomic and non-atomic accesses for a given memory word.

と[発言](https://github.com/golang/go/issues/5045#issuecomment-252730563)している。

どうやら、C++と同義の`Sequentially-consistent`を期待して良さそうである。

# おまけ
Double-Checked Lockingはわかったよ！でも、やりたいことは`chan struct{}` の初期化を遅延させたいだけなのにコードが複雑すぎない？と思うかもしれない。自分もそう思う。通常業務で同じ状況に遭遇すれば明らかにメンテの複雑さによるコストを避けるために遅延させず、構造体初期化時に`make(chan struct{})`するだろう。

でも、`context`パッケージにおいてはそういうわけにはいかない。パフォーマンス最優先である。
実は、当初は構造体初期化時に`make(chan struct{})`していたようで、遅延するようになったのは2017年の以下のcommitである。
https://github.com/golang/go/commit/986768de7fcf4def65cecd7eb0c34e2cdf92e78c

それなりに、メモリ使用量を抑えられているのがわかるだろう。

ただ、[bradfitzが指摘する](https://github.com/golang/go/issues/42564#issuecomment-761402848)ように当時の修正やbenchmarkではlockが新たに必要になるデメリットの方を考慮しきれていなかったようである。