맨위로가기

분기 테이블

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
목차

1. 개요

분기 테이블은 프로그램의 실행 흐름을 제어하기 위해 사용되는 자료 구조로, 특정 조건에 따라 실행될 코드 블록을 선택하는 데 활용된다. 분기 테이블은 일반적으로 무조건적 분기 명령어들의 연속적인 리스트로 구성되며, 입력 데이터를 오프셋으로 변환하여 해당 오프셋에 해당하는 코드 블록으로 분기하는 방식으로 작동한다. 분기 테이블은 코드 압축, 소스 구문 감소, 하위 소프트웨어 버전과의 호환성 증가 등의 장점을 가지지만, 추가적인 간접 참조로 인해 성능 저하를 유발할 수 있다. 분기 테이블은 초기 컴퓨터 시절 메모리 제약으로 인해 널리 사용되었으며, 현재는 임베디드 시스템, 운영 체제 개발, 인터럽트 디스패치 등 다양한 분야에서 활용된다.

더 읽어볼만한 페이지

  • 조건문 - 패턴 매칭
    패턴 매칭은 데이터 구조나 문자열에서 특정 패턴을 찾아 식별하는 기법으로, 다양한 프로그래밍 언어와 시스템에서 사용되며 데이터 필터링, 추출 및 선언적 프로그래밍에 중요한 역할을 수행한다.
  • 조건문 - Switch 문
    Switch 문은 변수나 표현식 값에 따라 프로그램 제어 흐름을 분기하는 제어문으로, 다양한 프로그래밍 언어에서 구현되어 여러 실행 경로 중 하나를 선택적으로 실행하며, 폴스루 동작 처리 방식에서 언어별 차이를 보인다.
  • 컴퓨터 성능 - 전송 (컴퓨팅)
    전송은 컴퓨터 시스템에서 데이터 전송 속도를 나타내는 단위로, 초당 전송 횟수를 의미하며, MT/s는 SCSI 등에서, GT/s는 PCI Express에서 주로 사용된다.
  • 컴퓨터 성능 - 초당 명령 수
    초당 명령 수는 컴퓨터 성능 지표로서 초당 실행 명령어 수를 나타내는 단위이며, MIPS는 유사한 아키텍처 프로세서 성능 비교에 유용하나, 벤치마크 테스트와 함께 다른 아키텍처 간 비교에 활용된다.
분기 테이블

2. 전형적인 구현

분기 테이블은 무조건 분기 명령어의 순차적 목록으로 구성되며, 순차적 인덱스를 명령어 길이(각 분기 명령어가 차지하는 메모리 내 바이트 수)로 곱하여 생성된 오프셋을 사용하여 분기한다. 이는 분기용 기계어 명령어가 고정된 길이를 가지며 대부분의 하드웨어에서 매우 효율적으로 실행될 수 있다는 사실에 의존한다. 원시 데이터 값을 처리할 때 가장 유용하며, 쉽게 순차적 인덱스 값으로 변환될 수 있다. 이러한 데이터가 주어지면 분기 테이블은 매우 효율적일 수 있다.

2. 1. 구현 단계

분기 테이블은 보통 다음 3단계로 구현된다.

# 입력 데이터를 선택적으로 유효화하여 허용 가능한지 확인한다. 입력이 단일 바이트이고 256바이트 변환 테이블이 아래의 오프셋을 획득하기 위해 직접적으로 사용된다면, 다음 단계의 한 부분으로써 비용 없이 일어날 수 있다. 또한 만약 입력 값에 대한 의심이 없다면, 이 단계는 생략될 수 있다.

# 데이터를 분기 테이블의 오프셋으로 변환한다. 이것은 보통 명령어 길이를 계산하기 위해 곱하고 시프트하는 것과 관련된다. 만약 정적 번역 테이블이 사용된다면, 이 곱셈은 다른 시간 비용 없이 직접 또는 컴파일러에 의해 수행될 수 있다.

# 주소로 분기하는 것은 분기 테이블의 베이스 주소와 방금 생성된 오프셋의 합으로 구성된다. 이것은 가끔 프로그램 카운터 레지스터 오프셋에 덧셈하는 것과 관련된다. (몇몇 명령어 집합에서, 분기 명령어가 추가적인 인덱스 레지스터를 허용하지 않는 한) 이 마지막 주소는 보통 무조건 분기 명령어들의 결과 또는 자기 바로 다음 명령어(테이블에서 한 엔트리를 절약하며)를 가리킨다.

아래의 가상 코드는 이 개념을 설명한다.

```c

... validate x /* x를 0 (유효하지 않음) 또는 1,2,3으로 변환(값에 따라..) */

y = x*4; /* 분기 명령어 길이(예: 4 )를 곱함 */

goto next(y); /* 분기 명령어의 'table'로 분기 */

/* 분기 테이블 시작 */

next: goto codebad; /* x= 0 (유효하지 않음) */

goto codeone; /* x= 1 */

goto codetwo; /* x= 2 */

... rest of branch table

codebad: /* 유효하지 않은 입력을 처리 */

2. 2. 가상 코드 예시

분기 테이블의 개념을 설명하는 가상 코드는 다음과 같다.[1]

```

... validate x /* x를 0 (유효하지 않음) 또는 1, 2, 3으로 변환(값에 따라..) */

y = x * 4; /* 분기 명령어 길이(예: 4)를 곱함 */

goto next + y; /* 분기 명령어의 'table'로 분기 */

/* 분기 테이블 시작 */

next: goto codebad; /* x= 0 (유효하지 않음) */

goto codeone; /* x= 1 */

goto codetwo; /* x= 2 */

... 분기 테이블의 나머지 부분

codebad: /* 유효하지 않은 입력을 처리 */

```

이 코드는 다음과 같은 단계를 거친다.

1. `x` 값을 검증한다. (선택적)

2. `x`에 분기 명령어의 길이를 곱하여 오프셋 `y`를 계산한다.

3. `next + y`로 분기하여 분기 테이블로 진입한다.

4. 분기 테이블 (`next` 레이블 이후)에서 `x` 값에 따라 적절한 코드로 분기한다.

5. 유효하지 않은 입력은 `codebad` 레이블에서 처리한다.

3. 주소를 사용한 대체 구현

분기 테이블은 필요한 함수의 주소를 담은 포인터 배열을 사용하여 구현할 수 있다. 이 방법은 "디스패치 테이블" 또는 "가상 메소드 테이블"이라고도 불리지만, 동일한 기능을 수행한다. 이러한 포인터 함수 방식은 기계어 명령 하나를 절약하고 간접 점프를 피할 수 있게 한다.[1]

함수 포인터 목록은 스레디드 코드와 유사하며, 제어 테이블과도 개념적으로 비슷하다.[1]

3. 1. 장점 (주소 기반 구현)

분기 테이블을 구현하는 또 다른 방법은 필요한 함수의 주소를 검색하는 포인터 배열을 사용하는 것이다. 원래 '''전송 벡터'''로 알려진 이 방법은 최근 "디스패치 테이블" 또는 "가상 메서드 테이블"과 같은 다양한 이름으로도 알려져 있지만, 본질적으로는 정확히 동일한 목적을 수행한다. 이 포인터 함수 방법은 하나의 기계 명령어를 절약하고 간접 점프(분기 명령어 중 하나)를 피할 수 있다.[1]

결과적인 함수 포인터 목록은 직접적인 스레드 코드와 거의 동일하며 제어 테이블과 개념적으로 유사하다.[1]

분기 테이블 구현에 사용되는 실제 방법은 일반적으로 다음을 기반으로 한다.[1]

  • 코드가 실행될 프로세서의 아키텍처
  • 컴파일된 언어인지 해석된 언어인지 여부
  • 늦은 바인딩 관련 여부

4. 역사

분기 테이블 및 기타 원시 자료 인코딩의 사용은 메모리가 비쌌고, CPU가 더 느렸으며, 데이터의 간결한 표현과 효율적인 대안 선택이 중요했던 초창기 컴퓨팅 시대에 일반적이었다. 오늘날에도 다음과 같은 분야에서 일반적으로 사용된다.


  • 임베디드 프로그래밍
  • 운영 체제 개발. 많은 운영 체제에서 시스템 콜과 라이브러리 함수는 분기 테이블의 정수 인덱스로 참조될 수 있다.
  • IBM/360과 같은 일부 컴퓨터 아키텍처는 인터럽트를 디스패치하기 위해 분기 테이블을 사용한다.

5. 장점


  • 코드 압축 구조 (반복적인 분기 연산 코드에도 불구하고)[1]
  • 감소된 소스 문 (반복적인 `If` 문과 비교하여)[1]
  • 개별적인 반환 코드 테스트 필요성 감소 (후속 프로그램 흐름을 결정하기 위해 호출 지점에서 사용되는 경우)[1]
  • 알고리즘 및 코드 효율성 (데이터는 한 번만 인코딩하면 되며, 분기 테이블 코드는 일반적으로 압축되어 있으며, 높은 데이터 압축 비율을 달성할 수 있는 잠재력이 있다). 예를 들어, "Central African Republic"와 같은 문자열을 단일 인덱스로 압축할 수 있으며, 이는 문자열이 여러 번 나타날 때 상당한 절약 효과를 가져온다. 또한, 동일한 인덱스를 사용하여 별도의 테이블에서 관련 데이터에 액세스하여 저장 공간 요구 사항을 더욱 줄일 수 있다.[1]
  • 라이브러리 함수의 경우, 정수로 참조될 수 있다.[1]
  • 후속 소프트웨어 버전과의 호환성 향상. 함수의 코드와 진입점 주소가 변경된 경우, 분기 테이블의 분기 명령어만 조정하면 된다. 라이브러리에 대해 컴파일되거나 운영 체제용으로 컴파일된 응용 소프트웨어는 수정할 필요가 없다.[1]


또한, 번호(테이블의 인덱스)로 함수를 호출하는 것은 일부 경우 일반적인 응용 프로그래밍에서 유용할 수 있다.[1]

6. 단점


  • 추가적인 인다이렉션이 있다.
  • 몇몇 언어들에서는 제약이 있다.
  • 추가적인 간접 참조 레벨이 있어, 일반적으로 약간의 성능 저하가 발생한다.
  • 일부 프로그래밍 언어에서는 제약이 있지만, 일반적으로 다중 분기의 기본 개념을 구현하는 다른 방법이 있다.

7. 예시

다음은 8비트 PIC 마이크로컨트롤러 어셈블리어와 C 언어에서의 분기 테이블 사용 예시이다.

PIC 마이크로컨트롤러 어셈블리어에서는 `table` 레이블 아래에 `goto` 명령어를 사용하여 분기 테이블을 구성하고, C 언어에서는 함수 포인터 배열 `jump_table`을 사용하여 분기 테이블을 구현한다.

7. 1. PIC 마이크로컨트롤러 어셈블리어

assembly

movf INDEX,W ; 인덱스 값을 메모리에서 W (작업) 레지스터로 이동한다.

addwf PCL,F ; 프로그램 카운터에 더한다. 각 PIC 명령어는 1바이트이므로 곱셈을 수행할 필요가 없다.

; 대부분의 아키텍처는 인덱스를 프로그램 카운터에 추가하기 전에 어떤 방식으로든 변환한다.

table ; 분기 테이블은 이 레이블로 시작한다.

goto index_zero ; 이러한 각 goto 명령어는 코드의 무조건 분기이다.

goto index_one

goto index_two

goto index_three

index_zero

; INDEX = 0일 때 필요한 작업을 수행하기 위해 여기에 코드가 추가된다.

return

index_one

...

```

8비트 PIC 마이크로컨트롤러 어셈블리 언어에서 분기 테이블을 사용하는 간단한 예시이다.

참고: 이 코드는 PCL < (table + index_last)인 경우에만 작동한다. 이 조건을 보장하기 위해 "org" 지시어를 사용할 수 있다. GOTO (예: PIC18F)가 2바이트인 경우 테이블 항목 수를 128개 미만으로 제한한다.

7. 2. C 언어

c

#include

#include

typedef void (*Handler)(void); /* 핸들러 함수에 대한 포인터 */

/* 함수 */

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;

/* 첫 번째 인수를 0-3 정수로 변환 (나머지 연산) */

value = atoi(argv[1]) % 4;

/* 적절한 함수 호출 (func0 ~ func3) */

jump_table[value]();

return 0;

}

```

위 코드는 점프 테이블을 활용한 예시이다. 점프 테이블을 이용하면 현재 프로시저/함수 외부의 프로그램 블록을 호출할 수 있다.

8. 컴파일러에 의해 생성된 분기 테이블

프로그래머들은 분기 테이블 생성 여부를 컴파일러에게 맡기는 경우가 많으며, 컴파일러가 알려진 검색 키로부터 올바른 선택을 할 수 있다고 믿는다. 이는 검색 키의 범위가 제한적인 경우에 최적화 컴파일러에게는 사실일 수 있다. 하지만 컴파일러는 인간만큼 지능적이지 않으며 '상황'에 대한 깊은 지식을 가질 수 없다.[2]

예를 들어, 가능한 검색 키 정수 값이 1, 2, 4, 6, 7, 20, 23, 40, 42, 50, 1000과 같이 매우 적더라도, 컴파일러는 900개 이상의 빈 항목을 가진 분기 테이블을 생성할 수 있다. 이 경우, 훌륭한 최적화 컴파일러는 값을 미리 정렬하고 이진 탐색 검색에 대한 코드를 생성하는 '두 번째 최선'의 옵션을 선택할 수 있다. 물론 애플리케이션이 매우 "시간이 중요한" 경우 메모리 요구 사항은 문제가 되지 않을 수 있다.[2]

하지만 약간의 '상식'을 통해 이러한 사례를 간단한 2단계 프로세스로 변환하여 컴파일러의 '결정을 지원'할 수 있다. (궁극적인 선택은 컴파일러에 맡긴다.)

범위 사이에 큰 간격이 있는 두 세트의 짧은 범위가 있는 경우에도 유사한 방식으로 변형하여 사용할 수 있다.

8. 1. 컴파일러 최적화의 한계

프로그래머들은 흔히 컴파일러가 검색 키를 통해 정확한 선택을 할 수 있다고 믿으며, 분기 테이블을 만들어야 할지를 컴파일러에게 맡긴다. 이것은 검색 키의 범위가 제한되어 있을 때 최적화하는 컴파일러에게 쉬운 일이라는 점에서 사실이다.[6] 그러나 컴파일러는 인간만큼 똑똑하지 않으며, 문맥에 대한 깊은 지식이 없다. 예를 들어, 검색 키 정수 값이 1, 2, 4, 6, 7, 20, 23, 40, 42, 50, 1000일 경우, 생성되는 분기 테이블은 900개 이상의 빈 엔트리가 포함된 매우 큰 테이블이 되어 이점이 사라진다. 물론 이 애플리케이션이 매우 시간 중시적이고 메모리 요구에는 관심이 없을 수도 있다.[6][2]

하지만 약간의 상식으로 이러한 상황을 바꿀 수 있다. 다음과 같이 컴파일러의 결정을 지원할 수 있다. (물론 궁극적인 선택은 컴파일러가 한다.)[6]

  • 첫째로, 검색 키 = 1000을 테스트하고 적절한 분기를 수행한다.
  • 컴파일러가 남은 검색 키 (1-50)에 대한 분기 테이블을 생성하게 한다.


위와 비슷한 형식으로 차이가 큰 범위에 사용할 수 있다.[6]

8. 2. 개발자의 역할

프로그래머는 흔히 컴파일러가 검색 키를 통해 정확한 선택을 할 수 있다고 믿으며, 분기 테이블 생성 여부를 컴파일러에게 맡긴다. 이는 검색 키의 범위가 제한되어 있을 때 최적화하는 컴파일러에게 쉬운 일이라는 점에서 사실이다. 그러나 컴파일러는 사람만큼 똑똑하지 않으며, 문맥에 대한 깊은 지식이 없다. 예를 들어, 검색 키 정수 값이 1, 2, 4, 6, 7, 20, 23, 40, 42, 50, 1000일 경우, 생성되는 분기 테이블은 900개 이상의 빈 엔트리가 포함된 매우 큰 형태가 되어 분기 테이블의 이점이 사라진다.[6] 물론 이 애플리케이션이 매우 시간 중시적이고 메모리 요구에는 관심이 없을 수 있다.[2]

그러나 작은 상식이 이러한 상황을 바꿔줄 수 있다. 아래와 같이 결정을 지원할 수 있다. (물론 궁극적인 선택은 컴파일러가 한다.)[6]

  • 첫째로, 검색 키 = 1000을 테스트하고 적절한 분기를 수행한다.
  • 컴파일러가 남은 검색 키 (1-50)에 대한 분기 테이블을 생성하게 한다.


위와 비슷한 형식으로 차이가 큰 범위에 사용할 수 있다.

9. 분기 테이블 인덱스 생성

분기 테이블에 사용할 명확한 정수 값이 없는 경우에도 검색 키(또는 검색 키의 일부)를 산술 변환하여 생성할 수 있으며, 데이터베이스의 행 번호 또는 이전에 키 유효성 검사를 수행하는 동안 발견된 검색 키가 포함된 배열의 항목 번호가 될 수 있다.[1]

어떤 경우에는 해시 테이블이 인덱스를 형성하는 데 필요할 수 있다.[2] 그러나 A-Z와 같은 단일 바이트 입력 값(또는 더 긴 키의 첫 번째 바이트)의 경우 바이트 자체의 내용(원시 데이터)을 2단계, "자명한 해시 함수" 프로세스에서 사용하여 갭이 없는 분기 테이블에 대한 최종 인덱스를 얻을 수 있다.[3]

# 원시 데이터 문자를 숫자 값으로 변환 (예: ASCII 'A' ==> 65 십진수, 0x41 16진수)[4]

# 숫자 정수 값을 256개 항목 2바이트 배열의 인덱스로 사용하여 두 번째 인덱스를 얻습니다(유효하지 않은 항목 0; 갭을 나타내고, 그렇지 않으면 1, 2, 3 등).[5]

이 배열은 가능한 모든 8비트 바이트에 대해 16비트 부호 없는(short) 정수를 저장하기 위해 (256 × 2) 바이트를 초과할 수 없다.[6] 유효성 검사가 필요하지 않고 대문자만 사용되는 경우 배열 크기는 (26 × 2) = 52 바이트로 작을 수 있다.

10. 기타 활용

분기 테이블을 사용하는 분기 기법은 주로 프로그램 흐름 변경을 위해 사용되지만, 다른 목적으로도 활용될 수 있다. 예를 들어, 컴파일러 최적화나 루프 풀기를 위한 JIT 컴파일러에서 사용되기도 한다.[1]

참조

[1] 서적 A Practical Introduction to Computer Architecture Springer Science & Business Media 2009
[2] 웹사이트 How to Create Jump Tables via Function Pointer Arrays in C and C++ http://www.netrino.c[...] 2008-07-12
[3] 웹사이트 Alternate Entry Points (ENTRY) https://gcc.gnu.org/[...] Free Software Foundation 2016-11-25
[4] 웹사이트 FORTRAN Compilers and Loaders http://www.chilton-c[...] ACD 2009-04-10
[5] 웹사이트 A Brief Introduction to Fortran 90 http://www.soton.ac.[...] 2009-04-10
[6] 웹인용 보관된 사본 http://www.netrino.c[...] 2015-10-27


본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com