분기 테이블
컴퓨터 프로그래밍에서 분기 테이블(branch table) 또는 점프 테이블(jump table)은 분기나 점프 명령어들을 이용해서, 프로그램의 제어를 프로그램의 다른 부분으로 옮기는 방법이다. 이것은 다방향 분기의 형태이다. 분기 테이블 구조는 주로 Switch 문을 구현하는, 컴파일러에 의해 생성된 어셈블리어 프로그램에 사용된다.
전형적인 구현
[편집]분기 테이블은 명령어 길이와 연속된 인덱스를 곱함으로써 생성된 오프셋을 사용함으로써 분기된, 무조건적 분기 명령어들의 연속적인 리스트로 이루어져 있다. 이것은 분기를 위한 기계어 명령어가 고정된 길이를 갖고 있으며, 대부분의 하드웨어에 의해 매우 효율적으로 실행되고, 쉽게 연속적 지수 값으로 전환될 수 있는 원시 자료 값을 다루는데 매우 유용하다. 이러한 주어진 값으로, 분기 테이블은 매우 효과적이 될 수 있다. 이것은 보통 3단계로 이루어진다.
- 받아들여질 수 있게 입력 데이터를 선택적으로 유효화한다. (만약 입력이 단일 바이트이고 256바이트 번역 테이블이 아래의 오프셋을 획득하기 위해 직접적으로 사용된다면, 이것은 다음 단계의 한 부분으로써 비용 없이 일어날 수 있다.) 또한 만약 입력 값에 대한 의심이 없다면, 이 단계는 생략될 수 있다.
- 데이터를 오프셋으로 변형해서 분기 테이블에 넣는다. 이것은 보통 명령어 길이를 계산하기 위해 곱하고 시프트하는 것과 관련된다. 만약 정적 번역 테이블이 사용된다며, 이 곱셈은 다른 시간 비용 없이 직접 또는 컴파일러에 의해 수행될 수 있다.
- 주소로 분기하는 것은 분기 테이블의 베이스 주소와 방금 생성된 오프셋의 합으로 구성된다. 이것은 가끔 프로그램 카운터 레지스터 오프셋에의 덧셈과 관련된다. (몇몇 명령어 집합에서, 분기 명령어가 추가적인 인덱스 레지스터를 허용하지 않는 한) 이 마지막 주소는 보통 무조건적인 분기 명령어들의 결과 또는 자기 바로 다음 명령어(테이블에서 한 엔트리를 절약하며)를 가리킨다.
아래의 가상 코드는 개념을 설명한다.
... validate x /* transform x to 0 (invalid) or 1,2,3, according to value..) */
y = x*4; /* multiply by branch instruction length (e.g. 4 ) */
goto next(y); /* branch into 'table' of branch instructions */
/* start of branch table */
next: goto codebad; /* x= 0 (invalid) */
goto codeone; /* x= 1 */
goto codetwo; /* x= 2 */
... rest of branch table
codebad: /* deal with invalid input */
주소들을 사용한 대체 구현
[편집]분기 테이블을 구현하는 다른 방법으로, 요구되는 검색된 함수의 주소들에서의 포인터들의 정렬로 가능하다. 이 방법은 또한 최근들어 "디스패치 테이블" 또는 "가상 메소드 테이블"로 불리기도 하지만 어쨌든 같은 행돌을 수행한다. 이 포인터 함수 방식은 하나의 기계어를 줄일 수 있으며, 간접 점프를 피할 수 있다.
함수들을 가리키는 포인터들의 결과 리스트는 직접적인 스레디드 코드와 거의 비슷하며, 제어 테이블과도 개념적으로 비슷하다.
분기 테이블을 구현하는데 사용되는 실제 방식은 아래에 기반한다.
- 코드가 실행되는 프로세서의 구조
- 컴파일 된 또는 인터프리터 언어
- 늦은 바인딩과 관련 여부에 따라
역사
[편집]분기 테이블과 원시 자료의 사용은 메모리가 비싸고 CPU가 느리며, 압축된 데이터 표현과 대안의 효율적인 선택이 중요했던, 컴퓨터의 초기 시절에는 흔했다. 요즘은 이것들이 보통 다음과 같이 사용된다.
- 임베디드 프로그래밍
- 운영 체제 개발. 많은 운영체제에서, 시스템 호출과 라이브러리 함수들은 분기 테이블에 대한 정수 인덱스에 의해 참조된다.
- IBM/360 같은 몇몇 컴퓨터 구조는 분기 테이블을 인터럽트 디스패치를 위해 사용한다.
장점
[편집]분기 테이블의 장점은 아래와 같다.
- 코드 압축 구조
- 감소된 소스 구문
- 리턴 코드를 각각 테스트해야 할 필요성의 감소
- 알고리즘과 코드 효율성 그리고 높은 데이터 압축 비율을 달성할 가능성
정수에 의해 참조되는 라이브러리 함수들
- 하위 소프트웨어 버전과의 호환성 증가. 만약 함수와 엔트리 포인트의 주소 코드가 바뀌면, 오직 분기 테이블의 분기 명령어만 바꾸면 된다.
게다가, 평범한 애플리케이션 프로그래밍 시 번호(테이블의 인덱스)에 의한 함수 호출이 유용할 때가 있다.
단점
[편집]- 추가적인 인다이렉션
- 몇몇 언어들에서의 제한
예시
[편집]8비트 PIC 마이크로컨트롤러 어셈블리어에서의 사용
movf INDEX,W ; move the index value into the W (working) register from memory
addwf PCL,F ; add it to the program counter. each PIC instruction is one byte
; so there is no need to perform any multiplication.
; Most architectures will transform the index in some way before
; adding it to the program counter
table ; the branch table begins here with this label
goto index_zero ; each of these goto instructions is an unconditional branch
goto index_one ; of code
goto index_two
goto index_three
index_zero
; code is added here to perform whatever action is required when INDEX = zero
return
index_one
...
C에서의 점프 테이블 예시
[편집]아래는 단지 분기 테이블이 아니라 점프 테이블을 보여준다. 이것은 프로그램이 현재의 프로시저/함수 외부에서 호출되는 것을 막는다.
#include <stdio.h>
#include <stdlib.h>
typedef void (*Handler)(void); /* A pointer to a handler function */
/* The functions */
void func3 (void) { printf( "3\n" ); }
void func2 (void) { printf( "2\n" ); }
void func1 (void) { printf( "1\n" ); }
void func0 (void) { printf( "0\n" ); }
Handler jump_table[4] = {func0, func1, func2, func3};
int main (int argc, char **argv) {
int value;
/* Convert first argument to 0-3 integer (modulus) */
value = ((atoi(argv[1]) % 4) + 4) % 4;
/* Call appropriate function (func0 thru func3) */
jump_table[value]();
return 0;
}
컴파일러에 의해 생성된 분기 테이블
[편집]프로그래머들은 흔히 컴파일러가 검색 키들을 통해 정확한 선택을 할 수 있다고 믿으며, 분기 테이블을 만들어야 할지를 컴파일러에게 맡긴다. 이것은 검색키의 범위가 제한되어 있을 때 최적화하는 컴파일러에게 쉬운 일이라는 점에서 사실이다. 그러나 컴파일러는 인간만큼 똑똑하지 않으며, 문맥에 대한 깊은 지식이 없다. 예를 들면, 검색키 정수 값이 1, 2, 4, 6, 7, 20, 23, 40, 42, 50 & 1000일 경우에 생성되는 분기 테이블은 900개 이상의 빈 엔트리가 포함된 매우 큰고 이점이 사라진 형태가 된다. 물론 이 애플리케이션이 매우 시간 중시적이고 메모리 요구에는 관심이 없을 수 있다.[1]
그러나 작은 상식이 이러한 상황을 바꿔줄 수 있다. 결정을 아래와 같이 지원하는 것이다. (물론 궁극적인 선택은 컴파일러가 한다.)
- 첫째로, 검색키 = 1000을 테스트하고 적절한 분기를 수행한다.
- 컴파일러가 남은 검색키 (1-50)에 대한 분기 테이블을 생성하게 한다.
위와 비슷한 형식으로 차이가 큰 범위에 사용할 수 있다.
분기 테이블을 위한 인덱스 생성
[편집]분기 테이블에서의 사용 가능한 명확한 정수 값이 있는 것은 아니지만, 검색키는 몇몇 산술 변환이나 간단히 데이터베이스의 원시 번호 또는 검색키들을 포함하는 배열의 엔트리 번호 등으로 생성된다.
해시 테이블도 몇몇 경우에 사용되기도 한다.
기법의 다른 사용들
[편집]비록 분기 테이블을 사용하는 분기 기법은 단지 프로그램 흐름 변경을 위해 사용되지만, 이 기법은 다른 목적으로 사용될 수도 있다. 예를 들면 컴파일러 최적화나 루프 풀기에 대한 JIT 컴파일러에서 사용되기도 한다.
같이 보기
[편집]각주
[편집]외부 링크
[편집]- [1] Example of branch table in Wikibooks for IBM S/360
- [2] Examples of, and arguments for, Jump Tables via Function Pointer Arrays in C/C++
- [3] Example code generated by 'Switch/Case' branch table in C, versus IF/ELSE.
- [4] Example code generated for array indexing if structure size is divisible by powers of 2 or otherwise.
- [5] "Arrays of Pointers to Functions" by Nigel Jones