Подтвердить что ты не робот

Эффективность цикла Java

Я сравниваю эффективность вложенных, while и do-while циклов в Java, и я столкнулся с некоторыми странными результатами, которые мне нужны для понимания.

public class Loops {
    public static void main(String[] args) {
        int L = 100000;    // number of iterations per loop
        // for loop
        double start = System.currentTimeMillis();
        long s1 = 0;
        for (int i=0; i < L; i++) {
            for (int j = 0; j < L; j++) {
                s1 += 1;
            }
        }
        double end = System.currentTimeMillis();
        String result1 = String.format("for loop: %.5f", (end-start) / 1000);
        System.out.println(s1);
        System.out.println(result1);

        // do-while loop
        double start1 = System.currentTimeMillis();
        int i = 0;
        long s2 = 0;
        do {
            i++;
            int j = 0;
            do {
                s2 += 1;
                j++;
            } while (j < L);
        } while (i < L);
        double end1 = System.currentTimeMillis();
        String result2 = String.format("do-while: %.5f", (end1-start1) / 1000);
        System.out.println(s2);
        System.out.println(result2);

        // while loop
        double start2 = System.currentTimeMillis();
        i = 0;
        long s3 = 0;
        while (i < L) {
            i++;
            int j = 0;
            while (j < L) {
                s3 += 1;
                j++;
            }
        }
        double end2 = System.currentTimeMillis();
        String result3 = String.format("while: %.5f", (end2-start2) / 1000);
        System.out.println(s3);
        System.out.println(result3);
    }
}

Все циклы соответствующих счетчиков составляют 10 миллиардов; результаты меня озадачивают:

для цикла: 6.48300

do-while: 0.41200

в то время как: 9.71500

Почему цикл do-while намного быстрее? Этот разрыв производительности масштабируется параллельно с любыми изменениями в L. Я выполнял эти циклы независимо, и они выполняют то же самое.

4b9b3361

Ответ 1

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

Мои результаты после первого запуска этих циклов были следующими:

for loop: 1.43100
do-while: 0.51300
while: 1.54500

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

for loop: 0.43200
do-while: 0.46100
while: 0.42900

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

  • Цикл do-while выполняет меньшее количество сравнений, чем циклы for и while

Для простоты предположим, что L = 1

long s1 = 0;
for (int i=0; i < L; i++) {
    for (int j = 0; j < L; j++) {
        s1 += 1;

внешний цикл: 0 < 1
внутренний цикл: 0 < 1
внутренний цикл: 1 < 1
внешний контур: 1 < 1

Всего 4 сравнения

int i = 0;
long s2 = 0;
do {
    i++;
    int j = 0;
    do {
        s2 += 1;
        j++;
    } while (j < L);
} while (i < L);

внутренний цикл: 1 < 1
внешний контур: 1 < 1

Всего 2 сравнения

  • Различные сгенерированные bytecodes

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

public class Loops {
    final static int L = 100000; // number of iterations per loop

    public static void main(String[] args) {
        int round = 10;
        while (round-- > 0) {
            forLoop();
            doWhileLoop();
            whileLoop();
        }
    }

    private static long whileLoop() {
        int i = 0;
        long s3 = 0;
        while (i++ < L) {
            int j = 0;
            while (j++ < L) {
                s3 += 1;
            }
        }
        return s3;
    }

    private static long doWhileLoop() {
        int i = 0;
        long s2 = 0;
        do {
            int j = 0;
            do {
                s2 += 1;
            } while (++j < L);
        } while (++i < L);
        return s2;
    }

    private static long forLoop() {
        long s1 = 0;
        for (int i = 0; i < L; i++) {
            for (int j = 0; j < L; j++) {
                s1 += 1;
            }
        }
        return s1;
    }
}

Затем скомпилировал его и вызвал javap -c -s -private -l Loop, чтобы получить байт-код.

Сначала байт-код doWhileLoop.

   0:   iconst_0        // push the int value 0 onto the stack
   1:   istore_1        // store int value into variable 1 (i)
   2:   lconst_0        // push the long 0 onto the stack
   3:   lstore_2        // store a long value in a local variable 2 (s2)
   4:   iconst_0        // push the int value 0 onto the stack
   5:   istore  4   // store int value into variable 4 (j)
   7:   lload_2     // load a long value from a local variable 2 (i)
   8:   lconst_1        // push the long 1 onto the stack
   9:   ladd        // add two longs
   10:  lstore_2        // store a long value in a local variable 2 (i)
   11:  iinc    4, 1    // increment local variable 4 (j) by signed byte 1
   14:  iload   4   // load an int value from a local variable 4 (j)
   16:  iload_0     // load an int value from a local variable 0 (L)
   17:  if_icmplt   7   // if value1 is less than value2, branch to instruction at 7
   20:  iinc    1, 1    // increment local variable 1 (i) by signed byte 1
   23:  iload_1     // load an int value from a local variable 1 (i)
   24:  iload_0     // load an int value from a local variable 0 (L)
   25:  if_icmplt   4   // if value1 is less than value2, branch to instruction at 4
   28:  lload_2     // load a long value from a local variable 2 (s2)
   29:  lreturn     // return a long value

Теперь байт-код whileLooP:

   0:   iconst_0        // push int value 0 onto the stack
   1:   istore_1        // store int value into variable 1 (i)
   2:   lconst_0        // push the long 0 onto the stack
   3:   lstore_2        // store a long value in a local variable 2 (s3)
   4:   goto        26
   7:   iconst_0        // push the int value 0 onto the stack
   8:   istore  4   // store int value into variable 4 (j)
   10:  goto        17
   13:  lload_2     // load a long value from a local variable 2 (s3)
   14:  lconst_1        // push the long 1 onto the stack
   15:  ladd        // add two longs
   16:  lstore_2        // store a long value in a local variable 2 (s3)
   17:  iload   4   // load an int value from a local variable 4 (j)
   19:  iinc    4, 1    // increment local variable 4 (j) by signed byte 1
   22:  iload_0     // load an int value from a local variable 0 (L)
   23:  if_icmplt   13  // if value1 is less than value2, branch to instruction at 13
   26:  iload_1     // load an int value from a local variable 1 (i)
   27:  iinc    1, 1    // increment local variable 1 by signed byte 1
   30:  iload_0     // load an int value from a local variable 0 (L)
   31:  if_icmplt   7   // if value1 is less than value2, branch to instruction at 7
   34:  lload_2     // load a long value from a local variable 2 (s3)
   35:  lreturn     // return a long value

Чтобы сделать вывод более читаемым, я добавляю комментарии, описывающие, что каждая инструкция делает на основе списков инструкций Java bytecode.

Если вы присмотритесь ближе, вы увидите, что между этими двумя байт-кодами существует важная разница. Цикл while (то же самое верно для цикла for) имеет инструкции if (if_icmplt), определенные в конце байт-кода. Это означает, что для проверки условия выхода первого цикла необходимо вывести goto в строку 26 и аналогичным образом перейти к строке 17 для второго цикла.

Вышеуказанный байт-код был сгенерирован с использованием javac 1.6.0_45 в Mac OS X.

Резюме

Я думаю, что различная сумма сравнений плюс наличие команд goto в байт-коде while и for, отвечает за разницу в производительности между этими циклами.