함수형 자바스크립트 [7장]

※ 함수형 자바스크립트 라는 책을 한 장씩 리뷰해보도록 하겠습니다.

 

Chapter 7. 함수형 최적화

 

" 자그마한 효율은 그냥 잊으세요. 대략 97%의 경우 어설픈 최적화가 모든 걸 망쳐놓는 원인이 됩니다. 하지만 나머지 결정적 3%는 최적화할 기회를 절대로 놓쳐서는 안 됩니다. "

 

이번 장에서는 느긋한 평가, 메모화, 꼬리 호출 최적화 함수형 최적화 기법에 대해 다룰 것입니다. 함수형 프로그래밍은 개별 함수의 평가 속도를 올리기보다는 주로 함수 중복 호출을 피해 코드가 정말 필요할 때까지 평가를 지연시키는 전략을 구사합니다.

 

7.1 함수 실행의 내부 작동 원리

 

자바스크릡트에서는 함수를 호출할 때마다 함수 컨텍스트 스택에 레코드 (프레임) 가 생성됩니다. 전역 컨텍스트 프레임은 항상 스택 맨 밑에 위치합니다. 함수 컨텍스트 프레임은 각각 내부 지역 변수의 개수만큼 메모리를 점유합니다.

빈 프레임은 48바이트 정도 되고, 숫자, 불리언 같은 지역 변수/매개변수는 8바이트를 차지합니다.

프레임엔 아래와 같은 정보가 담겨져 있습니다.

executionContextData = {
  scopeChain, // 이 함수의 variableObject 와 부모 실행 컨텍스트의 variableObject 에 접근하는 연결 고리
  variableObject, // 함수의 인수, 내부변수, 함수 선언부를 포함
  this // 함수 객체를 가리키는 레퍼런스
}

variableObject 는 지역 변수와 함수는 물론, 함수의 안수, 유사배열 객체 arguments 를 가리키는 속성이므로 이 속성에 의해 스택 프레임의 크기가 결정됩니다.

스코프 체인은 이 함수의 컨텍스트를 그 부모 실행 컨텍스트와 연결하거나 참조합니다. 모든 함수는 스코프 체인에 의하 직/간접적으로 전역 컨텍스트와 연결됩니다.

 

스택의 주요 작동 규칙은 아래와 같습니다.

• 자바스크립트는 단일 스레드로 작동하며, 동기 실행 방식
• 전역 컨텍스트는 단 하나만 존재 (모든 함수 컨텍스트는 전역 컨텍스트를 공유)
• 함수 컨텍스트 개수에 제한은 없음 (클라이언트 사이드에선 브라우저마다 제한 갯수 다름)
• 함수를 호출할 때마다 실행 컨텍스트가 새로 생성되며, 재귀 호출 시에도 마찬가지

함수형 프로그래밍은 함수를 최대한 사용하려 하므로 가능한 많은 함수로 분해하고 커리하는건 좋지만, 지나치게 커리할 시 컨텍스트 스택에 영향을 끼칩니다.

 

7.1.1 커링과 함수 컨텍스트 스택

 

함수에 추상화를 한 꺼풀 더 입히면, 일반적인 함수 평가보다 컨텍스트에 오버헤드가 더 많이 발생할 수 있습니다.

logger 함수를 커리하는 코드 예시를 보도록 하겠습니다.

// 일반 함수
const logger = function (appender, layout, name, level, message)

// 커리
const logger =
  function (appender) {
    return function (layout) {
      return function (name) {
        return function (level) {
          return function (message) {
        ...

중첩구조는 한 번에 호출하는 것보다 함수 스택을 더 많이 사용합니다. logger 함수를 커링 없이 실행하면 자바스크립트는 동기 실행되기 때문에 우선 전역 컨텍스트 실행을 잠시 멈추고 새 컨텍스트를 만든 후, 변수 해석에 사용할 전역 컨텍스트 레퍼런스를 생성합니다.

 

logger 함수는 그 안에서 Log4js 연산을 호출하므로 또 다른 컨텍스트가 생성되어 스택에 쌓입니다. 클로저때문에 내부 함수 호출로 비롯된 함수 컨텍스트는 스택에 쌓이며, 각 컨텍스트는 일정 메모리를 차지한 채 scopeChain 레퍼런스를 통해 연결되어 있는 상태입니다. 이후 Log4js 코드 실행이 완료되면 스택에서 빠지고, 이어서 logger 함수가 실행되어 마지막엔 전역 컨텍스트 하나만 실행 상태로 남습니다.

 

이러한 구조때문에 함수가 깊이 중첩될수록 메모리를 과다하게 점유할 가능성이 있습니다. 그래서 비동기 코드를 다루는 RxJS 라이브러리는 성능에 올인해 클로저 수를 줄이는 데 집중하기도 했습니다.

 

함수형 프로그래밍 패러다임에 따라 모든 함수를 커리하면 좋을 순 있지만, 과용하면 엄청난 메모리가 소모되면서 프로그램 실행 속도가 현저히 떨어질 수 있습니다. 이외에 비효율적으로, 부정확하게 구현한 재귀 코드 역시 스택을 커지게 합니다.

 

7.1.2 재귀 코드의 문제점

 

함수가 자신을 호출할 때에도 새 함수 컨텍스트가 만들어집니다. 하지만 기저 케이스에 도달할 수 없게 잘못 구현된 재귀 코드를 호출하면 스택이 넘칠 수 있습니다. 다만 재귀는 제대로 작동하지 않으면 Range Error : Maximum Call Stack Exceeded 라는 에러를 바로 뱉습니다. 스택 에러가 발생하는 로직은 브라우저마다 다르며, 이 경우 외에 잘못 구현되지 않았더라도 엄청 큰 용량의 데이터를 재귀로 처리할 때 그 배열의 크기만큼 스택이 커질 수 있습니다.

 

이처럼 커링과 재귀를 함수에 적용하면 명령형 코드보다는 메모리를 더 차지하겠지만 반대로 얻을 수 있는 이점과는 비교해봐야 합니다.

 

7.2 느긋한 평가로 실행을 늦춤

 

불필요한 함수 호출을 삼가고 꼭 필요한 입력만 넣고 실행하면 여러모로 성능 향상을 기대할 수 있습니다. 하스켈 같은 함수형 언어는 기본적으로 모든 함수 표현식을 느긋하게 평가 (lazy evaluation) 하도록 지원합니다. 자바스크립트는 기본적으로 함수를 조급하게 평가 (eager evaluation) 하며, 함수 결과값이 필요한지 따져볼 새도 없이 변수에 바인딩되자마자 표현식 평가를 마칩니다. 이는 탐욕스런 평가 (greedy evaluation) 라고도 합니다. 두 차이를 예시로 보겠습니다.

• 조급한 계산
  • range(1, 10) -> [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] -> take(3) -> [1, 2, 3] 
  • range 에서 먼저 함수를 평가한 다음 10개의 원소 모두 생성, take 에서 처음 세 원소만 가져오고 버림
• 느긋한 계산
  • range(1, 10) -> 함수 호출을 나중으로 미룸 -> take(3) -> [1, 2, 3]
  • 원소를 3개만 생성

느긋하게 평가하면, 위처럼 의존 연산인 take 가 호출되기 전까지 range 는 실행되지 않습니다.

아래는 느긋한 평가를 활용하는 두가지 방법입니다.

• 불필요한 계산을 피함
• 함수형 라이브러리에서 단축 융합을 사용

 

7.2.1 대체 함수형 조합으로 계산을 회피

 

느긋한 평가의 단순한 용례는 레퍼런스로 전달하고 조건에 따라 한쪽만 호출하여 쓸데없는 계산을 건너뛰는 것입니다.

const alt = R.curry((func1, func2, val) => func1(val) || func2(val));

const showStudent = R.compose(append('#student-info'),
  alt(findStudent, createNewStudent)); // 함수를 레퍼런스로 전달

showStudent('444-44-4444');

이렇게 중복을 줄이고 불필요한 함수 계산을 간단하게 넘어가는 방법이 있습니다.

 

7.2.2 단축 융합을 활용

 

로대시JS 라이브러리의 _.chain 함수를 사용했을 시 맨 끝에 value() 함수를 걸면 전체 함수 순차열을 한꺼번에 실행하도록 만들 수 있습니다. 이렇게 하면 함수 실행 중 차지하는 공간을 로대시JS 가 효율적으로 통합하여 최적화하도록 지시 할 수 있습니다. 

_.chain 을 사용해 선언적 형태로 프로그램을 작성하면, 하고 싶은 일을 미리 정의함으로써 어떻게 작동하는지는 신경 쓰지 않고 무슨 일을 해야 할지 밝히는 것입니다. 이로 인해 단축융합 이라는 기법으로 로대시JS 가 프로그램 실행을 내부적으로 최적화할 수 있습니다. (단축융합 : 몇 개 함수의 실행을 하나로 병합하고 중간 결과를 계산할 때 사용하는 내부 자료구조의 개수를 줄이는 최적화) 자료구조가 줄면 대량 데이터를 처리할 때 필요한 메모리 사용을 낮출 수 있습니다.

 

const square = x => Math.pow(x, 2);
const isEven = x => x % 2 === 0;
const numbers = _.range(200);

const result =
  _.chain(numbers)
   .map(square)
   .filter(isEven)
   .take(3) // 조건을 만족하는 처음 세 숫자만 처리
   .value(); // -> [0, 4, 16]

result.length; // -> 5

위 코드는 두가지를 최적화합니다. 1) take(3) 을 호출해 map, filter 를 통과한 처음 세 값만 신경 쓰고 나머지 195개 값들에 대해선 신경쓰지 않도록 로대시JS 에 지시합니다. 2) 단축융합을 이용해 이후 map/filter 호출은 compose(filter(isEven), map(square)) 속으로 융합시킵니다.

 

7.3 필요할 때 부르기 전략

 

반복적인 계산 (자원을 많이 소모하는 계산) 을 피하는 것도 어플리케이션 실행 속도를 끌어올리는 방법입니다. 캐시란 값비싼 연산을 하기 전에 일단 질의하는 중간 저장소/메모리 입니다. 함수형 언어에는 이러한 캐시 혜택을 누리면서 코드 및 테스트를 잘 작동시키는 메모화 라는 메커니즘이 있습니다.

 

7.3.1 메모화

 

메모화 배후의 캐시 전략도 함수 인수로 키값을 만들고 이 키로 계산 결과를 캐시에 보관해두었다가, 이후 다시 같은 인수로 함수를 호출하면 보관된 결과를 즉시 반환한다는 로직입니다.

 

7.3.2 계산량이 많은 함수를 메모화

 

순수 함수형 언어는 자동으로 메모화를 실천하지만, 자바스크립트나 파이썬 같은 언어에서는 개발자가 함수를 언제 메모할지 선택 가능합니다. 이러한 캐시는 계산 집약적인 함수에 적용하면 큰 이득을 볼 수 있습니다.

const rot13 = s =>
  s.replace(/[a-zA-Z]/g, c =>
    String.fromCharCode((c <= 'Z' ? 90 : 122)
      >= (c = c.charCodeAt(0) + 13) ? c : c - 26));
  });
};

const discountCode = 'functional_js_50_off';

rot13(discountCode); // -> shapgvbany_wf_50_bss

위의 rot13 함수는 동일한 문자열을 입력하면 반드시 동일한 문자열이 출력되는, 참조 투명성을 갖고 있습니다. 따라서 이 함수를 메모하면 상당한 성능 향상을 기대할 수 있습니다. 메모화에는 두가지 적용 방법이 있습니다.

// 1. 함수 객체의 메서드를 호출
let rot13 = rot13.memoize();

// 2. 함수 정의부를 감쌈
let rot13 = s =>
  s.replace(/[a-zA-Z]/g, c =>
    String.fromCharCode((c <= 'Z' ? 90 : 122)
      >= (c = c.charCodeAt(0) + 13) ? c : c - 26))).memoize();

메모화를 하면 동일한 입력으로 함수를 재호출할 때 내부 캐시가 히트되어 즉시 결과가 반환됩니다. 이러한 메모화는 자바스크립트에서 자동 메모화를 지원하진 않지만, 아래와 같이 Function 객체에 보강해 사용 가능합니다.

Function.prototype.memoized = function () {
  let key = JSON.stringify(arguments);
  
  this._cache = this._cache || {};
  
  this._cache[key] = this._cache[key] || this.apply(this, arguments);
  
  return this._cache[key];
};

Function.prototype.memoize = function () {
  let fn = this;
  if (fn.length === 0 || fn.length > 1) {
    return fn;
  }
  
  return function() {
    return fn.memoized.apply(fn, arguments);
  };
};

 

7.3.3 커링과 메모화를 활용

 

인수가 여러 개인 복잡한 함수는 순수 함수라 해도 캐시하기 어렵습니다. 이러한 문제의 한 가지 해결 방법은 커링입니다. 다항 함수를 커리해 단항 함수로 바꿔 메모하는 것입니다.

 

7.3.4 분해하여 메모화를 극대화

 

코드를 잘게 나눌수록 메모화 효과는 더욱 커집니다. 여러 함수가 조합된 함수 중 일부만 메모된 함수로 바꿔도 큰 속도 향상의 효과를 볼 수 있습니다.

 

7.3.5 재귀 호출에도 메모화를 적용

 

재귀는 때때로 브라우저를 죽음으로 몰고 가거나 예외를 던지게 합니다. 이는 엄청 큰 입력을 처리하면서 스택이 비정상적으로 커질 때 일어날 수 있으며, 메모화를 이용하면 문제가 해결될 수 있습니다.

재귀 호출은 기저 케이스에 도달할 때까지 하위 문제들을 풀어 마지막에 호출 스택이 풀리며 최종 결과를 내는데, 하위 문제들의 결과를 캐시하면 성능을 끌어올릴 수 있습니다.

(흔히 찾을 수 있는 메모이제이션을 활용한 팩토리얼 함수가 그 예시입니다)

 

7.4 재귀와 꼬리 호출 최적화

 

위에서 봤던 예제처럼 입력이 동일한 경우가 아닌, 입력이 계속 바뀌어 내부 캐시 계층이 별 역할을 할 수 없다면 메모화도 도움이 되지 않습니다. 재귀를 일반 루프만큼 실행을 최적화하기 위해선, 꼬리 재귀 호출 - tail call optimization (TCO) - 을 수행하게끔 재귀 알고리즘을 구현하면 됩니다.

팩토리얼 함수를 꼬리 위치에서 재귀하도록 바꾸는 아래 예시입니다.

const factorial = (n, current = 1) => 
  n === 1 ? current : factorial(n - 1, n * current); // 함수의 마지막 구문에서 재귀 단계를 밟음

TCO 는 꼬리 호출 제거 라고도 하는데, 재귀 프로그램이 제일 마지막에 다른 함수를 호출할 경우에만 TCO 가 일어납니다. 이때 마지막 호출이 꼬리 위치에 있다고 부릅니다.

 

이러한 방법이 최적인 이유는, 재귀 함수가 가장 마지막에 함수를 호출하면 자바스크립트 런타임은 남은 할 일이 없기 때문에 현재 스택 프레임을 들고 있을 이유가 없어 폐기합니다. 이처럼 재귀를 반복할 때마다 스택에 새 프레임은 쌓이지 않고 버려진 프레임을 재활용할 수 있습니다.

// 일반 재귀
factorial(4)
  4 * factorial(3)
    4 * 3 * factorial(2)
      4 * 3 * 2 * factorial(1)
        4 * 3 * 2 * 1 * factorial(0)
          4 * 3 * 2 * 1 * 1
      4 * 3 * 2 * 1
    4 * 3 * 2
  4 * 6
return 24

// 꼬리 재귀 호출
factorial(4)
  factorial(3,4)
  factorial(2, 12)
  factorial(1, 24)
  factorial(0, 24)
  return 24
return 24

 

7.4.1 비꼬리 호출을 꼬리 호출로 전환

 

자바스크립트의 TCO 체제를 활용해 계승 함수를 최적화 해보겠습니다.

const factorial = n => n === 1 ? 1 : n * factorial(n-1));
// 마지막에 재귀 단계와 숫자 n 을 곱한 결과를 반환하므로 꼬리 호출이 아님
// 이 부분을 바꿔야 TCO 활용 가능

// 1. 곱셈 부분을 함수의 매개변수로 추가해 현재 곱셈을 추적
// 2. ES6 기본 매개변수로 기본 인수 값을 미리 정함
const factorial = (n, current = 1) => 
  n === 1 ? current : factorial(n - 1, n * current);

또 다른 예시도 보겠습니다.

// 비꼬리 호출
function sum(arr) {
  if (_.isEmpty(arr)) {
    return 0;
  }
  return _.first(arr) + sum(_.rest(arr)); // 이 부분을 수정
}

// 꼬리 호출
function sum(arr, acc = 0) {
  if (_.isEmpty(arr)) {
    return acc;
  }
  return sum(_.rest(arr), arr + _.first(arr));
}

꼬리 재귀는 재귀 루프의 성능을 수동 루프급으로 끌어올립니다. 다만 TCO 는 ES4 시절 처음 나온 후로 자바스크립트 표준이 되었지만 이를 지원하지 않는 브라우저가 더 많아 바벨을 같이 사용해야 합니다.

 

빡빡한 그래픽 렌더링 루프를 돌리거나, 짧은 시간 내에 대량 데이터를 처리할 경우 성능이 관건입니다. 처리 속도를 높이는 일이 우선이므로 우아하고 확장 가능한 코드는 차치하고 절충점을 찾아야 하며, 최적화는 제일 마지막에 하더라도 밀리초 단위의 성능을 뽑아내야 하는 경우라면 이번 6장에서 본 기법들을 적용해 볼 법 합니다.

 

7.5 Summary

 

• 함수형 코드는 동등한 명령형 코드보다 더 느리게 실행되거나 더 많은 메모리를 점유할 수 있음
• 조합기로 대체하거나 로대시JS 같은 함수형 라이브러리의 도움을 받아 느긋하게 평가하는 지연 전략 구사 가능
• 메모화는 내부적인 함수 수준의 캐시 전략으로, 잠재적으로 값비싼 함수를 중복 평가 방지함
• 프로그램을 단순 함수로 분해하면 메모화를 통해 효츌적이고 확장 가능한 코드로 개발 가능
• 메모화를 십분 활용
• 꼬리 재귀 함수로 바꾸면 꼬리 호출 최적화라는 컴파일러 확장 기능 활용 가능

 

 

출처 : 함수형 자바스크립트(책)