Node.js - trampoline이란? ( tail call, recursion )

개요

• trampoline이라는 기법을 알아보려고 한다.

시나리오

먼저 1 ~ n 까지 더하는 함수를 작성한다고 하자.

테스팅 코드

우선 아래의 코드를 통해서 테스트를 진행할 것이다.

const test = (name, n, fn) => {
  try {
    console.time(name);
    fn(n);
    console.timeEnd(name);
  } catch (error) {
    console.error(error);
  }
}

// test('counter1', 100, counter);

1. 기본

우리는 바로 다음과 같이 작성할 것이다.

const counter1 = (n) => {
  let sum = 0;
  for (let i = 1; i <= n; i++) {
    sum += i;
  }
  return sum;
};

2. recursive

또한 우리는 recursive하게 아래와 같이 작성할 수도 있을 것이다.

const counter2 = (n) => {
  if (n === 0) {
    return n;
  }

  return n + counter2(n - 1);
};

하지만 우리는 해당 함수가 n이 커지게 되면 call stack이 쌓이면서 아래와 같은 에러가 발생하게 된다.

RangeError: Maximum call stack size exceeded
    at counter2 (/Users/malgogi/Desktop/test.js:17:18)
    at counter2 (/Users/malgogi/Desktop/test.js:22:14)
    at counter2 (/Users/malgogi/Desktop/test.js:22:14)
    at counter2 (/Users/malgogi/Desktop/test.js:22:14)
    at counter2 (/Users/malgogi/Desktop/test.js:22:14)
    at counter2 (/Users/malgogi/Desktop/test.js:22:14)
    at counter2 (/Users/malgogi/Desktop/test.js:22:14)
    at counter2 (/Users/malgogi/Desktop/test.js:22:14)
    at counter2 (/Users/malgogi/Desktop/test.js:22:14)
    at counter2 (/Users/malgogi/Desktop/test.js:22:14)

3. proper tail call 최적화

이에 따라 우리는 tail call을 통해서 call stack이 쌓이지 않게 개선할 수 있다. (해당 내용은 node v6에서 실험적인 기능으로 제공 가능하고, 현재는 해당 flag가 지원이 되지 않고 있다. 아래에서 더 기술할 것이다.)

const counter3 = (n, acc = 0) => {
  if (n === 0) {
    return acc;
  }

  return counter3(n - 1, n + acc);
};

해당 함수를 아래의 환경에서 실행할 경우 정상적으로 실행이 되는 것을 확인할 수 있다.

node --harmony_tailcalls --use-strict test.js // v6 version, harmony_tailcalls은 7.10까지 지원이 되는 flag이다.

proper tail call이 되지 않는다?

• 안타깝게도 node 7.10 이후부터는 tail call flag을 지원하지 않는다.
• 그래서 해당 방식을 회피하기 위한 기법이 trampoline이다.

trampoline 예제

아래와 같이 counter4 함수를 생성해보자.

const trampoline = fn => (...args) => {
  let result = fn(...args);
  while (typeof result === 'function') {
    result = result(); // 결과값이 나올 때까지 함수를 실행
  }
  return result;
};

const counter4Inner = (n, acc = 0) => { // 0이 아닌 경우 함수를 반환
  return n === 0 ? acc : () => counter4Inner(n - 1, acc + n);
};
const counter4 = trampoline(counter4Inner);

해당 방식은 call stack이 쌓이지 않기 때문에 큰 수에서도 실행이 되는 것을 볼 수 있다.

그렇다면 trampoline은 만능인가?

• 아쉽게도 그렇지 않다. call stack을 쌓지는 않지만 함수를 지속적으로 반환하고 실행하는 cost가 있기 때문에 성능은 더 느리다.
• 또한 코드의 이해 난이도가 상승하는 단점이 존재한다.
• 다만 사이즈가 작거나 적합한 케이스에서는 해당 기법을 통해서 call stack을 막을 수 있다.

// n = 100000000
counter1: 114.929ms // while문
counter4: 2.359s // trampoline

출처

• Stack Overflow - tail call support
• v8 - proper tail call 관련 논의 내용
• tc39 status
• trampoline 관련 블로그