Почему 2 * (i * i) быстрее, чем 2 * i * i в Java?

Ответ:

При перемножении в виде 2 * (i * i) JVM может вынести умножение на 2 за пределы цикла, в результате получая эквивалентный, но более эффективный код:

int n = 0;
for (int i = 0; i < 1000000000; i++) {
    n += i * i;
}
n *= 2;

Тем не менее, когда используется выражение (2 * i) * i, JVM не оптимизирует код, поскольку умножение на константу больше не происходит непосредственно перед присваиванием n +=.

Вот несколько причин, по которым я считаю, что это так:

• Если добавить условие if (n == 0) n = 1 в начале цикла, обе версии становятся по эффективности сопоставимыми, так как вынос умножения больше не гарантирует равенство результатов.
• Оптимизированная версия (с вынесением умножения на 2) оказывается на уровне скорости такой же, как и версия 2 * (i * i).

Вот тестовый код, который я использовал для получения этих выводов:

public static void main(String[] args) {
    long fastVersion = 0;
    long slowVersion = 0;
    long optimizedVersion = 0;
    long modifiedFastVersion = 0;
    long modifiedSlowVersion = 0;

    for (int i = 0; i < 10; i++) {
        fastVersion += fastVersion();
        slowVersion += slowVersion();
        optimizedVersion += optimizedVersion();
        modifiedFastVersion += modifiedFastVersion();
        modifiedSlowVersion += modifiedSlowVersion();
    }

    System.out.println("Fast version: " + (double) fastVersion / 1000000000 + " s");
    System.out.println("Slow version: " + (double) slowVersion / 1000000000 + " s");
    System.out.println("Optimized version: " + (double) optimizedVersion / 1000000000 + " s");
    System.out.println("Modified fast version: " + (double) modifiedFastVersion / 1000000000 + " s");
    System.out.println("Modified slow version: " + (double) modifiedSlowVersion / 1000000000 + " s");
}

private static long fastVersion() {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        n += 2 * (i * i);
    }
    return System.nanoTime() - startTime;
}

private static long slowVersion() {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        n += 2 * i * i;
    }
    return System.nanoTime() - startTime;
}

private static long optimizedVersion() {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        n += i * i;
    }
    n *= 2;
    return System.nanoTime() - startTime;
}

private static long modifiedFastVersion() {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        if (n == 0) n = 1;
        n += 2 * (i * i);
    }
    return System.nanoTime() - startTime;
}

private static long modifiedSlowVersion() {
    long startTime = System.nanoTime();
    int n = 0;
    for (int i = 0; i < 1000000000; i++) {
        if (n == 0) n = 1;
        n += 2 * i * i;
    }
    return System.nanoTime() - startTime;
}

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

Fast version: 5.7274411 s
Slow version: 7.6190804 s
Optimized version: 5.1348007 s
Modified fast version: 7.1492705 s
Modified slow version: 7.2952668 s

Примечание редактора: этот ответ противоречит данным из анализа ассемблера, как показано в другом ответе. Это было предположение, подкрепленное некоторыми экспериментами, но оно оказалось неверным.

Ваш вопрос касаемо разницы производительности между функциями multi и multiB в Java является интересным примером оптимизации кода на уровне байт-кода. Давайте рассмотрим это подробнее.

Ваша программа выполняет две похожие функции: multiB, где выражение 2 * (i * i) заключено в скобки, и multi, где используется выражение 2 * i * i. При этом вы заметили, что multiB работает быстрее, чем multi.

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

private static multiB(int arg0) { // 2 * (i * i)
    L1 {
        iconst_2         // положить константу 2 в стек
        iload0           // загрузить i в стек
        iload0           // снова загрузить i в стек
        imul              // перемножить верхние два значения в стеке (i * i)
        imul              // перемножить результат с 2
        ireturn          // вернуть результат
    }
}

private static multi(int arg0) { // 2 * i * i
    L1 {
        iconst_2         // положить константу 2 в стек
        iload0           // загрузить i в стек
        imul              // перемножить 2 и i
        iload0           // снова загрузить i в стек
        imul              // перемножить результат со значением i
        ireturn          // вернуть результат
    }
}

Объяснение:

1. С функцией multiB:

   • Значение 2 загружается в стек.
   • i загружается в стек дважды, чтобы потом перемножить.
   • Стековая операция позволяет сразу хранить результат i * i, и затем легко перемножить его на 2.
   • Таким образом, выполнение операций основывается на простом и прямом доступе к стеку.

2. С функцией multi:

   • Точно так же начинается с загрузки 2 в стек.
   • После этого i загружается и перемножается с 2.
   • Затем i снова загружается, и производится второй множитель, что требует дополнительной работы со стеком для доступа к значениям.
   • Этот переключатель между операциями записи и вычисления, как правило, замедляет выполнение, так как каждая операция требует свой обход стека.

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

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

Хотя это не совсем связано с окружением вопроса, просто из любопытства, я провел тот же тест на .NET Core 2.1, x64, в режиме релиза.

Вот интересный результат, подтверждающий похожие явления, но в другую сторону. Код:

static void Main(string[] args)
{
    Stopwatch watch = new Stopwatch();

    Console.WriteLine("2 * (i * i)");

    for (int a = 0; a < 10; a++)
    {
        int n = 0;

        watch.Restart();

        for (int i = 0; i < 1000000000; i++)
        {
            n += 2 * (i * i);
        }

        watch.Stop();

        Console.WriteLine($"result:{n}, {watch.ElapsedMilliseconds} ms");
    }

    Console.WriteLine();
    Console.WriteLine("2 * i * i");

    for (int a = 0; a < 10; a++)
    {
        int n = 0;

        watch.Restart();

        for (int i = 0; i < 1000000000; i++)
        {
            n += 2 * i * i;
        }

        watch.Stop();

        Console.WriteLine($"result:{n}, {watch.ElapsedMilliseconds}ms");
    }
}

Результаты:

2 * (i * i)

• result:119860736, 438 ms
• result:119860736, 433 ms
• result:119860736, 437 ms
• result:119860736, 435 ms
• result:119860736, 436 ms
• result:119860736, 435 ms
• result:119860736, 435 ms
• result:119860736, 439 ms
• result:119860736, 436 ms
• result:119860736, 437 ms

2 * i * i

• result:119860736, 417 ms
• result:119860736, 417 ms
• result:119860736, 417 ms
• result:119860736, 418 ms
• result:119860736, 418 ms
• result:119860736, 417 ms
• result:119860736, 418 ms
• result:119860736, 416 ms
• result:119860736, 417 ms
• result:119860736, 418 ms

Можно заметить, что вычисление 2 * i * i выполняется быстрее, чем 2 * (i * i), что может быть связано с оптимизациями компилятора и разницей в порядке вычислений.

Ваша ситуация интересна и, похоже, что оптимизация компилятора играет существенную роль в том, как выполняется ваш код. Основное, что можно отметить:

Оба фрагмента кода выполняются в одинаковых условиях и с одинаковыми параметрами, тем не менее, они показывают разные подходы к вычислению, практически не влияя на конечное время выполнения. Вы можете наблюдать, что JVM (Java Virtual Machine) может оптимизировать как один, так и другой вариант кода, в результате чего результаты получаются сопоставимыми.

Сравнение байт-кода, который вы предоставили, показывает, что с точки зрения компиляции, они очень похожи, но различаются на некоторых уровнях операторов imul:

1. В первом примере: 2 * (i * i) — компилятор обрабатывает операции по порядку, что даёт возможность выполнять одну умножение (i * i) и затем умножать на 2.
2. Во втором примере: 2 * i * i — здесь сначала идет умножение 2 * i, и затем результат умножается на i.

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

Если вы хотите протестировать и сравнить производительность более точно, вы можете рассмотреть использование более серьезных инструментов, таких как JMH (Java Microbenchmark Harness), который предназначен специально для микробенчмарков. Он предоставит более надежное измерение времени выполнения и производительности ваших фрагментов кода.

Надеюсь, это поможет прояснить ситуацию!

Интересное наблюдение, связанное с использованием Java 11 и отключением разворачивания циклов с помощью следующей VM опции:

-XX:LoopUnrollLimit=0

Цикл с выражением 2 * (i * i) дает более компактный машинный код¹:

L0001: add    eax,r11d
       inc    r8d
       mov    r11d,r8d
       imul   r11d,r8d
       shl    r11d,1h
       cmp    r8d,r10d
       jl     L0001

по сравнению с версией 2 * i * i, который выглядит следующим образом:

L0001: add    eax,r11d
       mov    r11d,r8d
       shl    r11d,1h
       add    r11d,2h
       inc    r8d
       imul   r11d,r8d
       cmp    r8d,r10d
       jl     L0001

Используемая версия Java:

java version "11" 2018-09-25
Java(TM) SE Runtime Environment 18.9 (build 11+28)
Java HotSpot(TM) 64-Bit Server VM 18.9 (build 11+28, mixed mode)

Результаты бенчмарка:

Benchmark          (size)  Mode  Cnt    Score     Error  Units
LoopTest.fast  1000000000  avgt    5  694,868 ±  36,470  ms/op
LoopTest.slow  1000000000  avgt    5  769,840 ± 135,006  ms/op

Исходный код бенчмарка:

@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
@Warmup(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
@Measurement(iterations = 5, time = 5, timeUnit = TimeUnit.SECONDS)
@State(Scope.Thread)
@Fork(1)
public class LoopTest {

    @Param("1000000000") private int size;

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
            .include(LoopTest.class.getSimpleName())
            .jvmArgs("-XX:LoopUnrollLimit=0")
            .build();
        new Runner(opt).run();
    }

    @Benchmark
    public int slow() {
        int n = 0;
        for (int i = 0; i < size; i++)
            n += 2 * i * i;
        return n;
    }

    @Benchmark
    public int fast() {
        int n = 0;
        for (int i = 0; i < size; i++)
            n += 2 * (i * i);
        return n;
    }
}

^1 - Используемые опции VM: -XX:+UnlockDiagnosticVMOptions -XX:+PrintAssembly -XX:LoopUnrollLimit=0