Rust 의 끝 부분에서 최적화된 스토리 호출

나는 꼬리부분 호출 최적화가 매우 교묘하다고 생각한다. 특히 그들은 귀속 함수 호출이 어떻게 집행되는지의 기본적인 문제를 어떻게 해결하는가.Haskell과 Lisp 가족의 함수식 언어, 논리적 언어 (그 중에서 Prolog가 가장 유명한 예일 수 있음) 는 모두 문제를 귀속적으로 사고하는 방법을 강조한다.꼬리 부분 호출 최적화를 이용하여 이런 언어들은 성능에 있어 많은 장점을 가진다.

Note: I don't go into excruciating details on how tail calls work in this post. If you feel like you need/want some more background on them, here are a few awesome resources:

• The YouTube channel has a video where they walk through examples of tail-recursive functions in painstaking detail.
• A detailed explanation on Stack Overflow on the concept of tail recursion.

최근 몇 년 동안 프로그래밍 커뮤니티에서 함수 패턴과 습관 용법을 강조하는 추세에 따라 꼬리 호출 최적화가 많은 컴파일러/해석기 구현에 나타난다고 생각할 수 있습니다.그러나 이러한 유행어 중 많은 것들이 꼬리 호출 최적화를 이루지 못했다는 사실이 증명되었다.JavaScript는 몇 년 전까지만 해도 지원을 취소했습니다1.Python은 지원하지 않습니다2.녹슬지도 않아요.
이런 상황의 원인을 깊이 연구하기 전에 꼬리부분 호출 최적화 배후의 생각을 간단하게 요약해 봅시다.

꼬리 부분 호출 최적화 어떻게 작업 (이론적)

TCO가 지원되지 않는 환경에서 실행되면 끝부분 귀속 함수는 함수의 입력 크기에 따라 선형 메모리 증가를 나타냅니다.이것은 모든 귀속 호출이 호출 창고에 추가 창고 프레임을 분배하기 때문이다.TCO의 목표는 꼬리 귀속 함수를 실행함으로써 이런 선형 메모리 사용을 없애는 것이다. 이렇게 하면 모든 호출에 새로운 창고 프레임을 분배할 필요가 없다.
이를 실현하는 방법 중 하나는 컴파일러가 TCO를 실행해야 한다는 것을 깨달은 후 꼬리 귀속 함수 실행을 백그라운드에서 반복 순환과 유사한 것으로 바꾸는 것이다.그 효과는 꼬리 귀속 함수를 단일 창고 프레임으로만 계산한 결과입니다.Ta da!고정 메모리 사용.

이렇게 되면 왜 녹이 TCO를 나타내지 않는지 되돌아봅시다.

녹을 뚫고 귀항기

내가 찾을 수 있는 Rust의 끝부분 호출 최적화에 대한 최초의 참고는 Rust 프로젝트의 시작까지 거슬러 올라갈 수 있다.2013년 this 메일 목록 라인을 찾았습니다. Graydon Hoare는 끝부분 호출 최적화가 Rust에 속하지 않는다고 생각하는 이유를 열거했습니다.

이 메일 목록 라인은 this GitHub 문제를 가리킨다. 2011년 당시 이 프로젝트의 최초 작성자는 당시 싹트기 시작한 컴파일러에서 TCO를 어떻게 실현하는지 해결하기 위해 노력하고 있었다.문제의 핵심은 당시 LLVM과 호환되지 않았기 때문인 것 같다.공평하게 말하자면, 그들이 이 문제에 대해 이야기하는 많은 일들이 나의 이해 범위를 넘어섰다.
그러나 흥미로운 것은 처음에 TCO가 Rust에서 실현되지 않을 것이라는 무서운 예측이 있었지만 오늘날까지도 사람들은 Rust 컴파일러에 TCO를 입력하는 것을 멈추지 않았다는 것이다.

Rust 컴파일러에 TCO 추가 권장 사항

2014년 5월, this PR이 개방되었는데, 그 이유는 LLVM이 현재 TCO를 지원하여 초기의 메일 목록 라인에 응답할 수 있기 때문이다.더 구체적으로 말하면 이 PR은 새로운 키워드become를 도입하여 필요에 따라 TCO를 실현한다. 이 키워드는 컴파일러가 지정한 꼬리 귀속 함수를 실행할 때 TCO를 실행하도록 알려준다.
PR의 생명 주기 내에 어떤 경우 Rust 컴파일러는 TCO가 언제 적합한지 추정하고 실행할 수 있다3.따라서 become 키워드는 정신적으로는 unsafe 키워드와 비슷하지만 구체적으로 TCO를 대상으로 한다.말할 것도 없이 이 공관은 결국 받아들여지고 합병되지 않았다.
뒤이어 RFC는 2017년 2월 개방돼 이전 제안과 매우 비슷하다.흥미로운 것은 저자가 꼬리 호출 최적화 ('정확한 꼬리 호출') 를 합병하는 데 가장 큰 장애는 다음과 같다고 지적했다.

이식성 문제;당시 LLVM은 특정 아키텍처 (특히 MIPS 및 WebAssembly) 에 대해 올바른 후면 호출을 지원하지 않았습니다.

LLVM의 정확한 꼬리 부분 호출은 실제적으로 그 당시의 실현 방식에 따라 성능이 떨어질 수 있다.

TCO는 스택 값을 덮어쓰기 때문에 디버깅을 더욱 어렵게 합니다.

사실 RFC의 저자는 지금까지 TCO가 없는 상황에서 녹병은 이미 매우 좋아졌고 그것이 없으면 틀림없이 계속 좋아질 것이라고 인정했다.
지금까지 현식 사용자가 제어하는 TCO는 러스트 컴파일러에 들어가지 않았다.

라이브러리를 통한 TCO 실현

그러나 TCO RFC와 제안을 방해하는 많은 문제를 어느 정도 회피할 수 있다.Rust에 현식 TCO를 추가하는 몇 가지 자체 제작 솔루션이 있습니다.
전체적인 사고방식은 이른바'번지점프대'를 실현하는 것이다.이것은 실제로 꼬리 귀속 함수를 사용하고 이를 교체 순환을 사용하는 추상으로 바꾸는 것을 가리킨다.

How about we first implement this with a trampoline as a slow cross-platform fallback implementation, and then successively implement faster methods for each architecture/platform?
This way the feature can be ready quite quickly, so people can use it for elegant programming. In a future version of rustc such code will magically become fast.
@ConnyOnny, 4

Bruno Corrêa Zimmermann의 tramp.rs 라이브러리는 아마도 이 라이브러리 해결 방안 중에서 가장 사람들의 주목을 끄는 것일 것이다.엔진 덮개 아래에서 어떻게 작동하는지 봅시다.

떠돌이로 뛰어들다.루피

떠돌이.rslibrary는 두 개의 매크로rec_call!와 rec_ret!를 내보냅니다. 이 두 매크로는 제안된 become 키워드와 같은 행동을 촉진합니다. 프로그래머가 반복 순환을 통해 Rust가 실행될 때 지정한 꼬리 귀속 함수를 실행하여 함수의 메모리 비용을 상수로 낮출 수 있도록 합니다.rec_call! 매크로가 이 과정을 시작했는데 become 키워드가 2014년 Rust 컴파일러에 도입되었을 때와 가장 비슷한 효과가 있었다.

macro_rules! rec_call {
    ($call:expr) => {
        return BorrowRec::Call(Thunk::new(move || $call));
    };
}

rec_call!는 두 개의 추가 중요 구조BorrowRec와 Thunk를 사용했다.

enum BorrowRec<'a, T> {
    Ret(T),
    Call(Thunk<'a, BorrowRec<'a, T>>),
}

BorrowRec 매거는 꼬리 귀속 함수 호출이 언제든지 있을 수 있는 두 가지 상태를 나타낸다. 즉, 기본적인 상황에 도달하지 않았거나, 이런 상황에서 우리는 여전히 BorrowRec::Call 상태에 있거나, 기본적인 상황에 도달하여 최종 값을 생성했다. 이런 상황에서 우리는 이미 BorrowRec::Ret 상태에 이르렀다.Call 열거된 BorrowRec 변형에는 Thunk 의 다음 정의가 포함되어 있습니다.

struct Thunk<'a, T> {
    fun: Box<FnThunk<Out = T> + 'a>,
}

Thunk 구조는 꼬리 귀속 함수에 대한 인용을 보존하고 이 함수는 FnThunk 특징에 의해 표시된다.
마지막으로 이 모든 것은 tramp 함수와 연결되어 있다.

fn tramp<'a, T>(mut res: BorrowRec<'a, T>) -> T {
    loop {
        match res {
            BorrowRec::Ret(x) => break x,
            BorrowRec::Call(thunk) => res = thunk.compute(),
        }
    }
}

이것은 BorrowRec 실례에 포함된 꼬리 귀속 함수를 입력으로 수신하고 BorrowRec 상태를 유지하는 상황에서 이 함수를 계속 호출합니다.그렇지 않으면 귀속 함수와 최종 계산 값이 Call 상태에 도달하면 최종 값은 Ret 매크로를 통해 되돌아옵니다.

저희가 TCO가 있나요?

그래서 그런가?rec_ret! 우리가 Rust 프로젝트에서 필요에 따라 TCO를 실현하는 데 필요한 영웅인가?
아마 안 될 거예요.
비록 나는 트램펄린이 일종의 증량으로 TCO를 도입하는 방식을 정말 좋아하지만 어떻게 이 실현에서 제기된 것인지benchmarks는 트램펄린을 사용하는 것을 우아하게 운행하고 있음을 나타낸다.수동으로 꼬리 귀속 함수를 교체 순환으로 바꾸는 것에 비해rs는 성능이 약간 떨어진다.
@timthelion
일부 원인은 유랑자의 감속을 초래했다.에서 지적한 바와 같이rs의 성능은 각각tramp.rs 호출이 호출rec_call!으로 인해 더미 위에 메모리를 분배할 수 있습니다.
@jonhoo
따라서 Thunk::new의 번지점프는 TCO가 약속한 일정한 메모리 사용조차 실현하지 못했다!
아, 그래.나중에 필요에 따라 Rust 컴파일러에 TCO가 추가될 수 있습니다.그렇게 지도 모른다, 아마, 아마...지금까지 녹균 생태계는 그것 없이도 잘 지내고 있다.

링크 및 참조

1:
2: https://stackoverflow.com/questions/42788139/es6-tail-recursion-optimisation-stack-overflow
3: http://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html
4: https://github.com/rust-lang/rfcs/issues/271#issuecomment-271161622