Цикл с нулевым временем выполнения

Question

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

Answer 1

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

Примеры

Например, следующий код:

int main()
{
  int j = 0 ;
  for( int i = 0; i < 10000; ++i )
  {
    ++j ;
  }
}

составлено с gcc 4.9 с использованием -O3 Флаг в основном сводится к следующему ( смотрите его вживую):

main:
  xorl  %eax, %eax  #
  ret

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

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

#include <stdio.h>

int main()
{
  int j = 0 ;
  if( false ) // The loop will never execute
  {
    for( int i = 0; i < 10000; ++i )
    {
      printf( "%d\n", j ) ;
      ++j ;
    }
  }
}

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

int j = 0 ;
for( int i = 0; i < 10000; ++i )
{
  ++j ;
}
printf( "%d\n", j ) ;

можно оптимизировать до ( посмотреть вживую):

movl    $10000, %esi    #,
movl    $.LC0, %edi #,
xorl    %eax, %eax  #
call    printf  #

Мы видим, что в этом нет петли.

Где как-будто правило, охватываемое стандартом

Правило " как будто" описано в разделе стандарта C99. 5.1.2.3 Выполнение программы, которое говорит:

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

Правило " как будто" также применяется к C++, gcc выдаст тот же результат и в режиме C++. Проект стандарта C++ охватывает это в разделе 1.9 Выполнение программы:

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

Answer 2

Да - если компилятор определяет, что цикл является мертвым кодом (никогда не будет выполняться), он не будет генерировать для него код. Этот цикл будет иметь 0 времени выполнения, хотя, строго говоря, он не существует на уровне машинного кода.

Answer 3

Наряду с оптимизацией компилятора, некоторые архитектуры ЦП, в частности DSP, имеют нулевую циклическую нагрузку, благодаря которой цикл с фиксированным числом итераций эффективно оптимизируется аппаратными средствами, см., Например, http://www.dsprelated.com/showmessage/20681/1.php

Answer 4

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

Харбисон и Стил, C: Справочное руководство