Петля с нулевым временем выполнения

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

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

Примеры

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

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

скомпилированный с gcc 4.9 с использованием флага -O3 основном заканчивается сокращением до следующего ( см. его в прямом эфире ):

 main: xorl %eax, %eax # ret 

Практически все оптимизационные разрешения попадают под правило as-if , единственным исключением, о котором я знаю, является копия elison, которой разрешено осуществлять наблюдаемое поведение.

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

 #include  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 # 

Мы видим, что в этом нет никакого цикла.

Где такое, как правило, в стандарте

Правило as-if рассматривается в проекте стандарта C99 5.1.2.3 Выполнение программы, в котором говорится:

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

Правило as-if также применимо к C ++, gcc также даст тот же результат в режиме C ++. Проект стандарта C ++ охватывает это в разделе 1.9 Исполнение программы :

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

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

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

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

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

  • Файловый ввод-вывод с streamами - лучший размер буфера памяти
  • Big O, как вы его вычисляете / приближаете?
  • Самый эффективный способ увидеть, содержит ли ArrayList объект в Java
  • Как быстро определить, переопределен ли метод в Java
  • Что означают термины «граница процессора» и «граница ввода-вывода»?
  • Наиболее эффективный способ преобразования String в Integer в java
  • Interesting Posts

    Что такое независимые ассоциации и ассоциации с иностранными ключами?

    Указанный член типа «Дата» не поддерживается в LINQ to Exities Exception

    Сохранение ссылок на объекты при преобразовании XML с помощью XSLT?

    C # реализация глубокого / рекурсивного сравнения объектов в .net 3.5

    Использование переменной iteratorа цикла foreach в выражении lambda – почему не удается?

    Mac OS X для VirtualBox

    Создание XML-сопоставлений из свободного Nhibernate

    Как написать новый символ строки в файл в Java

    Изменить существующий контент XML в C #

    Как включить режим AHCI после установки Windows Vista в режиме IDE и до / для Windows 7 чистой установки?

    Как я могу запустить стартапы и посмотреть, какие процессы занимают дольше всего?

    BigInteger – Hex / Decimal / Octal / Binary string?

    Автоматическая передача файлов с использованием метода проверки ответа на запрос

    Программа не может найти libgcc_s_dw2-1.dll

    В чем разница между сигмацией и сигналом?

    Давайте будем гением компьютера.