Оптимизация «время (1);» в C ++ 0x

Обновлено, смотрите ниже!

Я слышал и читал, что 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Трюк будет не работать больше!

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

Да, Ганс Бём приводит обоснование этого в 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;
}

Могут ли эти два цикла быть объединены и заменены следующим циклом?

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.

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

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

Предположительно, это связано с тем, что механическое доказательство завершения затруднено , а невозможность доказать завершение мешает компиляторам, которые в противном случае могли бы выполнять полезные преобразования, такие как перемещение независимых операций из цикла перед циклом в цикл после и наоборот, выполнение операций после цикла в одном потоке, пока цикл выполняется в другом, и так далее. Без этих преобразований цикл может блокировать все другие потоки, пока они ожидают, пока один поток завершит указанный цикл. (Я использую «поток» свободно для обозначения любой формы параллельной обработки, включая отдельные потоки команд 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 более одного раза между точками последовательности не определено».

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

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

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

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

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

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

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

volatile int dummy_side_effect;

while (1) {
    dummy_side_effect = 0;
}

printf("Never prints.\n");

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

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 ++; иначе, если (c> b) {a = 1; б ++}; еще {а = 1; B = 1; C ++};
  }
  printf («Результат есть»);
  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 ++; иначе, если (c> b) {a = 1; б ++}; еще {а = 1; B = 1; C ++};
    }
    signal_other_thread_and_die ();
  }
  else // Второй поток
  {
    printf («Результат есть»);
    wait_for_other_thread ();
  }
  printf («% d /% d /% d», a, b, c);
}

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

  int total = 0;
  для (i = 0; num_reps> i; i ++)
  {
    update_progress_bar (я);
    всего + = do_something_slow_with_no_side_effects (I);
  }
  show_result (всего);

станет

  int total = 0;
  if (fork_is_first_thread ())
  {
    для (i = 0; num_reps> i; i ++)
      всего + = do_something_slow_with_no_side_effects (I);
    signal_other_thread_and_die ();
  }
  еще
  {
    для (i = 0; num_reps> i; i ++)
      update_progress_bar (я);
    wait_for_other_thread ();
  }
  show_result (всего);

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

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

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

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

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

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

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

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

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