[C++] jamp table, switch case

Notice

Recent Posts

Recent Comments

Link

« 2025/05 »
일	월	화	수	목	금	토
				1	2	3
4	5	6	7	8	9	10
11	12	13	14	15	16	17
18	19	20	21	22	23	24
25	26	27	28	29	30	31

Tags more

Archives

Today

Total

관리 메뉴

total_activ

[C++] jamp table, switch case 본문

코테/C++ 공부

[C++] jamp table, switch case

INFOO 2023. 11. 10. 14:59

jamp table은 제어권을 다른 특정 위치로 전송하는데 사용되는 추상 데이터 구조이다.

일반적인 경우, 구현이 더 쉽고 빠르게 만들기 위해 제한된 형식에서만 제공된다.

하지만, 모든 case문에 break문이 존재하는데, 이는 각 경우가 서로 독립적인 경우이다. 이러한 독립적인 경우에는 jump table의 전체 기능이 필요하지 않다.

이에, "제한된 jump table'은 효율성을 활용하지만, 각 '액션'이 다른 액션과 독립적일 때 사용된다. 즉, 각 경우가 서로 영향을 주지 않고 독립적으로 동작할 때 사용하여 코드의 효율성을 높일 수 있다.

해당 매핑은 보통 해쉬 테이블이 그 예시이며, jump table과 독립적으로 사용될 수 있다/

jump table의 복잡도는 다음과 같다.

보통은 O(K) 복잡도를 갖지만 최악의 경우 O(N)까지 갖는다.

그 이유는 jump table이 주로 키-값 매칭, 즉 해쉬 테이블로 사용되지만, 다양한 형태를 가질 수 있기 때문이다.

그렇기 때문에 무엇을 조회하는가, 어떻게 구현되어 있는가에 따라 달라질 수있다.

예를 들어, 데이터 구조가 균형 이진 트리라면, O(log n)일 것이다. 또한 해시 테이블의 복잡성은 사용하는 해시 함수와 충돌 처리 방식에 따라 달라진다.

다음은 직접 코드를 제작하여 컴파일 한 어셈블리어이다.

#include <iostream>

int main() {
    int choice = 2;

    switch (choice) {
        case 1:
            std::cout << "Choice 1\n";
            break;
        case 2:
            std::cout << "Choice 2\n";
            break;
        case 3:
            std::cout << "Choice 3\n";
            break;
        case 4:
            std::cout << "Choice 3\n";
            break;
        case 5:
            std::cout << "Choice 3\n";
            break;
        case 6:
            std::cout << "Choice 3\n";
            break;
        case 7:
            std::cout << "Choice 3\n";
            break;
        case 8:
            std::cout << "Choice 3\n";
            break;
        case 9:
            std::cout << "Choice 3\n";
            break;
        case 10:
            std::cout << "Choice 3\n";
            break;
        default:
            std::cout << "Invalid Choice\n";
            break;
    }

    return 0;
}

main:
.LFB1559:
	push	rbp
	.seh_pushreg	rbp 
	mov	rbp, rsp
	.seh_setframe	rbp, 0
	sub	rsp, 48 
	.seh_stackalloc	48
	.seh_endprologue
	call	__main //c++ 프로그램이 시작될때 실행되는 초기화 코드
	mov	DWORD PTR -4[rbp], 2 //지역변수로 사용될 메모리 위치에 2를 저장
	cmp	DWORD PTR -4[rbp], 10 //2가 10보다 큰지 비교
	ja	.L2 // 만약 2가 10보다 크면 .L2로 점프
	mov	eax, DWORD PTR -4[rbp]
	lea	rdx, 0[0+rax*4]
	lea	rax, .L4[rip]  //.L4의 주소를 rax에 로드
	mov	eax, DWORD PTR [rdx+rax]
	cdqe
	lea	rdx, .L4[rip] //.L4의 주소를 rdx에 로드
	add	rax, rdx
	jmp	rax
	.section .rdata,"dr"
	.align 4
.L4:  // jump table
	.long	.L2-.L4
	.long	.L13-.L4
	.long	.L12-.L4
	.long	.L11-.L4
	.long	.L10-.L4
	.long	.L9-.L4
	.long	.L8-.L4
	.long	.L7-.L4
	.long	.L6-.L4
	.long	.L5-.L4
	.long	.L3-.L4
	.text
.L13: //각의 swich case문
	lea	rdx, .LC0[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L14
.L12:  //각의 swich case문
	lea	rdx, .LC1[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L14
.L11:  //각의 swich case문
	lea	rdx, .LC2[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L14
.L10:  //각의 swich case문
	lea	rdx, .LC2[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L14

지금 ,.L4부분이 jump table이다. switch case문은 cmp와 jne 명령어를 각 조건문마다 사용하지 않고 jump table을 통해 특정 위치로 이동한다.

#include <iostream>

int main() {
    int choice = 2;
    if (choice ==1)
        std::cout << "Choice 1\n";
    else if (choice ==2)
        std::cout << "Choice 2\n";
    else if (choice ==3)
        std::cout << "Choice 3\n";
    else if (choice ==4)
        std::cout << "Choice 4\n";
    else if (choice ==5)
        std::cout << "Choice 5\n";
    else if (choice ==6)
        std::cout << "Choice 6\n";
    else if (choice ==7)
        std::cout << "Choice 7\n";
    else if (choice ==8)
        std::cout << "Choice 8\n";
    else if (choice ==9)
        std::cout << "Choice 9\n";
    else if (choice ==10)
        std::cout << "Choice 10\n";
    return 0;
}

하지만 if문을 사용한 경우 각 if 조건문 마다 cmp 명령어를 사용하여 O(n)의 복잡도를 갖는다.

.lcomm _ZStL8__ioinit,1,1
	.def	__main;	.scl	2;	.type	32;	.endef
.LC0:
	.ascii "Choice 1\12\0"
.LC1:
	.ascii "Choice 2\12\0"
.LC2:
	.ascii "Choice 3\12\0"
.LC3:
	.ascii "Choice 4\12\0"
.LC4:
	.ascii "Choice 5\12\0"
.LC5:
	.ascii "Choice 6\12\0"
.LC6:
	.ascii "Choice 7\12\0"
.LC7:
	.ascii "Choice 8\12\0"
.LC8:
	.ascii "Choice 9\12\0"
.LC9:
	.ascii "Choice 10\12\0"
	.text
	.globl	main
	.def	main;	.scl	2;	.type	32;	.endef
	.seh_proc	main

main:
.LFB1559:
	push	rbp
	.seh_pushreg	rbp
	mov	rbp, rsp
	.seh_setframe	rbp, 0
	sub	rsp, 48
	.seh_stackalloc	48
	.seh_endprologue
	call	__main
	mov	DWORD PTR -4[rbp], 2
	cmp	DWORD PTR -4[rbp], 1
	jne	.L2
	lea	rdx, .LC0[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L3
.L2:
	cmp	DWORD PTR -4[rbp], 2
	jne	.L4
	lea	rdx, .LC1[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L3
.L4:
	cmp	DWORD PTR -4[rbp], 3
	jne	.L5
	lea	rdx, .LC2[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L3
.L5:
	cmp	DWORD PTR -4[rbp], 4
	jne	.L6
	lea	rdx, .LC3[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L3
.L6:
	cmp	DWORD PTR -4[rbp], 5
	jne	.L7
	lea	rdx, .LC4[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L3
.L7:
	cmp	DWORD PTR -4[rbp], 6
	jne	.L8
	lea	rdx, .LC5[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L3
.L8:
	cmp	DWORD PTR -4[rbp], 7
	jne	.L9
	lea	rdx, .LC6[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L3
.L9:
	cmp	DWORD PTR -4[rbp], 8
	jne	.L10
	lea	rdx, .LC7[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L3
.L10:
	cmp	DWORD PTR -4[rbp], 9
	jne	.L11
	lea	rdx, .LC8[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L3
.L11:
	cmp	DWORD PTR -4[rbp], 10
	jne	.L3
	lea	rdx, .LC9[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
.L3:
	mov	eax, 0
	add	rsp, 48
	pop	rbp
	ret
	.seh_endproc
	.def	__tcf_0;	.scl	3;	.type	32;	.endef
	.seh_proc	__tcf_0
__tcf_0:

하지만 아래 코드의 어셈블리 코드에서는 jump table을 사용하지 않았다.

그 이유는 컴파일러가 최적화하여 je와 jne 명령어를 통해 각 case에 작접 점프하고 있기 때문이다.

main:
.LFB1559:
	push	rbp
	.seh_pushreg	rbp
	mov	rbp, rsp
	.seh_setframe	rbp, 0
	sub	rsp, 48
	.seh_stackalloc	48
	.seh_endprologue
	call	__main
	mov	DWORD PTR -4[rbp], 2
	cmp	DWORD PTR -4[rbp], 2
	je	.L2
	cmp	DWORD PTR -4[rbp], 3
	je	.L3
	cmp	DWORD PTR -4[rbp], 1
	jne	.L4
	lea	rdx, .LC0[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L5
.L2:
	lea	rdx, .LC1[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L5
.L3:
	lea	rdx, .LC2[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	jmp	.L5
.L4:
	lea	rdx, .LC3[rip]
	mov	rcx, QWORD PTR .refptr._ZSt4cout[rip]
	call	_ZStlsISt11char_traitsIcEERSt13basic_ostreamIcT_ES5_PKc
	nop
.L5:
	mov	eax, 0
	add	rsp, 48
	pop	rbp
	ret
	.seh_endproc
	.def	__tcf_0;	.scl	3;	.type	32;	.endef
	.seh_proc	__tcf_0
__tcf_0:

그렇게 때문에 많은 if 조건문을 사용할때 lookup table을 사용하면 좋다.

아래 예시를 보여주면서 설명하겠다.

#include <iostream>

typedef struct choice
{
	char answerName[30];
} Ans

int main()
{
int choice = 2;
    Ans tAns[3];
    
    strcpy(tAns[0].answerName, "Choice 1\n");
    strcpy(tAns[1].answerName, "Choice 2\n");
    strcpy(tAns[2].answerName, "Choice 3\n");
    
    printf("원하는 번호를 입력하세요: ");
    scanf("%d", &Input );
    
    if (Inpust <0 || Input >2)
    {
    	puts("Invalid Choice\n");
    }
    
    printf("%s\n", tAns[Input].answerName);
    
    return 0;
}

이러한 lookup table은 연산 속도와 가독성이 좋으며 추가하거나 삭제할때도 좋다는 장점이 존재한다.

단점은 고정된 작업만 가능하다는 것이다. 이에, switch case문과 혼용해서 사용한다고 한다.

그래서 보통 구조체보다는 포인터를 이용하여 정보를 가져온다고 한다.

#include <iostream>

typedef int(* PINT_DOUBLEINT)(int, int);

int One
int main() 
{
	/*미완성*/
}

'코테 > C++ 공부' 카테고리의 다른 글

[코테/C++공부] 클래스와 객체 (0)	2024.03.25
[코테/C++공부] C++란? (0)	2024.03.22

'코테/C++ 공부' Related Articles

total_activ

[C++] jamp table, switch case 본문

[C++] jamp table, switch case

'코테 > C++ 공부' 카테고리의 다른 글

티스토리툴바