ECMAScript Proper Tail Calls (PTC)

적절한 꼬리 호출이라고 번역하는 것이 옳을까?

 

일반적으로 재귀호출은 콜스택을 쌓아올리지만, 여러 프로그래밍 언어는 꼬리 재귀 호출(영문/국문 위키피디아 참고)의 최적화를 지원한다.

ECMAScript(자바스크립트는 이것의 명세를 따름) 6은 이와 비슷하지만 다른 'PTC(Proper Tail Calls)'를 지원한다.

 

현재 사파리(웹킷) 또는 harmony 플래그가 있는 Node.js(7, 8)에서만 PTC를 지원한다.

하지만 Node.js 18(PTC 미지원) 환경에서 직접 테스트한 결과, 꼬리 재귀 호출 최적화가 가능한 코드가 그렇지 않은 것에 비해 성능이 약간 더 우수한 것으로 나타나 다른 유형의 꼬리 재귀 최적화가 존재하지 않을까 생각한다.

 

PTC는 (재귀)호출되는 함수가 호출하는 함수의 콜스택 영역을 재사용하도록 한다. 이를 통해 깊은 재귀호출 상황에서도 콜스택 오버플로우가 발생하지 않게 될 수 있다.

 

다음 4가지를 만족하는 경우를 꼬리호출로 본다.

• 호출 함수가 strict mode에 있다.
• 호출 함수가 일반 혹은 화살표 함수다.
• 호출 함수가 제너레이터 함수가 아니다.
• 호출 함수는 호출된 함수의 리턴값을 리턴한다.

 

일반적인 재귀 호출

"use strict";
function factorial(n)
{
    if (!n)
        return 1;
    return n * factorial(n - 1);
}

factorial(n-1)이 종료된 후 n과 곱해야 하기 때문에 콜스택은 유지되어야 한다.

 

꼬리 재귀 호출

"use strict";
function factorial(n, partialFactorial = 1)
{
    if (!n)
        return partialFactorial;
    return factorial(n - 1, n * partialFactorial);
}

 

PTC는 여러 이점이 있다.

PTC는 동일 메모리 공간(콜스택)을 계속 사용하므로, 이에 사용되는 캐시 공간 또한 최소화하게 되는 장점이 있다.

 

가비지 컬렉션에 대해서도 더 효과적이다. 함수 내 로컬 개체를 할당하는 경우를 생각해보자. 일반적인 재귀 호출이라면 해당 호출이 반환될 때까지 로컬 개체가 메모리 상에 유지되지만, 꼬리호출의 경우 이에 대한 더이상의 참조가 없기 때문에 가비지 컬렉션의 대상이 될수 있다.

 

마지막 꼬리 호출이 반환될 때, PTC는 중간의 모든 호출 반환을 건너뛰고 첫 호출의 반환으로 처리한다. 이는 호출 깊이가 깊을수록 성능상 이득이다. 이것은 상호 꼬리 호출(두 함수가 서로를 꼬리 호출하는 경우 등)에도 적용된다.

 

다음 코드는 PTC가 지원되는 환경에서는 정상 동작하지만, 그 외에는 Maximum call stack exceeded 에러가 발생한다.

'use strict';

const direct = () => {
  const f = (n) => (n <= 0 ? 'foo' : f(n - 1));
  return f(1e6) === 'foo';
};

const mutual = () => {
  const f = (n) => (n <= 0 ? 'foo' : g(n - 1));
  const g = (n) => (n <= 0 ? 'bar' : f(n - 1));
  return f(1e6) === 'foo' && f(1e6 + 1) === 'bar';
};

console.log(direct());
console.log(mutual());

 

주의 사항

PTC가 있을 때 자바스크립트에는 비표준 ECMAScript 기능이 포함된다. 여기에는 Error.stack 및 Console의 스택 추적 등이 해당된다.

꼬리 호출된 함수가 Error를 던지는 경우, Console 스택 추적에는 꼬리 호출한 함수가 포함되지 않을 수 있다.

 

Error에 func이 중첩된 횟수만큼 나타나지 않는다. (Safari 16.0)

 

성능 비교

Node.js 7에서 다음 8개 함수에 대해 PTC 지원 여부(--harmony 플래그 여부)에 따른 성능을 비교해보았다.

function f1(n) {
  if (n === 0) return 0;
  return n + f1(n - 1);
}

const f2 = (n) => {
  if (n === 0) return 0;
  return n + f2(n - 1);
};

function f3(n, r = 0) {
  if (n === 0) return r;
  return f3(n - 1, n + r);
}

const f4 = (n, r = 0) => {
  if (n === 0) return r;
  return f4(n - 1, n + r);
};

function f5(n) {
  return (n === 0) ? 0 : n + f5(n - 1);
}

const f6 = (n) => (n === 0) ? 0 : n + f6(n - 1);

function f7(n, r = 0) {
  return (n === 0) ? r : f7(n - 1, n + r);
}

const f8 = (n, r = 0) => (n === 0) ? r : f8(n - 1, n + r);

 

위 8개 함수가 동일한 테스트를 수행하는 데 걸린 시간은 다음과 같다.

(그래프의 시작점이 0이 아니므로 실제보다 과장됨)

각 함수의 테스트 소요 시간

꼬리 재귀 호출이 아닌 f1, f2, f5, f6은 PTC 지원 여부에 사실상 영향을 받지 않은 것을 알 수 있다.

꼬리 재귀 호출에 해당하는 f3, f4, f7, f8은 PTC 지원 시 성능이 꽤 좋아진 것을 알 수 있다.

 

한편, Node.js 18.9.1에서 위 테스트를 수행했을 때의 결과는 다음과 같다.

(그래프의 시작점이 0이 아니므로 실제보다 과장됨)

PTC가 지원되지 않음에도 불구하고 f3, f4, f7, f8의 성능이 좋은 것으로 보아, PTC 이외의 꼬리 재귀 최적화가 존재할 것으로 짐작된다.

결국 PTC가 지원되지 않는 환경에서도 꼬리 재귀 최적화를 인지하고 코드를 작성하는 것은 도움이 될 것 같다.

 

참고

https://webkit.org/blog/6240/ecmascript-6-proper-tail-calls-in-webkit/

ECMAScript 6 Proper Tail Calls in WebKit

https://kangax.github.io/compat-table/es6/#test-proper_tail_calls_(tail_call_optimisation) 

ECMAScript 6 compatibility table

https://node.green/#ES2015-optimisation-proper-tail-calls--tail-call-optimisation-

Node.js ES2015/ES6, ES2016 and ES2017 support