[자바스크립트 성능 최적화] Ch04. 알고리즘과 흐름 제어

 

 

코드가 작다고 꼭 빠른 것도 아니고, 길다고 꼭 느린 것도 아니다

코드의 전반적인 구조도 실행 속도를 결정하는 주요 요인 중 하나

이 장의 내용들은 JS 뿐만 아니라 다른 언어에서도 종종 사용되는 최적화 기법

 

루프

프로그래밍 언어 대부분이 코드 실행 시간의 상당 부분을 루프에서 소비함

무한 루프, 오래 지속되는 루프는 성능에 심각한 악영향을 미칠 수 있음

 

종류

ECMA-262 3판에서는 4가지 타입의 루프를 정의

for-loop

• 초기화, 실행 조건, 실행 후 코드, 루프 몸체로 구성
• 초기화 부분 변수는 루프 레벨이 아니라 함수 레벨임에 유의
• 루프 몸체는 캡슐화됨

for (var i=0; i < num; i++) {
    // loop 몸체
}

while-loop

• 실행 조건, 루프 몸체로 구성된 검사 후 루프(pretest loop)
• 실행 조건 검사 후 실행

var i = 0;
while (i < num) {
    // loop 몸체
    i++;
}

do-while loop

• JS에서 유일한 검사 전 루프(posttest loop)
• 실행 후 조건 평가

var i = 0;
do {
    // loop 몸체
}
while (i++ < num);

for-in loop

• 객체의 속성 열거
• 객체 인스턴스의 속성과 프로토타입 체인을 통해 상속받은 속성 구분하지 않고 모두 반환

for (let prop in object) {
    // loop 몸체
}

(이후 추가된 loop)
for-of loop

• 객체의 요소 열거

for (let ele of object) {
    // loop 몸체
}

성능

위 4가지 loop 중 명확한 속도 차이가 있는 것은 for-in

• 다른 loop에 비해 최대 7배까지 많은 시간 걸림
• 인스턴스 또는 프로토타입 체인을 검색해야 하므로 상당한 부담
• 속성이 몇 개인지 알 수 없는 객체에 대해 루프를 실행하려는 것이 아니면 쓰지 않는 것이 좋다
• 특히 배열에서는 절대 쓰지 말자

 

나머지 loop 성능은 거의 동등함

 

루프의 성능을 높이기 위한 방법

루프 몸체에서 하는 일 줄이기

배열 순회하는 loop 예시

for (let i=0; i < items.length; i++) {
    process(items[i]);
}

 

루프 몸체를 한번 실행할 때마다 내부에서 발생하는 일

1. 실행 조건에서 속성 검색; items.length
2. 실행 조건에서 비교; i < items.length
3. 실행 조건이 true 인지 확인하기 위한 비교; i < items.length === true
4. 증가 연산; i++
5. 배열 검색; items[i]
6. 함수 호출; process(items[i])

 

process 함수 작업 외 이러한 보조 작업을 최소화하여 최적화할 수 있음

 

객체 멤버와 배열 항목 검색 최소화

1. items.length 값을 지역 변수에 복사해 저장
   • ex. const count = items.length;
   • 매번 객체 속성 검색할 필요 없기 때문에, 25% 이상 실행 시간 축소 가능
2. 루프 순서를 거꾸로
   • ex. for (let i = items.length; i--; ) {...}
   • i === 0 일 때 실행 조건이 false로 평가되고, 비교 연산도 줄일 수 있어 50~60%까지 실행시간 줄일 수 있음

 

시간 복잡도가 O(n)일 때 가장 효율적

O(n) 보다 복잡한 경우 반복 횟수 줄이는데 집중하는 것이 좋음

 

반복 횟수 줄이기; Duff's Device

loop 몸체 전체를 펼쳐 여러 번에 걸쳐할 일을 한 번에 하도록 하는 것

• C언어로 구현된 테크닉을 Jeff Greenberg가 최초로 JS에 적용
• 반복 횟수가 1,000회 넘어가면 큰 차이 보임, 50만 회 반복 시 일반 반복문 보다 성능 70% 향상
• 배열 항목이 12개인 경우, 8로 나눈 나머지 4번 미리 시행하고, 다음 loop에서 8번 시행

var iterations = items.length % 8, i = items.length - 1;

// 아래 loop에서 한번에 8번씩 실행하기 위해
// 8로 나눈 나머지 미리 시행
while (iterations) {
    process(items[i--]);
    iterations--;
}

// loop 한번에 8번 process
iterations = Math.floor(items.length / 8);
while (iterations) {
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    process(items[i--]);
    iterations--;
}

 

함수에 기반을 둔 loop

forEach

• ECMA-262 5판에서 array 객체에 도입
• 편리하지만 배열 항목 전체에 대해 함수를 호출하기 때문에 loop보다 느림
• 최대 8배까지 느리므로 실행 속도가 중요할 때는 지양

items.forEach(function(value, index, array) {
    process(value);
});

 

---

조건문

if-else vs. switch

• 테스트할 조건이 몇 개냐에 따라 성능은 다름
• 조건이 많을수록 switch가 좀 더 빠르고, 가독성이 중요

 

if-else 최적화

• 분기하기 전 평가해야 하는 조건의 수를 최소한으로 줄여야 하므로, 많이 쓰이는 순서로 조건을 나열
  • 실제 평가되는 데이터의 속성에 따라 다름
• if-else 중첩
  • 한 단계에 여러 개의 if-else가 있는 경우 최악의 경우 n번의 조건 평가
  • 중첩된 if-else로 조건 평가 횟수 줄이면, binary search와 유사한 방법으로 최적화 가능

// 한 단계에 여러개의 if-else 있는 경우
// 최대 10번 조건 평가
if (value === 0) return result0;
else if (value === 1) return result1;
...
else if (value === 9) return result9;
else return result10;

// 위 코드를 개선해 중첩 if-else로 변경
// 최대 4번 조건 평가
if (value < 6) {
    if (value < 3) {
        if (value === 0) return result0;
        else if (value === 1) return result1;
        else return result2;
    } else {
        //
    }
} else {
    if (value < 8) {
        //
    } else {
        //
    }
}

 

참조 테이블

• 테스트할 값이 아주 많다면 조건문 쓰지 말고
• 배열, Map 활용해 참조 테이블 구현하는 것이 훨씬 빠를 수 있음
• 조건문 평가 결과가 key-value 형태로 1:1 대응인 경우 가장 유용
• 조건 평가를 배열 항목, 객체 멤버 참조로 대체

const results = [result0, result1, result2, result3, result4, result5, result6, result7, result8, result9, result10];

return results[value];

 

---

재귀

잘못 정의됐거나 종료 조건을 명시하지 않은 재귀 함수는 오래 실행되거나 브라우저 콜 스택 제한 초과할 가능성이 큼

 

콜 스택 제한

JS 엔진에 따라 재귀 허용 한도는 다름

• IE는 시스템 메모리에 따라 다름
• 다른 브라우저들은 고정
• 최신 브라우저일수록 한도가 커지는 경향; Safari 2는 100으로 제한
• 몇몇 브라우저는 JS 에러로 간주해 try-catch로 처리할 수 있기는 함, 콜 스택 크기 초과할 가능성 있는 코드는 애초에 배포하면 안 됨

 

재귀 패턴

• 종료 조건이 정확한지 확인
• 너무 많은 재귀가 실행되는 것은 아닌지 확인 후 반복, 메모이제이션으로 변경 등

 

일반적인 패턴

function recurse() {
    recurse();
}

recurse();

 

상호 참조하는 경우

• 무한 루프 발생
• 찾기도 어려움

function first() {
    second();
}

function second() {
    first();
}

first();

 

반복

• 재귀로 구현할 수 있는 알고리즘은 모두 반복문으로 구현 가능
• 반복문 코드가 재귀 코드보다 조금 느릴 수는 있으나 콜 스택 제한 초과하는 경우는 없음
  • leetcode에서 채점한 결과만 보면, `shift` 연산 때문인지 보통은 재귀 코드가 빠른 경우가 많았음
• 일반적으로 프로세스를 몇 가지 루프로 나누어 구현하기 때문에 성능 부하가 있지만
• 루프 성능 부하는 함수 성능 부하보다 낮기 때문에 재귀를 최적화된 루프로 대체하여 성능 개선
• ex. 병합 정렬

function merge(left, right) {
    const result = [];

    while (left.length > 0 && right.length > 0) {
        (left[0] < right[0])
            ? result.push(left.shift())
            : result.push(right.shift());
    }

    return result.concat(left).concat(right);
}

function mergeSort(items) {
    if (items.length === 1) return items;

  const len = items.length;
    const work = [];
    for (let i = 0; i < len; i++) {
        work.push([items[i]]);
    }
    work.push([]);

  for (let lim = len; lim > 1; lim=Math.floor((lim + 1) / 2)) {
    for (let j=0, k=0; k < lim; j++, k+=2) {
      work[j] = merge(work[k], work[k+1]);
    }
    work[j] = [];
  }
  return work[0];
}

 

메모이제이션

메모이제이션 함수로 구현한 팩토리얼

function memoize(func, cache) {
  cache = cache || {};
  const shell = function (arg) {
    if (cache[arg] === undefined) {
      cache[arg] = func(arg);
    }
    return cache[arg];
  }
  return shell;
}

function factorial(n) {
  if (n < 2) return 1;
  return factorial(n-1) * n;
}

const memFactorial = memoize(factorial, {0: 1, 1: 1});
console.log(memFactorial(10));
console.log(memFactorial(6));
console.log(memFactorial(9));
console.log(memFactorial(4));