실행 시간이없는 루프

실행 시간이없는 루프

---

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

---

예, as-if 규칙에 따라 컴파일러는 코드의 관찰 가능한 동작 만 에뮬레이션 할 의무가 있으므로 관찰 가능한 동작이없는 루프가있는 경우 완전히 최적화 될 수 있으므로 효과적으로 실행 시간이 0이됩니다. .

예

예를 들어 다음 코드 :

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

플래그 를 gcc 4.9사용하여 컴파일 하면 -O3기본적으로 다음과 같이 줄어 듭니다 ( live 참조 ).

main:
  xorl  %eax, %eax  #
  ret

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

다른 예에는 컴파일러가 실행되지 않을 것이라는 것을 증명할 수있는 코드를 제거 할 수있는 데드 코드 제거 가 포함 됩니다. 예를 들어 다음 루프에 실제로 부작용이 포함되어 있어도 실행되지 않을 것임을 증명할 수 있으므로 최적화 할 수 있습니다 ( live를 참조하십시오 ).

#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 프로그램 실행 말한다 :

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

규칙 것처럼- 에도 적용 C ++, gccC ++ 모드에서 동일한 결과를 생성 할뿐만 아니라. C ++ 초안 표준은 1.9 프로그램 실행 섹션에서이를 다룹니다 .

The semantic descriptions in this International Standard define a parameterized nondeterministic abstract machine. This International Standard places no requirement on the structure of conforming implementations. In particular, they need not copy or emulate the structure of the abstract machine. Rather, conforming implementations are required to emulate (only) the observable behavior of the abstract machine as explained below.5

---

Yes - if the compiler determines that the loop is dead code (will never execute) then it will not generate code for it. That loop will have 0 execution time, although strictly speaking it doesn't exist at the machine code level.

---

As well as compiler optimisations, some CPU architectures, particularly DSPs, have zero overhead looping, whereby a loop with a fixed number of iterations is effectively optimised away by the hardware, see e.g. http://www.dsprelated.com/showmessage/20681/1.php

---

The compiler is not obliged to evaluate the expression, or a portion of an expression, that has no side effects and whose result is discarded.

Harbison and Steele, C: A Reference Manual

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