🌈 Chapter 7: 함수형 최적화

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

• 자바스크립트에서는 함수를 호출할 때마다 함수 콘텍스트 스택에 레코드(프레임) 가 생성된다.
• 콘텍스트 스택은 함수 실행 및 함수가 에워싼(클로저 같은 것) 변수를 관리하는 자바스크립트 프로그래밍 모델이다.
• 스택은 언제나 전역 데이터가 담긴, 전역 실행 콘텍스트 프레임에서 시작한다.
• 전역 콘텍스트 프레임은 항상 스택 맨 밑에 위치한다. 지역 변수가 하나도 없는 빈 프레임은 48비트 정도 되고, 숫자, 불리언 같은 지역 변수/매개변수는 8바이트를 차지한다.

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

• variableObject는 지역 변수와 함수는 물론, 함수의 인수, 유사배열 객체 arguments를 가리키는 속성이므로, 사실상 스택 프레임의 크기는 이 속성으로 결정된다.
• 스코프 체인은 이 함수의 콘텍스트를 그 부모 실행 콘텍스트와 연결하거나 참조한다.
• 모든 함수는 스코프 체인이 결국 직/간접적으로 전역 콘텍스트와 연결된다.
• 📌 스택의 주요 작동 규칙
  1. 자바크립트는 단일 스레드로 작동한다. 즉, 동기 실행 방식이다.
  2. 전역 콘텍스트는 단 하나만 존재한다. (모든 함수 콘텍스트는 전역 콘텍스트를 공유한다.)
  3. 함수 콘텍스트 개수는 제한은 없다.
  4. 함수가 호출할 때마다 실행 콘텍스트가 새로 생성되며, 자기 자신을 재귀 호출할 때도 마찬가지이다.
• 함수형 프로그래밍은 함수를 최대한 사용하려고 하므로, 유연성과 재사용을 늘리고자 당면한 문제를 가능한 한 많은 함수로 분해하고 커리하는 건 얼마든지 좋지만, 커리된 함수를 지나치게 사용하면 콘텍스트 스택에 어떤 식으로든 영향을 끼친다.

🎈 커링과 함수 콘텍스트 스택

• 추상화를 한 꺼풀 더 입히면 일반적인 함수 평가보다 콘텍스트 오버해드가 더 많이 발생할 수 있다.

const logger = function(appender, layout, layout, name, level, message);
// ...

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

• 위와 같은 중첩 구조는 한 번에 호출하는 것 보다 함수 스택을 더 많이 쓴다.
• logger 함수를 커링 없이 실행하면 자바스크립트는 동기 실행되기 때문에 우선 전역 콘텍스트 실행을 잠시 멈추고 새 활성 콘텍스트를 만든 다음, 변수 해석에 사용할 전역 콘텍스트 레퍼런스를 생성한다.
• logger 함수는 그 안에서 다른 Log4js 연산을 호출하므로 새 함수 콘텍스트가 생성되어 스택에 쌓인다. 자바스크립트 클로저 떄문에 내부 함수 호출로 비롯된 함수 콘텍스트는 다른 콘텍스트 위에 차곡차곡 쌓이며, 각 콘텍스트는 일정 메모리를 차지한 채 scopeChain 레퍼런스를 통해 연결된다.
• 중첩 함수를 실행하면 이런 식으로 함수 콘텍스트가 증가하고, 함수마다 스택 프레임이 새로 생기므로 함수가 중첩된 정보만큼 스택이 커진다. 커링과 재귀는 함수 호출을 중첩하여 작동한다.
• 다시 실행이 순서대로 실행이 완료되면 런타임은 다시 처음 상태로 돌아가고 전역 콘텍스트 단 하나만 실행 상태로 남는다. 이것이 자바스크립트 클로저라는 것이다.
• 모든 함수를 커리하면 항상 좋을 것 같지만, 과용하면 엄청난 메모리가 소모되면서 프로그램 실행 속도가 현저히 떨어질 수 있다.

const add = function (a, b) {
  return a + b;
};

const c_add = curry2(add);

const input = _.range(80000);

addAll(input, add); // -> 511993600000000
addAll(input, c_add); // -> 브라우저가 뻗음

function addAll(arr, fn) {
  let result = 0;
  for(let i = 0; i < arr.length; i++) {
    for(let j = 0; j < arr.length; j++) {
      result += fn(arr[i], arr[j]);
    }
  }
  return result;
}

🎈 재귀 코드의 문제점

• 함수가 자신을 호출할 때에도 새 함수 콘텍스트가 만들어진다.
• 엄청 큰 용량의 데이터를 재귀로 처리할 때에는 배열 크기만큼 스택이 커질 수 있다.
• 리스트, 특히 원소가 아주 많은 리스트는 map, filter, reduce 등의 고계함수를 이용해서 탐색하는 방법이 좋다. 이런 함수를 쓰면 함수 호출을 중첩하지 않고 반복할 때마다 스택을 계속 재활용할 수 있다.

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

• 불필요한 함수 호출을 삼가고 꼭 필요한 입력만 넣고 실행하면 여러모로 성능 향상을 기대할 수 있다.
• 하스켈 같은 함수형 언어는 기본적으로 모든 함수 평가식을 느긋하게 평가(lazy function evaluation) 하도록 지원한다.
• 느긋한 평가는 여러 가지 전략이 있지만, 가능한 한 오래, 의존하는 표현식이 호출될 때까지 미룬다는 근본 사상은 같다.
• 자바스크립트는 기본적으로 함수 결괏값이 필요한지 따져볼 새도 없이 변수에 바인딩되자마자 표현식 평가를 마친다. 그래서 탐욕스런 평가라고 한다.
• 다음 Maybe 모나드 예제이다.

// Maybe 모나드
Maybe.of(student).getOrElse(createNewStudent());

// 아래와 같이 실행될 거 같지만 자바스크립트 엔진은 그렇지 않다.
if(!student) {
  return createNewStudent();
}
else {
  return student;
}

• 자바스크립트 엔진은 조급하게 평가하므로 학생 객체가 null 이든 아니든 createNewStudent 함수를 무조건 실행한다.
• 느긋하게 평가하면, 표현식은 위 코드처럼 작동하겠지만 학생 객체가 정상이 아닐 경우 createNewStudent 함수는 호출하지 않는다.
• 느긋한 평가는 어떻게 활용할 수 있을까?
  1. 불필요한 계산을 피한다.
  2. 함수형 라이브러리에서 단축 융합(shortcut fusion)을 사용한다.

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

• 가장 단순한 용례는 함수를 레퍼런스로 전달하고 조건에 따라 한쪽만 호출하여 쓸데없는 계산을 건너뛰는 것이다.

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');

• 함수 조합기가 알아서 함수 호출을 관장하기 때문에 이 코드는 다음 명령형 코드와 똑같이 작동한다.

var student = findStudent('444-44-4444');
if(student !== null) {
  append('#student-info', student);
}
else {
  append('#student-info', createNewStudent('444-44-4444'));
}

🎈 단축 융합을 활용

• 다음은 로대시 JS를 사용한 거주 국가별 인원수에 따라 정렬한 리스트를 만드는 코드이다.

_.chain([p1, p2, p3, p4, p5, p6, p7])
  .filter(isValid)
  .map(_.property('address.country')).reduce(gatherStats, {})
  .values()
  .sortBy('count')
  .reverse()
  .first()
  .value()

• 이처럼 선언적인 형태로 프로그램을 작성하는 건, 하고 싶은 일을 미리 정의함으로써 함수가 어떻게 작동하든 신경 쓰지 않고 무슨 일을 해야 하는지만 밝힌다는 의미이다.
• 덕분에 단축 융합이라는 기법으로 로대시 JS가 프로그램 실행을 내부적으로 최적화할 수 있다.
• 단축 융합은 몇 개 함수의 실행을 하나로 병합하고 중간 결과를 계산할 때 사용하는 내부 자료구조의 개수를 줄이는 함수 수준의 최적화이다.
• 자료구조가 줄면 대량 데이터를 처리할 때 필요한 과도한 메모리 사용을 낮출 수 있다.
• 다음은 로대시 JS의 느긋한 평가 및 단축 융합을 사용한 것이다.

const square = (x) => Math.pow(x, 2);
const isEven = (x) => x % 2 === 0;
const numbers = _.range(200); // 1 ~ 200 사이의 숫자로 구성된 배열을 생성

const result = 
  _.chain(numbers)
  .map(square)
  .filter(isEven)
  .take(3)  // filter 기준으로 만족하는 처음 세 숫자만 처리한다.
  .value(); // [0, 4, 16]

result.length; // 5

📚 '필요할 때 부르리' 전략

• 반복적인 계산을 피하는 것도 애플리케이션 실행 속도를 끌어올리는 방법으로 캐시를 사용했었다.
• 다음은 함수에 캐시 계층을 간단히 구현한 코드이다.

function cachedFn (cache, fn, args) {
  // 함수 실행 결과를 식별하기 위해 함수명과 인수를 조합하여 키값을 정한다.
  let key = fn.name + JSON.stringify(args);
  if (contains(cache, key)) {
    return get(cache, key);
  }
  else {
    let result = fn.apply(this, args); // 캐시에 값이 없으면 함수를 실행한다. (캐시 미스)
    put(cache, key, result); // 결과를 캐시에 담는다.
    return result;
  }
}

• findStudent 함수 실행을 cachedFn으로 감싸면 다음과 같다.

var cache = {};
cachedFn(cache, findStudent, '444-44-4444'); // 처음에는 캐시 미스이므로 findStudent를 실행
cachedFn(cache, findStudent, '444-44-4444'); // 두 번째는 캐시에 보관된 값을 곧바로 읽는다.

• 하지만 이런 함수에 일일이 이런 래퍼를 두고 호출하게끔 코딩하는 건 상당히 버겁기도 하고 가독성이 떨어지고, 그렇게 작성한 함수는 전역 공유 캐시 객체에 의존하는 부수효과가 있다.
• 그렇기 때문에 함수형 언어에는 메모화(memoization) 라는 메커니즘이 있다.

🎈 메모화

• 함수의 결과를 해당 입력과 연관시키는 일, 즉 다시 말해, 함수의 입력을 어떤 값으로 계산해내는 건 어떤 함수형 프로그래밍의 원리 덕분에 가능할까? 그렇다. 바로 참조 투명성이다.

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

• 순수 함수형 언어는 자동으로 메모화를 실천하지만, 자바스크립트나 파이썬 같은 언어에서는 함수를 언제 메모할지 선택할 수 있는데, 예를 들어 문자열 ROT13 형식으로 인코딩하는 rot13 함수를 보자.

var discountCode = 'functional_js_50_off';

rot13(discountCode); // shapgvbany_wf_50_bss

• 여기서 중요한 점은 rot13 함수에 동일한 문자열을 입력하면 반드시 동일한 문자열이 출력된다 (즉, 참조 투명하다)는 사실이다.
• 바꿔 말해, 이 함수를 메모하면 엄청난 성능 향상을 기대할 수 있다.
• 메모화를 하면 동일한 입력으로 함수를 재호출할 때 내부 캐시가 히트되어 즉시 결과가 반환된다.
• 자바스크립트의 고정밀 시각 API가 그 예이다. 이 API는 Date.now(), console.time() 같은 기본 자바스크립트 함수보다 더 정확한 타임스탬프를 계산하고 함수 호출 경과 시간을 잴 수 있다.
• 시간을 재는 호출을 tap으로 추가

const start = () => now();
const runs = [];
const end = function (start) {
  let end = now();
  let result = (end - start).toFixed(3);
  runs.push(result);
  return result;
};

const test = function (fn, input) {
  return () => fn(input);
};

const testRot13 = IO.form(start)
  // tap 조합기로 모나드를 통해 시작 시간 정보를 전파한다.
  .map(R.tap(test(rot13, 'functional_js_50_off')))
  .map(end);

testRot13.run();
testRot13.run();
assert.ok(runs[0] >= runs[1]);

• 함수 호출에 메모화 추가

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;
  is(fn.length === 0 || fn.length > 1) {
    return fn; // 단항 함수만 메모한다.
  }

  return function () {
    // 함수 인스턴스를 memoized 함수로 감싼다.
    return fn.memoized.apply(fn, arguments); 
  }
}

• 위와 같이 Function 객체를 확장하니 어디서건 메모화 기능을 꺼내 쓸 수 있고 전역 공유 캐시에 접근하는 기시적인 부수효과가 사라졌다.
• 또 함수의 내부 캐시 체제를 추상하여 테스트와 완전히 무관한 코드로 만들었다.
• 여러 인수를 받는 함수의 메모화 과정에는 아무래도 적합한 캐시키를 생성하는 작업이 복잡하고 비싼 연산을 수반하게 되기 때문에 이럴 때 커링을 사용한다.

🎈 커링과 메모화를 활용

• 복잡한 함수, 즉 인수가 여러 개인 함수는 아무리 순수함수라 해도 캐시하기가 어렵다.
• 한 가지 해결 방법은 커링이다.

// 이 함수는 참조 투명하지 않지만, 실제로 값비싼 검색이나 원격 HTTP 요청을 할 때는 보통 결과를 캐시하는 경우가 많다.
const safeFindObject = R.curry(function (db, ssn) {
  // 값비싼 IO 검색 수행
});

const findStudent = safeFindObject(DB('student')).memoize();
findStudent('444-44-4444');

• 단항 함수로 만들면 다루기 쉽고 합성하기도 쉬울 뿐만 아니라, 프로그램을 더 잘게 분해하여 전체를 구성하는 요소별로 메모화하고 캐시를 적용하는 이점을 살릴 수 있다.

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

• 코드를 잘게 나눌수록 메모화 효과는 더욱 커진다.
• 메모화가 일종의 작은 쿼리 캐시 역할을 담당하면서 이미 조회한 객체를 다음에 빨리 접근할 수 있게 보관한다는 점이다.
• 함수를 어떤 값, 즉 느긋하게 계산된 값으로 바라보는 관점에서 메모화는 확실히 그만한 가치가 있다.
• showStudent에 있는 일부 함수를 메모된 함수로 변경한 코드다.

const showStudent = R.compose(
  map(append('#student-info')),
  liftIO,
  getOrElse('학생을 찾을 수 없습니다!'),
  map(csv),
  map(R.props(['ssn', 'firstname', 'lastname'])),
  chain(findStudent),
  chain(checkLengthSsn),
  lift(cleanInput),
);

showStudent('444-44-4444').run(); // 평균 9.2 밀리초 (메모화 X)
showStudent('444-44-4444').run(); // 평균 2.5 밀리초 (메모화 O)

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

• 재귀는 때때로 브라우저를 망치게 한다. 스택이 비정상적으로 커질 때이다.
• 메모화를 이용하면 이런 문제를 해결하는 데 도움이 될 때가 있다.
• 일반적으로, 재귀 호출은 기저 케이스에 도달할 때까지 같은 문제,즉 큰 문제의 하위 문제들을 풀어, 결국 마지막에 스택이 풀리며 최종 결과를 낸다.
• 이때 하위 문제의 결과를 캐시하면 같은 함수를 호출할 때 성능을 끌어올릴 수 있다.

3! = 3 * 2 * 1 = 6
// 4! = 4 x 3! 처럼 계승도 더 작은 계승으로 재귀적 표현이 가능하다.
4! = 4 * 3 * 2 * 1 = 4 * 3! = 24

• 따라서 계승을 계산하는 프로그램은 메모화한 재귀 호출 형태로 구현할 수 있다.

const factorial = ((n) => (n === 0) ? 1
  : (n * factorial(n - 1))).memoize();

factorial(100); // .299밀리초
factorial(101); // .021밀리초

• 계승의 수학적 원리를 메모화 형태로 응용할 수 있어 두 번째 함수를 실행할 때 처리율(throughput)이 확 올라간다.
• 스택 프레임을 관리하고 스택 오염을 방지하는 효과도 있다.
• 처음 factorial(100)을 실행하면 전체 알고리즘을 실행하면 100개의 프레임을 함수 스택에 쌓는다. 이것이 재귀 해법의 흠이다.
• 계승을 계산하는 일처럼 주어진 입력 숫자만큼 프레임 개수가 늘어날 수밖에 없는 경우, 재귀는 스택 공간을 너무 많이 허비하는 경향이 있다.
• 하지만 메모화를 이용하면 다음 숫자를 계산할 때 필요한 스택 프레임 개수를 엄청나게 줄일 수 있다.

📚 재귀와 꼬리 호출 최적화

• 재귀 호출할 때 메모화도 별 도움이 되지 않는 경우가 있다. 함수 입력이 계속 바뀔 수밖에 없어 내부 캐시 계층이 제 임무를 수행할 기회조차 없다면 그렇다.
• 그렇다면 재귀를 일반 루프만큼 실행을 최적화할 방법은 컴파일러가 대신 꼬리 재귀 호출(tail call optimization, TCO) 을 수행하게끔 재귀 호출을 짜면 된다.
• 앞에서 재귀적인 계승 함수를 꼬리 위치에서 재귀하도록 바꾼다.

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

• 이렇게 하면 명령형 버전만큼 신속하게 실행할 수 있다.
• TCO는 **꼬리 호출 제거(tail call elimination)**라고도 하는데, ES6부터 신설된 컴파일러 개선 항목으로서, 재귀 호출 실행을 단일 프레임으로 눌러 펴 실행한다.
• 물론 재귀 프로그램이 제일 마지막에 다른 함수(보통 자기 자신)를 호출할 경우에만 TCO가 일어난다. 이때 마지막 호출이 꼬리 위치에 있다고 부른다.
• 이렇게 하는 것이 최적일까??
• 재귀 함수가 가장 마지막에 함수를 호출하면, 자바스크립트 런타임은 남은 할 일이 없기 때문에 더 이상 현재 스택 프레임을 붙들고 있을 이유가 없고 따라서 그대로 폐기한다.
• 함수 콘텍스트에서 필요한 상태 값은 대부분 인수 형태로 다음 함수에 넘기면 된다.
• 이러면 재귀를 반복할 때마다 스택에 새 프레임이 계속 쌓이지 않고 이전에 쓰고 버린 프레임을 재활용할 수 있다.

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

• 자바스크립트의 TCO 체제를 활용하여 계승 함수를 최적화할 수 있다.

// 초기 버전의 재귀 함수
const factorial = (n) =>
  (n === 1) ? 1
            : (n * factorial(n - 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));
}

• 함수가 마지막으로 취하는 행위, 즉, _.first(arr) + sum(_.rest(arr))은 꼬리 호출이 아니다.
• 후속 호출과 공유할 데이터는 함수 인수의 일부로 추가한다.

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

• 여기서 유의할 점은, TCO가 ES4 시절 처음 초안이 나온 이후 지금은 사실상 자바스크립트 표준이 되었지만 아직 이를 지원하지 않는 브라우저가 더 많다. (그래서 바벨과 트랜스파일러를 사용)

📚 마치며

• 함수형 코드는 동등한 명령형 코드보다 더 느리게 실행되거나 더 많은 메모리를 점유하는 경우가 있다.
• 조합기로 대체하거나 로대시JS 같은 함수형 라이브러리의 도움을 받아 느긋하게 평가하는 지연 전략을 구사할 수 있다.
• 메모화는 내부적인 함수 수준의 캐시 전략으로, 잠재적으로 값비싼 함수를 중복 평가하지 않게 한다.
• 프로그램을 단순 함수로 분해하면, 메모화를 통해 보다 효율적인, 확장 가능한 코드로 개발할 수 있다.
• 분해의 확장판인 재귀는 자기 반복적인, 더 단순한 문제들로 나누어 해법을 찾는 기법이다. 콘텍스트 스택 사용까지 최적화하려면 메모화를 십분 활용해야 한다.
• 꼬리 재귀 함수로 바꾸면 꼬리 호출 최적화라는 컴파일러 확장 기능을 활용할 여지가 생긴다.