java - これらのコードのうち、Javaで高速なものはどれですか？

Question

a） for(int i = 100000; i > 0; i--) {}

b） for(int i = 1; i < 100001; i++) {}

答えはこのウェブサイトにあります（質問3）。理由がわからないのですか？ウェブサイトから：

3. a

score 69 · Accepted Answer

最下位レベル (マシンコードですが、ほとんどが 1 対 1 でマップされるため、アセンブリを使用します) に到達すると、0 に減少する空のループと 50 に増加するループ (たとえば) の違いは、しばしば次のようになります。次の行:

      ld  a,50                ld  a,0
loop: dec a             loop: inc a
      jnz loop                cmp a,50
                              jnz loop

これは、ほとんどの正常な CPU のゼロフラグは、ゼロに到達したときにデクリメント命令によって設定されるためです。インクリメント命令が 50 に達すると、通常は同じことは言えません (ゼロとは異なり、その値について特別なことは何もないため)。したがって、ゼロフラグを設定するには、レジスタを 50 と比較する必要があります。

ただし、2 つのループのどちらかを尋ねると、次のようになります。

for(int i = 100000; i > 0; i--) {}
for(int i = 1; i < 100001; i++) {}

どちらも何も役に立たないため、（Javaまたはその他のほとんどすべての環境で）より高速です。これら両方のループの最速バージョンでは、ループはまったくありません。それよりも速いバージョンを考え出すように誰にでも挑戦します:-)

これらは、ブレース内で何らかの有用な作業を開始した場合にのみ役立ちます。その時点で、使用する順序が作業によって決まります。

たとえば、1 から 100,000 までカウントする必要がある場合は、2 番目のループを使用する必要があります。100000-iこれは、カウントダウンを使用する必要があるたびにループ内で評価する必要があるという事実によって、カウントダウンの利点が (あるとしても) 失われる可能性が高いためです。アセンブリ用語では、次の違いがあります。

     ld  b,100000             dsw a
     sub b,a
     dsw b

(dswもちろん、悪名高いdo something withアセンブラのニーモニックです)。

反復ごとに 1 回だけインクリメントループのヒットを取得し、反復ごとに少なくとも1 回は減算のヒットを取得するため (を使用すると仮定します。iそれ以外の場合は、ループの必要性はほとんどありません。）、より自然なバージョンを使用する必要があります。

カウントアップする必要がある場合は、カウントアップします。カウントダウンする必要がある場合は、カウントダウンします。

score 23 · Accepted Answer

多くのコンパイラでは、ループの逆方向に出力されるマシン命令の方が効率的です。これは、ゼロのテスト（したがってレジスタのゼロ化）が定数値の即時ロードよりも高速であるためです。

一方、優れた最適化コンパイラは、ループの内部を検査し、逆方向に進んでも副作用が発生しないことを確認できる必要があります...

ところで、それは私の意見ではひどいインタビューの質問です。1000万回実行されるループについて話していて、順方向ループ値（n-i）を再作成する多くのインスタンスがわずかなゲインを上回っていないことを確認していない限り、パフォーマンスの向上は最小限に抑えられます。

いつものように、パフォーマンスベンチマークなしで、コードを理解するのが難しくなるという犠牲を払って、マイクロ最適化しないでください。

score 17 · Accepted Answer

この種の質問は、主に無関係な気晴らしであり、一部の人々はそれに取りつかれています. それをマイクロ最適化のカルトなどと呼びますが、ループアップとループダウンのどちらが速いですか? 真剣に？あなたがしていることに適したものを使用してください。2 クロックサイクルを節約するなどの目的でコードを書くことはありません。

コンパイラにその目的を実行させ、(コンパイラと読者の両方に対して)意図を明確にします。もう 1 つの一般的な Java ペシミゼーションは次のとおりです。

public final static String BLAH = new StringBuilder().append("This is ").append(3).append(' text").toString();

過度の連結はメモリの断片化を引き起こしますが、定数の場合、コンパイラはこれを最適化できます (そしてそうします)。

public final static String BLAH = "This is a " + 3 + " test";

最初は最適化されず、2番目は読みやすくなります。

(a>b)?a:bvsはどうMath.max(a,b)ですか？私はむしろ 2 番目を読みたいと思っているので、1 番目が関数呼び出しのオーバーヘッドを被らないかどうかはあまり気にしません。

このリストには、finallyブロックが呼び出されていないことを知ることSystem.exit()が潜在的に役立つなど、いくつかの便利なことがあります。float を 0.0 で除算しても例外がスローされないことを知っておくと便利です。

しかし、それが本当に重要でない限り、わざわざコンパイラーを推測する必要はありません(99.99% の確率でそうではないことは間違いありません)。

score 13 · Accepted Answer

より良い質問は;

どちらが理解しやすく、操作しやすいですか？

これは、パフォーマンスの概念的な違いよりもはるかに重要です。個人的には、パフォーマンスがここでの違いを決定するための基準であってはならないことを指摘しておきます。彼らが私がこれについて彼らの仮定に挑戦することを好まなかったならば、私は仕事を得ないことについて不幸ではないでしょう。;）

score 10 · Accepted Answer

最新のJava実装では、これは当てはまりません。ベンチマークとして最大10億の数値を合計します。

Java（TM）SEランタイム環境1.6.0_05-b13
Java HotSpot（TM）サーバーVM 10.0-b19
最大1000000000：1817ms 1.817ns /反復（合計499999999500000000）
最大1000000000：1786ms 1.786ns /反復（合計499999999500000000）
最大1000000000：1778ms 1.778ns /反復（合計499999999500000000）
最大1000000000：1769ms 1.769ns /反復（合計499999999500000000）
最大1000000000：1769ms 1.769ns /反復（合計499999999500000000）
最大1000000000：1766ms 1.766ns /反復（合計499999999500000000）
最大1000000000：1776ms 1.776ns /反復（合計499999999500000000）
最大1000000000：1768ms 1.768ns /反復（合計499999999500000000）
最大1000000000：1771ms 1.771ns /反復（合計499999999500000000）
最大1000000000：1768ms 1.768ns /反復（合計499999999500000000）
ダウン1000000000：1847ms 1.847ns /反復（合計499999999500000000）
ダウン1000000000：1842ms 1.842ns /反復（合計499999999500000000）
ダウン1000000000：1838ms 1.838ns /反復（合計499999999500000000）
ダウン1000000000：1832ms 1.832ns /反復（合計499999999500000000）
ダウン1000000000：1842ms 1.842ns /反復（合計499999999500000000）
ダウン1000000000：1838ms 1.838ns /反復（合計499999999500000000）
ダウン1000000000：1838ms 1.838ns /反復（合計499999999500000000）
ダウン1000000000：1847ms 1.847ns /反復（合計499999999500000000）
ダウン1000000000：1839ms 1.839ns /反復（合計499999999500000000）
ダウン1000000000：1838ms 1.838ns /反復（合計499999999500000000）

時間差は脆弱であり、ループの近くのどこかで小さな変化がそれらを好転させる可能性があることに注意してください。

編集： ベンチマークループは

        long sum = 0;
        for (int i = 0; i < limit; i++)
        {
            sum += i;
        }

と

        long sum = 0;
        for (int i = limit - 1; i >= 0; i--)
        {
            sum += i;
        }

int型の合計を使用すると、約3倍高速になりますが、合計がオーバーフローします。BigIntegerを使用すると、50倍以上遅くなります。

BigInteger up 1000000000: 105943ms 105.943ns/iteration (sum 499999999500000000)

score 6 · Accepted Answer

通常、実際のコードは上向きにカウントして高速に実行されます。これにはいくつかの理由があります。

プロセッサは、メモリ転送を読み取るように最適化されています。
HotSpot (およびおそらく他のバイトコード -> ネイティブコンパイラ) は順方向ループを大幅に最適化しますが、逆方向ループはめったに発生しないため気にしません。
上向きは通常より明白であり、よりクリーンなコードは多くの場合より高速です。

したがって、正しいことを喜んで行うと、通常はより速くなります。不必要なマイクロ最適化は悪です。6502 アセンブラをプログラミングして以来、意図的に後方ループを記述していません。

score 6 · Accepted Answer

この質問に答えるには、実際には 2 つの方法しかありません。

それは本当に、本当に問題ではないことをあなたに伝えるために、あなたは不思議に思っても時間を無駄にしています.
知る唯一の方法は、関心のある実際の本番ハードウェア、OS、および JRE インストールで信頼できるベンチマークを実行することです。

そこで、ここでそれを試すために使用できる実行可能なベンチマークを作成しました。

http://code.google.com/p/caliper/source/browse/trunk/test/examples/LoopingBackwardsBenchmark.java

この Caliper フレームワークはまだ本格的な準備ができていないため、これをどうするかは完全には明らかではないかもしれませんが、十分に気にかけているなら、それを理解することができます。私のLinuxボックスでの結果は次のとおりです。

     max benchmark        ns
       2  Forwards         4
       2 Backwards         3
      20  Forwards         9
      20 Backwards        20
    2000  Forwards      1007
    2000 Backwards      1011
20000000  Forwards   9757363
20000000 Backwards  10303707

逆方向にループすることは、誰にとっても勝利のように見えますか?

score 3 · Accepted Answer

そのような質問をするインタビュアーは、正解（「1番が速い」または「2番が速い」）を期待していると思いますか、またはこの質問がディスカッションを誘発するように求められた場合、人々が答えているようにここにあげる？

一般に、Javaコンパイラ、JRE、CPU、およびその他の要因に大きく依存するため、どちらが高速であるかを判断することはできません。最下位レベルの詳細を理解せずに2つのうちの一方が高速であると考えるという理由だけで、プログラムでどちらか一方を使用することは迷信的なプログラミングです。また、特定の環境で1つのバージョンが他のバージョンよりも高速である場合でも、違いが非常に小さいため、関係がない可能性があります。

賢くしようとするのではなく、明確なコードを書いてください。

score 3 · Accepted Answer

このような質問は、古いベストプラクティスの推奨事項に基づいています。比較がすべてです。0 と比較すると、より高速であることが知られています。何年も前には、これは非常に重要であると見なされていたかもしれません。最近では、特に Java に関しては、コンパイラーと VM に仕事を任せて、保守と理解が容易なコードを書くことに集中したいと考えています。

それ以外の理由がある場合を除きます。Java アプリは常に HotSpot や高速ハードウェアで実行できるとは限らないことに注意してください。

score 2 · Accepted Answer

JVM でのゼロのテストに関しては、明らかにifeqを使用して実行できますが、それ以外のテストにはif_icmpeqが必要です。これには、スタックに追加の値を入れることも含まれます。

> 0質問のように、のテストは ifgt で行うことができますが、のテストにはif_icmplt< 100001が必要です。

score 2 · Accepted Answer

これは私が今まで見た中で最もばかげた質問です。ループ本体が空です。コンパイラが優れていれば、コードはまったく出力されません。何もせず、例外をスローすることも、スコープ外のものを変更することもできません。

コンパイラがそれほどスマートではない、または実際に空のループ本体がなかったと仮定すると、「後方ループカウンター」引数は、一部のアセンブリ言語では意味があります (Java バイトコードでも意味があるかもしれませんが、私にはわかりません)。具体的にはわかりません）。ただし、多くの場合、コンパイラはループを変換してデクリメントカウンターを使用することができます。i の値が明示的に使用されているループ本体がない限り、コンパイラはこの変換を実行できます。繰り返しになりますが、多くの場合、違いは見られません。

score 2 · Accepted Answer

私は糸を噛んでネクロバックすることにしました。

両方のループは、JVM によって no-ops として無視されます。したがって、基本的にループの 1 つでさえ 10 まで、もう 1 つは 10000000 までであり、違いはありませんでした。

ゼロにループバックすることは別のことです (jne 命令の場合、繰り返しますが、そのようにコンパイルされていません)。リンクされたサイトは明らかに奇妙です (そして間違っています)。

このタイプの質問は、どの JVM にも適合しません (また、最適化できる他のコンパイラにも適合しません)。

score 1 · Accepted Answer

ループは、1 つの重要な部分を除いて同一です。

私 > 0; および i < 100001;

ゼロより大きいチェックは、コンピューターの NZP (一般に条件コードまたは負のゼロまたは正のビットとして知られている) ビットをチェックすることによって行われます。

NZP ビットは、ロード、AND、加算などの演算が行われるたびにセットされます。実行されます。

大なりチェックでは、このビットを直接利用することはできません (したがって、もう少し時間がかかります...) 一般的な解決策は、値の 1 つを負にして (ビットごとの NOT を実行してから 1 を加算することによって)、それを比較値に加算することです。 . 結果がゼロの場合、それらは等しいです。正の場合、2 番目の値 (負ではない) が大きくなります。負の場合、最初の値 (neg) の方が大きくなります。このチェックは、直接の nzp チェックよりも少し時間がかかります。

これがその背後にある理由であると100％確信しているわけではありませんが、考えられる理由のようです...

score 0 · Accepted Answer

答えは (おそらくウェブサイトで見つけたように) です。

i > 0その理由は、ループを終了する条件の方がテストが高速だからだと思います。

score 0 · Accepted Answer

要するに、パフォーマンスが重要でないアプリケーションの場合、違いはおそらく関係ないということです。他の人が指摘しているように、i++ の代わりに ++i を使用すると高速になる場合がありますが、特に for ループでは、最新のコンパイラはその区別を最適化する必要があります。

とはいえ、違いはおそらく、比較のために生成される基本的な命令に関係しています。値が 0 に等しいかどうかのテストは、単なる~~NAND~~ NOR ゲートです。一方、値が任意の定数と等しいかどうかをテストするには、その定数をレジスタにロードしてから、2 つのレジスタを比較する必要があります。(これには、おそらく追加のゲート遅延が 1 つか 2 つ必要になるでしょう。) とはいえ、パイプライン処理と最新の ALU を使用すると、最初から違いが大きかったとしたら驚くでしょう。

score 0 · Accepted Answer

念のためEclipse以外は何も実行せずに、約15分間テストを行ってきましたが、実際の違いがわかりました。試してみてください。

Javaが「何もしない」のにかかる時間を計ってみたところ、アイデアを得るのに約500ナノ秒かかりました。

for次に、増加するステートメントを実行するのにかかる時間をテストしました。

for(i=0;i<100;i++){}

それから5分後、私は「後方」のものを試しました：

for(i=100;i>0;i--)

そして、最初のステートメントと 2 番目のステートメントの間には 16% という大きな違い (わずかなレベルで) がありfor、後者は 16% 高速です。

for2000 年のテストで「増加」ステートメントを実行する平均時間: 1838 n/s

2000 年のテストで「減少」forステートメントを実行する平均時間: 1555 n/s

このようなテストに使用されるコード:

public static void main(String[] args) {
    long time = 0;  
    for(int j=0; j<100; j++){
    long startTime = System.nanoTime();
    int i;
        /*for(i=0;i<100;i++){

        }*/
        for(i=100;i>0;i--){

        }
    long endTime = System.nanoTime();
    time += ((endTime-startTime));
    }
    time = time/100;
    System.out.print("Time: "+time);
}

結論: 違いは基本的にはありません。ステートメントテストに関連して「何もしない」ためには、すでにかなりの量の「何もしない」必要がありfor、それらの違いはごくわずかです。java.utilなどのライブラリをインポートするのにかかる時間だけです。 .Scannerは、ステートメントを実行するよりも読み込みに時間がかかりforます。アプリケーションのパフォーマンスが大幅に向上するわけではありませんが、知っておくと便利です。

java - これらのコードのうち、Javaで高速なものはどれですか？

16 に答える 16

Related

Reference