Вопрос Java для цикла

с учетом этого примера:

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

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

Ответ 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 нс, вам следует позаботиться об этом. В противном случае, не делайте.

Ответ 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
}

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

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

Ответ 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]
}

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

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

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

Ответ 4

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

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

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

Ответ 5

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

Ответ 6

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

Ответ 7

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

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

Ответ 8

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

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

Ответ 9

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

Ответ 10

В случае "оптимизации компилятора" лучшее, что вы можете сделать, это для каждого цикла:

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

Что позволяет компилятору обеспечить самую быструю реализацию.

Edit:

Разница между примерами кода приведена во втором аргументе for-loop. В первом примере виртуальная машина будет выполнять вызов метода (более дорогостоящий) и, следовательно, медленнее (только значительная, когда есть много итераций). Во втором примере виртуальная машина будет делать стек pop (менее дорогостоящие, а локальные переменные находятся в стеке) и, следовательно, быстрее (только значительная, когда есть много итераций: для одной итерации первая быстрее, с точки зрения использования памяти).

Также: "Преждевременная оптимизация - это корень всего зла". Дональд Кнут позорный закон.

Ответ 11

Разница заключается в том, что один метод меньше для каждой итерации, поэтому вторая версия должна работать немного быстрее. Хотя, если вы используете компилятор Just-In-Time, он может оптимизировать это - выясняя, что он не меняется во время цикла. Стандартные возможности реализации Java JIT, но не каждая реализация Java делает.

Ответ 12

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

Однако, как было указано Pindatjuh, лучше использовать цикл foreach, когда вы собираетесь выполнять итерацию по всей коллекции. Это должно позволить компилятору оптимизировать вещи лучше и меньше подвержено ошибкам.

Ответ 13

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

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

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