Day 8: GCのデザイン ~RCUの動作原理~

RCUのGC

昨日はRCUの基礎を学び、古いデータの解放(GC)はグレースポイントが終了したときにされるということを学んだ。今日はその実装方法についての話をする。

参照カウンタ(Arc)は遅い

昨日の記事でGCの実装方法の一つとして、Atomic Reference Counter (Arc) を使用したGCがある。
これは以下のような実装である:

• rcu_read_lock()時に参照カウンタを増加
• rcu_read_unlock()時にカウンタを減少
• カウンタが0になった時点でデータを解放

一見シンプルに見えるこの方式だが、実はパフォーマンス上の大きな問題がある。その理由をキャッシュコヒーレンスの観点から説明する。

キャッシュコヒーレンスによる性能低下

Arcのパフォーマンス問題の原因を知るには、以前「Day 5: キャッシュコヒーレンスプロトコル ~並行処理の基礎~」で解説したキャッシュコヒーレンスプロトコルの知識が役立つ。

要するにマルチコアで同じメモリの値に対して書き込みを行う問題は2つある。

• 他のSステートのキャッシュラインをIステートに遷移させること
  • のちにCPUがアクセスした際にキャッシュミスになる
• 自身のキャッシュラインがMステートとなること
  • 他のCPUとMステートのキャッシュラインを共有するときに、一度下層のメモリに書き込んでSステートにしなければならない

Arc方式のRCUでは、読み込み操作のたびにこれらの問題が発生する。つまり、頻繁なキャッシュライン競合により、システム全体のパフォーマンスが低下する。

他のGCの実装

Arcが遅くてダメなので、代わりにどういったGCの実装があるのかというと結構色々ある。

Rust Atomics and LocksのChapter 10では、Hazard Pointer、EBR、QSBRなどが紹介されている。

細かい実装の話をすると大変なんだが、どのGCもスレッドローカルストレージ(Thread Local Strage, TLS)を使われているので、そこを軽く解説する。

スレッドローカルストレージはマルチスレッドにおける重要な概念で、各スレッドが独自のデータ領域を持つことができる仕組みである。他のスレッドもそのデータ領域のデータを読むことはできるが、基本的にはそのスレッド自身からしか読み書きしないのでキャッシュライン競合によって起きるキャッシュコヒーレンスプロトコルの負荷が減る。ちなみに、RustだとTLSを初期化するmacroが提供されている。

また、最後にHazard Pointer、EBR、QSBRではスレッドローカルストレージが各実装でどのように使われているか簡単に説明する。

• Hazard Pointer
  • スレッドローカルストレージにそのスレッドで使用するデータのポインタを登録して、「このデータを使うので、勝手に消したりしないように」と宣言する
  • GCでは各スレッドのスレッドローカルストレージを走査して消していいポインタを調べる
• EBR/QSBR
  • 各スレッドローカルストレージにそのスレッドが扱っているデータのバージョンを示すローカルカウンタを置く
  • 古いデータの解放の可否を判断する際に、最新のバージョンを示すグローバルカウンタと各ローカルカウンタと比較結果を見ている

ちなみに、このアドベントカレンダーでは最も読み込み性能が高いQSBRを実装する。

今日はここで終了。明日はQSBRをより細かく解説する。