Как gcc оптимизирует этот цикл?
Итак, я столкнулся с каким-то странным поведением, которое я сократил до следующего минимального примера:
#include <iostream>
#include <vector>
int main()
{
std::vector<int> vec;
for(int i = 0; i < 1000; i++)
{
vec.push_back(2150000 * i);
if (i % 100 == 0) std::cout << i << std::endl;
}
}
При компиляции с gcc 7.3.0 с помощью команды
c++ -Wall -O2 program.cpp -o program
Я не получаю предупреждений. Запуск программы дает следующий результат:
0
100
200
300
400
500
600
700
800
900
1000
1100
1200
1300
[ snip several thousand lines of output ]
1073741600
1073741700
1073741800
terminate called after throwing an instance of 'std::bad_alloc'
what(): std::bad_alloc
Aborted (core dumped)
что, как я полагаю, означает, что у меня, наконец, закончилась память для вектора.
Ясно, что здесь что-то не так. Я предполагаю, что это как-то связано с тем фактом, что 2150000 * 1000 немного больше, чем 2 ^ 31, но это не так просто - если я уменьшу это число до 2149000, программа будет вести себя так, как ожидалось:
0
100
200
300
400
500
600
700
800
900
cout не нужен для воспроизведения такого поведения, поэтому я полагаю, что минимальный пример на самом деле
#include <vector>
int main()
{
std::vector<int> vec;
for(int i = 0; i < 1000; i++)
{
vec.push_back(2150000 * i);
}
}
Выполнение этого заставляет программу ждать долгое время, а затем аварийно завершает работу.
Вопрос
Я новичок в C++ на любом серьезном уровне. Я делаю здесь что-то глупое, допускающее неопределенное поведение, и если да, то что? Или это ошибка в gcc?
Я действительно пытался погуглить, но я действительно не знаю, что гуглить.
Дополнение
Я вижу, что (подписанное) целочисленное переполнение - это неопределенное поведение в C++. Насколько я понимаю, это будет означать только то, что поведение выражения
21500000 * i
не определено, то есть может быть вычислено до произвольного числа. Тем не менее, мы видим, что это выражение, по крайней мере, не меняет значение i.
«Насколько я понимаю, это будет означать только то, что поведение выражения 21500000 * i не определено, т.е. что оно может быть оценено произвольным числом». Это неверно. Как только программа достигает неопределенного поведения, все ее поведение прошлое, настоящее и будущее также становится неопределенным.
Есть несколько проходов, которые находят UB и преобразуют цикл в бесконечный. В моем тестировании g++ -O2 x.cc -fno-tree-vrp -fdisable-tree-cunrolli -fdisable-tree-cunroll требуется для получения «ожидаемого» результата, поэтому распространение и развертывание диапазона значений являются «нарушителями».
Интересный факт: clang 6.0 с -O2 работает нормально, но с -O3 ничего не выводит :) Clang 7.0 работает как с -O2, так и с -O3, как и ожидалось.
Последнее умножение - 999, а не 1000, и 2149000 * 999 находится в пределах целого диапазона.
Ответы 1
Чтобы ответить на мой собственный вопрос, после изучения вывода ассемблера похоже, что g ++ оптимизирует этот цикл, изменив
for(int i = 0; i < 1000; i++)
{
vec.push_back(2150000 * i);
}
к чему-то вроде
for(int j = 0; j < 1000 * 2150000; j += 2150000)
{
vec.push_back(j);
}
Я предполагаю, что сложение происходит быстрее, чем умножение в каждом цикле, и правило о том, что переполнение является неопределенным поведением, означает, что это изменение может быть сделано, не беспокоясь о том, приведет ли это к неожиданному поведению, если это вычисление переполнится.
Конечно, условное выражение в оптимизированном цикле всегда терпит неудачу, поэтому в конечном итоге я получаю что-то вроде
for(int j = 0; true; j += 2150000)
{
vec.push_back(j);
}
Это работает как ментальная модель, но на самом деле условие цикла исчезает после прохода раннего распространения диапазона значений, задолго до того (в моем случае между ними 63 прохода!) Оптимизация индукционной переменной имеет шанс уменьшить умножение до сложения. .
Вы можете добавить ответ, объясняющий, что это значит?
Извините, у меня есть только общее представление о том, как работают проходы компилятора, я не знаю достаточно, чтобы превратить это в хороший ответ.
Согласно опубликованному документу Rationale для стандарта C, авторы ожидали (и, по-видимому, думали, что другие люди будут вправе ожидать), что большинство реализаций C будут обрабатывать целочисленное переполнение без побочных эффектов, но gcc обрабатывает программы. таким образом, что целочисленное переполнение может иметь непредсказуемые побочные эффекты даже в тех случаях, когда верхние биты результата игнорируются (например, при назначении продукта двух unsigned short на unsigned - случай, когда Обоснование описывает то, что авторы ожидали быть типичным поведением].
Я предлагаю вам посмотреть на различия в выводе сборки и использовать отладчик, и если вы еще не решили свою проблему, вы можете спросить. Я не могу воспроизвести это, например.