java - Javaforループのパフォーマンスに関する質問

Question

この例を考えると：

public static void main(final String[] args) {
    final List<String> myList = Arrays.asList("A", "B", "C", "D");
    final long start = System.currentTimeMillis();
    for (int i = 1000000; i > myList.size(); i--) {
        System.out.println("Hello");
    }
    final long stop = System.currentTimeMillis();
    System.out.println("Finish: " + (stop - start));
}

vs

public static void main(final String[] args) {
    final List<String> myList = Arrays.asList("A", "B", "C", "D");
    final long start = System.currentTimeMillis();
    final int size = myList.size();
    for (int i = 1000000; i > size; i--) {
        System.out.println("Hello");
    }
    final long stop = System.currentTimeMillis();
    System.out.println("Finish: " + (stop - start));
}

これは何か違いがありますか？私のマシンでは、2番目のマシンの方がパフォーマンスが速いようですが、本当に正確かどうかはわかりません。コンパイラはこのコードを最適化しますか？ループ条件が不変オブジェクト（文字列配列など）の場合、彼はそうするだろうと思います。

score 25 · Accepted Answer

このようなものをテストしたい場合は、マイクロベンチマークを最適化して、気になるものを測定する必要があります。

まず、ループを安価にしますが、スキップすることはできません。合計を計算すると、通常はうまくいきます。

次に、2つのタイミングを比較します。

両方を行うコードを次に示します。

import java.util.*;

public class Test {

public static long run1() {
  final List<String> myList = Arrays.asList("A", "B", "C", "D");
  final long start = System.nanoTime();
  int sum = 0;
  for (int i = 1000000000; i > myList.size(); i--) sum += i;
  final long stop = System.nanoTime();
  System.out.println("Finish: " + (stop - start)*1e-9 + " ns/op; sum = " + sum);
  return stop-start;
}

public static long run2() {
  final List<String> myList = Arrays.asList("A", "B", "C", "D");
  final long start = System.nanoTime();
  int sum = 0;
  int limit = myList.size();
  for (int i = 1000000000; i > limit; i--) sum += i;
  final long stop = System.nanoTime();
  System.out.println("Finish: " + (stop - start)*1e-9 + " ns/op; sum = " + sum);
  return stop-start;
}

public static void main(String[] args) {
  for (int i=0 ; i<5 ; i++) {
    long t1 = run1();
    long t2 = run2();
    System.out.println("  Speedup = " + (t1-t2)*1e-9 + " ns/op\n");
  }
}

}

そして、それを実行すると、私のシステムでは次のようになります。

Finish: 0.481741256 ns/op; sum = -243309322
Finish: 0.40228402 ns/op; sum = -243309322
  Speedup = 0.079457236 ns/op

Finish: 0.450627151 ns/op; sum = -243309322
Finish: 0.43534661700000005 ns/op; sum = -243309322
  Speedup = 0.015280534 ns/op

Finish: 0.47738474700000005 ns/op; sum = -243309322
Finish: 0.403698331 ns/op; sum = -243309322
  Speedup = 0.073686416 ns/op

Finish: 0.47729349600000004 ns/op; sum = -243309322
Finish: 0.405540508 ns/op; sum = -243309322
  Speedup = 0.071752988 ns/op

Finish: 0.478979617 ns/op; sum = -243309322
Finish: 0.36067492700000003 ns/op; sum = -243309322
  Speedup = 0.11830469 ns/op

これは、メソッド呼び出しのオーバーヘッドが約0.1nsであることを意味します。ループが1〜2 nsしかかからないことを行う場合は、これに注意する必要があります。そうでなければ、しないでください。

score 10 · Accepted Answer

個人的には、このような不自然な例から意味のある結論を引き出すことはできないと思います。

しかし、本当に知りたいのであれば、javapを使用してコードを逆コンパイルし、何が違うのかを見てみませんか？ここで質問せずに自分で確認できるのに、なぜコンパイラが何をしているのかを推測するのですか？

最初のケースのバイトコード：

public class Stackoverflow extends java.lang.Object{
public Stackoverflow();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

public static void main(java.lang.String[]);
  Code:
   0:   iconst_4
   1:   anewarray       #2; //class java/lang/String
   4:   dup
   5:   iconst_0
   6:   ldc     #3; //String A
   8:   aastore
   9:   dup
   10:  iconst_1
   11:  ldc     #4; //String B
   13:  aastore
   14:  dup
   15:  iconst_2
   16:  ldc     #5; //String C
   18:  aastore
   19:  dup
   20:  iconst_3
   21:  ldc     #6; //String D
   23:  aastore
   24:  invokestatic    #7; //Method java/util/Arrays.asList:([Ljava/lang/Object;)Ljava/util/List
   27:  astore_1
   28:  invokestatic    #8; //Method java/lang/System.currentTimeMillis:()J
   31:  lstore_2
   32:  ldc     #9; //int 1000000
   34:  istore  4
   36:  iload   4
   38:  aload_1
   39:  invokeinterface #10,  1; //InterfaceMethod java/util/List.size:()I
   44:  if_icmple       61
   47:  getstatic       #11; //Field java/lang/System.out:Ljava/io/PrintStream;
   50:  ldc     #12; //String Hello
   52:  invokevirtual   #13; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   55:  iinc    4, -1
   58:  goto    36
   61:  invokestatic    #8; //Method java/lang/System.currentTimeMillis:()J
   64:  lstore  4
   66:  getstatic       #11; //Field java/lang/System.out:Ljava/io/PrintStream;
   69:  new     #14; //class java/lang/StringBuilder
   72:  dup
   73:  invokespecial   #15; //Method java/lang/StringBuilder."<init>":()V
   76:  ldc     #16; //String Finish:
   78:  invokevirtual   #17; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/la
   81:  lload   4
   83:  lload_2
   84:  lsub
   85:  invokevirtual   #18; //Method java/lang/StringBuilder.append:(J)Ljava/lang/StringBuilder;
   88:  invokevirtual   #19; //Method java/lang/StringBuilder.toString:()Ljava/lang/String;
   91:  invokevirtual   #13; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   94:  return
}

2番目の場合のバイトコード：

public class Stackoverflow extends java.lang.Object{
public Stackoverflow();
  Code:
   0:   aload_0
   1:   invokespecial   #1; //Method java/lang/Object."<init>":()V
   4:   return

public static void main(java.lang.String[]);
  Code:
   0:   iconst_4
   1:   anewarray       #2; //class java/lang/String
   4:   dup
   5:   iconst_0
   6:   ldc     #3; //String A
   8:   aastore
   9:   dup
   10:  iconst_1
   11:  ldc     #4; //String B
   13:  aastore
   14:  dup
   15:  iconst_2
   16:  ldc     #5; //String C
   18:  aastore
   19:  dup
   20:  iconst_3
   21:  ldc     #6; //String D
   23:  aastore
   24:  invokestatic    #7; //Method java/util/Arrays.asList:([Ljava/lang/Object;)Ljava/util/List;
   27:  astore_1
   28:  invokestatic    #8; //Method java/lang/System.currentTimeMillis:()J
   31:  lstore_2
   32:  aload_1
   33:  invokeinterface #9,  1; //InterfaceMethod java/util/List.size:()I
   38:  istore  4
   40:  ldc     #10; //int 1000000
   42:  istore  5
   44:  iload   5
   46:  iload   4
   48:  if_icmple       65
   51:  getstatic       #11; //Field java/lang/System.out:Ljava/io/PrintStream;
   54:  ldc     #12; //String Hello
   56:  invokevirtual   #13; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   59:  iinc    5, -1
   62:  goto    44
   65:  invokestatic    #8; //Method java/lang/System.currentTimeMillis:()J
   68:  lstore  5
   70:  getstatic       #11; //Field java/lang/System.out:Ljava/io/PrintStream;
   73:  new     #14; //class java/lang/StringBuilder
   76:  dup
   77:  invokespecial   #15; //Method java/lang/StringBuilder."<init>":()V
   80:  ldc     #16; //String Finish:
   82:  invokevirtual   #17; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
   85:  lload   5
   87:  lload_2
   88:  lsub
   89:  invokevirtual   #18; //Method java/lang/StringBuilder.append:(J)Ljava/lang/StringBuilder;
   92:  invokevirtual   #19; //Method java/lang/StringBuilder.toString:()Ljava/lang/String;
   95:  invokevirtual   #13; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   98:  return
}

違いはありますが、パフォーマンスへの影響について明確に述べることができるかどうかはわかりません。

2番目のコードは、ループの反復ごとに1つではなく、（表面的には）1つのメソッド呼び出しを意味するためです。コンパイラーがそれを最適化できるかどうかはわかりませんが、かなり簡単にできると確信しています。ですから、壁時間への影響に関係なく、そうします。

score 10 · Accepted Answer

私はかつて、私の最初のタスクがいくつかのめちゃくちゃ遅いコードを追跡することであったプロジェクトに取り組んだことがあります（それは真新しい486マシン上にあり、実行するのに約20分かかりました）：

for(size_t i = 0; i < strlen(data); i++)
{
    // do something with data[i]
}

解決策は次のとおりです（2分以内にそれを取得しました）：

size_t length = strlen(data);

for(int i = 0; i < length; i++)
{
    // do something with data[i]
}

問題は、「データ」が100万文字を超えていて、strlenが常にそれぞれをカウントする必要があることです。

Javaの場合、「size（）」メソッドはおそらく変数を返すため、VMはそれをインライン化します。AndroidのようなVMでは、おそらくそうではありません。したがって、答えは「状況によって異なります」です。

私の個人的な好みは、メソッドが毎回同じ結果を返すことになっている場合は、メソッドを2回以上呼び出さないことです。そうすれば、メソッドに計算が含まれる場合、それは1回だけ実行され、問題になることはありません。

score 5 · Accepted Answer

javacコンパイラは最適化とはほとんど関係がないことに注意してください。「重要な」コンパイラは、JVM内に存在するJITコンパイラです。

あなたの例では、最も一般的なケースでは、は単純なメソッドディスパッチであり、インスタンスmyList.size()内のフィールドの内容を返します。Listこれは、暗示される作業と比較してごくわずかな作業ですSystem.out.println("Hello")（少なくとも1つのシステムコール、したがって数百のクロックサイクル、メソッドディスパッチの場合は12以下）。あなたのコードが意味のある速度の違いを示す可能性があることを私は非常に疑っています。

より一般的には、JITコンパイラは、この呼び出しをsize()既知のインスタンスへの呼び出しとして認識し、直接関数呼び出し（より高速）でメソッドディスパッチを実行したり、メソッド呼び出しをインライン化して、size()メソッド呼び出しを削減したりする必要があります。単純なインスタンスのフィールドアクセスを呼び出します。

score 2 · Accepted Answer

mylist.size（）はループの実行中に変更される可能性があるため、最適化できません。これはfinalであっても、参照がfinalであることを意味します（myListを他のオブジェクトに再割り当てできないことを意味します）が、remove（）やadd（）などのmyListのメソッドは引き続き使用できます。Finalはオブジェクトを不変にしません。

score 1 · Accepted Answer

.size()ループが実行されるたびにを呼び出す必要がないため、2番目の方が高速である必要があります。何度も言うよりも、1 + 2=3と言う方がはるかに速いです。

score 1 · Accepted Answer

変数の単一の最終的なローカルコピーを格納するため、2番目の実装の方が高速であることは理にかなっています。コンパイラは、パフォーマンスをほぼ同等にするために、ループ内でサイズを変更できないことを理解する必要があります。

1つの質問は、この種のマイクロ最適化は本当に重要なのかということです。含まれている場合は、テストでより高速に実行されているものを使用し、コンパイラーの最適化に依存しません。

score 1 · Accepted Answer

Javaコンパイラはそれを最適化したはずですが、おかしな状態を見てそうしませんでした。このように書いていれば問題ありません。

for (int i = myList.size(); i < 1000000; i--) {
    System.out.println("Hello");
}

score 1 · Accepted Answer

ほぼ確実に、ここで表示されているのは、HotSpotのインライン化の違いです。より単純なループを使用すると、インライン化する可能性が高くなるため、余分なゴミをすべて取り除くことができます。同じインライン化を行う場合がありますが、早い段階で、または少ない労力で行います。通常、Javaマイクロベンチマークでは、コードを複数回実行する必要があります。このコードから、起動時間、平均時間、および偏差を計算できます。

score 0 · Accepted Answer

「コンパイラの最適化」の場合、実行できる最善の方法はfor-eachループです。

for(final String x : myList) { ... }

これにより、コンパイラは最速の実装を提供できます。

編集：

コード例の違いは、forループの2番目の引数にあります。最初の例では、VMはメソッド呼び出し（より高価）を実行するため、速度が低下します（反復が多い場合にのみ重要です）。2番目の例では、VMはスタックポップを実行し（より安価で、ローカル変数はスタック上にあります）、したがってより高速になります（反復が多い場合にのみ重要です。1回の反復で、最初の反復がより高速になります。メモリ使用量の観点から）。

また、「時期尚早の最適化はすべての悪の根源です。」ドナルド・クヌースの悪名高い法律。

score 0 · Accepted Answer

違いは、反復ごとに1つのメソッド呼び出しが少ないため、2番目のバージョンはわずかに高速に実行されるはずです。ジャストインタイムコンパイラを使用している場合でも、彼はそれを最適化する可能性があります-ループ中に変更されないことを理解します。標準のJava実装はJITを備えていますが、すべてのJava実装が備えているわけではありません。

score 0 · Accepted Answer

いつものように、両方を実行して、使用している実装を考えるとどちらが速いかを確認する必要があります。ただし、最初のものには、反復ごとにsize（）を呼び出さなければならないという潜在的なパフォーマンスの低下があり、関数呼び出しは、単に変数を直接チェックするよりもコストがかかります。ただし、コードやコンパイラの動作によっては、その関数呼び出しが最適化される可能性があるため、テストを実行して確認する必要があります。

ただし、Pindatjuhが指摘したように、このようにコレクション全体を反復処理する場合は、foreachループを使用することをお勧めします。これにより、コンパイラーは物事をより適切に最適化し、エラーが発生しにくくなります。

score 0 · Accepted Answer

最後の例では、配列の現在のサイズを解決する必要がないため、最初の例よりもわずかに高速になります。

これは、配列内の値の数を変更しない場合にのみ役立つことを覚えておいてください。

Androidでは、最新の例であるDesigningforPerformanceを使用することをお勧めします。 http://developer.android.com/guide/practices/design/performance.html#foreach

java - Javaforループのパフォーマンスに関する質問

13 に答える 13

Related

Reference