Почему не может (или нет) компилятор оптимизировать предсказуемый цикл добавления в умножение?

Ответ 1

Компилятор вообще не может преобразовать

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

в

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000 * data[c];

потому что последнее может привести к переполнению целых чисел, в которых первое не имеет. Даже при гарантированном обертывании для переполнения подписанных двух целых чисел, это изменит результат (если data[c] равно 30000, продукт станет -1294967296 для типичного 32-битного int с оберткой, а 100000 раз добавление 30000 к sum, если это не переполнение, увеличьте sum на 3000000000). Обратите внимание, что то же самое верно для неподписанных величин с разными номерами, переполнение 100000 * data[c] обычно вводит редукцию по модулю 2^32, которая не должна появляться в конечном результате.

Он может преобразовать его в

for (int c = 0; c < arraySize; ++c)
    if (data[c] >= 128)
        sum += 100000LL * data[c];  // resp. 100000ull

хотя, если, как обычно, long long достаточно больше, чем int.

Почему он этого не делает, я не могу сказать, я предполагаю, что Mystical сказал, "по-видимому, он не запускает провал цикла после цикла-обмена".

Обратите внимание, что сам обмен цикла вообще недействителен (для целых чисел со знаком), так как

for (int c = 0; c < arraySize; ++c)
    if (condition(data[c]))
        for (int i = 0; i < 100000; ++i)
            sum += data[c];

может привести к переполнению, где

for (int i = 0; i < 100000; ++i)
    for (int c = 0; c < arraySize; ++c)
        if (condition(data[c]))
            sum += data[c];

не будет. Это кошерно здесь, так как условие гарантирует, что все добавленные data[c] имеют один и тот же знак, поэтому, если один из них переполняется, оба выполняются.

Я не был бы слишком уверен, что компилятор учитывал это, хотя (@Mysticial, вы могли бы попробовать с условием типа data[c] & 0x80 или так, что это может быть верно для положительных и отрицательных значений?). У меня были компиляторы для недопустимых оптимизаций (например, пару лет назад у меня было ICC (11.0, iirc) использование конвертирования с 32-битным int-в-double в формате 1.0/n, где n было unsigned int > Было примерно в два раза быстрее, чем gcc-выход. Но неправильно, много значений было больше, чем 2^31, oops.).

Ответ 2

Этот ответ не относится к конкретному связанному случаю, но относится к названию вопроса и может быть интересен будущим читателям:

Из-за конечной точности повторное сложение с плавающей точкой не эквивалентно умножению. Рассмотрим:

float const step = 1e-15;
float const init = 1;
long int const count = 1000000000;

float result1 = init;
for( int i = 0; i < count; ++i ) result1 += step;

float result2 = init;
result2 += step * count;

cout << (result1 - result2);

Demo

Ответ 3

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

Оптимизация, которая была выполнена, - это движение цикла с инвариантом цикла. Это можно сделать с помощью набора методов.

Ответ 4

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

В то же время некоторые компиляторы могут отказаться делать это, потому что замена повторяющегося сложения на умножение может изменить поведение кода при переполнении. Для целочисленных типов без знака это не должно иметь значения, так как их поведение переполнения полностью определяется языком. Но для подписанных, это могло бы (вероятно не на платформе с 2 дополнениями все же). Это правда, что переполнение со знаком на самом деле приводит к неопределенному поведению в C, что означает, что должно быть совершенно нормально игнорировать эту семантику переполнения, но не все компиляторы достаточно смелы, чтобы сделать это. Это часто вызывает много критики со стороны "C - это просто язык ассемблера более высокого уровня". (Помните, что произошло, когда GCC ввел оптимизации, основанные на семантике строгого наложения имен?)

Исторически GCC показывал себя как компилятор, у которого есть все, что нужно, чтобы предпринимать такие радикальные шаги, но другие компиляторы могут предпочесть придерживаться воспринимаемого "предназначенного для пользователя" поведения, даже если оно не определено языком.

Ответ 5

Существует концептуальный барьер для такого рода оптимизации. Авторы компилятора тратят много усилий на снижение прочности - например, заменяя умножения на добавления и сдвиги. Они привыкли думать, что умножение это плохо. Так что случай, когда нужно идти другим путем, удивителен и нелогичен. Так что никто не думает реализовать это.

Ответ 6

Люди, которые разрабатывают и поддерживают компиляторы, имеют ограниченное количество времени и энергии, чтобы тратить на их работу, поэтому они обычно хотят сосредоточиться на том, что их пользователям больше всего волнует: превращение хорошо написанного кода в быстрый код. Они не хотят тратить свое время, пытаясь найти способы превратить глупый код в быстрый код - что такое обзор кода. На высокоуровневом языке может быть "глупый" код, который выражает важную идею, что делает его временем разработчиков, чтобы сделать это быстро, например, сокращение вырубки и слияние потоков позволяют программам Haskell структурироваться вокруг определенных видов лениво созданные структуры данных, которые должны быть скомпилированы в тесные петли, которые не выделяют память. Но такой стимул просто не применяется для превращения петлевого добавления в умножение. Если вы хотите, чтобы он был быстрым, просто напишите его с помощью умножения.