89

Java の Just-In -Time コンパイラ(JIT) 最適化手法について説明しているドキュメントを調べていました。その一つが「ループ反転」でした。そしてドキュメントには次のように書かれています。

通常whileのループをループに置き換えdo-whileます。そして、 do-whileループはif句内に設定されます。この置換により、ジャンプが 2 回少なくなります。

ループ反転はどのように機能し、コード パスをどのように最適化するのでしょうか?

注: 誰かが Java コードの例と、JIT がそれをネイティブ コードに最適化する方法と、最新のプロセッサで最適である理由を説明できれば素晴らしいことです。

4

4 に答える 4

108 
while (condition) { 
  ... 
}

ワークフロー:

  1. 状態を確認してください。
  2. false の場合、ループの外側にジャンプします。
  3. 1回の反復を実行します。
  4. トップにジャンプします。
if (condition) do {
  ...
} while (condition);

ワークフロー:

  1. 状態を確認してください。
  2. false の場合、ループを超えてジャンプします。
  3. 1回の反復を実行します。
  4. 状態を確認してください。
  5. true の場合、ステップ 3 にジャンプします。

これら 2 つを比較すると、ループのステップが 1 つだけで、一般にジャンプの数が反復の数よりも 1 つ少ない場合、後者はまったくジャンプしない可能性があることが簡単にわかります。前者は条件をチェックするためにジャンプして戻る必要があり、条件が false の場合にのみループから飛び出します。

最新のパイプライン化された CPU アーキテクチャでのジャンプは、非常にコストがかかる可能性があります。CPU はジャンプ前にチェックの実行を終了しているため、そのジャンプ以降の命令は既にパイプラインの途中にあります。分岐予測が失敗した場合、この処理はすべて破棄する必要があります。パイプラインが再準備されている間、それ以上の実行は遅れます。

前述の分岐予測の説明: 条件付きジャンプの種類ごとに、CPU には2 つの命令があり、それぞれに結果への賭けが含まれます。たとえば、最後の反復を除くすべての反復でジャンプを行う必要があるため、「ゼロでない場合はジャンプ、ゼロでないことに賭ける」という命令をループの最後に配置します。こうすることで、CPU は、ジャンプ命令自体に続く命令ではなく、ジャンプ ターゲットに続く命令でパイプラインのポンピングを開始します。

重要な注意点

これを、ソース コード レベルで最適化する方法の例として取り上げないでください。あなたの質問からすでに明らかなように、最初の形式から2番目の形式への変換は、JITコンパイラがルーチンの問題として完全に独自に行うものであるため、それは完全に見当違いです。

于 2013-12-29T15:36:20.903 に答える
24

これにより、常に少なくとも 1 回は実行されるループを最適化できます。

通常のwhileループは常に、少なくとも 1 回は先頭に戻り、最後に 1 回は最後にジャンプします。1 回実行される単純なループの例: 

int i = 0;
while (i++ < 1) {
    //do something
}

do-while一方、ループは最初と最後のジャンプをスキップします。上記と同等のループで、ジャンプなしで実行されます。 

int i = 0;
if (i++ < 1) {
    do {
        //do something
    } while (i++ < 1); 
}
于 2013-12-29T15:31:34.017 に答える
3

ループ反転は、プロセッサがより少ない命令で同じ結果を達成できるため、パフォーマンスを向上させるパフォーマンス最適化手法です。これにより、境界条件でのパフォーマンスが大幅に向上します。

このリンクは、ループ反転の別の例を提供します。デクリメントと比較が単一の命令セットとして実装されているいくつかのアーキテクチャでは、 for ループをデクリメントと比較操作を使用して while に変換することは理にかなっています。

ウィキペディアには非常に良い例があり、ここでもう一度説明します。

 int i, a[100];
  i = 0;
  while (i < 100) {
    a[i] = 0;
    i++;
  }

コンパイラによってに変換されます

  int i, a[100];
  i = 0;
  if (i < 100) {
    do {
      a[i] = 0;
      i++;
    } while (i < 100);
  }

これはどのようにパフォーマンスに変換されますか? i の値が 99 の場合、プロセッサは GOTO を実行する必要はありません (最初のケースで必要です)。これにより、パフォーマンスが向上します。

于 2013-12-29T15:44:28.180 に答える
3

それらを見てみましょう：

whileバージョン:

void foo(int n) {
    while (n < 10) {
       use(n);
       ++n;
    }
    done();
}
  1. 最初に、条件が true でないかどうかをテストnしてジャンプします。done();
  2. 次に、 を使用してインクリメントしますn。
  3. ここで、条件に戻ります。
  4. すすぎ、繰り返します。
  5. 条件が真でなくなると、 にジャンプしdone()ます。

do-whileバージョン:

(覚えておいてください、私たちは実際にソースコードでこれを行っていません [それはメンテナンスの問題を引き起こします]、コンパイラ/JIT が私たちのためにそれを行います。)

void foo(int n) {
    if (n < 10) {
        do {
            use(n);
            ++n;
        }
        while (n < 10);
    }
    done();
}
  1. 最初に、条件が true でないかどうかをテストnしてジャンプします。done();
  2. 次に、 を使用してインクリメントしますn。
  3. ここで、条件をテストし、真であればジャンプして戻ります。
  4. すすぎ、繰り返します。
  5. 条件が真でなくなると、フロー (ジャンプではなく) に移動しdone()ます。

したがって、たとえば、 でn始まる場合、バージョン9ではまったくジャンプしませんが、バージョンでは、最初に戻ってテストを実行し、それが正しくないことがわかったときに最後にジャンプする必要があります。 .do-whilewhile

于 2013-12-29T15:38:28.237 に答える