[C++] C ++ 컴파일러가 꼬리 재귀 최적화를 수행합니까?


Answers

현재 버전의 VC ++과 GCC는 꼬리 호출 최적화를 상당히 잘 수행하며 상호 재귀 호출도 마찬가지입니다. Intel 컴파일러도 마찬가지입니다.

컴파일러가 최적화를 수행하게하는 것은 간단합니다. 속도 최적화를 켜십시오. 하지만 어쨌든 그렇게하지? ;-)

  • MSVC의 경우 / O2 또는 / Ox을 사용하십시오.
  • GCC의 경우 -O3을 사용하십시오.

컴파일러가 (내가 알고있는) 최적화를 수행했는지 확인하는 가장 쉬운 방법은 그렇지 않으면 스택 오버플로가 발생하거나 어셈블리 출력을 보는 호출을 수행하는 것입니다. 그러나 일반적으로 컴파일러가 최적화를 수행했다고 가정 할 수는 없습니다.

/ EDIT : Mark Probst의 졸업 논문 을 통해 GCC에 C의 테일 호출 최적화가 추가되었습니다. 이 논문은 구현에서 흥미로운 몇 가지주의 사항을 설명합니다. 그것은 읽을만한 가치가 있습니다.

Question

C와 C ++ 모두에서 tail-recursion 최적화를 수행하는 것이 완벽하게 잘 작동하는 것으로 보입니다. 그러나 디버깅하는 동안이 최적화를 나타내는 프레임 스택을 보지 못했습니다. 스택은 재귀가 얼마나 깊은 지 알려주기 때문에 일종의 좋은 방법입니다. 그러나 최적화도 훌륭합니다.

C ++ 컴파일러가이 최적화를 수행합니까? 왜? 왜 안돼?

컴파일러에게 어떻게 할 것인가?

  • MSVC의 경우 : / O2 또는 / Ox
  • GCC의 경우 : -O2 또는 -O3

컴파일러가 어떤 경우에 이것을 수행했는지 확인하는 것은 어떻습니까?

  • MSVC의 경우 PDB 출력을 활성화하여 코드를 추적 한 다음 코드를 검사합니다.
  • GCC ..의 경우?

나는 여전히 특정 함수가 컴파일러에 의해 이와 같이 최적화되었는지를 결정하는 방법에 대한 제안을하고 싶다. (비록 Konrad가 나에게 그것을 가정한다는 것을 안심할지라도)

컴파일러가 무한 재귀를 만들고 무한 루프 나 스택 오버플로를 일으키는 지 확인하면 컴파일러에서이 작업을 수행하는지 항상 확인할 수 있습니다 (GCC에서이 작업을 수행 한 결과 -O2가 충분하다는 사실을 알았지 만). 내가 알고있는 특정 기능을 확인하려면 어쨌든 종료됩니다. 나는 이것을 확인하기위한 쉬운 방법을 원한다. :)

몇 가지 테스트를 거친 후에, 나는 소멸자가이 최적화를 할 수있는 가능성을 망쳐 놓는다는 것을 발견했다. 특정 변수 및 임시 변수의 범위를 변경하여 return 문이 시작되기 전에 범위를 벗어나는 지 확인할 수있는 경우가 있습니다.

tail-call 후에 어떤 소멸자가 실행되어야한다면, tail-call optimization은 수행 될 수 없다.




대부분의 컴파일러는 디버그 빌드에서 어떤 종류의 최적화도하지 않습니다.

VC를 사용하는 경우 PDB 정보가 켜진 상태로 릴리스 빌드를 시도하십시오. 이렇게하면 최적화 된 응용 프로그램을 추적 할 수 있으므로 원하는 내용을 볼 수 있습니다. 그러나 최적화 된 빌드를 디버깅하고 추적하면 모든 곳을 뛰어 넘을 수 있으며 흔히 레지스터에서 끝나거나 완전히 최적화 된 상태로 변수를 직접 검사 할 수 없습니다. 그것은 "재미있는"경험입니다 ...




gcc 4.3.2는 main() 에이 함수 (crappy / trivial atoi() 구현)를 완전히 인라인합니다. 최적화 수준은 -O1 입니다. 나는 그것으로 extern 는 것을 알아 차릴 수있다. (심지어는 static 에서 extern 바꾼다. 꼬리 재귀는 꽤 빨리 사라지므로 프로그램의 정확성에 의존하지 않을 것이다.

#include <stdio.h>
static int atoi(const char *str, int n)
{
    if (str == 0 || *str == 0)
        return n;
    return atoi(str+1, n*10 + *str-'0');
}
int main(int argc, char **argv)
{
    for (int i = 1; i != argc; ++i)
        printf("%s -> %d\n", argv[i], atoi(argv[i], 0));
    return 0;
}



Greg가 언급했듯이, 컴파일러는 디버그 모드에서이를 수행하지 않습니다. 디버그 빌드가 딱딱한 빌드보다 느린 것은 좋지만, 더 자주 충돌해서는 안됩니다. 꼬리 호출 최적화를 사용하는 경우 정확히 수행 할 수 있습니다. 이 때문에 꼬리 호출을 일반 루프로 다시 작성하는 것이 가장 좋습니다. :-(




명백한 (컴파일러는 요구하지 않는 한 이런 종류의 최적화를 수행하지 않는다.) C ++의 테일 콜 최적화에 대한 복잡성은 소멸자이다.

주어진 것과 같이 :

   int fn(int j, int i)
   {
      if (i <= 0) return j;
      Funky cls(j,i);
      return fn(j, i-1);
   }

컴파일러는 재귀 호출이 반환 된 후에 cls 의 소멸자를 호출해야하므로 (일반적으로) 꼬리 호출을 최적화 할 수 없습니다.

때때로 컴파일러는 소멸자가 외부에서 볼 수있는 부작용이 없다는 것을 볼 수 있지만 (그렇게 빨리 처리 할 수는 있지만) 종종 그렇게 할 수 없습니다.

이 중 특히 일반적인 형태는 Funky 가 실제로 std::vector 또는 이와 유사한 부분입니다.