g ++ -O оптимизаций

Question

У меня есть следующий код:

#include <iostream>
int main()
{
        int n = 100;
        long a = 0;
        int *x = new int[n];

        for(int i = 0; i < n; ++i)
                for(int j = 0; j < n; ++j)
                        for(int k = 0; k < n; ++k)
                                for(int l = 0; l < n; ++l)
                                {   

                                        a += x[(j + k + l) % 100];
                                }   
        std::cout << a << std::endl;
        delete[] x;
        return 0;
}

Если я скомпилирую без оптимизации g ++ test.cc, а затем запустлю время выполнения ./a.out, он покажет 0,7 с. Однако, когда я компилирую это с -O, время уменьшается в 2 раза.

Используется компилятор

g++ (Ubuntu/Linaro 4.5.2-8ubuntu4) 4.5.2

Мой вопрос

Как я могу переписать код, чтобы при компиляции без -O я мог получить то же время (или близко к нему)? Другими словами, как вручную оптимизировать вложенные циклы ?

Почему я спрашиваю

У меня похожий код, который работает примерно в 4 раза быстрее, если я использую оптимизацию -O.

PS: я посмотрел руководство к компилятору, но там слишком много флагов, чтобы проверить, какой из них действительно имеет значение.

Answer 1

Большинство вещей, которые оптимизатор компилирует с -O, это вещи на уровне ниже C ++. Например, все переменные живут в памяти, включая переменные вашего цикла. Поэтому без оптимизации компилятор, скорее всего, на каждой итерации внутреннего цикла сначала считывает переменную цикла, чтобы сравнить ее с 0, внутри цикла загружает ее снова, чтобы использовать ее для индекса, а затем в конце цикла. будет читать значение снова, увеличивать его и записывать обратно. При оптимизации он заметит, что переменная цикла не изменяется в теле цикла, и, следовательно, нет необходимости каждый раз перечитываться из памяти. Кроме того, он также заметит, что адрес переменной никогда не берется, поэтому никакой другой код никогда не получит к нему доступ, и поэтому запись его в память также может быть опущена. То есть переменная цикла будет жить только в памяти. Одна только эта оптимизация сэкономит триста миллионов операций чтения из памяти и сто миллионов операций записи в память во время выполнения вашей функции. Но поскольку такие вещи, как регистры процессора и чтение / запись в память, не отображаются на уровне языка, его невозможно оптимизировать на уровне языка.

Кроме того, не имеет смысла оптимизировать то, что оптимизирует компилятор вручную. Лучше потратить время на оптимизацию вещей, которые компилятор не может оптимизировать.

Answer 2

Этот код имеет неопределенное поведение, поэтому на самом деле оптимизатор может делать все, что он хочет ..

a += x[j + k + l % 100];

должно быть:

a += x[(j + k + l) % 100];

Если вы исправите это, я все равно не сделаюпонять, почему вы хотите оптимизировать что-то, что на самом деле ничего не делает ...

Лично я бы оптимизировал это следующим образом::)

std::cout << 0 << std::endl;

Примечание: удалите цикл для iи сделать std::cout << a * n << std::endl;

Answer 3

Как я могу переписать код, чтобы при компиляции без -O я мог получить то же время (или близко к нему)? Другими словами, как оптимизировать вложенные циклы вручную?

Вы пишете их в сборке. Удачи с , что , кстати.

Цель переключателей оптимизации в компиляторах - сказать вам: «Компилятор, я хочу, чтобы вы попытались сгенерировать быструю сборку». По умолчанию компиляторы не выполняют оптимизацию, поскольку эти оптимизации могут препятствовать отладке полученного кода. Поэтому вы должны специально попросить их.

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

Answer 4

Вы используете алгоритм полиномиального времени (n ** 4), поэтому понятно, что он будет медленным, особенно для больших n. Возможно, вам поможет алгоритм с меньшей сложностью?

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

Answer 5

Вы могли заметить, что ваши циклы образуют набор коэффициентов coeff[i], так что при суммировании одного цикла a[i] * coeff[i] получается столько же, сколько во вложенном цикле.Если мы предположим, что ваш индекс должен был быть (i + j + k) % 100, то coeff[i] = n * n * n для всех i, поэтому вся ваша программа упрощается до

long coeff = n * n * n;
for (int i = 0; i < n; ++n)
    a += x[i] * coeff;

, что, я уверен, выполняется менее чем за 0,7 секунды.