Оптимизация деления в gcc

Question

Вот некоторый код (полная программа следует далее в вопросе):

template <typename T>
T fizzbuzz(T n) {
    T count(0);
    #if CONST
        const T div(3);
    #else
        T div(3);
    #endif
    for (T i(0); i <= n; ++i) {
        if (i % div == T(0)) count += i;
    }
    return count;
}

Теперь, если я вызову эту шаблонную функцию с int, тогда я получу разницу в 6 раз в зависимости от того, определю я CONST или нет:

$ gcc --version
gcc (GCC) 3.4.4 (cygming special, gdc 0.12, using dmd 0.125)

$ make -B wrappedint CPPFLAGS="-O3 -Wall -Werror -DWRAP=0 -DCONST=0" &&
 time ./wrappedint
g++  -O3 -Wall -Werror -DWRAP=0 -DCONST=0   wrappedint.cpp   -o wrappedi
nt
484573652

real    0m2.543s
user    0m2.059s
sys     0m0.046s

$ make -B wrappedint CPPFLAGS="-O3 -Wall -Werror -DWRAP=0 -DCONST=1" &&
 time ./wrappedint
g++  -O3 -Wall -Werror -DWRAP=0 -DCONST=1   wrappedint.cpp   -o wrappedi
nt
484573652

real    0m0.655s
user    0m0.327s
sys     0m0.046s

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

Еще хуже, если я попытаюсь обернуть мое целое число в классе, тогда оптимизация не произойдет, использую ли я const или нет. Код всегда использует idivl и работает медленно:

#include <iostream>

struct WrappedInt {
    int v;
    explicit WrappedInt(const int &val) : v(val) {}
    bool operator<=(const WrappedInt &rhs) const { return v <= rhs.v; }
    bool operator==(const WrappedInt &rhs) const { return v == rhs.v; }
    WrappedInt &operator++() { ++v; return *this; }
    WrappedInt &operator+=(const WrappedInt &rhs) { v += rhs.v; return *this; }
    WrappedInt operator%(const WrappedInt &rhs) const 
        { return WrappedInt(v%rhs.v); }
};

std::ostream &operator<<(std::ostream &s, WrappedInt w) {
    return s << w.v;
}

template <typename T>
T fizzbuzz(T n) {
    T count(0);
    #if CONST
        const T div(3);
    #else
        T div(3);
    #endif
    for (T i(0); i <= n; ++i) {
        if (i % div == T(0)) count += i;
    }
    return count;
}

int main() {
    #if WRAP
        WrappedInt w(123456789);
        std::cout << fizzbuzz(w) << "\n";
    #else
        std::cout << fizzbuzz<int>(123456789) << "\n";
    #endif
}

Мои вопросы:

1) Существует ли простой принцип самого C ++ или оптимизации gcc, объясняющий, почему это происходит, или это всего лишь случай «запуска различных эвристик, это код, который вы получаете»?

2) Есть ли способ заставить компилятор понять, что мой локально объявленный и никогда не упоминаемый const WrappedInt может рассматриваться как значение const во время компиляции? Я хочу, чтобы эта вещь была прямой заменой int в шаблонах.

3) Известен ли способ обёртывания int таким образом, что компилятор может отбрасывать обёртку при оптимизации? Цель состоит в том, что WrappedInt будет основанным на политике шаблоном. Но если политика «ничего не делает» приводит к произвольным 6-кратным штрафам за превышение скорости по сравнению с int, я бы лучше использовал специальный случай и использовал int напрямую.

Answer 1

Полагаю, это просто старая версия GCC, которую вы используете. Самый старый компилятор, который у меня есть на моей машине - gcc-4.1.2, выполняет быстрый способ с версиями не-const и wrap (и делает это только при -O1).

Answer 2

Попробуйте объединить const int v в вашем классе WrappedInt с const T в вашей функции fizzbuzz и посмотрите, может ли компилятор оптимизировать это.

Объявляя const int, вы создали специальный случай - постоянную времени компиляции. Компилятор знает, что это за значение, и может оптимизировать его сильнее, чем значение, которое может измениться во время выполнения программы.

Answer 3

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

if (i  % 3 == 0)

Я немного удивлен, что он не использовал побитовое И (&).

WrappedInt не оптимизируется, потому что, ну, это не int. Это класс.

Что-то, что вы могли бы сделать, это включить fizzbuzz в WrappedInt.

Answer 4

Известен ли способ обёртывания int таким образом, что компилятор может отказаться от обёртывания при оптимизации?

Попробуйте передать WrappedInt по значению. Затем WrappedInt s может быть передано в регистры. Передача по константной ссылке иногда вынуждает gcc возвращаться к стеку для передачи аргументов.

Что касается замедления int против const int, я могу только предположить, что GCC пытается обезопасить себя перед лицом алиасинга. По сути, если он не может доказать, что div не является псевдонимом для другой, более доступной переменной, он не может превратить ее в константу. Если вы объявляете его const, GCC предполагает, что он не имеет псевдонима, и выполняет преобразование в константу. Помимо idivl, вы также должны увидеть один раз выборку памяти при входе в функцию, в отличие от непосредственных значений, используемых для случая const.