Как gcc оптимизирует этот цикл? - PullRequest
Новая
       22

Как gcc оптимизирует этот цикл?

0 голосов
/ 16 октября 2018

Поэтому я столкнулся с некоторым странным поведением, которое я сократил до следующего минимального примера: 

#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?

Я пытался это Google, но я не знаю, что с Google.

Приложение

Я вижу, что целочисленное переполнение (со знаком) - неопределенное поведение в C ++.Насколько я понимаю, это будет означать только то, что поведение выражения 

21500000 * i

не определено, т. Е. Оно может принимать произвольное число.Тем не менее, мы можем видеть, что это выражение, по крайней мере, не меняет значение i.

1 Ответ

0 голосов
/ 16 октября 2018

Чтобы ответить на мой собственный вопрос, после изучения вывода на ассемблере похоже, что 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);
}
...