Оптимизация циклов Java

Дайте следующий (простой) код:

public class pr1 {

    public static void f1(){
        long sx = 0, s;
        s = System.currentTimeMillis();
        for(long i = 0; i < Integer.MAX_VALUE; ++i){
            sx += i;
        }
        System.out.println("f1(): " + (System.currentTimeMillis() - s));
    }

    public static void f2(){
        long sx = 0, s, i;
        s = System.currentTimeMillis();
        i = Integer.MAX_VALUE;
        while(i-->0){
            sx+=i;
        }
        sx += Integer.MAX_VALUE;
        System.out.println("f2(): " + (System.currentTimeMillis() - s));
    }

    public static void f3(){
        long sx = 0, s, i;
        s = System.currentTimeMillis();
        i = Integer.MAX_VALUE;
        while(--i>0){
            sx+=i;
        }
        sx += Integer.MAX_VALUE;
        System.out.println("f3(): " + (System.currentTimeMillis() - s));
    }

    public static void f4(){
        long sx = 0, s, i;
        s = System.currentTimeMillis();
        i = Integer.MAX_VALUE;
        do{
            sx+=i;
        }while(--i>0);
        System.out.println("f4(): " + (System.currentTimeMillis() - s));
    }

    public static void main(String args[]){
        f1();
        f2();
        f3();
        f4();
    }
}

И фактические результаты после выполнения кода:

f1(): 5828
f2(): 8125
f3(): 3406
f4(): 3781

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

После повторяющегося выполнения результаты являются почти такими же.

ПОЗЖЕ ОТРЕДАКТИРУЙТЕ Как другой тест, я переписал основной метод:

public static void main(String args[]){
    for(int i = 0; i < 4; ++i){
        f1(); f2(); f3(); f4();
    }
}

И новые результаты:

f1(): 5906
f2(): 8266
f3(): 3406
f4(): 3844
f1(): 5843
f2(): 8125
f3(): 3438
f4(): 3859
f1(): 5891
f2(): 8156
f3(): 3406
f4(): 3813
f1(): 5859
f2(): 8172
f3(): 3438
f4(): 3828

И для 10 повторений:

f1(): 5844
f2(): 8156
f3(): 3453
f4(): 3813
f1(): 5844
f2(): 8218
f3(): 3485
f4(): 3937
f1(): 5985
f2(): 8156
f3(): 3422
f4(): 3781
f1(): 5828
f2(): 8234
f3(): 3469
f4(): 3828
f1(): 5844
f2(): 8328
f3(): 3422
f4(): 3859
f1(): 5844
f2(): 8188
f3(): 3406
f4(): 3797
f1(): 5906
f2(): 8219
f3(): 3422
f4(): 3797
f1(): 5843
f2(): 8203
f3(): 3454
f4(): 3906
f1(): 5844
f2(): 8140
f3(): 3469
f4(): 3812
f1(): 5860
f2(): 8109
f3(): 3422
f4(): 3813

После удаления исчисления между циклами результаты все еще немного отличаются:

public class pr2 {

    public static void f1(){
        long sx = 0, s;
        s = System.currentTimeMillis();
        for(long i = 0; i < Integer.MAX_VALUE; ++i);
        System.out.println("f1(): " + (System.currentTimeMillis() - s));
    }

    public static void f2(){
        long sx = 0, s, i;
        s = System.currentTimeMillis();
        i = Integer.MAX_VALUE;
        while(i-->0);
        System.out.println("f2(): " + (System.currentTimeMillis() - s));
    }

    public static void f3(){
        long sx = 0, s, i;
        s = System.currentTimeMillis();
        i = Integer.MAX_VALUE;
        while(--i>0);
        System.out.println("f3(): " + (System.currentTimeMillis() - s));
    }

    public static void f4(){
        long sx = 0, s, i;
        s = System.currentTimeMillis();
        i = Integer.MAX_VALUE;
        do{
        }while(--i>0);
        System.out.println("f4(): " + (System.currentTimeMillis() - s));
    }

    public static void main(String args[]){
        for(int i = 0; i < 2; ++i){
            f1(); f2(); f3(); f4();
        }
    }
}

Но разница во времени все еще существует:

f1(): 3219
f2(): 4859
f3(): 2610
f4(): 3031
f1(): 3219
f2(): 4812
f3(): 2610
f4(): 3062

JVM:

java version "1.6.0_20"
Java(TM) SE Runtime Environment (build 1.6.0_20-b02)
Java HotSpot(TM) Client VM (build 16.3-b01, mixed mode, sharing)

БОЛЕЕ ПОЗДНЕЕ РЕДАКТИРОВАНИЕ: Для первой версии я использовал-O параметр для javac. Новые результаты:

f1(): 3219
f2(): 4859
f3(): 2610
f4(): 3031

БОЛЕЕ ПОЗДНЕЕ РЕДАКТИРОВАНИЕ

Хорошо, я попробовал тот же код дома, с помощью машины Linux с:

java version "1.6.0_18"
OpenJDK Runtime Environment (IcedTea6 1.8) (6b18-1.8-0ubuntu1)
OpenJDK Server VM (build 14.0-b16, mixed mode)

И результаты были "нормальны". Никакие проблемы теперь:

f1(): 7495
f2(): 7418
f3(): 7457
f4(): 7384
7
задан Andrei Ciobanu 20 July 2010 в 17:27
поделиться

5 ответов

Когда я запускаю этот код на моей JVM (Java HotSpot(TM) 64-Bit Server VM (build 16.0-b13, mixed mode)), все четыре функции дают схожие результаты:

f1(): 3234
f2(): 3132
f3(): 3114
f4(): 3089

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

Вы можете просмотреть байткод, сгенерированный для различных функций, используя javap: javap -l -c pr1. Когда я делаю это, я получаю следующее для f2():

public static void f2();
  Code:
   0:   lconst_0
   1:   lstore_0
   2:   invokestatic    #2; //Method java/lang/System.currentTimeMillis:()J
   5:   lstore_2
   6:   ldc2_w  #3; //long 2147483647l
   9:   lstore  4
   11:  lload   4
   13:  dup2
   14:  lconst_1
   15:  lsub
   16:  lstore  4
   18:  lconst_0
   19:  lcmp
   20:  ifle    31
   23:  lload_0
   24:  lload   4
   26:  ladd
   27:  lstore_0
   28:  goto    11
   31:  lload_0
   32:  ldc2_w  #3; //long 2147483647l
   35:  ladd
   36:  lstore_0
   37:  getstatic       #5; //Field java/lang/System.out:Ljava/io/PrintStream;
   40:  new     #6; //class java/lang/StringBuilder
   43:  dup
   44:  invokespecial   #7; //Method java/lang/StringBuilder."<init>":()V
   47:  ldc     #13; //String f2():
   49:  invokevirtual   #9; //Method java/lang/StringBuilder.append:(Ljava/lang/String;)Ljava/lang/StringBuilder;
   52:  invokestatic    #2; //Method java/lang/System.currentTimeMillis:()J
   55:  lload_2
   56:  lsub
   57:  invokevirtual   #10; //Method java/lang/StringBuilder.append:(J)Ljava/lang/StringBuilder;
   60:  invokevirtual   #11; //Method java/lang/StringBuilder.toString:()Ljava/lang/String;
   63:  invokevirtual   #12; //Method java/io/PrintStream.println:(Ljava/lang/String;)V
   66:  return

Одной из возможных причин того, что f2() работает медленнее, может быть то, что компилятор/JVM не очень умны в отношении while(i-->0) оператора post-decrement. По сути, вам нужно значение i как до, так и после инкремента, поэтому эта операция требует больше работы, если реализована наивно.

5
ответ дан 6 December 2019 в 10:47
поделиться

Фактически вы тестируете JVM, а не код.

См. Также:


Обновление : Хорошо, это был кратковременный ответ. Цикл с использованием постфиксного оператора ( i - ) кажется медленнее, чем циклы с использованием префиксного оператора ( - i ). Это может быть правдой, поскольку значение изменяется во время оценки выражения, но компилятор должен хранить копию исходного значения для использования в выражении. Использование оператора префикса позволяет избежать необходимости хранить копию, поскольку в выражении будет использоваться только измененное значение.

См. Также:

В конце концов, эта микрооптимизация сэкономит вам одну или две секунды при выполнении 2 31 . Вы на самом деле тоже так часто его выполняете? Я бы предпочел удобочитаемость преждевременной оптимизации.

10
ответ дан 6 December 2019 в 10:47
поделиться

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

1
ответ дан 6 December 2019 в 10:47
поделиться

Я подозреваю, что это как-то связано с выполнением 64-битной арифметики на машине с 32-битным ALU. Я подозреваю, что определенные комбинации теста до / после увеличения / уменьшения занимают больше времени на уровне собственных инструкций из-за тонких эффектов конвейерной обработки. Тот факт, что кто-то сообщил, что числа на 64-битной машине равны, подтверждает эту теорию. Способ подтвердить это - получить дамп собственного кода, сгенерированного JIT-компилятором, получить документацию для вашего конкретного процессора и выяснить, куда идут тактовые циклы.

Но, честно говоря, я не знаю, стоит ли это того. У нас есть четкие доказательства того, что ваши результаты микротестов зависят от ЦП, а проделанная «работа» явно не репрезентативна. (Зачем вам использовать счетчик циклов long на 32-битной машине?)

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

1
ответ дан 6 December 2019 в 10:47
поделиться

Некоторые моменты, почему скорость выполнения может отличаться

  • сборка мусора JVM могла во время выполнения некоторых заданий
  • ваша ОС запланировала другие и таким образом отдала ресурсы другим приложениям. Или даже приоритет им и потом, возможно, есть разница из-за способа компиляции do/while и for, но этим можно пренебречь

давайте нацарапаем мой ответ.

это должно быть связано с ОС или способом компиляции Java для windows, я тестировал это на Windows и получил результаты как у вас на windows.

1
ответ дан 6 December 2019 в 10:47
поделиться
Другие вопросы по тегам:

Похожие вопросы: