Blog

詰めバリアント技術を用いて高速並行カウンターを作ってみる


こんにちは、CA ProFit-Xのフックです。

今の時代、コンピューターのCPUといえば 間違いなくマルチコアのCPUであります。マルチコアCPUが普及したことがきっかけでプログラミングモデルも根本的に変わっています。高いパフォーマンスのアプリを作るために、マルチコアCPUで色々なプログラミングモデル・技術が誕生しています。一方、マルチコアCPUでプログラミングする際に、リソースの衝突(contention)が発生しやすくなってしまうので、衝突が減らせることが大事です。

今回は詰めバリアント(英語: Padded Variant)技術を使ってシンプルな高速並行カウンターを作り方を紹介させていただきたいと思います。

volatileで並行性保証

上記のコードでは簡単なアトミックカウンターを定義しています。Counterクラスにはvolatile変数valueがあります。

volatileアノテーションはJava 5から提供されており、volatile変数はスレッド・セーフにコードを実行するために使用されます。

スレッドではvolatile変数を読み込み・書み込み時に、(コア別のL1キャッシュではなく) 必ずシェアキャッシュ(CPU L2、L3キャッシュ 又は メインメモリー)で操作することになります。

別のコアにあるスレッドから同じvolatile変数の値を読み込む場合と同じ値になり、並行性的なカウンターが保証できます。

Counterの更新パフォーマンス

Counterインスタンスの並行性が保証できますが、更新速度はどうでしょう。下記のケースで検討してみました。

2つのCounterインスタンスcounter 1counter 2を定義して、別のスレッドでそれぞれインスタンスのvalueを更新します。

並行的にcounter 1counter 2valueの更新速度を下記のコードで確認します。

実行:

実行結果によって、3回目から更新速度が数倍ぐらい落ちてしまうことが分かりました。

どうしてこの結果になってしまうのか?次の節で説明します。

キャッシュ行の長さ

キャッシュ行の長さ(英語: cache line size)はCPUキャッシュ上の1行の容量であり、x86アーキテクチャのCPUではキャッシュ行のサイズは64バイトです。

CPUのキャッシュ長さは下記のコマンドで確認できます。

Macの場合:

Linuxの場合:

JOLツール

jol(Java Object Layout)は、Javaのオブジェクトがどのようにメモリ上にレイアウトされるのか確認できるツールです。

Scalaでjolを使えるようにするため、下記のコードのようにbuild.sbtに追加します

実装したCounterのオブジェクトのレイアウトを確認しましょう。

ということは1つのCounterのインスタンスはメモリ上に24バイトの領域を確保していることがわかります。

キャッシュ行の衝突問題 (False sharing問題)

上記の確認したキャッシュ行の長さ及びCounterのインスタンスサイズにおける2つのCounterインスタンスのvalueが、1つのキャッシュ行に放置されることがあります (以下の画像のように)。

cache-contention

その場合、仮に

  1. コア0にあるスレッドはcounter 1valueを書き込む
  2. 並行でコア1にあるスレッドはcounter 2valueを書き込むときは、キャッシュ行が ‘dirty’としてマークされるようになる。
  3. 次に、コア0にあるスレッドは*counter 1*の*value*を読み込もうとするとき、キャッシュ行が消毒(sanitize)できるまで待つ。言い換えると、キャッシュ行の衝突が発生してしまいました。

そのため、counter 1及びcounter 2valueへの書き込み速度に影響してしまいます。

詰めバリアントを利用してキャッシュ行の衝突を解決

詰めバリアントはvolatile変数を詰め物に挟むようにする技術であり、2つのCounterインスタンスのvalueが絶対に別のキャッシュ行に放置されるようにします。
それに従い、別のCounterインスタンスのvalueに書き込むとき、別のキャッシュ行に操作することになるため、衝突が減らせます。

コードは下記です

JOLツールでPaddedCounterインスタンスのオブジェクトレイアウトを確認してみます。

オブジェクトレイアウト結果によって、1つのPaddedCounterインスタンスがメモリ上に136バイトレイアウトされて、value変数が56バイトのp*変数と56バイトのq*変数に挟まれました。

どんな放置方法でも2つPaddedCounterインスタンスのvalueが別のキャッシュ行に放置されるので、キャッシュ行の衝突が減らせるようになりました。

CounterPaddedCounterの更新パフォーマンス

では作ったCounterPaddedCounterの更新速度を確認しましょう。

まとめるコード:

実行:

1回目の実行ではCounterのほうが更新速度が早いですが、

2回目からキャッシュ行の衝突が発生してしまうため、上記のCounterパフォーマンスを確認する結果と同様に更新速度が数倍落ちてしまいました。

PaddedCounterの更新速度は安定的に1500 ms程かかることが分かりました。

まとめ

今回は詰めバリアント技術を使ってとてもシンプルなPaddedCounterを作ってみました。 マルチコアCPUで共通のvolatile変数を使用する場合よりもPaddedCounterの更新速度が早く、並行性を守ることができます。

詰めバリアント技術はJava 8から提供されているjava.util.concurrent.atomic.{LongAdder,DoubleAdder,…}などの親クラスStrip64にあるCellクラス またはContendedアノテーションで使われています。

詳細は下記のリンクになります。

長い記事ですが、読んでいただきありがとうございます。m(_ _)m

Author

アバター
phuc

関連記事