読者です 読者をやめる 読者になる 読者になる

yoskhdia’s diary

DDDとかプログラミングとかアーキテクチャとか雑多に

false sharingの整理

マルチスレッド時代における意外なハマりどころfalse sharingについてまとめておきます。 参考にあげている書籍「Javaパフォーマンス」からのまとめです。

false sharingとは

例えば、以下の様なコードがあるとします。

public class DataHolder {
    public volatile long l1;
    public volatile long l2;
    public volatile long l3;
    public volatile long l4;
}

このとき、longは64bit = 8バイトのサイズですが、これらはメモリ上で近接して配置されます。 プログラムがl2を操作しようとすると、ある程度まとまったサイズのメモリが読み込まれます。(※2) 多くの場合、近接するインスタンス変数も操作するため、アクセスはとても高速にでき、パフォーマンスに貢献します。 しかし、複数のスレッド(コア)によって頻繁にアクセスする場合、異なる変数への操作であっても、キャッシュにまとまって載っているため、あるコアでの操作結果を他のコアに通知し、そのコアでは再読み込みを行う必要がでてきます。(volatile変数に書込を行うと、他のすべてのスレッドでキャッシュ上の値が無効化され、メモリから再読み込みが必要) このように意図せず 競合 干渉(※1)が発生し、パフォーマンスが大幅に劣化することをfalse sharingと呼びます。

※厳密には、false sharingは同期やvolatile変数とは無関係に発生しますが、Javaのメモリモデルではメインメモリへの書き出しは同期プリミティブ(CAS命令やvolatile変数も含む)の末尾でのみ行うと定められているため、最も頻繁に発生するのは同期に関連するケースとなります。


※1(2016.7.7追記)
"競合"というとプログラムが意図しない間違った動作を引き起こし性能劣化以外の影響があるように捉えられる、とご指摘いただいたので"干渉"という表現に変更いたしました。 性能劣化以外の影響をご存知の方がいらっしゃいましたら、教えていただけると幸いです。

(※1追記終)


※2(2016.7.8追記)
キャッシュ ライン の説明があった方が干渉の説明に繋がるとご指摘いただいたので補足します。
下記参考1で解説されている内容を抜粋します。

キャッシュでは,メイン・メモリを数バイトから数十バイトの「ライン(あるいはブロック)」という単位で管理します.具体的には,キャッシュとメイン・メモリの間のデータ転送,キャッシュ上にデータがあるかどうか(ヒット/ミス・ヒット)を,すべてラインの単位で管理します

(※2)の個所は、このキャッシュラインの単位でデータがメモリからキャッシュへ読み込まれることを指しています。 イメージとしては参考2の図がわかりやすいと思います。false sharingは各スレッドが同じ変数への アクセス を実際に共有していないのに、キャッシュラインの単位で共有している状態になっており、お互いのアクセスによってメモリからの再ロードを頻発させます。インテルガイドの日本語訳がありましたので末尾の参考に追記しました。
また、JEP 142の @Contended アノテーションも指摘されていたのですが、書籍にはこれにも言及があります。ただ、これは「JEPを経てはいますが、このアノテーションJVM内部での利用を主に想定しています。このアノテーションが今後のリリースで使われ続ける保証も、機能が変わらない保証もありません。」とあるためこの記事では省略していました。

参考1:今さら聞けないマルチプロセッサの基礎教えます ――キャッシュの共有,割り込みの共有,OSによる制御|Tech Village (テックビレッジ) / CQ出版株式会社(キャッシュライン)

参考2:今さら聞けないマルチプロセッサの基礎教えます ――キャッシュの共有,割り込みの共有,OSによる制御|Tech Village (テックビレッジ) / CQ出版株式会社(false sharingの図)

参考3:コンピュータアーキテクチャの話 (6) キャッシュの構造(基礎編) - どういう単位でキャッシュに入れるのか? | マイナビニュース

(ご指摘いただいてキャッシュラインについて改めて調べたのですが、自分の理解が曖昧だったことが分かりました...勉強になります)

(※2追記終)


対策

明確な対策はありません。

検出のためには、プロセッサのアーキテクチャに関する詳細な知識が必要で、また検出するツールもベンダーによって対応が異なるようです。(IntelだとVTuneというツールを公開している。)
ネイティブなプロファイラでは、指定されたコードについて命令ごとに必要なクロックサイクル数(CPI)を知ることができるため、多くのCPIが費やされているかがfalse sharingが発生している可能性を検知する材料になります。

通常false sharingが発生した場合、コードの変更が必要です。 大まかな方針は以下のとおり。
パディングは後述のとおり、期待する効果が得られるか微妙な面があるため、前者のローカル変数で処理をし、最後に同期処理でまとめてしまう方法をまずは検討した方が良いでしょう。

  • データをローカル変数へ移動して、書込は最後に行うようにする。
  • パディングを行って複数の変数が同じキャッシュに読み込まれないようにする。

パディング

CPUのキャッシュが128バイトだとしたら、以下のようなコードにします。

public class DataHolder {
    public volatile long l1;
    public long[] dummy1 = new long[128 / 8];
    public volatile long l2;
    public long[] dummy2 = new long[128 / 8];
    public volatile long l3;
    public long[] dummy3 = new long[128 / 8];
    public volatile long l4;
}

ただし、このようにしてしまうと、キャッシュのサイズはCPUごとに異なるため、異なるアーキテクチャへの移行難易度が上がることと、また、パディングした分、インスタンスサイズが増加するため、インスタンスの数によってはGCに悪影響を及ぼします。 さらに、JVMがこれらの変数を配列ごとやlongごとに並べ替えてしまい、期待通りに機能しない可能性もあります。 (その場合、プリミティブ型の変数を使ってパディングすることもできるが、大量の変数が必要になって現実的ではなくなってしまう。)

Actorモデルとfalse sharing

Actorモデル(Akkaを想定)を使う場合、false sharingはほとんど気にする必要はありません。 それは、対策の1点目のようにActorの持つローカル変数は1つのスレッドのみからアクセスすることになるため、意地悪なコードを無理やり書かない限りは競合しなくなるためです。(Actorの内部データは参照されることがなく、Actor間はメッセージによってやり取りされる。)

ただし、Actorそれ自体が同じキャッシュに載ってしまうという可能性は否定することができません。 (たとえ自分がローカル変数を持つようにプログラミングしなくても、Akkaを使っている場合Actorトレイトでローカル変数を持っているため。) しかし、この場合にfalse sharingが何故発生するのかまでは追えていません。 通常ActorRefを通してActorにはアクセスしますが、Actor System内でどのようにActorを管理しているかによって、false sharingが発生し得るのでしょうか。 ご存知の方がいらっしゃいましたら、教えていただけると幸いです。

(※追記) @TanUkkii007 さんが「Akkaはマルチスレッドプログラミングにおける可視性の問題をどう解決しているか」について書いてくれました。

github.com (※追記終)

参考

XLsoft エクセルソフト : インテル ガイド : 3-4 スレッド間のフォールス・シェアリングの回避と特定(2016.7.8追記)

Mechanical Sympathy: False Sharing

Mechanical Sympathy: False Sharing && Java 7

www.oreilly.co.jp