[c#] .NET / C #이 꼬리 호출 재귀를 최적화하지 않는 이유는 무엇입니까?

어떤 언어가 꼬리 재귀를 최적화하는지에 대한 질문을 찾았습니다 . 가능할 때마다 C #이 꼬리 재귀를 최적화하지 않는 이유는 무엇입니까?

구체적인 경우이 메서드가 루프로 최적화되지 않는 이유는 무엇입니까 ( 중요한 경우 Visual Studio 2008 32 비트) ?:

private static void Foo(int i)
{
    if (i == 1000000)
        return;

    if (i % 100 == 0)
        Console.WriteLine(i);

    Foo(i+1);
}

답변

JIT 컴파일은 컴파일 단계를 수행하는 데 너무 많은 시간을 소비하지 않는 것 (따라서 수명이 짧은 애플리케이션을 상당히 느리게하는 것)과 표준 사전 컴파일을 사용하여 장기적으로 애플리케이션 경쟁력을 유지하기에 충분한 분석을 수행하지 않는 것 사이의 까다로운 균형 작업입니다. .

흥미롭게도 NGen 컴파일 단계는 최적화에 더 적극적인 대상이 아닙니다. 나는 JIT 또는 NGen이 기계 코드를 담당했는지 여부에 따라 행동이 의존하는 버그를 원하지 않기 때문이라고 생각합니다.

CLR 자체가 지원 꼬리 호출 최적화를 수행하지만, 특정 언어 컴파일러 관련 생성하는 방법을 알고 있어야합니다 오피를 하고 JIT 그것을 존중 기꺼이해야합니다.
F #의 fsc는 관련 opcode를 생성합니다 (단순한 재귀의 경우 전체를 while루프로 직접 변환 할 수 있음 ). C #의 csc는 그렇지 않습니다.

자세한 내용은 이 블로그 게시물 을 참조 하십시오 (최근 JIT 변경 사항을 고려할 때 현재 구식 일 수 있음). 4.0의 CLR 변경 사항 은 x86, x64 및 ia64가이를 준수합니다 .

답변

이 Microsoft Connect 피드백 제출 은 귀하의 질문에 대한 답변을 제공합니다. 여기에는 Microsoft의 공식 응답이 포함되어 있으므로 그렇게하는 것이 좋습니다.

제안 해 주셔서 감사합니다. 우리는 C # 컴파일러 개발의 여러 지점에서 꼬리 호출 명령어를 방출하는 것을 고려했습니다. 그러나 지금까지 이것을 피해야하는 몇 가지 미묘한 문제가 있습니다. 1) 실제로 CLR에서 .tail 명령어를 사용하는 데는 사소한 오버 헤드 비용이 있습니다 (꼬리 호출이 궁극적으로되기 때문에 점프 명령어가 아닙니다. 테일 호출이 크게 최적화 된 기능적 언어 런타임 환경과 같이 덜 엄격한 환경에서). 2) 꼬리 호출을 방출하는 것이 합법적 인 실제 C # 메서드가 거의 없습니다 (다른 언어는 꼬리 재귀가 더 많은 코딩 패턴을 권장합니다. 꼬리 호출 최적화에 크게 의존하는 많은 사람들이 꼬리 재귀의 양을 늘리기 위해 실제로 전역 재 작성 (예 : 연속 전달 변환)을 수행합니다. 3) 부분적으로는 2)로 인해 성공해야하는 깊은 재귀로 인해 C # 메서드가 스택 오버플로되는 경우는 매우 드뭅니다.

즉, 우리는 계속해서 이것을 살펴보고, 컴파일러의 향후 릴리스에서 .tail 명령어를 내보내는 것이 합당한 패턴을 찾을 수 있습니다.

그건 그렇고, 지적했듯이 꼬리 재귀 가 x64에서 최적화 된다는 점에 주목할 가치가 있습니다.

답변

C #은 꼬리 호출 재귀를 최적화하지 않습니다. F #이 그 이유이기 때문입니다!

C # 컴파일러가 마무리 호출 최적화를 수행하지 못하게하는 조건에 대한 자세한 내용은이 문서 : JIT CLR 마무리 호출 조건을 참조하십시오 .

C #과 F # 간의 상호 운용성

C #과 F #은 매우 잘 상호 운용되며 .NET CLR (공용 언어 런타임)은 이러한 상호 운용성을 염두에두고 설계 되었기 때문에 각 언어는 그 의도와 목적에 맞는 최적화로 설계되었습니다. C # 코드에서 F # 코드를 호출하는 것이 얼마나 쉬운 지 보여주는 예제는 C # 코드에서 F # 코드 호출을 참조하십시오 . F # 코드에서 C # 함수를 호출하는 예는 F #에서 C # 함수 호출을 참조하세요 .

대리자 상호 운용성에 대해서는이 문서 : F #, C # 및 Visual Basic 간의 상호 운용성 위임을 참조하십시오 .

C #과 F #의 이론적, 실제적 차이점

다음은 몇 가지 차이점을 다루고 C #과 F # 간의 마무리 호출 재귀의 디자인 차이점을 설명하는 문서입니다. C # 및 F #에서 마무리 호출 Opcode 생성 .

다음은 C #, F # 및 C ++ \ CLI의 몇 가지 예제가 포함 된 문서입니다. Adventures in Tail Recursion in C #, F # 및 C ++ \ CLI

이론상의 주요 차이점은 C #은 루프로 설계되었지만 F #은 Lambda 미적분 원칙에 따라 설계되었다는 것입니다. Lambda 미적분의 원리에 대한 아주 좋은 책은 Abelson, Sussman 및 Sussman의 무료 책 : Structure and Interpretation of Computer Programs,를 참조하십시오 .

F #의 마무리 호출에 대한 매우 좋은 소개 문서는 F #의 마무리 호출에 대한 자세한 소개 문서를 참조하세요 . 마지막으로 비 꼬리 재귀와 꼬리 호출 재귀 (F #)의 차이점을 다루는 기사가 있습니다 : 꼬리 재귀 대 꼬리가없는 재귀 F 날카로운 .

답변

최근에 64 비트 용 C # 컴파일러가 꼬리 재귀를 최적화한다고 들었습니다.

C #도 이것을 구현합니다. 항상 적용되지 않는 이유는 꼬리 재귀를 적용하는 데 사용되는 규칙이 매우 엄격하기 때문입니다.

답변

C # (또는 Java)에서 꼬리 재귀 함수에 트램폴린 기술 을 사용할 수 있습니다 . 그러나 더 나은 솔루션 (스택 활용에 관심이있는 경우) 은이 작은 도우미 메서드를 사용 하여 동일한 재귀 함수의 일부를 래핑하고 함수를 읽기 쉽게 유지하면서 반복적으로 만드는 것입니다.

답변

다른 답변에서 언급했듯이 CLR은 테일 콜 최적화를 지원하며 역사적으로 점진적인 개선을 겪은 것 같습니다. 그러나 C #에서 지원하는 것은 ProposalC # 프로그래밍 언어 Support tail recursion # 2544 의 설계를 위해 git 저장소에 공개 된 문제가 있습니다 .

여기에서 유용한 세부 정보와 정보를 찾을 수 있습니다. 예를 들어 @jaykrell이 언급되었습니다.

내가 아는 것을 알려주세요.

때때로 tailcall은 성능 윈윈입니다. CPU를 절약 할 수 있습니다. jmp는 call / ret보다 저렴합니다. 스택을 절약 할 수 있습니다. 더 적은 스택을 만지면 더 나은 지역성을 만듭니다.

때때로 tailcall은 성능 손실, 스택 승리입니다. CLR에는 호출자가 수신 한 것보다 더 많은 매개 변수를 호출자에게 전달하는 복잡한 메커니즘이 있습니다. 특히 매개 변수를위한 더 많은 스택 공간을 의미합니다. 이것은 느립니다. 그러나 스택을 절약합니다. 이것은 꼬리로만 할 것입니다. 접두사.

호출자 매개 변수가 수신자 매개 변수보다 스택 크기가 큰 경우 일반적으로 매우 쉬운 윈-윈 변환입니다. 매개 변수 위치가 관리 형에서 정수 / 부동 수로 변경되고 정확한 StackMaps 등을 생성하는 것과 같은 요인이있을 수 있습니다.

이제 고정 / 작은 스택으로 임의의 큰 데이터를 처리 할 수 있도록 테일 콜 제거를 요구하는 알고리즘의 또 다른 각도가 있습니다. 이것은 성능에 관한 것이 아니라 실행 능력에 관한 것입니다.

또한 (추가 정보로) 언급하겠습니다. System.Linq.Expressions네임 스페이스의 표현식 클래스를 사용하여 컴파일 된 람다를 생성 할 때 ‘tailCall’이라는 인수가 있습니다.

생성 된 표현식을 컴파일 할 때 마무리 호출 최적화가 적용 될지 여부를 나타내는 부울입니다.

나는 아직 시도하지 않았고 귀하의 질문과 관련하여 어떻게 도움이 될 수 있는지 확실하지 않지만 아마도 누군가가 시도해 볼 수 있으며 일부 시나리오에서 유용 할 수 있습니다.


var myFuncExpression = System.Linq.Expressions.Expression.Lambda<Func< … >>(body: … , tailCall: true, parameters: … );

var myFunc =  myFuncExpression.Compile();