Повлияет ли переназначение переменной на каждой итерации цикла на производительность?

Question

Рассмотрим следующие два способа написания цикла в Java, чтобы увидеть, содержит ли список заданное значение:

Стиль 1

boolean found = false;
for(int i = 0; i < list.length && !found; i++)
{
   if(list[i] == testVal)
     found = true;
}

Стиль 2

boolean found = false;
for(int i = 0; i < list.length && !found; i++)
{
   found = (list[i] == testVal);
}

Они эквивалентны, но я всегда использую стиль 1, потому что 1) я нахожу его более читабельным, и 2) я предполагаю, что переназначение found на false сотни раз кажется, что это займет больше времени. Мне интересно: верно ли это второе предположение?

Угол Нитпикера

• Мне хорошо известно, что это случай преждевременной оптимизации. Это не значит, что это не то, что полезно знать.
• Мне все равно, какой стиль вы считаете более читабельным. Меня интересует только то, имеет ли одно снижение производительности по сравнению с другим.
• Я знаю, что у стиля 1 есть преимущество, позволяющее вам также помещать оператор break; в блок if, но мне все равно. Опять же, этот вопрос касается производительности, а не стиля.

Answer 1

Ну, просто напишите микро-тест:

import java.util.*;

public class Test {
    private static int[] list = new int[] {1, 2, 3, 4, 5, 6, 7, 8, 9} ;
    private static int testVal = 6;


    public static boolean version1() {
        boolean found = false;
        for(int i = 0; i < list.length && !found; i++)
        {
        if(list[i] == testVal)
            found = true;
        }
        return found;

    }

    public static boolean version2() {
    boolean found = false;
    for(int i = 0; i < list.length && !found; i++)
        {
        found = (list[i] == testVal);
        }

    return found;
    }


    public static void main(String[] args) {

        // warm up
    for (int i=0; i<100000000; i++) {
        version1();
        version2();
    }


    long time = System.currentTimeMillis();
    for (int i=0; i<100000000; i++) {
        version1();
    }

    System.out.println("Version1:" + (System.currentTimeMillis() - time));

    time = System.currentTimeMillis();
    for (int i=0; i@lt;100000000; i++) {
        version2();
    }

        System.out.println("Version2:" + (System.currentTimeMillis() - time));
    }
}

На моей машине версия 1 кажется немного быстрее:

Version1: 5236

Version2: 5477

(Но это 100 секунд на 100 миллионов итераций. Мне бы все равно.)

Если вы посмотрите на сгенерированный байт-код, в версии 2 есть еще две инструкции, которые, вероятно, приводят к увеличению времени выполнения:

public static boolean version1();
  Code:
   0:   iconst_0
   1:   istore_0
   2:   iconst_0
   3:   istore_1
   4:   iload_1
   5:   getstatic   #2; //Field list:[I
   8:   arraylength
   9:   if_icmpge   35
   12:  iload_0
   13:  ifne    35
   16:  getstatic   #2; //Field list:[I
   19:  iload_1
   20:  iaload
   21:  getstatic   #3; //Field testVal:I
   24:  if_icmpne   29
   27:  iconst_1
   28:  istore_0
   29:  iinc    1, 1
   32:  goto    4
   35:  iload_0
   36:  ireturn

public static boolean version2();
  Code:
   0:   iconst_0
   1:   istore_0
   2:   iconst_0
   3:   istore_1
   4:   iload_1
   5:   getstatic   #2; //Field list:[I
   8:   arraylength
   9:   if_icmpge   39
   12:  iload_0
   13:  ifne    39
   16:  getstatic   #2; //Field list:[I
   19:  iload_1
   20:  iaload
   21:  getstatic   #3; //Field testVal:I
   24:  if_icmpne   31
   27:  iconst_1
   28:  goto    32
   31:  iconst_0
   32:  istore_0
   33:  iinc    1, 1
   36:  goto    4
   39:  iload_0
   40:  ireturn

Answer 2

Комментарий к углу "Ниппикс":

Если вы действительно озабочены абсолютной производительностью, то добавление паузы и удаление "&&! Found" теоретически даст вам лучшую производительность на # 1 Два бинарных операции меньше, чтобы беспокоиться о каждой итерации.

Если вы хотите по-настоящему проанализировать оптимизацию без перерывов,

boolean notFound = true;
    for(int i = 0; notFound && i < list.length; i++)
    {
       if(list[i] == testVal)
         notFound = false;
    }

будет работать быстрее в среднем случае, чем существующая опция # 1.

И, конечно, это личное предпочтение, но я предпочитаю никогда не помещать никаких дополнительных оценок в заголовок цикла for. Я считаю, что это может вызвать путаницу при чтении кода, потому что это легко пропустить. Если я не могу получить желаемое поведение, используя break / continue, я буду использовать цикл while или do / while.

Answer 3

На самом деле, «если» замедлит вашу программу больше, чем назначение из-за конвейера .

Answer 4

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

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

Решение, которое Мэтт выдает, когда ответ найден, уменьшает количество тестов с трех (итератор цикла, найденный тест в цикле, фактическое сравнение) до двух. Проведение «найденного» теста, по сути, дважды, расточительно.

Я не уверен, что классический, но несколько запутанный трюк с возвратом назад - это победа в Java, и он недостаточно хорош для чтения кода JVM, чтобы понять это прямо сейчас.

Answer 5

Вот другой стиль

for(int i = 0; i < list.length; i++)
{
   if(list[i] == testVal)
     return true;
}

return false;

Answer 6

Мне кажется, что если вы ожидаете, что ваше значение будет найдено до конца списка, вам лучше использовать # 2 - поскольку он замыкает проверку с помощью! Предполагая, что вы вставили разрыв, 1-й вариант (единственная разумная вещь, IMO), тогда псевдосборка будет выглядеть примерно так:

Вариант 1:

start:
  CMP i, list.length
  JE end
  CMP list[i], testval
  JE equal
  JMP start
equal:
  MOV true, found
end:

Вариант 2:

start:
  CMP i, list.length
  JE end
  CMP true, found
  JE end
  CMP list[i], testval
  JE equal
  JNE notequal
equal:
  MOV true, found
  JMP start
notequal:
  MOV false, found
  JMP start
end:

Я бы сказал, что вариант 1 здесь лучше, так как он примерно на 1/3 меньше инструкций. Конечно, это без оптимизации - но это будет зависеть от компилятора и конкретной ситуации (что будет после этого делать? Мы можем просто оптимизировать все это вместе?).

Answer 7

Я считаю, что стиль 2 немного быстрее - скажем, 1 такт или около того.

Я бы переписал это следующим образом, если бы занялся этим:

for(i=0; i<list.length && list[i]!=testval; i++);
boolean found = (i!=list.length);

Answer 8

Это зависит от того, какой компилятор вы используете, так как разные компиляторы могут выполнять разные оптимизации.

Answer 9

boolean found = false;
for(int i = 0; i < list.length && !found; i++)
{
   if(list[i] == testVal)
     found = true;
}

Я не вижу оператора break в блоке.

Кроме этого, я предпочитаю этот стиль. Это улучшает читабельность и, следовательно, вероятность того, что сопровождающий неправильно его прочитает и исправит.

Answer 10

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