C 내장 소프트웨어에서 룩업 테이블 대 스위치
또 다른 이야기를 들어보면, 저는 그 말을 들었습니다.switch속도와 컴팩트성 면에서 룩업 테이블보다 더 나을 수 있습니다.
그래서 저는 이것의 차이점을 이해하고 싶습니다.
조회표
static void func1(){}
static void func2(){}
typedef enum
{
FUNC1,
FUNC2,
FUNC_COUNT
} state_e;
typedef void (*func_t)(void);
const func_t lookUpTable[FUNC_COUNT] =
{
[FUNC1] = &func1,
[FUNC2] = &func2
};
void fsm(state_e state)
{
if (state < FUNC_COUNT)
lookUpTable[state]();
else
;// Error handling
}
그리고 이것:
스위치
static void func1(){}
static void func2(){}
void fsm(int state)
{
switch(state)
{
case FUNC1: func1(); break;
case FUNC2: func2(); break;
default: ;// Error handling
}
}
컴파일러들이 가능하면 스위치 문을 점프 테이블로 변환하려고 하기 때문에 룩업 테이블이 더 빠르다고 생각했습니다.이것이 틀렸을 수도 있기 때문에, 저는 왜 그런지 알고 싶습니다!
도와주셔서 감사합니다!
제가 댓글의 원저자였기 때문에, 질문에서 언급하지 않으셨던 아주 중요한 문제를 추가해야 합니다.즉, 원본은 임베디드 시스템에 관한 것이었습니다.이 시스템이 플래시가 통합된 일반적인 베어 메탈 시스템이라고 가정할 때, 제가 집중할 PC와는 매우 중요한 차이점이 있습니다.
이러한 임베디드 시스템은 일반적으로 다음과 같은 제약 조건을 갖습니다.
- CPU 캐시 없음.
- 플래시에는 더 높은 CPU 클럭(예: >ca 32MHz)에 대한 대기 상태가 필요합니다.실제 비율은 다이 설계, 저전력/고속 공정, 작동 전압 등에 따라 달라집니다.
- 대기 상태를 숨기기 위해 플래시에는 CPU 버스보다 더 넓은 읽기 라인이 있습니다.
- 명령 프리페치가 있는 선형 코드에만 적합합니다.
- 데이터 액세스는 명령 프리페치를 방해하거나 종료될 때까지 정지됩니다.
- 플래시에는 내부의 매우 작은 명령 캐시가 있을 수 있습니다.
- 데이터 캐시가 조금이라도 있다면 데이터 캐시는 훨씬 더 작습니다.
- 캐시가 작으면 폐기 빈도가 높아집니다(이전 항목을 다른 시간에 사용하기 전에 교체).
예를 들어, STM32F4xxa 판독에는 150MHz/3에서 6개의 클럭이 소요됩니다.128비트(4단어)에 대해 3V.따라서 데이터 액세스가 필요한 경우 모든 데이터를 가져올 때 12개 이상의 클럭 지연이 발생할 가능성이 높습니다(추가 사이클이 포함됨).
실제 문제에 대해 콤팩트한 상태 코드를 가정하면 이 아키텍처(Cortex-M4)에 다음과 같은 효과가 있습니다.
- Lookup-table: 함수 주소를 읽는 것은 데이터 액세스입니다.위에서 언급한 모든 시사점을 포함하여.
- 스위치 오토는 코드 공간 데이터를 명령 바로 뒤에 사용하는 특별한 "테이블 룩업" 명령을 사용합니다.따라서 첫 번째 항목은 이미 프리페치되어 있을 가능성이 있습니다.다른 항목은 프리페치를 깨지 않습니다.또한 액세스는 코드 액세스이므로 데이터는 플래시의 명령 캐시로 이동합니다.
또한 주의할 점은switch함수를 필요로 하지 않으므로 컴파일러는 코드를 완전히 최적화할 수 있습니다.룩업 테이블에서는 불가능합니다.함수 진입/종료에 대한 코드가 적어도 필요하지 않습니다.
앞서 언급한 것과 다른 요인들 때문에, 추정치를 분간하기 어렵습니다.플랫폼과 코드 구조에 따라 크게 달라집니다.그러나 위에 제시된 시스템을 가정하면 스위치가 더 빠를 가능성이 매우 높습니다(그런데 말입니다.
첫째, 일부 프로세서에서는 Lookup Table 예제와 같이 간접 호출(예: 포인터를 통한) 비용이 많이 듭니다(파이프라인 파손, TLB, 캐시 효과).간접 점프의 경우에도 그럴 수 있습니다.
그러면, 좋은 최적화 컴파일러가 호출에 줄을 설 수 있을 것입니다.func1()스위치 예제에서는 인라인 함수에 대해 프롤로그나 에필로그를 실행하지 않습니다.
다른 많은 요소들이 성능에 중요하기 때문에 벤치마킹을 해야 합니다.이 항목(및 참조)도 참조하십시오.
함수 포인터의 LUT를 사용하면 컴파일러가 해당 전략을 사용할 수 있습니다.이론적으로 스위치 버전을 LUT 버전과 기본적으로 동일한 코드로 컴파일할 수 있습니다(이제 두 버전 모두에 아웃오브바운드 검사를 추가했습니다).실제로 그것은 gcc나 clang이 선택하는 것이 아니기 때문에 어떤 일이 일어났는지 확인하기 위해 asm 출력을 살펴볼 필요가 있습니다.
(: gcc)-fpie(대부분의 현대 리눅스 배포판에서는 기본적으로) 절대 함수 포인터 대신 상대적 오프셋 표를 만드는 것을 좋아하기 때문에 로데이터도 위치에 무관합니다.movsxd 및 add?를 생성하는 GCC 점프 테이블 초기화 코드입니다.최적화를 놓친 것일 수 있습니다. gcc 버그 보고서에 대한 링크는 거기서 제 답변을 참조하십시오.함수 포인터의 배열을 수동으로 만드는 것이 이를 해결할 수 있습니다.)
실제로 어떻게 컴파일되었는지 보기 위해 두 기능이 하나의 컴파일 단위(gcc와 clang 출력 포함)에 있는 Godbolt 컴파일러 탐색기에 코드를 넣었습니다.제가 기능을 조금 더 확장해서 두 가지 경우가 아니었습니다.
void fsm_switch(int state) {
switch(state) {
case FUNC0: func0(); break;
case FUNC1: func1(); break;
case FUNC2: func2(); break;
case FUNC3: func3(); break;
default: ;// Error handling
}
//prevent_tailcall();
}
void fsm_lut(state_e state) {
if (likely(state < FUNC_COUNT)) // without likely(), gcc puts the LUT on the taken side of this branch
lookUpTable[state]();
else
;// Error handling
//prevent_tailcall();
}
참고 항목Linux 커널에서 가능성이 높은() 매크로와 가능성이 낮은() 매크로는 어떻게 작동하며 이점은 무엇입니까?
x86
x86에서 clang은 스위치에 대한 자체 LUT를 만들지만, 최종 함수 포인터가 아닌 함수 내에 대한 포인터입니다.따라서 clang-3.7의 경우 스위치가 수동으로 구현된 LUT보다 엄격하게 더 나쁜 코드로 컴파일됩니다.어느 쪽이든, x86 CPU는 간접 호출/점프를 처리할 수 있는 분기 예측 기능을 갖는 경향이 있습니다. 적어도 예측이 용이하다면 말이죠.
GCC는 일련의 조건부 분기를 사용합니다. (하지만 불행히도 조건부 분기와 직접 테일콜을 하지는 않습니다.) AFAICT는 x86에서 안전합니다.일치하는 것을 찾을 때까지 대부분 가지를 가져가지 않은 채로 1, <1, 2, 3>을 순서대로 확인합니다.
이들은 LUT: 경계 검사를 위해 본질적으로 동일한 코드를 만들고, arg 레지스터의 상위 32비트를 a로 0으로 만듭니다.mov, 그리고 색인화된 주소 지정 모드로 메모리 indirect 점프를 합니다.
ARM:
, 4.8.2-mcpu=cortex-m4 -O2흥미로운 코드를 만듭니다.
올라프의 말대로 1B 엔트리로 구성된 인라인 테이블을 만듭니다.목표 함수로 직접 점프하는 것이 아니라 일반 점프 명령으로 점프합니다(예:b func3입니다.) 이것은 일반적인 무조건 점프입니다. 왜냐하면 이것은 테일 콜이기 때문입니다.
각 테이블 대상 항목에는 다음과 같은 경우 코드(Godbolt)가 훨씬 더 필요합니다.fsm_switch통화 후에 모든 작업을 수행합니다(이 경우와 마찬가지로 inline 이외의 기능 호출, 경우).void prevent_tailcall(void);선언되지만 정의되지 않음), 또는 이 함수가 더 큰 함수에 인라인된 경우.
@@ With void prevent_tailcall(void){} defined so it can inline:
@@ Unlike in the godbolt link, this is doing tailcalls.
fsm_switch:
cmp r0, #3 @ state,
bhi .L5 @
tbb [pc, r0] @ state
@@ There's no section .rodata directive here: the table is in-line with the code, so there's no need for base pointer to be loaded into a reg. And apparently it's even loaded from I-cache, not D-cache
.byte (.L7-.L8)/2
.byte (.L9-.L8)/2
.byte (.L10-.L8)/2
.byte (.L11-.L8)/2
.L11:
b func3 @ optimized tail-call
.L10:
b func2
.L9:
b func1
.L7:
b func0
.L5:
bx lr @ This is ARM's equivalent of an x86 ret insn
분기 예측이 얼마나 잘 작동하는지 간에 많은 차이가 있는지 알 수 없습니다.tbb인 간접 콜 Vs. 전면적인 간접 점프 또는 호출(blx), 경량 ARM 코어에 있습니다.테이블을 로드하는 데이터 액세스는 분기 명령으로 두 단계 점프하는 것보다 더 중요할 수 있습니다.switch.
ARM에서 간접지사가 잘 예측되지 않는다고 읽었습니다.간접지사도 매번 같은 목표를 가지고 있다면 나쁘지 않았으면 좋겠습니다.하지만 그렇지 않다면 대부분의 ARM 코어는 x86 코어처럼 짧은 패턴도 발견하지 못할 것입니다.
x86에서는 명령어 페치/디코드 시간이 더 오래 걸리므로 명령어 스트림에서 버블을 방지하는 것이 더 중요합니다.이것이 x86 CPU가 이렇게 좋은 분기 예측을 하는 이유 중 하나입니다.현대의 분기 예측기는 해당 분기 및/또는 해당 분기에 이르는 다른 분기의 이력에 기초하여 간접 분기에 대한 패턴으로 작업을 잘 수행합니다.
LUT 함수는 LUT의 기본 주소를 레지스터에 로드하는 데 몇 가지 명령을 사용해야 하지만 그렇지 않으면 x86과 거의 유사합니다.
fsm_lut:
cmp r0, #3 @ state,
bhi .L13 @,
movw r3, #:lower16:.LANCHOR0 @ tmp112,
movt r3, #:upper16:.LANCHOR0 @ tmp112,
ldr r3, [r3, r0, lsl #2] @ tmp113, lookUpTable
bx r3 @ indirect register sibling call @ tmp113
.L13:
bx lr @
@ in the .rodata section
lookUpTable:
.word func0
.word func1
.word func2
.word func3
Microchip dsPIC에 대한 유사한 분석은 SST의 Mike의 답변을 참조하십시오.
msc의 답변과 댓글은 왜 성과가 기대하는 것과 다를 수 있는지에 대한 좋은 힌트를 줍니다.벤치마킹이 원칙이지만 결과는 아키텍처마다 다르며 컴파일러의 다른 버전과 물론 선택한 구성 및 옵션에 따라 달라질 수 있습니다.
그러나 당신의 코드 2개는 동일한 유효성 검사를 수행하지 않습니다.state:
- 스위치는 우아하게 아무것도 하지 않습니다.
state정의된 값 중 하나가 아닙니다. - 점프 테이블 버전은 2개의 값을 제외한 모든 값에 대해 정의되지 않은 동작을 호출합니다.
FUNC1그리고.FUNC2.
다음과 같은 가정을 하지 않고 더미 함수 포인터로 점프 테이블을 초기화하는 일반적인 방법은 없습니다.FUNC_COUNT을 취하십시오. 점프 동일한 동작을 취하십시오. 점프 테이블 버전은 다음과 같습니다.
void fsm(int state) {
if (state >= 0 && state < FUNC_COUNT && lookUpTable[state] != NULL)
lookUpTable[state]();
}
이를 벤치마킹하여 조립 코드를 검사해 보십시오.다음은 이것을 위한 편리한 온라인 컴파일러입니다: http://gcc.godbolt.org/ #.
Microchip dsPIC 장치 제품군에는 조회 테이블이 플래시 자체에 일련의 명령어 주소로 저장됩니다.조회를 수행하려면 플래시에서 주소를 읽은 다음 루틴을 호출해야 합니다.호출을 수행하면 명령 포인터 및 기타 비트를 푸시하는 몇 개의 주기가 추가되며 하우스키핑의 봅(예: 스택 프레임 설정)이 추가됩니다.
예를 들어 dsPIC33E512의 경우MU810, XC16(v1.24)을 사용하여 조회 코드:
lookUpTable[state]();
(MPLAB-X의 분해 창에서) 다음으로 컴파일합니다.
! lookUpTable[state]();
0x2D20: MOV [W14], W4 ; get state from stack-frame (not counted)
0x2D22: ADD W4, W4, W5 ; 1 cycle (addresses are 16 bit aligned)
0x2D24: MOV #0xA238, W4 ; 1 cycle (get base address of look-up table)
0x2D26: ADD W5, W4, W4 ; 1 cycle (get address of entry in table)
0x2D28: MOV [W4], W4 ; 1 cycle (get address of the function)
0x2D2A: CALL W4 ; 2 cycles (push PC+2 set PC=W4)
... 그리고 각 함수(공백, 수행 없음)는 다음과 같습니다.
!static void func1()
!{}
0x2D0A: LNK #0x0 ; 1 cycle (set up stack frame)
! Function body goes here
0x2D0C: ULNK ; 1 cycle (un-link frame pointer)
0x2D0E: RETURN ; 3 cycles
이것은 어느 경우든 총 11번의 오버헤드 명령 사이클이며, 모두 동일한 오버헤드를 사용합니다.(참고: 테이블이나 테이블에 포함된 기능 중 하나가 동일한 32K 프로그램 워드 플래시 페이지에 없으면 주소 생성 장치를 올바른 페이지에서 읽게 하거나 장시간 통화를 위해 PC를 설정해야 하기 때문에 훨씬 더 큰 오버헤드가 발생합니다.)
반면, 전체 스위치 문이 특정 크기 내에 맞는 경우 컴파일러는 테스트 및 상대 분기를 수행하는 코드를 하나의 경우에 세 번(또는 네 번) 사이클을 수행하는 명령어로 생성합니다.
예를 들어, switch 문은 다음과 같습니다.
switch(state)
{
case FUNC1: state++; break;
case FUNC2: state--; break;
default: break;
}
컴파일 대상:
! switch(state)
0x2D2C: MOV [W14], W4 ; get state from stack-frame (not counted)
0x2D2E: SUB W4, #0x0, [W15] ; 1 cycle (compare with first case)
0x2D30: BRA Z, 0x2D38 ; 1 cycle (if branch not taken, or 2 if it is)
0x2D32: SUB W4, #0x1, [W15] ; 1 cycle (compare with second case)
0x2D34: BRA Z, 0x2D3C ; 1 cycle (if branch not taken, or 2 if it is)
! {
! case FUNC1: state++; break;
0x2D38: INC [W14], [W14] ; To stop the switch being optimised out
0x2D3A: BRA 0x2D40 ; 2 cycles (go to end of switch)
! case FUNC2: state--; break;
0x2D3C: DEC [W14], [W14] ; To stop the switch being optimised out
0x2D3E: NOP ; compiler did a fall-through (for some reason)
! default: break;
0x2D36: BRA 0x2D40 ; 2 cycles (go to end of switch)
! }
이것은 첫 번째 케이스가 취해질 경우 5 사이클, 두 번째 케이스가 취해질 경우 7 사이클 등의 오버헤드로, 네 번째 케이스에서도 깨짐을 의미합니다.
즉, 설계 시점에 데이터를 파악하는 것이 장기적인 속도에 상당한 영향을 미칠 것입니다.상당한 수(약 4건 이상)를 가지고 있고 모두 비슷한 빈도로 발생하는 경우 장기적으로 조회 테이블이 더 빠릅니다.케이스의 빈도가 현저하게 다른 경우(예: 케이스 1이 케이스 2보다 더 높은 경우, 케이스 3보다 더 높은 경우 등), 케이스가 가장 높은 스위치를 먼저 주문하면 장기적으로 스위치가 더 빨라집니다.엣지 케이스의 경우, 대부분의 실행의 경우 스위치가 (아마도) 더 빠르고 읽기 쉽고 오류 발생률이 낮습니다.
스위치에 몇 가지 경우만 있거나 어떤 경우는 다른 경우보다 더 자주 발생할 수 있습니다. 그러면 스위치의 테스트와 분기를 수행하는 것이 룩업 테이블을 사용하는 것보다 더 적은 사이클이 걸릴 수 있습니다.반면, 유사한 빈도로 발생하는 사례가 소수 이상인 경우 검색 속도가 평균적으로 빨라질 수 있습니다.
팁: 검색이 확실히 더 빠르고 실행에 걸리는 시간이 중요하다는 것을 알지 못하면 스위치를 사용하십시오.
편집: 제 스위치 예제는 약간 불공평합니다. 왜냐하면 저는 원래 질문을 무시하고 검색보다 스위치를 사용하는 것의 실제 이점을 강조하기 위해 사례의 '본문'에 줄을 그었기 때문입니다.스위치도 통화를 해야 한다면 첫 번째 경우에만 유리합니다!
더 많은 컴파일러 출력을 얻으려면, @PeterCordes 샘플 코드를 사용하여 TIC28x 컴파일러에서 생성된 것은 다음과 같습니다.
_fsm_switch:
CMPB AL,#0 ; [CPU_] |62|
BF $C$L3,EQ ; [CPU_] |62|
; branchcc occurs ; [] |62|
CMPB AL,#1 ; [CPU_] |62|
BF $C$L2,EQ ; [CPU_] |62|
; branchcc occurs ; [] |62|
CMPB AL,#2 ; [CPU_] |62|
BF $C$L1,EQ ; [CPU_] |62|
; branchcc occurs ; [] |62|
CMPB AL,#3 ; [CPU_] |62|
BF $C$L4,NEQ ; [CPU_] |62|
; branchcc occurs ; [] |62|
LCR #_func3 ; [CPU_] |66|
; call occurs [#_func3] ; [] |66|
B $C$L4,UNC ; [CPU_] |66|
; branch occurs ; [] |66|
$C$L1:
LCR #_func2 ; [CPU_] |65|
; call occurs [#_func2] ; [] |65|
B $C$L4,UNC ; [CPU_] |65|
; branch occurs ; [] |65|
$C$L2:
LCR #_func1 ; [CPU_] |64|
; call occurs [#_func1] ; [] |64|
B $C$L4,UNC ; [CPU_] |64|
; branch occurs ; [] |64|
$C$L3:
LCR #_func0 ; [CPU_] |63|
; call occurs [#_func0] ; [] |63|
$C$L4:
LCR #_prevent_tailcall ; [CPU_] |69|
; call occurs [#_prevent_tailcall] ; [] |69|
LRETR ; [CPU_]
; return occurs ; []
_fsm_lut:
;* AL assigned to _state
CMPB AL,#4 ; [CPU_] |84|
BF $C$L5,HIS ; [CPU_] |84|
; branchcc occurs ; [] |84|
CLRC SXM ; [CPU_]
MOVL XAR4,#_lookUpTable ; [CPU_U] |85|
MOV ACC,AL << 1 ; [CPU_] |85|
ADDL XAR4,ACC ; [CPU_] |85|
MOVL XAR7,*+XAR4[0] ; [CPU_] |85|
LCR *XAR7 ; [CPU_] |85|
; call occurs [XAR7] ; [] |85|
$C$L5:
LCR #_prevent_tailcall ; [CPU_] |88|
; call occurs [#_prevent_tailcall] ; [] |88|
LRETR ; [CPU_]
; return occurs ; []
또한 -O2 최적화를 사용했습니다.우리는 컴파일러가 능력이 있다고 해도 스위치가 점프 테이블로 변환되지 않는다는 것을 알 수 있습니다.
언급URL : https://stackoverflow.com/questions/35838849/lookup-table-vs-switch-in-c-embedded-software
'sourcetip' 카테고리의 다른 글
| Mount-DiskImage와 함께 마운트된 ISOI의 드라이브 문자를 가져오려면 어떻게 해야 합니까? (0) | 2023.10.30 |
|---|---|
| Swift를 사용하여 iOS에서 뷰 컨트롤러를 오른쪽에서 왼쪽으로 표시하는 방법 (0) | 2023.10.30 |
| 도커 컨테이너 실행 시 자동으로 서비스를 시작하는 방법은? (0) | 2023.10.30 |
| 프로그래밍 언어에 키워드가 필요한 이유는 무엇입니까? (0) | 2023.10.30 |
| SonarQuebe가 AngularJS로 멋지게 플레이하게 하는 방법은? (0) | 2023.10.30 |