테일 콜 최적화 란 무엇입니까?

StackOverflow https://stackoverflow.com/questions/310974

문제

간단히 말해서, 꼬리는 최적화 가란 무엇입니까? 보다 구체적으로, 누구나 적용 할 수있는 작은 코드 스 니펫을 보여줄 수 있습니까?

도움이 되었습니까?

해결책

테일 콜 최적화는 호출 함수가 단순히 호출 된 함수에서 얻는 값을 반환하기 때문에 함수에 새 스택 프레임을 할당하는 것을 피할 수있는 곳입니다. 가장 일반적인 사용은 꼬리 추방으로, 테일 콜 최적화를 활용하기 위해 쓰여진 재귀 함수는 일정한 스택 공간을 사용할 수 있습니다.

체계는 모든 구현 이이 최적화를 제공해야한다는 사양에서 보장하는 몇 안되는 프로그래밍 언어 중 하나입니다. (JavaScript도 ES6부터 시작합니다), 다음은 체계의 요인 기능의 두 가지 예입니다.

(define (fact x)
  (if (= x 0) 1
      (* x (fact (- x 1)))))

(define (fact x)
  (define (fact-tail x accum)
    (if (= x 0) accum
        (fact-tail (- x 1) (* x accum))))
  (fact-tail x 1))

첫 번째 함수는 재귀 호출이 이루어질 때 호출이 반환 된 후 결과와 관련하여 곱셈을 추적해야하기 때문에 꼬리 재귀가 아닙니다. 따라서 스택은 다음과 같이 보입니다.

(fact 3)
(* 3 (fact 2))
(* 3 (* 2 (fact 1)))
(* 3 (* 2 (* 1 (fact 0))))
(* 3 (* 2 (* 1 1)))
(* 3 (* 2 1))
(* 3 2)
6

대조적으로, 꼬리 재귀 요인의 스택 추적은 다음과 같이 보입니다.

(fact 3)
(fact-tail 3 1)
(fact-tail 2 3)
(fact-tail 1 6)
(fact-tail 0 6)
6

보시다시피, 우리는 단순히 우리가 맨 위로 올바른 값을 반환하기 때문에 사실 꼬리에 대한 모든 호출에 대해 동일한 양의 데이터를 추적하면됩니다. 이것은 내가 전화를 걸더라도 (사실 1000000) (사실 3)과 같은 공간 만 필요하다는 것을 의미합니다. 이는 비 꼬리 수반 사실의 경우에는 해당되지 않으며, 그러한 큰 값으로 인해 스택 오버플로가 발생할 수 있습니다.

다른 팁

간단한 예를 살펴 보겠습니다 : C에서 구현 된 계승 기능

우리는 명백한 재귀 정의로 시작합니다

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    return n * fac(n - 1);
}

함수가 반환되기 전에 마지막 작업이 다른 함수 호출 인 경우 기능은 꼬리 호출로 끝납니다. 이 호출이 동일한 함수를 호출하면 꼬리 추론 적입니다.

일지라도 fac() 언뜻보기에 꼬리를 보이는 것처럼 보이면 실제로 일어나는 일이 아닙니다.

unsigned fac(unsigned n)
{
    if (n < 2) return 1;
    unsigned acc = fac(n - 1);
    return n * acc;
}

즉, 마지막 작업은 곱셈이며 함수 호출이 아닙니다.

그러나 다시 작성할 수 있습니다 fac() 누적 된 값을 추가 인수로 통화 체인 아래로 전달하고 최종 결과 만 다시 반환 값으로 전달함으로써 테일 리퍼링이 되려면 :

unsigned fac(unsigned n)
{
    return fac_tailrec(1, n);
}

unsigned fac_tailrec(unsigned acc, unsigned n)
{
    if (n < 2) return acc;
    return fac_tailrec(n * acc, n - 1);
}

자, 왜 이것이 유용한가? 테일 호출 후 즉시 돌아 오기 때문에 꼬리 위치에서 함수를 호출하기 전에 이전 스택 프레임을 폐기 할 수 있습니다.

테일 콜 최적화는 재귀 코드를 변환합니다

unsigned fac_tailrec(unsigned acc, unsigned n)
{
TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

이것은 감소 할 수 있습니다 fac() 그리고 우리는 도착합니다

unsigned fac(unsigned n)
{
    unsigned acc = 1;

TOP:
    if (n < 2) return acc;
    acc = n * acc;
    n = n - 1;
    goto TOP;
}

이는 동등합니다

unsigned fac(unsigned n)
{
    unsigned acc = 1;

    for (; n > 1; --n)
        acc *= n;

    return acc;
}

여기서 볼 수 있듯이 충분히 발전된 최적화는 테일 리퍼션을 반복으로 대체 할 수 있습니다. 기능 호출 오버 헤드를 피하고 일정한 양의 스택 공간 만 사용하므로 훨씬 더 효율적입니다.

TCO (Tail Call Optimization)는 스마트 컴파일러가 기능을 호출하고 추가 스택 공간을 취하지 않는 프로세스입니다. 그만큼 이런 일이 발생하는 상황만이 기능에서 마지막 지침이 실행 된 경우입니다. 에프 함수 g (메모: g 할 수 있습니다 에프). 여기서 핵심은 그 것입니다 에프 더 이상 스택 공간이 필요하지 않습니다. 단순히 호출됩니다 g 그런 다음 무엇이든 반환합니다 g 돌아올 것입니다. 이 경우 G가 단지 실행되고 F라고 불리는 값에 대한 모든 값을 반환하는 최적화가 이루어질 수 있습니다.

이 최적화는 반복적 인 호출이 폭발하기보다는 일정한 스택 공간을 취할 수 있습니다.

예 :이 요인 기능은 tcoptopleable :

def fact(n):
    if n == 0:
        return 1
    return n * fact(n-1)

이 기능은 반환 문에서 다른 함수를 호출하는 것 외에 작업을 수행합니다.

아래 기능은 tcoptiomable입니다.

def fact_h(n, acc):
    if n == 0:
        return acc
    return fact_h(n-1, acc*n)

def fact(n):
    return fact_h(n, 1)

이 기능에서 마지막으로 일어날 일은 다른 기능을 호출하는 것이기 때문입니다.

아마도 내가 꼬리 통화, 재귀 테일 콜 및 테일 콜 최적화에 대해 찾은 최고의 높은 수준의 설명은 블로그 게시물입니다.

"도대체 : 꼬리 콜"

Dan Sugalski. 꼬리 통화 최적화에 그는 다음을 씁니다.

잠시 동안이 간단한 기능을 고려하십시오.

sub foo (int a) {
  a += 15;
  return bar(a);
}

그렇다면 당신은 무엇을 할 수 있습니까? 글쎄, 그것이 할 수있는 일은 양식의 코드를 돌리는 것입니다 return somefunc(); 저수준 시퀀스로 pop stack frame; goto somefunc();. 이 예에서는 우리가 전화하기 전에 의미합니다 bar, foo 전화보다는 스스로를 청소합니다 bar 서브 루틴으로서, 우리는 낮은 수준을합니다 goto 시작까지 작동 bar. Foo이미 스택에서 스스로를 청소 했으므로 언제 bar 시작하는 사람처럼 시작합니다 foo 실제로 전화했습니다 bar, 그리고 언제 bar 그 가치를 반환하고, 전화 한 사람에게 직접 반환합니다. foo, 그것을 반환하기보다는 foo 그런 다음 발신자에게 반환합니다.

그리고 꼬리 재귀에서 :

마지막 작업으로 기능을하는 경우 꼬리 재귀가 발생합니다. 스스로 전화 한 결과를 반환합니다. 꼬리 재귀는 어딘가에 임의의 기능의 시작으로 점프하지 않고 자신의 시작으로 되돌아 가기 때문에 다루기가 더 쉽습니다.

그래서 이것은 :

sub foo (int a, int b) {
  if (b == 1) {
    return a;
  } else {
    return foo(a*a + a, b - 1);
  }

조용히로 변합니다.

sub foo (int a, int b) {
  label:
    if (b == 1) {
      return a;
    } else {
      a = a*a + a;
      b = b - 1;
      goto label;
   }

이 설명에서 내가 좋아하는 것은 명령적인 언어 배경에서 오는 사람들 (C, C ++, Java)에서 오는 사람들을 이해하는 것이 간결하고 쉬운 일입니다.

모든 언어가 지원하는 것은 아닙니다.

TCO는 특별한 재귀 사례에 적용됩니다. 그것의 요점은, 당신이 함수에서 마지막으로하는 것이 호출 자체라면 (예 : "꼬리"위치에서 스스로 호출되는 경우), 이것은 표준 재귀 대신 반복처럼 행동하도록 컴파일러에 의해 최적화 될 수 있습니다.

일반적으로 재귀 중에 런타임은 모든 재귀 호출을 추적해야하므로 반환하면 이전 통화 등에서 재개 할 수 있습니다. (재귀적인 호출 결과를 수동으로 작성하여 이것이 어떻게 작동하는지에 대한 시각적 아이디어를 얻으십시오.) 모든 통화를 추적하면 공간이 차지하면 기능이 많이 호출 될 때 중요합니다. 그러나 TCO를 사용하면 "처음으로 돌아가서 이번에는 매개 변수 값을이 새로운 값으로 변경합니다."라고 말할 수 있습니다. 재귀 호출 후에는 그 값을 말하기 때문에 그렇게 할 수 있습니다.

X86 분해 분석을 사용한 GCC 최소 실행 가능한 예제

GCC가 생성 된 어셈블리를 살펴보면 어떻게 테일 콜 최적화를 어떻게 자동으로 수행 할 수 있는지 살펴 보겠습니다.

이것은 다른 답변에서 언급 된 것에 대한 매우 구체적인 예가됩니다. https://stackoverflow.com/a/9814654/895245 최적화가 재귀 함수 호출을 루프로 변환 할 수 있습니다.

이로 인해 메모리를 절약하고 성능을 향상시킵니다. 메모리 액세스는 종종 요즘 프로그램을 느리게 만드는 가장 중요한 것입니다..

입력으로, 우리는 GCC를 최적화되지 않은 순진한 스택 기반 계승자에게 제공합니다.

tail_call.c

#include <stdio.h>
#include <stdlib.h>

unsigned factorial(unsigned n) {
    if (n == 1) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main(int argc, char **argv) {
    int input;
    if (argc > 1) {
        input = strtoul(argv[1], NULL, 0);
    } else {
        input = 5;
    }
    printf("%u\n", factorial(input));
    return EXIT_SUCCESS;
}

Github 상류.

컴파일 및 분해 :

gcc -O1 -foptimize-sibling-calls -ggdb3 -std=c99 -Wall -Wextra -Wpedantic \
  -o tail_call.out tail_call.c
objdump -d tail_call.out

어디 -foptimize-sibling-calls 다음에 따른 꼬리 통화의 일반화의 이름입니다. man gcc:

   -foptimize-sibling-calls
       Optimize sibling and tail recursive calls.

       Enabled at levels -O2, -O3, -Os.

언급했듯이 : GCC가 꼬리 수익성 최적화를 수행하는지 어떻게 확인합니까?

나는 선택한다 -O1 왜냐하면:

  • 최적화는 완료되지 않습니다 -O0. 나는 이것이 중간 변환이 누락되어 있기 때문이라고 생각합니다.
  • -O3 꼬리 통화 최적화이지만 교육적이지 않은 불경건하게 효율적인 코드를 생성합니다.

분해합니다 -fno-optimize-sibling-calls:

0000000000001145 <factorial>:
    1145:       89 f8                   mov    %edi,%eax
    1147:       83 ff 01                cmp    $0x1,%edi
    114a:       74 10                   je     115c <factorial+0x17>
    114c:       53                      push   %rbx
    114d:       89 fb                   mov    %edi,%ebx
    114f:       8d 7f ff                lea    -0x1(%rdi),%edi
    1152:       e8 ee ff ff ff          callq  1145 <factorial>
    1157:       0f af c3                imul   %ebx,%eax
    115a:       5b                      pop    %rbx
    115b:       c3                      retq
    115c:       c3                      retq

와 함께 -foptimize-sibling-calls:

0000000000001145 <factorial>:
    1145:       b8 01 00 00 00          mov    $0x1,%eax
    114a:       83 ff 01                cmp    $0x1,%edi
    114d:       74 0e                   je     115d <factorial+0x18>
    114f:       8d 57 ff                lea    -0x1(%rdi),%edx
    1152:       0f af c7                imul   %edi,%eax
    1155:       89 d7                   mov    %edx,%edi
    1157:       83 fa 01                cmp    $0x1,%edx
    115a:       75 f3                   jne    114f <factorial+0xa>
    115c:       c3                      retq
    115d:       89 f8                   mov    %edi,%eax
    115f:       c3                      retq

둘의 주요 차이점은 다음과 같습니다.

  • 그만큼 -fno-optimize-sibling-calls 용도 callq, 이는 일반적인 비 최적화 된 기능 호출입니다.

    이 명령어는 리턴 주소를 스택으로 밀어냅니다.

    또한이 버전도 마찬가지입니다 push %rbx, 어느 푸시 %rbx 스택에.

    GCC는 저장하기 때문에이를 수행합니다 edi, 이것은 첫 번째 기능 인수입니다 (n) 안으로 ebx, 그런 다음 전화합니다 factorial.

    GCC는 다른 전화를 준비하고 있기 때문에이를 수행해야합니다. factorial, 새로운 것을 사용할 것입니다 edi == n-1.

    그것은 선택합니다 ebx 이 레지스터는 callee-seaved이기 때문에 : Linux x86-64 기능 호출을 통해 보존되는 레지스터 그래서 서브 콜 factorial 그것을 바꾸지 않고 잃지 않습니다 n.

  • 그만큼 -foptimize-sibling-calls 스택으로 밀리는 지침을 사용하지 않습니다. goto 내면에서 점프합니다 factorial 지침과 함께 je 그리고 jne.

    따라서이 버전은 함수 호출없이 while 루프와 동일합니다. 스택 사용이 일정합니다.

우분투 18.10, GCC 8.2에서 테스트.

이봐:

http://tratt.net/laurie/tech_articles/articles/tail_call_optimization

아시다시피, 재귀 함수 호출은 스택에 혼란을 일으킬 수 있습니다. 스택 공간이 빠르게 떨어질 수 있습니다. 테일 콜 최적화는 일정한 스택 공간을 사용하는 재귀 스타일 알고리즘을 만들 수있는 방법입니다. 따라서 성장하고 성장하지 않고 스택 오류가 발생합니다.

  1. 기능 자체에 GOTO 문이 없도록해야합니다. Callee 함수의 마지막 일이되는 기능 호출에 의해 관리됩니다.

  2. 대규모 재귀는 최적화에이를 사용할 수 있지만 소규모로 기능을 호출하는 기능 오버 헤드는 실제 목적을 줄입니다.

  3. TCO는 영원히 실행되는 기능을 유발할 수 있습니다.

    void eternity()
{
    eternity();
}

재귀 기능 접근법에는 문제가 있습니다. 크기 O (N)의 통화 스택을 구축하여 총 메모리 비용 O (N)을 만듭니다. 따라서 통화 스택이 너무 커서 공간이 부족한 스택 오버플로 오류에 취약합니다. 꼬리 비용 최적화 (TCO) 체계. 큰 호출 스택을 구축하지 않도록 재귀 기능을 최적화 할 수있는 경우 메모리 비용이 절약됩니다.

파이썬과 Java가 TCO를하지 않는 TCO와 같은 (JavaScript, Ruby 및 C)를하는 많은 언어가 있습니다.

JavaScript 언어는 사용을 확인했습니다 :) http://2ality.com/2015/06/tail-call-optimization.html

라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top