Java для вопроса производительности цикла

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));
}

против

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));
}

Будет ли это чем-то отличаться? На моей машине второй, кажется, работает быстрее, но я не знаю, насколько он точен. Будет ли компилятор оптимизировать этот код? Я мог бы подумать, что он будет, если условие цикла является неизменным объектом (например, массив строк).

Answer 1

Если вы хотите протестировать что-то подобное, вы действительно должны оптимизировать микробенчмарк, чтобы измерить то, что вас волнует.

Во-первых, сделайте цикл недорогим , но пропустить невозможно. Вычисление суммы обычно делает свое дело.

Во-вторых, сравните два времени.

Вот код, который делает оба:

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,1 нс. Если ваш цикл выполняет действия, которые занимают не более 1-2 нс, вам следует позаботиться об этом. Иначе не надо.

Answer 2

Лично я не думаю, что вы можете сделать какие-либо значимые выводы из надуманного примера, подобного этому.

Но если вы действительно хотите знать, почему бы не использовать 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
}

Байт-код для второго случая:

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
}

Есть различия, но я не уверен, что могу сделать однозначное заявление об их влиянии на производительность.

Я бы написал второй, потому что это будет означать (на первый взгляд) один вызов метода, а не один на итерацию цикла. Я не знаю, сможет ли компилятор оптимизировать его, но я уверен, что смогу сделать это довольно легко. Так и есть, независимо от его влияния на время стены.

Answer 3

Однажды я работал над проектом, где моей первой задачей было отыскать какой-то безумно медленный код (это было на совершенно новой машине 486 и выполнение заняло около 20 минут):

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

Решение было (до двух минут или меньше):

size_t length = strlen(data);

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

Проблема в том, что «data» было более 1 миллиона символов, и strlen должен считать каждый из них все время.

В случае Java метод «size ()», вероятно, возвращает переменную, и, как таковая, виртуальная машина встроит ее. На ВМ, как на Android, это, вероятно, нет. Таким образом, ответ «это зависит».

Мое личное предпочтение - никогда не вызывать метод более одного раза, если предполагается, что он каждый раз возвращает один и тот же результат. Таким образом, если метод требует вычисления, он выполняется только один раз, и это никогда не является проблемой.

Answer 4

Обратите внимание, что компилятор javac не имеет ничего общего с оптимизацией. «Важным» компилятором является JIT-компилятор, который находится внутри JVM.

В вашем примере, в наиболее общем случае, myList.size() - это простая отправка метода, которая возвращает содержимое поля в экземпляре List. Это незначительная работа по сравнению с тем, что подразумевается под System.out.println("Hello") (по крайней мере, один системный вызов, следовательно, сотни тактов, по сравнению с не более чем дюжиной для отправки метода). Я очень сомневаюсь, что ваш код может показать значительную разницу в скорости.

В более общем смысле, JIT-компилятор должен распознавать этот вызов size() как вызов известного экземпляра, чтобы он мог выполнять диспетчеризацию метода с помощью прямого вызова функции (что быстрее) или даже встроенного вызов метода size(), сводящий вызов к простому доступу к полю экземпляра.

Answer 5

Он не может оптимизировать его, потому что mylist.size () может измениться во время выполнения цикла. Даже если он окончательный, это просто означает, что ссылка является окончательной (то есть вы не можете переназначить myList другому объекту), но методы в myList, такие как remove () и add (), все еще доступны. Final не делает объект неизменным.

Answer 6

Почти наверняка вы видите здесь разницу во встраивании HotSpot. С более простой петлей это более вероятно встроено, и поэтому избавляется от всего лишнего мусора. Он может делать то же самое, но делать это раньше или с меньшими усилиями. Как правило, с микробенчами Java вы должны запускать код несколько раз, из которого вы можете определить время запуска, среднее время и отклонения.

Answer 7

Java-компилятор оптимизировал бы его так, но не сделал бы этого, увидев забавное условие. Если бы вы написали это так, проблем не было.

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

Answer 8

Имеет смысл, что вторая реализация быстрее, потому что вы храните одну, окончательную, локальную копию переменной. Компилятор должен выяснить, что размер не может измениться внутри цикла, чтобы производительность была примерно эквивалентной.

Один вопрос - действительно ли этот вид микрооптимизации имеет значение? Если да, то следуйте тому, что работает быстрее в ваших тестах и ​​не полагайтесь на оптимизацию компилятора.

Answer 9

Второй должен быть быстрее, потому что .size() не нужно вызывать каждый раз при выполнении цикла.Гораздо быстрее сказать 1 + 2 = 3 один раз, чем много раз.

Answer 10

В последнем примере вам не нужно разрешать текущий размер массива, поэтому он будет немного быстрее, чем в первом примере.

Просто помните, что это полезно, только если вы не меняете количество значений в вашем массиве.

В Android рекомендуется использовать последний пример в этом примере, Designing for Performance. http://developer.android.com/guide/practices/design/performance.html#foreach