개요

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

출처

728x90