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

Ответ 1

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

Да, Hans Boehm объясняет это в N1528: Почему поведение undefined для бесконечных циклов?, хотя это документ WG14 обоснование также относится к С++, а документ относится как к WG14, так и к РГ21:

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

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

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

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

или

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

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

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

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

Ответ 2

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

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

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

EDIT: немой пример:

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) является проблемой остановки. С помощью предложения он может считать, что цикл завершается и получает выигрыш в параллелизации.

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

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

EDIT: в отношении проницательной статьи, которую вы сейчас связываете, я бы сказал, что "компилятор может предположить, что X о программе" логически эквивалентен "если программа не удовлетворяет X, поведение undefined", Мы можем показать это следующим образом: предположим, что существует программа, которая не удовлетворяет свойству X. Где будет определяться поведение этой программы? Стандарт определяет только поведение, предполагающее, что свойство X истинно. Хотя в стандарте явно не указано поведение undefined, он объявил его undefined отсутствием.

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

Ответ 3

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

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

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

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

Ответ 4

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

Ответ 5

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

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

volatile int dummy_side_effect;

while (1) {
    dummy_side_effect = 0;
}

printf("Never prints.\n");

Ответ 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);

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

Ответ 7

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

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

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

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

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

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

Ответ 8

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

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