실행 시간이 0인 루프

실행 시간이 0인 루프

실행 시간이 0인 루프를 가질 수 있습니까?빈 루프에도 오버헤드가 있기 때문에 실행 시간이 있다고 생각합니다.

네, as-if 규칙 하에서 컴파일러는 코드의 관찰 가능한 동작을 에뮬레이트할 의무가 있기 때문에 관찰 가능한 동작이 없는 루프가 있으면 완전히 최적화되어 실행 시간이 0이 됩니다.

예

예를 들어 다음과 같은 코드입니다.

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

와 함께 컴파일된.gcc 4.9사용방법-O3플래그는 기본적으로 다음과 같이 감소합니다(실시간 참조).

main:
  xorl  %eax, %eax  #
  ret

허용되는 거의 모든 최적화는 as-if 규칙에 속하지만, 내가 알고 있는 유일한 예외는 관찰 가능한 동작에 영향을 줄 수 있는 복사 엘리슨입니다.

다른 예로는 데드 코드 제거가 있습니다. 데드 코드 제거는 컴파일러가 절대 실행되지 않는다는 것을 증명할 수 있습니다.예를 들어, 다음 루프는 실제로 부작용을 포함하고 있지만 실행하지 않음을 증명할 수 있기 때문에 최적화될 수 있습니다(실시간 참조).

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

루프가 포함되어 있지 않은 것을 알 수 있습니다.

현재 규칙은 표준에서 다루어집니까?

as-if 규칙은 초안 C99 표준 섹션에서 설명합니다.5.1.2.3 다음과 같은 프로그램 실행:

추상기계에서 모든 표현은 의미론에 의해 지정된 대로 평가된다.실제 구현에서는 그 값이 사용되지 않고 필요한 부작용이 발생하지 않는다고 추론할 수 있는 경우(함수를 호출하거나 휘발성 객체에 액세스하여 발생하는 부작용 포함)에는 표현의 일부를 평가할 필요가 없습니다.

as-if 규칙은 C++에도 적용됩니다.gccC++ 모드에서도 같은 결과를 얻을 수 있습니다.C++ 드래프트 규격에서는, 이 점에 대해 설명합니다.1.9 프로그램 실행:

이 국제 표준의 의미 설명은 매개 변수화된 비결정론적 추상 기계를 정의한다.본 국제표준은 적합 구현 구조에 대해 어떠한 요구사항도 두지 않는다.특히 추상 기계의 구조를 복사하거나 에뮬레이트할 필요가 없습니다.그 대신에, 이하의 설명에 따라서, 추상 머신의 관측 가능한 동작을 에뮬레이트(만)하기 위해서, 준거한 실장이 필요합니다.5

네 - 컴파일러가 루프가 데드코드(실행하지 않음)라고 판단했을 경우 해당 코드는 생성되지 않습니다.이 루프는 엄밀히 말하면 머신 코드레벨에는 존재하지 않지만 실행시간이 0이 됩니다.

컴파일러 최적화뿐만 아니라 일부 CPU 아키텍처, 특히 DSP에는 오버헤드루프가 없기 때문에 하드웨어에 의해 반복 횟수가 고정된 루프가 효율적으로 최적화되어 있습니다(http://www.dsprelated.com/showmessage/20681/1.php 참조).

컴파일러는 부작용이 없고 결과가 폐기된 표현식 또는 표현식의 일부를 평가할 의무가 없습니다.

Harbison and Steel, C: 참조 매뉴얼

언급URL : https://stackoverflow.com/questions/26771692/loop-with-a-zero-execution-time