Оптимизация с помощью & ldquo; while (1); & rdquo; в C ++ 0x

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

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

volatile int dummy_side_effect;

while (1) {
    dummy_side_effect = 0;
}

printf("Never prints.\n");

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

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

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

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

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

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

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

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

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

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

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

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

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);

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

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