자바스크립트 점프테이블에 대해 알아보기

점프를… 한다고…?

Jump table (=점프 테이블)

• 정의
  • 예시
• 용도
• 정리

정의

컴퓨터 프로그래밍에서 분기 테이블(branch table) 또는 점프 테이블(jump table)은 분기나 점프 명령어들을 이용해서, 프로그램의 제어를 프로그램의 다른 부분으로 옮기는 방법이다. 이것은 다방향 분기의 형태이다. 분기 테이블 구조는 주로 Switch 문을 구현하는, 컴파일러에 의해 생성된 어셈블리어 프로그램에 사용된다. - 출처 위키백과

점프 테이블은 역사적으로 컴퓨터의 초기 시절, 느린 CPU와 비싼 메모리의 자원을 효율적으로 선택해야만 했던 시절에 많이 사용 되었다.

프로그램의 흐름을 제어하는 하나의 기법으로 사용된다.

예시

const handlers = {
    start: ctx => {
        console.log("start: ", ctx);
        return 'process';
    },
    process: ctx => {
        console.log("process: ", ctx);
        return 'end';
    },
    end: () => {
        console.log('end');
        return null;
    }
}

function runStateMachine(initialState, ctx) {
    let state = initialState;
    while (state) {
        state = handlers[state]?.(ctx) || null;
    }
}

runStateMachine('start', 'A');
// start: A
// process: A
// end

이렇게 작성할 수 있다. 물론 저 output을 받을 수 있는 방법은 아주 다양하나, 이 방식의 장점은 금세 눈에 들어온다. 해당 인터페이스를 지키기만 한다면 안정적으로 상태를 진행시킬 수 있다.

또한 initialState 를 동적으로 고를 수 있다는 점, handlers 코드를 작성하고 나면 원하는 지점으로 점프 시킬 수 있다는 점도 훌륭하다.

회사에서 공통적인 코드를 작성할 때도 좋은 방법일 것 같다.

용도

용도는 위의 예시에서도 확인할 수 있듯이 state machine을 구현하거나 if-else문의 분기가 많을 경우에도 사용할 수 있다.

특히 if-else 혹은 switch-case 분기가 길어지면 길어질수록 사용을 검토해보는 것이 좋은데, 이유는 if-else나 switch-case보다 보다 속도가 빠르다.

단순한 예시로 if-else는 아래와 같이 작성된다.

const e = 'e';

if(e === 'a') {
// ... 어떤 작업
} else if(e === 'b') {
// ... 어떤 또 다른 작업
} else if(e === 'c') {
// ... 어떤 또 다른 작업
}
//...
else if(e === 'e') {
// 어떤 작업
}

이를 점프 테이블로 작성한다면

const handlers2 = {
    a: () => 'a',
    b: () => 'b',
    c: () => 'c',
    d: () => 'd',
    e: () => 'e'
};

function runHandlers2(key) {
    return handlers2[key]?.() || null;
}

위의 if-else문은 최악의 경우 O(n)만큼 시간복잡도가 소요되며, 점프 테이블은 공간복잡도를 소모해 시간복잡도를 O(1)로 단축시킨다.

이를 정리하면 아래와 같다.

• 공간복잡도는 분기 케이스만큼 늘어나게 된다.

정리

현업의 코드들은 정말 많은 if-else에 시달리고 있다. 이걸 깔끔하게 정리하는 방법이 없을까 고안하던 중에 babel로 최적화 된 코드들을 디버깅하다 찾게 되었다.

babel로 최적화되는 코드들은 조금 더 기괴하게 생겼는데, 대략 이렇게 생겼다.

let state = 2;
while(true) {
    switch(state) {
        case 1:
        // 뭔가 함..
        state = 2;
        break;
        case 2:
        // 뭔가..
        state = 3;
        break;
        case 3:
        //...
    }
    break;
}

이렇게 생긴 코드는 위에서 언급한 점프 테이블이 아닌 단순 switch-case문으로, switch-case 문은 if-else와 비슷하게 위에서부터 아래로 모든 요소를 검사한다 (break를 만날 수 있겠음)

이 방식도 결국 O(n)만큼 시간을 소모하게 된다.

단, 위의 switch-case는 case가 숫자로 되어 있는데, 이는 js 엔진이 switch-case의 case문의 숫자가 연속적일 경우 배열로 만든 점프 테이블로 치환할 수 있게 된다. (엔진에 따라 하는 경우도 있고 아닌 경우도 있다.)

예를 들어

const handlers = [
() => console.log('case 0'),
() => console.log('case 1'),
() => console.log('case 2'),
...
];
const val = 0'
handlers[val]?.();

if-else를 탈출 할 수 있는 방법으로 기억해두면 좋겠다.