Оптимизация "while (1);" в C ++ 0x

Question

Обновлено, см. Ниже!

Я слышал и читал, что C ++ 0x позволяет компилятору напечатать "Hello" для следующего фрагмента

#include <iostream>

int main() {
  while(1) 
    ;
  std::cout << "Hello" << std::endl;
}

По-видимому, это связано с потоками и возможностями оптимизации.Мне кажется, что это может удивить многих людей.

Есть ли у кого-нибудь хорошее объяснение того, почему это необходимо было разрешить?Для справки, самый последний черновик C ++ 0x говорит в 6.5/5

Цикл, который вне оператора for-init-в случае оператора for,

• не вызывает функции библиотечного ввода-вывода, а
• не обращается к изменяемым объектам и не изменяет их, а
• не выполняет операций синхронизации (1.10) или атомарных операций (пункт 29)

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

Редактировать:

В этой проницательной статье говорится об этом тексте стандартов

К сожалению, слова «неопределенное поведение» не используются.Однако всякий раз, когда стандарт говорит, что «компилятор может принять P», подразумевается, что программа, обладающая свойством not-P, имеет неопределенную семантику.

Это правильно, и разрешено ли компиляторунапечатать «Пока» для вышеуказанной программы?

---

Здесь есть еще более проницательный поток , который примерно аналогичен изменению C, начатому парнем, сделавшим вышеописанное.связанная статья.Среди других полезных фактов они представляют решение, которое, похоже, также применимо к C ++ 0x ( Обновление : это больше не будет работать с n3225 - см. Ниже!)

endless:
  goto endless;

Кажется, компилятору не разрешается оптимизировать это, потому что это не цикл, а скачок.Другой парень резюмирует предлагаемое изменение в C ++ 0x и C201X

Записывая цикл, программист утверждает либо , что цикл выполняет что-то с видимым поведением (выполняет I /O, получает доступ к энергозависимым объектам или выполняет синхронизацию или атомарные операции), или , которые в конечном итоге завершаются.Если я нарушу это предположение, написав бесконечный цикл без побочных эффектов, я лгу компилятору, и поведение моей программы не определено.(Если мне повезет, компилятор может предупредить меня об этом.) Язык не предоставляет (больше не предоставляет?) Способ выражения бесконечного цикла без видимого поведения.

---

Обновление 3.1.2011 с n3225: Комитет переместил текст в 1.10 / 24 и сказал:

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

• завершить,
• сделать вызов функции ввода-вывода библиотеки,
• получить доступ или изменить энергозависимый объект, или
• выполняет операцию синхронизации или атомарную операцию.

Трюк goto будет не работать больше!

Answer 1

Для меня соответствующее обоснование:

Это предназначено для разрешения преобразований компилятора, таких как удаление пустых циклов, даже если завершение не может быть доказано.

Предположительно, это потому, что механическое доказательство завершения является трудным , а невозможность доказать завершение мешает компиляторам, которые в противном случае могли бы сделать полезные преобразования, такие как перемещение независимых операций от цикла до цикла к циклу после или наоборот, выполнение операций после цикла в одном потоке, в то время как цикл выполняется в другом, и так далее. Без этих преобразований цикл может блокировать все остальные потоки, пока они ожидают, пока один поток завершит указанный цикл. (Я использую «поток» свободно для обозначения любой формы параллельной обработки, включая отдельные потоки команд VLIW.)

РЕДАКТИРОВАТЬ: тупой пример:

while (complicated_condition()) {
    x = complicated_but_externally_invisible_operation(x);
}
complex_io_operation();
cout << "Results:" << endl;
cout << x << endl;

Здесь, один поток будет быстрее выполнять complex_io_operation, в то время как другой выполняет все сложные вычисления в цикле. Но без процитированного вами предложения компилятор должен доказать две вещи, прежде чем он сможет выполнить оптимизацию: 1) что complex_io_operation() не зависит от результатов цикла, и 2) , что цикл завершится . Доказательство 1) довольно просто, доказательство 2) является проблемой остановки. С помощью этого предложения он может предположить, что цикл завершается и получить выигрыш при распараллеливании.

Я также представляю, что разработчики считали, что случаи, когда бесконечные циклы происходят в производственном коде, очень редки и обычно представляют собой такие вещи, как управляемые событиями циклы, которые каким-то образом обращаются к вводу / выводу. В результате они пессимизировали редкий случай (бесконечные циклы) в пользу оптимизации более распространенного случая (бесконечный, но трудно механически доказать бесконечный цикл).

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

РЕДАКТИРОВАТЬ: в отношении проницательной статьи, на которую вы сейчас ссылаетесь, я бы сказал, что «компилятор может предположить, что X о программе» логически эквивалентно «если программа не удовлетворяет X, поведение не определено». Мы можем показать это следующим образом: предположим, что существует программа, которая не удовлетворяет свойству X. Где будет определено поведение этой программы? Стандарт определяет поведение только при условии, что свойство X истинно. Хотя Стандарт не объявляет явное поведение как неопределенное, он объявляет его неопределенным из-за упущения.

Рассмотрим аналогичный аргумент: «компилятор может предположить, что переменная x назначается не более одного раза между точками последовательности», что эквивалентно «назначению x более одного раза между точками последовательности не определено».

Answer 2

Есть ли у кого-нибудь хорошее объяснение того, почему это необходимо было разрешить?

Да, Ганс Бём приводит обоснование этого в N1528: Почему неопределенное поведение для бесконечных циклов? , хотя это документ WG14, логическое обоснование применимо и к C ++, и документ ссылается как на WG14, так и на WG21:

Как правильно указывает N1509, текущий черновик по существу дает неопределенное поведениебесконечные циклы в 6.8.5p6.Основной проблемой для этого является то, что он позволяет коду перемещаться по потенциально не завершающемуся циклу.Например, предположим, что у нас есть следующие циклы, где count и count2 - глобальные переменные (или у них был взят их адрес), а p - локальная переменная, адрес которой не был взят:

for (p = q; p != 0; p = p -> next) {
    ++count;
}
for (p = q; p != 0; p = p -> next) {
    ++count2;
}

Couldэти два цикла объединяются и заменяются следующим циклом?

for (p = q; p != 0; p = p -> next) {
        ++count;
        ++count2;
}

Без специального разрешения в 6.8.5p6 для бесконечных циклов это будет запрещено: если первый цикл не завершается, поскольку q указывает накруговой список, оригинал никогда не пишет в count2.Таким образом, он может быть запущен параллельно с другим потоком, который обращается или обновляет count2.Это больше не безопасно с преобразованной версией, которая делает доступ к count2, несмотря на бесконечный цикл.Таким образом, преобразование потенциально представляет гонку данных.

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

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

Существуют также явные циклы for с целочисленной переменной цикла, в которых компилятору будет трудно доказать завершение, и этоТаким образом, компилятору будет трудно реструктурировать циклы без 6.8.5p6.Даже что-то вроде

for (i = 1; i != 15; i += 2)

или

for (i = 1; i <= 10; i += j)

кажется нетривиальным в обращении.(В первом случае для доказательства завершения требуется некоторая базовая теория чисел, во втором случае нам нужно что-то знать о возможных значениях j, чтобы сделать это. Обтекание целых чисел без знака может усложнить некоторые из этих рассуждений.)

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

Одно существенное отличиес C это то, что C11 предоставляет исключение для управления выражениями, которые являются константными выражениями , что отличается от C ++ и делает ваш конкретный пример хорошо определенным в C11.

Answer 3

Я думаю, что правильная интерпретация - та, что из вашего редактирования: пустые бесконечные циклы - неопределенное поведение.

Я бы не сказал, что это особенно интуитивное поведение, но эта интерпретация имеет больше смысла, чем альтернативная, так как компилятору произвольно разрешено игнорировать бесконечные циклы без вызова UB.

Если бесконечные циклы - это UB, это просто означает, что не завершающиеся программы не считаются значимыми: в соответствии с C ++ 0x они не имеют семантики.

Это тоже имеет определенный смысл.Это особый случай, когда ряд побочных эффектов просто больше не возникает (например, ничего не возвращается из main), а ряду оптимизаций компилятора препятствует необходимость сохранять бесконечные циклы.Например, перемещение вычислений по циклу вполне допустимо, если цикл не имеет побочных эффектов, потому что в конечном итоге вычисления будут выполняться в любом случае.Но если цикл никогда не завершается, мы не можем безопасно переставить код через него, потому что мы могли бы просто изменить, какие операции на самом деле выполняются до зависания программы.Если только мы не рассматриваем зависшую программу как UB, то есть.

Answer 4

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

Я считаю, что это правильный подход.Спецификация языка определяет способы обеспечения порядка выполнения.Если вы хотите бесконечный цикл, который нельзя переупорядочить, напишите:

volatile int dummy_side_effect;

while (1) {
    dummy_side_effect = 0;
}

printf("Never prints.\n");

Answer 5

Я думаю, что это похоже на этот тип вопрос , который ссылается на другой поток . Оптимизация может иногда удалять пустые циклы.

Answer 6

Я думаю, что эту проблему лучше всего сформулировать следующим образом: «Если более поздняя часть кода не зависит от более ранней части кода, а более ранняя часть кода не имеет побочных эффектов ни в какой другой части системы, выходные данные компилятора могут выполнить более позднюю часть кода до, после или смешанным с выполнением первого, даже если первый содержит циклы, без учета того, когда или действительно первый код завершит . Например, компилятор может переписать:

void testfermat(int n)
{
  int a=1,b=1,c=1;
  while(pow(a,n)+pow(b,n) != pow(c,n))
  {
    if (b > a) a++; else if (c > b) {a=1; b++}; else {a=1; b=1; c++};
  }
  printf("The result is ");
  printf("%d/%d/%d", a,b,c);
}

в

void testfermat(int n)
{
  if (fork_is_first_thread())
  {
    int a=1,b=1,c=1;
    while(pow(a,n)+pow(b,n) != pow(c,n))
    {
      if (b > a) a++; else if (c > b) {a=1; b++}; else {a=1; b=1; c++};
    }
    signal_other_thread_and_die();
  }
  else // Second thread
  {
    printf("The result is ");
    wait_for_other_thread();
  }
  printf("%d/%d/%d", a,b,c);
}

Как правило, это не лишено смысла, хотя я мог бы волноваться, что:

  int total=0;
  for (i=0; num_reps > i; i++)
  {
    update_progress_bar(i);
    total+=do_something_slow_with_no_side_effects(i);
  }
  show_result(total);

станет

  int total=0;
  if (fork_is_first_thread())
  {
    for (i=0; num_reps > i; i++)
      total+=do_something_slow_with_no_side_effects(i);
    signal_other_thread_and_die();
  }
  else
  {
    for (i=0; num_reps > i; i++)
      update_progress_bar(i);
    wait_for_other_thread();
  }
  show_result(total);

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

Answer 7

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

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

Answer 8

Это не разрешимо для компилятора для нетривиальных случаев, если это вообще бесконечный цикл.

В разных случаях может случиться, что ваш оптимизатор достигнет более высокого класса сложности для вашего кода (например, это был O (n ^ 2), и вы получите O (n) или O (1) после оптимизации).

Таким образом, включение в правило C ++ такого правила, которое запрещает удаление бесконечного цикла, сделало бы невозможной многие оптимизации. И большинство людей этого не хотят. Я думаю, что это вполне отвечает на ваш вопрос.

---

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

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

Если вам известен какой-либо действительный / хороший пример, где вам нужен бесконечный цикл, который ничего не делает, пожалуйста, скажите мне.