偽共有と@Contendedのガイド

投稿日: 2022-10-28 2022-10-28
タグ: Java Concurrency, JVM

1. 概要

この記事では、偽共有がマルチスレッド化を私たちに逆行させることがあることを説明します。

まず、キャッシングと空間的局所性の理論について少し説明します。次に、 LongAdder 同時ユーティリティを書き直し、 java.util.concurrent実装に対してベンチマークします。記事全体を通して、さまざまなレベルのベンチマーク結果を使用して、偽共有の影響を調査します。

この記事のJava関連の部分は、オブジェクトのメモリレイアウトに大きく依存しています。これらのレイアウトの詳細はJVM仕様の一部ではなく、実装者の裁量に委ねられているため、特定のJVM実装であるHotSpotJVMのみに焦点を当てます。また、記事全体でJVMとHotSpotJVMの用語を同じ意味で使用する場合があります。

2. キャッシュラインとコヒーレンシー

プロセッサはさまざまなレベルのキャッシュを使用します—プロセッサがメインメモリから値を読み取るとき、パフォーマンスを向上させるためにその値をキャッシュする場合があります。

結局のところ、最新のプロセッサのほとんどは、要求された値をキャッシュするだけでなく、さらにいくつかの近くの値もキャッシュします。この最適化は、空間的な局所性の概念に基づいており、アプリケーションの全体的なパフォーマンスを大幅に向上させることができます。簡単に言えば、プロセッサキャッシュは、単一のキャッシュ可能な値ではなく、キャッシュラインの観点から機能しています。

複数のプロセッサが同じまたは近くのメモリ位置で動作している場合、それらは同じキャッシュラインを共有することになります。このような状況では、異なるコアで重複するキャッシュを相互に一貫性のある状態に保つことが不可欠です。このような一貫性を維持する行為は、キャッシュコヒーレンシと呼ばれます。

CPUコア間のキャッシュコヒーレンシを維持するためのプロトコルはかなりあります。この記事では、MESIプロトコルについて説明します。

2.1. MESIプロトコル

MESIプロトコルでは、各キャッシュラインは、変更、排他、共有、無効の4つの異なる状態のいずれかになります。 MESIという単語は、これらの状態の頭字語です。

このプロトコルがどのように機能するかをよりよく理解するために、例を見ていきましょう。 2つのコアが近くのメモリ位置から読み取ると仮定します。

コアAは、メインメモリからaの値を読み取ります。上に示したように、このコアはメモリからさらにいくつかの値をフェッチし、それらをキャッシュラインに格納します。 次に、コアAがこのキャッシュラインで動作する唯一のコアであるため、そのキャッシュラインを排他的としてマークします。今後、可能であれば、このコアは代わりにキャッシュラインから読み取ることにより、非効率的なメモリアクセスを回避します。

しばらくすると、コアBもメインメモリからbの値を読み取ることを決定します。

aとbは互いに非常に近く、同じキャッシュラインに存在するため、両方のコアがキャッシュラインに共有のタグを付けます。

ここで、コアAがaの値を変更することを決定したと仮定します。

コアAは、この変更をストアバッファーにのみ保存し、キャッシュラインを変更済みとしてマークします。また、この変更をコア B、に伝達し、このコアはキャッシュラインを無効としてマークします。

これが、さまざまなプロセッサがキャッシュが相互にコヒーレントであることを確認する方法です。

3. 偽共有

ここで、コアBがbの値を再読み取りすることを決定したときに何が起こるかを見てみましょう。この値は最近変更されていないため、キャッシュラインからの高速読み取りが期待される場合があります。ただし、共有マルチプロセッサアーキテクチャの性質により、実際にはこの期待は無効になります。

前述のように、キャッシュライン全体が2つのコア間で共有されていました。 コアBのキャッシュラインが無効になっているため、メインメモリから値bを再度読み取る必要があります：

上に示したように、メインメモリから同じ b 値を読み取ることだけが、ここでの非効率性ではありません。 コアBは最新の値を取得する必要があるため、このメモリアクセスにより、コアAはストアバッファを強制的にフラッシュします。値をフラッシュしてフェッチした後、両方のコアは、shared状態でタグ付けされた最新のキャッシュラインバージョンになります。

したがって、2つのコアが同じメモリ位置で動作していなくても、これにより1つのコアにキャッシュミスが発生し、別のコアに早期バッファフラッシュが発生します。偽共有として知られるこの現象は、特にキャッシュミスの割合が高い場合に、全体的なパフォーマンスを低下させる可能性があります。具体的には、このレートが高い場合、プロセッサはキャッシュから読み取るのではなく、常にメインメモリにアクセスします。

4. 例：ダイナミックストライピング

偽共有がアプリケーションのスループットまたはレイテンシーにどのように影響するかを示すために、このセクションでごまかします。 2つの空のクラスを定義しましょう：

abstract class Striped64 extends Number {}
public class LongAdder extends Striped64 implements Serializable {}

もちろん、空のクラスはそれほど有用ではないので、いくつかのロジックをコピーして貼り付けましょう。

Striped64 クラスの場合、 java.util.concurrent.atomic.Striped64 クラスからすべてをコピーして、クラスに貼り付けることができます。 importステートメントも必ずコピーしてください。また、Java 8を使用している場合は、 sun.misc.Unsafe.getUnsafe（）メソッドの呼び出しをカスタムメソッドに置き換える必要があります。

private static Unsafe getUnsafe() {
    try {
        Field field = Unsafe.class.getDeclaredField("theUnsafe");
        field.setAccessible(true);

        return (Unsafe) field.get(null);
    } catch (Exception e) {
        throw new RuntimeException(e);
    }
}

アプリケーションクラスローダーからsun.misc.Unsafe.getUnsafe（）を呼び出すことはできないため、この静的メソッドを使用して再度チートする必要があります。ただし、Java 9 では、 VarHandles を使用して同じロジックが実装されているため、特別なことを行う必要はなく、単純なコピーアンドペーストで十分です。。

LongAdder クラスの場合、 java .util.concurrent.atomic.LongAdder クラスからすべてをコピーして、私たちのクラスに貼り付けましょう。ここでも、importステートメントもコピーする必要があります。

次に、これら2つのクラスを相互にベンチマークしてみましょう。カスタムLongAdderとjava.util.concurrent.atomic.LongAdder。

4.1. 基準

これらのクラスを相互にベンチマークするために、簡単なJMHベンチマークを作成しましょう。

@State(Scope.Benchmark)
public class FalseSharing {

    private java.util.concurrent.atomic.LongAdder builtin = new java.util.concurrent.atomic.LongAdder();
    private LongAdder custom = new LongAdder();

    @Benchmark
    public void builtin() {
        builtin.increment();
    }

    @Benchmark
    public void custom() {
        custom.increment();
    }
}

このベンチマークをスループットベンチマークモードで2つのフォークと16のスレッドで実行すると（ “ – -bm thrpt -f 2 -t 16″ 引数を渡すのと同じ）、JMHはこれらの統計を印刷します。

Benchmark              Mode  Cnt          Score          Error  Units
FalseSharing.builtin  thrpt   40  523964013.730 ± 10617539.010  ops/s
FalseSharing.custom   thrpt   40  112940117.197 ±  9921707.098  ops/s

結果はまったく意味がありません。 JDKの組み込み実装は、コピー貼り付けソリューションのスループットをほぼ360％削減します。

レイテンシーの違いを見てみましょう。

Benchmark             Mode  Cnt   Score   Error  Units
FalseSharing.builtin  avgt   40  28.396 ± 0.357  ns/op
FalseSharing.custom   avgt   40  51.595 ± 0.663  ns/op

上に示したように、組み込みのソリューションには、より優れたレイテンシー特性もあります。

これらの一見同一の実装の違いをよりよく理解するために、いくつかの低レベルのパフォーマンス監視カウンターを調べてみましょう。

5. パフォーマンスイベント

サイクル、ストールサイクル、サイクルごとの命令、キャッシュのロード/ミス、メモリのロード/ストアなどの低レベルのCPUイベントを計測するために、プロセッサに特別なハードウェアレジスタをプログラムできます。

実は、perfやeBPFのようなツールは、すでにこのアプローチを使用して有用なメトリックを公開しています。 Linux 2.6.31の時点で、 perf は、有用なパフォーマンス監視カウンターまたはPMCを公開できる標準のLinuxプロファイラーです。

したがって、perfイベントを使用して、これら2つのベンチマークのそれぞれを実行するときにCPUレベルで何が起こっているかを確認できます。たとえば、次のように実行します。

perf stat -d java -jar benchmarks.jar -f 2 -t 16 --bm thrpt custom

Perfは、JMHにコピー貼り付けソリューションに対してベンチマークを実行させ、統計を出力します。

161657.133662      task-clock (msec)         #    3.951 CPUs utilized
         9321      context-switches          #    0.058 K/sec
          185      cpu-migrations            #    0.001 K/sec
        20514      page-faults               #    0.127 K/sec
            0      cycles                    #    0.000 GHz
 219476182640      instructions
  44787498110      branches                  #  277.052 M/sec
     37831175      branch-misses             #    0.08% of all branches
  91534635176      L1-dcache-loads           #  566.227 M/sec
   1036004767      L1-dcache-load-misses     #    1.13% of all L1-dcache hits

L1-dcache-load-misses フィールドは、L1データキャッシュのキャッシュミスの数を表します。上に示したように、このソリューションでは約10億のキャッシュミスが発生しています（正確には1,036,004,767）。組み込みのアプローチと同じ統計を収集する場合：

161742.243922      task-clock (msec)         #    3.955 CPUs utilized
         9041      context-switches          #    0.056 K/sec
          220      cpu-migrations            #    0.001 K/sec
        21678      page-faults               #    0.134 K/sec
            0      cycles                    #    0.000 GHz
 692586696913      instructions
 138097405127      branches                  #  853.812 M/sec
     39010267      branch-misses             #    0.03% of all branches
 291832840178      L1-dcache-loads           # 1804.308 M/sec
    120239626      L1-dcache-load-misses     #    0.04% of all L1-dcache hits

カスタムアプローチと比較して、発生するキャッシュミスがはるかに少ない（120,239,626〜1億2000万）ことがわかります。したがって、キャッシュミスの数が多いことが、このようなパフォーマンスの違いの原因である可能性があります。

LongAdder の内部表現をさらに深く掘り下げて、実際の原因を見つけましょう。

6. ダイナミックストライピングの再検討

java.util.concurrent.atomic.LongAdder は、高スループットのアトミックカウンター実装です。 1つのカウンターを使用するのではなく、それらの配列を使用して、それらの間でメモリの競合を分散します。このように、それは非常に競争の激しいアプリケーションでAtomicLongのような単純なアトミックよりも優れています。

Striped64 クラスは、このメモリ競合の分散を担当します。これが、このクラスがこれらのカウンターの配列を実装する方法です。

@jdk.internal.vm.annotation.Contended 
static final class Cell {
    volatile long value;
    // omitted
}
transient volatile Cell[] cells;

各Cellは、各カウンターの詳細をカプセル化します。この実装により、さまざまなスレッドがさまざまなメモリ位置を更新できるようになります。状態の配列（つまり、ストライプ）を使用しているため、このアイデアは動的ストライピングと呼ばれます。興味深いことに、 Striped64 は、このアイデアと64ビットデータ型で機能するという事実にちなんで名付けられました。

とにかく、JVMはこれらのカウンターをヒープ内で互いに近くに割り当てることができます。つまり、これらのカウンターのいくつかは同じキャッシュラインにあります。したがって、 1つのカウンターを更新すると、近くのカウンターのキャッシュが無効になる場合があります。

ここで重要なポイントは、動的ストライピングのナイーブな実装は誤った共有に悩まされることです。ただし、各カウンターの周囲に十分なパディングを追加することで、各カウンターがキャッシュライン上にあることを確認できるため、誤った共有を防ぐことができます。

結局のところ、 @ jdk.internal.vm.annotation.Contended アノテーションは、このパディングを追加する責任があります。

唯一の問題は、この注釈がコピー貼り付けの実装で機能しなかったのはなぜですか？

7. @Contendedに会います

Java 8では、偽共有を防ぐためにsun.misc.Contendedアノテーション（Java 9はjdk.internal.vm.annotationパッケージで再パッケージ化）を導入しました。

基本的に、この注釈でフィールドに注釈を付けると、HotSpotJVMは注釈付きフィールドの周りにいくつかのパディングを追加します。このようにして、フィールドが独自のキャッシュラインに存在することを確認できます。さらに、クラス全体にこのアノテーションを付けると、HotSoptJVMはすべてのフィールドの前に同じパディングを追加します。

@Contended アノテーションは、JDK自体によって内部的に使用されることを意図しています。 したがって、デフォルトでは、非内部オブジェクトのメモリレイアウトには影響しません。これが、コピーして貼り付けた加算器が組み込みの加算器ほど機能しない理由です。

この内部のみの制限を削除するには、 -XX：-RestrictContended 調整フラグを使用して、ベンチマークを再実行します。

Benchmark              Mode  Cnt          Score          Error  Units
FalseSharing.builtin  thrpt   40  541148225.959 ± 18336783.899  ops/s
FalseSharing.custom   thrpt   40  546022431.969 ± 16406252.364  ops/s

上に示したように、ベンチマークの結果ははるかに近くなり、違いはおそらくほんの少しのノイズです。

7.1. パディングサイズ

デフォルトでは、@Contendedアノテーションは128バイトのパディングを追加します。 これは主に、最近の多くのプロセッサのキャッシュラインサイズが約64/128バイトであるためです。

ただし、この値は、 -XX：ContendedPaddingWidth調整フラグを使用して構成できます。この記事の執筆時点では、このフラグは0〜8192の値のみを受け入れます。

7.2. @Contendedを無効にする

-XX：-EnableContended チューニングを使用して、@Contendedエフェクトを無効にすることもできます。これは、メモリが貴重であり、パフォーマンスを少し（場合によっては多く）失う余裕がある場合に役立つことがあります。

7.3. ユースケース

最初のリリース以降、 @Contended アノテーションは、JDKの内部データ構造での誤った共有を防ぐために非常に広く使用されています。このような実装のいくつかの注目すべき例を次に示します。

Striped64 クラスは、カウンターとアキュムレーターを高スループットで実装します
スレッドクラスは、効率的な乱数ジェネレーターの実装を容易にします。
ForkJoinPoolワークスティーリングキュー
ConcurrentHashMapの実装
Exchangerクラスで使用されるデュアルデータ構造

8. 結論

この記事では、誤った共有がマルチスレッドアプリケーションのパフォーマンスに逆効果をもたらすことがあることを確認しました。

さらに具体的に言うと、Javaでの LongAdder 実装をそのコピーに対してベンチマークし、その結果をパフォーマンス調査の開始点として使用しました。

また、 perf ツールを使用して、Linuxで実行中のアプリケーションのパフォーマンスメトリックに関するいくつかの統計を収集しました。 perfの例をもっと見るには、 BrandenGregのブログを読むことを強くお勧めします。さらに、Linuxカーネルバージョン4.4の時点で利用可能なeBPF は、多くのトレースおよびプロファイリングシナリオでも役立ちます。

いつものように、すべての例はGitHubでから入手できます。

getdocs

13036