Javaでの分岐予測

投稿日: 2022-11-05 2022-11-05
タグ: Algorithms, Java

1. 序章

分岐予測はコンピュータサイエンスの興味深い概念であり、アプリケーションのパフォーマンスに大きな影響を与える可能性があります。それでもそれは一般的によく理解されておらず、ほとんどの開発者はそれにほとんど注意を払っていません。

この記事では、それが何であるか、それがソフトウェアにどのように影響するか、そしてそれに対して何ができるかを正確に探求します。

2. 命令パイプラインとは何ですか？

コンピュータープログラムを作成するときは、コンピューターが順番に実行することを期待する一連のコマンドを作成します。

初期のコンピューターは、これらを一度に1つずつ実行していました。これは、各コマンドがメモリにロードされ、完全に実行され、コマンドが完了したときにのみ次のコマンドがロードされることを意味します。

命令パイプラインはこれを改善したものです。これにより、プロセッサは作業を分割して、さまざまな部分を並行して実行できます。これにより、プロセッサは次のコマンドをロードしながら1つのコマンドを実行できるようになり、準備が整います。

プロセッサ内のパイプラインが長くなると、各部分が単純化されるだけでなく、より多くの部分が並行して実行されるようになります。これにより、システムの全体的なパフォーマンスを向上させることができます。

たとえば、次のような簡単なプログラムを作成できます。

int a = 0;
a += 1;
a += 2;
a += 3;

これは、Fetch、Decode、Execute、Storeセグメントで構成されるパイプラインによって次のように処理される場合があります。

ここで、4つのコマンドの全体的な実行がどのように並行して実行され、シーケンス全体が高速化されるかを確認できます。

3. 危険は何ですか？

プロセッサが実行する必要のある特定のコマンドは、パイプラインの問題を引き起こします。これらは、パイプラインの一部の実行が以前の部分に依存しているが、それらの以前の部分がまだ実行されていない可能性があるコマンドです。

枝は特定の形態の危険です。これらにより、実行は2つの方向のいずれかに進み、分岐が解決されるまでどちらの方向に進むかを知ることはできません。これは、ブランチを超えてコマンドをロードしようとする試みは、コマンドをどこからロードするかを知る方法がないため、安全ではないことを意味します。

ブランチを導入するために、単純なプログラムを変更してみましょう。

int a = 0;
a += 1;
if (a < 10) {
  a += 2;
}
a += 3;

この結果は以前と同じですが、その途中にifステートメントを導入しました。 コンピュータはこれを認識し、解決されるまでこれを超えてコマンドをロードすることはできません。そのため、フローは次のようになります。

これがプログラムの実行に与える影響と、同じ結果を実行するために必要なクロックステップ数をすぐに確認できます。

4. 分岐予測とは何ですか？

分岐予測は上記の拡張機能であり、コンピューターは分岐がどちらの方向に進むかを予測し、それに応じて動作しようとします。

上記の例では、プロセッサは次のように予測する可能性があります if（a <10） 可能性が高い真実、したがって、命令のように動作します a + = 2 次に実行するのはでした。これにより、フローは次のようになります。

これにより、プログラムのパフォーマンスが向上したことがすぐにわかります – 11ではなく9ティックを使用しているため、19% fasterです。

ただし、これにはリスクが伴います。分岐予測が間違っていると、実行されるべきではない命令をキューに入れ始めます。これが発生した場合、コンピュータはそれらを破棄して最初からやり直す必要があります。

条件を変えて、falseになるようにしましょう。

int a = 0;
a += 1;
if (a > 10) {
  a += 2;
}
a += 3;

これは次のように実行される可能性があります。

これは、以前のフローよりも遅くなりましたが、実行回数は少なくなりました！プロセッサは、ブランチが true と評価されると誤って予測し、a+のキューイングを開始しました。 = 2 命令であり、ブランチがfalseと評価されたときにそれを破棄して最初からやり直す必要がありました。

5. コードへの実際の影響

分岐予測とは何か、そして利点は何かがわかったので、それはどのように私たちに影響を与えることができますか？結局のところ、高速コンピュータで数プロセッササイクルを失うことについて話しているので、確かにそれは目立たないでしょう。

そして時々それは本当です。ただし、アプリケーションのパフォーマンスに驚くべき違いが生じる場合があります。 それは私たちが何をしているかに大きく依存します。具体的には、それは私たちが短時間にどれだけやっているかに依存します。

5.1. リストエントリのカウント

リスト内のエントリを数えてみましょう。数値のリストを生成してから、特定のカットオフよりも小さい数値を数えます。これは上記の例と非常に似ていますが、単一の命令としてではなく、ループで実行しています。

List<Long> numbers = LongStream.range(0, top)
    .boxed()
    .collect(Collectors.toList());

if (shuffle) {
    Collections.shuffle(numbers);
}

long cutoff = top / 2;
long count = 0;

long start = System.currentTimeMillis();
for (Long number : numbers) {
    if (number < cutoff) {
        ++count;
    }
}
long end = System.currentTimeMillis();

LOG.info("Counted {}/{} {} numbers in {}ms",
    count, top, shuffle ? "shuffled" : "sorted", end - start);

これが私たちが興味を持っているものであるため、カウントを行うループのタイミングのみを取っていることに注意してください。では、これにはどのくらい時間がかかりますか？

十分に小さいリストを生成している場合、コードは非常に高速に実行されるため、タイミングをとることができません。サイズ100,000のリストでも、0msの時間が表示されます。ただし、リストが十分に大きくなり、時間を計ることができるようになると、リストをシャッフルしたかどうかに基づいて大きな違いが見られます。 10,000,000の数字のリストについては、次のようになります。

並べ替え– 44ms
シャッフル– 221ms

つまり、シャッフルされたリストは、実際にカウントされる数が同じであっても、ソートされたリストよりもカウントに5倍長くかかります。

ただし、リストを並べ替える操作は、単にカウントを実行するよりもはるかにコストがかかります。常にコードのプロファイルを作成し、パフォーマンスの向上が有益かどうかを判断する必要があります。

5.2. ブランチの順序

上記に続いて、 if/elseステートメントの分岐の順序が重要であることが合理的であるように思われます。つまり、ブランチを並べ替えた場合よりも、次のパフォーマンスが向上することが期待できます。

if (mostLikely) {
  // Do something
} else if (lessLikely) {
  // Do something
} else if (leastLikely) {
  // Do something
}

ただし、最新のコンピューターは、分岐予測キャッシュを使用することでこの問題を回避できます。実際、これもテストできます。

List<Long> numbers = LongStream.range(0, top)
  .boxed()
  .collect(Collectors.toList());
if (shuffle) {
    Collections.shuffle(numbers);
}

long cutoff = (long)(top * cutoffPercentage);
long low = 0;
long high = 0;

long start = System.currentTimeMillis();
for (Long number : numbers) {
    if (number < cutoff) {
        ++low;
    } else {
        ++high;
    }
}
long end = System.currentTimeMillis();

LOG.info("Counted {}/{} numbers in {}ms", low, high, end - start);

このコードは、 cutoffPercentage の値に関係なく、10,000,000の数値をカウントするときに、ほぼ同時に実行されます（ソートされた数値の場合は約35ミリ秒、シャッフルされた数値の場合は約200ミリ秒）。

これは、分岐予測子が両方の分岐を同等に処理し、どちらの方向に進むかを正しく推測しているためです。

5.3. 組み合わせ条件

1つまたは2つの条件から選択できる場合はどうなりますか？同じ動作をする別の方法でロジックを書き直すことは可能かもしれませんが、これを行う必要がありますか？

例として、2つの数値を0と比較する場合、別のアプローチは、それらを乗算して結果を0と比較することです。これにより、条件が乗算に置き換えられます。しかし、これは価値がありますか？

例を考えてみましょう：

long[] first = LongStream.range(0, TOP)
  .map(n -> Math.random() < FRACTION ? 0 : n)
  .toArray();
long[] second = LongStream.range(0, TOP)
  .map(n -> Math.random() < FRACTION ? 0 : n)
  .toArray();

long count = 0;
long start = System.currentTimeMillis();
for (int i = 0; i < TOP; i++) {
    if (first[i] != 0 && second[i] != 0) {
        ++count;
    }
}
long end = System.currentTimeMillis();

LOG.info("Counted {}/{} numbers using separate mode in {}ms", count, TOP, end - start);

上記のように、ループ内の状態を置き換えることができます。これを行うと、実際にはランタイムに影響します。

別の条件– 40ms
複数および単一の条件– 22ms

したがって、2つの異なる条件を使用するオプションは、実際には実行に2倍の時間がかかります。

6. 結論

分岐予測とは何か、そしてそれがプログラムにどのように影響するかを見てきました。これにより、プログラムを可能な限り効率的にするためのツールが追加されます。

ただし、いつものように、大きな変更を加える前にコードのプロファイルを作成することを忘れないでください。分岐予測を支援するために変更を加えると、他の方法でより多くのコストがかかる場合があります。

この記事の事例の例は、GitHubでから入手できます。

getdocs

13036