A는 switch문은 실제로 빠를 것보다 if문?
/Ox플래그를 사용하여 Visual Studio 2010의 x64 C ++ 컴파일러에서 아래 코드를 실행했습니다 .
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define MAX_COUNT (1 << 29)
size_t counter = 0;
size_t testSwitch()
{
clock_t start = clock();
size_t i;
for (i = 0; i < MAX_COUNT; i++)
{
switch (counter % 4 + 1)
{
case 1: counter += 4; break;
case 2: counter += 3; break;
case 3: counter += 2; break;
case 4: counter += 1; break;
}
}
return 1000 * (clock() - start) / CLOCKS_PER_SEC;
}
size_t testIf()
{
clock_t start = clock();
size_t i;
for (i = 0; i < MAX_COUNT; i++)
{
const size_t c = counter % 4 + 1;
if (c == 1) { counter += 4; }
else if (c == 2) { counter += 3; }
else if (c == 3) { counter += 2; }
else if (c == 4) { counter += 1; }
}
return 1000 * (clock() - start) / CLOCKS_PER_SEC;
}
int main()
{
printf("Starting...\n");
printf("Switch statement: %u ms\n", testSwitch());
printf("If statement: %u ms\n", testIf());
}그리고이 결과를 얻었다 :
스위치 문 : 5261ms
If 문 : 5196ms
내가 배운 내용에서 switch명령문은 분명히 분기 테이블을 최적화하기 위해 점프 테이블을 사용합니다.
질문 :
-
x86 또는 x64에서 기본 점프 테이블은 어떤 모양입니까?
-
이 코드는 점프 테이블을 사용합니까?
-
이 예제에서 성능 차이가없는 이유는 무엇입니까? 거기에있는 어떤 상황 거기에 있다 상당한 성능 차이는?
코드 분해 :
testIf:
13FE81B10 sub rsp,48h
13FE81B14 call qword ptr [__imp_clock (13FE81128h)]
13FE81B1A mov dword ptr [start],eax
13FE81B1E mov qword ptr [i],0
13FE81B27 jmp testIf+26h (13FE81B36h)
13FE81B29 mov rax,qword ptr [i]
13FE81B2E inc rax
13FE81B31 mov qword ptr [i],rax
13FE81B36 cmp qword ptr [i],20000000h
13FE81B3F jae testIf+0C3h (13FE81BD3h)
13FE81B45 xor edx,edx
13FE81B47 mov rax,qword ptr [counter (13FE835D0h)]
13FE81B4E mov ecx,4
13FE81B53 div rax,rcx
13FE81B56 mov rax,rdx
13FE81B59 inc rax
13FE81B5C mov qword ptr [c],rax
13FE81B61 cmp qword ptr [c],1
13FE81B67 jne testIf+6Dh (13FE81B7Dh)
13FE81B69 mov rax,qword ptr [counter (13FE835D0h)]
13FE81B70 add rax,4
13FE81B74 mov qword ptr [counter (13FE835D0h)],rax
13FE81B7B jmp testIf+0BEh (13FE81BCEh)
13FE81B7D cmp qword ptr [c],2
13FE81B83 jne testIf+89h (13FE81B99h)
13FE81B85 mov rax,qword ptr [counter (13FE835D0h)]
13FE81B8C add rax,3
13FE81B90 mov qword ptr [counter (13FE835D0h)],rax
13FE81B97 jmp testIf+0BEh (13FE81BCEh)
13FE81B99 cmp qword ptr [c],3
13FE81B9F jne testIf+0A5h (13FE81BB5h)
13FE81BA1 mov rax,qword ptr [counter (13FE835D0h)]
13FE81BA8 add rax,2
13FE81BAC mov qword ptr [counter (13FE835D0h)],rax
13FE81BB3 jmp testIf+0BEh (13FE81BCEh)
13FE81BB5 cmp qword ptr [c],4
13FE81BBB jne testIf+0BEh (13FE81BCEh)
13FE81BBD mov rax,qword ptr [counter (13FE835D0h)]
13FE81BC4 inc rax
13FE81BC7 mov qword ptr [counter (13FE835D0h)],rax
13FE81BCE jmp testIf+19h (13FE81B29h)
13FE81BD3 call qword ptr [__imp_clock (13FE81128h)]
13FE81BD9 sub eax,dword ptr [start]
13FE81BDD imul eax,eax,3E8h
13FE81BE3 cdq
13FE81BE4 mov ecx,3E8h
13FE81BE9 idiv eax,ecx
13FE81BEB cdqe
13FE81BED add rsp,48h
13FE81BF1 ret testSwitch:
13FE81C00 sub rsp,48h
13FE81C04 call qword ptr [__imp_clock (13FE81128h)]
13FE81C0A mov dword ptr [start],eax
13FE81C0E mov qword ptr [i],0
13FE81C17 jmp testSwitch+26h (13FE81C26h)
13FE81C19 mov rax,qword ptr [i]
13FE81C1E inc rax
13FE81C21 mov qword ptr [i],rax
13FE81C26 cmp qword ptr [i],20000000h
13FE81C2F jae testSwitch+0C5h (13FE81CC5h)
13FE81C35 xor edx,edx
13FE81C37 mov rax,qword ptr [counter (13FE835D0h)]
13FE81C3E mov ecx,4
13FE81C43 div rax,rcx
13FE81C46 mov rax,rdx
13FE81C49 inc rax
13FE81C4C mov qword ptr [rsp+30h],rax
13FE81C51 cmp qword ptr [rsp+30h],1
13FE81C57 je testSwitch+73h (13FE81C73h)
13FE81C59 cmp qword ptr [rsp+30h],2
13FE81C5F je testSwitch+87h (13FE81C87h)
13FE81C61 cmp qword ptr [rsp+30h],3
13FE81C67 je testSwitch+9Bh (13FE81C9Bh)
13FE81C69 cmp qword ptr [rsp+30h],4
13FE81C6F je testSwitch+0AFh (13FE81CAFh)
13FE81C71 jmp testSwitch+0C0h (13FE81CC0h)
13FE81C73 mov rax,qword ptr [counter (13FE835D0h)]
13FE81C7A add rax,4
13FE81C7E mov qword ptr [counter (13FE835D0h)],rax
13FE81C85 jmp testSwitch+0C0h (13FE81CC0h)
13FE81C87 mov rax,qword ptr [counter (13FE835D0h)]
13FE81C8E add rax,3
13FE81C92 mov qword ptr [counter (13FE835D0h)],rax
13FE81C99 jmp testSwitch+0C0h (13FE81CC0h)
13FE81C9B mov rax,qword ptr [counter (13FE835D0h)]
13FE81CA2 add rax,2
13FE81CA6 mov qword ptr [counter (13FE835D0h)],rax
13FE81CAD jmp testSwitch+0C0h (13FE81CC0h)
13FE81CAF mov rax,qword ptr [counter (13FE835D0h)]
13FE81CB6 inc rax
13FE81CB9 mov qword ptr [counter (13FE835D0h)],rax
13FE81CC0 jmp testSwitch+19h (13FE81C19h)
13FE81CC5 call qword ptr [__imp_clock (13FE81128h)]
13FE81CCB sub eax,dword ptr [start]
13FE81CCF imul eax,eax,3E8h
13FE81CD5 cdq
13FE81CD6 mov ecx,3E8h
13FE81CDB idiv eax,ecx
13FE81CDD cdqe
13FE81CDF add rsp,48h
13FE81CE3 ret 최신 정보:
답변
컴파일러 가 스위치에서 수행 할 수 있는 몇 가지 최적화가 있습니다 . 나는 종종 언급 된 “점프 테이블”은 입력이 어떤 식 으로든 바인딩 될 수있을 때만 작동하기 때문에 매우 유용한 것이라고 생각하지 않습니다.
C “점프 테이블”에 대한 의사 코드는 다음과 같습니다 . 실제로 컴파일러는 테이블에서 입력이 유효한지 확인하기 위해 테이블 주위에 if 테스트 형식을 삽입해야합니다. 또한 입력이 연속적인 숫자의 연속 인 특정 경우에만 작동합니다.
스위치의 분기 수가 매우 많은 경우 컴파일러는 스위치 값에 대해 이진 검색을 사용하는 것과 같은 작업을 수행 할 수 있습니다. 시나리오는 스위치만큼 일반적이며 코드 크기가 더 커지지 않습니다. 그러나 그것을 확인하려면 테스트 코드에 차이가 있는지 더 많은 분기가 필요합니다.
특정 질문에 대답하려면 다음을 수행하십시오.
-
Clang은 다음과 같은 것을 생성 합니다 :
test_switch(char): # @test_switch(char) movl %edi, %eax cmpl $19, %edi jbe .LBB0_1 retq .LBB0_1: jmpq *.LJTI0_0(,%rax,8) jmp void call<0u>() # TAILCALL jmp void call<1u>() # TAILCALL jmp void call<2u>() # TAILCALL jmp void call<3u>() # TAILCALL jmp void call<4u>() # TAILCALL jmp void call<5u>() # TAILCALL jmp void call<6u>() # TAILCALL jmp void call<7u>() # TAILCALL jmp void call<8u>() # TAILCALL jmp void call<9u>() # TAILCALL jmp void call<10u>() # TAILCALL jmp void call<11u>() # TAILCALL jmp void call<12u>() # TAILCALL jmp void call<13u>() # TAILCALL jmp void call<14u>() # TAILCALL jmp void call<15u>() # TAILCALL jmp void call<16u>() # TAILCALL jmp void call<17u>() # TAILCALL jmp void call<18u>() # TAILCALL jmp void call<19u>() # TAILCALL .LJTI0_0: .quad .LBB0_2 .quad .LBB0_3 .quad .LBB0_4 .quad .LBB0_5 .quad .LBB0_6 .quad .LBB0_7 .quad .LBB0_8 .quad .LBB0_9 .quad .LBB0_10 .quad .LBB0_11 .quad .LBB0_12 .quad .LBB0_13 .quad .LBB0_14 .quad .LBB0_15 .quad .LBB0_16 .quad .LBB0_17 .quad .LBB0_18 .quad .LBB0_19 .quad .LBB0_20 .quad .LBB0_21 -
점프 테이블을 사용하지 않는다고 말할 수 있습니다 .4 개의 비교 명령이 명확하게 보입니다.
13FE81C51 cmp qword ptr [rsp+30h],1 13FE81C57 je testSwitch+73h (13FE81C73h) 13FE81C59 cmp qword ptr [rsp+30h],2 13FE81C5F je testSwitch+87h (13FE81C87h) 13FE81C61 cmp qword ptr [rsp+30h],3 13FE81C67 je testSwitch+9Bh (13FE81C9Bh) 13FE81C69 cmp qword ptr [rsp+30h],4 13FE81C6F je testSwitch+0AFh (13FE81CAFh)점프 테이블 기반 솔루션은 비교를 전혀 사용하지 않습니다.
- 컴파일러가 점프 테이블을 생성 할 수있는 분기가 충분하지 않거나 컴파일러가 단순히 분기 테이블을 생성하지 않습니다. 확실하지 않습니다.
EDIT 2014 : LLVM 옵티 마이저에 익숙한 사람들과 다른 곳에서 점프 테이블 최적화가 많은 시나리오에서 중요 할 수 있다고 이야기했습니다. 예를 들어 많은 값을 가진 열거가 있고 상기 열거 된 값에 대해 많은 경우가 있습니다. 즉, 나는 2011 년에 내가 위에서 말한 것을지지합니다. 너무 자주 사람들이 “내가 스위치를 만들면 얼마나 많은 경우에 상관없이 같은 시간이 될 것”이라고 생각하는 것을 보게됩니다. 점프 테이블을 사용하더라도 간접 점프 비용이 발생하며 각 경우에 대해 테이블의 항목에 대해 비용을 지불합니다. 메모리 대역폭은 최신 하드웨어에서 큰 문제입니다.
가독성을위한 코드를 작성하십시오. 그 가치가있는 컴파일러는 if / else if 사다리를보고 더 빠른 경우 동등한 스위치로 또는 그 반대로 변환합니다.
답변
귀하의 질문에 :
1. x86 또는 x64에서 기본 점프 테이블의 모양은 무엇입니까?
점프 테이블은 배열 구조와 같은 레이블의 포인터를 보유하는 메모리 주소입니다. 다음 예제는 점프 테이블이 배치되는 방법을 이해하는 데 도움이됩니다.
00B14538 D8 09 AB 00 D8 09 AB 00 D8 09 AB 00 D8 09 AB 00 Ø.«.Ø.«.Ø.«.Ø.«.
00B14548 D8 09 AB 00 D8 09 AB 00 D8 09 AB 00 00 00 00 00 Ø.«.Ø.«.Ø.«.....
00B14558 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
00B14568 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 ................
여기서 00B14538 은 점프 테이블에 대한 포인터이고 D8 09 AB 00 과 같은 값 은 레이블 포인터를 나타냅니다.
2.이 코드는 점프 테이블을 사용합니까?
이 경우에는 아니요.
3.이 예제에서 성능 차이가없는 이유는 무엇입니까?
두 경우 모두 명령이 동일하고 점프 테이블이 없기 때문에 성능 차이가 없습니다.
4. 성능 차이가 큰 상황이 있습니까?
if 점검 순서가 매우 긴 경우 ,이 경우 점프 테이블을 사용하면 성능이 향상됩니다 ( 지점을 완벽하게 예측하지 않으면 분기 / jmp 명령이 비싸지 만 메모리 비용이 발생 함).
모든 비교 명령어의 코드도 크기가 있으므로 특히 32 비트 포인터 또는 오프셋의 경우 단일 점프 테이블 조회에 실행 파일의 크기가 더 크지 않을 수 있습니다.
결론 : 컴파일러는 그러한 경우를 충분히 처리하고 적절한 지침을 생성합니다. 🙂
답변
컴파일러는 스위치 문을 if 문과 동등한 코드로 컴파일하거나 점프 테이블을 만들 수 있습니다. 컴파일러 옵션에서 지정한 내용에 따라 실행 속도가 가장 빠르거나 가장 작은 코드를 생성하는 방법에 따라 다른 것을 선택했을 가능성이 높습니다. 따라서 최악의 경우 if 문과 동일한 속도가됩니다.
컴파일러가 최선의 선택을하고 코드를 가장 읽기 쉽게 만드는 것에 집중할 것을 신뢰합니다.
케이스 수가 매우 커지면 점프 테이블이 일련의 if보다 훨씬 빠릅니다. 그러나 값 사이의 단계가 매우 크면 점프 테이블이 커질 수 있으며 컴파일러는 하나를 생성하지 않도록 선택할 수 있습니다.
답변
컴퓨터가 스위치 테스트 루프 동안 테스트와 관련이없는 일부 작업을 수행하지 않았고 if 테스트 루프 동안 더 적은 작업을 수행하지 않았다는 것을 어떻게 알 수 있습니까? 테스트 결과에는 다음과 같은 내용이 표시되지 않습니다.
- 차이가 매우 작다
- 일련의 결과가 아닌 하나의 결과 만 있음
- 사례가 너무 적다
내 결과 :
나는 덧붙였다.
printf("counter: %u\n", counter);카운터가 예제에서 사용되지 않았기 때문에 루프를 최적화하지 못하도록 컴파일러가 루프를 수행하는 이유는 무엇입니까? 즉시, 그러한 마이크로 벤치 마크로도 스위치는 항상 승리했습니다.
코드의 다른 문제는 다음과 같습니다.
switch (counter % 4 + 1)스위치 루프에서
const size_t c = counter % 4 + 1; if 루프에서. 고치면 큰 차이가 있습니다. switch 문에 명령문을 넣으면 컴파일러가 값을 스택에 먼저 배치하지 않고 CPU 레지스터에 직접 값을 보내도록 유도합니다. 따라서 이것은 균형 잡힌 테스트가 아니라 switch 문을 선호합니다.
오, 나는 또한 테스트 사이에 카운터를 재설정해야한다고 생각합니다. 실제로, 아마도 무언가를 최적화 할 것이므로 +1, +2, +3 등 대신 임의의 종류의 난수를 사용해야합니다. 난수로, 예를 들어 현재 시간을 기준으로 한 숫자를 의미합니다. 그렇지 않으면 컴파일러는 두 함수를 하나의 긴 수학 연산으로 바꿀 수 있으며 루프를 방해하지 않을 수도 있습니다.
컴파일러가 코드를 실행하기 전에 알아낼 수 없도록 Ryan의 코드를 수정했습니다.
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#define MAX_COUNT (1 << 26)
size_t counter = 0;
long long testSwitch()
{
clock_t start = clock();
size_t i;
for (i = 0; i < MAX_COUNT; i++)
{
const size_t c = rand() % 20 + 1;
switch (c)
{
case 1: counter += 20; break;
case 2: counter += 33; break;
case 3: counter += 62; break;
case 4: counter += 15; break;
case 5: counter += 416; break;
case 6: counter += 3545; break;
case 7: counter += 23; break;
case 8: counter += 81; break;
case 9: counter += 256; break;
case 10: counter += 15865; break;
case 11: counter += 3234; break;
case 12: counter += 22345; break;
case 13: counter += 1242; break;
case 14: counter += 12341; break;
case 15: counter += 41; break;
case 16: counter += 34321; break;
case 17: counter += 232; break;
case 18: counter += 144231; break;
case 19: counter += 32; break;
case 20: counter += 1231; break;
}
}
return 1000 * (long long)(clock() - start) / CLOCKS_PER_SEC;
}
long long testIf()
{
clock_t start = clock();
size_t i;
for (i = 0; i < MAX_COUNT; i++)
{
const size_t c = rand() % 20 + 1;
if (c == 1) { counter += 20; }
else if (c == 2) { counter += 33; }
else if (c == 3) { counter += 62; }
else if (c == 4) { counter += 15; }
else if (c == 5) { counter += 416; }
else if (c == 6) { counter += 3545; }
else if (c == 7) { counter += 23; }
else if (c == 8) { counter += 81; }
else if (c == 9) { counter += 256; }
else if (c == 10) { counter += 15865; }
else if (c == 11) { counter += 3234; }
else if (c == 12) { counter += 22345; }
else if (c == 13) { counter += 1242; }
else if (c == 14) { counter += 12341; }
else if (c == 15) { counter += 41; }
else if (c == 16) { counter += 34321; }
else if (c == 17) { counter += 232; }
else if (c == 18) { counter += 144231; }
else if (c == 19) { counter += 32; }
else if (c == 20) { counter += 1231; }
}
return 1000 * (long long)(clock() - start) / CLOCKS_PER_SEC;
}
int main()
{
srand(time(NULL));
printf("Starting...\n");
printf("Switch statement: %lld ms\n", testSwitch()); fflush(stdout);
printf("counter: %d\n", counter);
counter = 0;
srand(time(NULL));
printf("If statement: %lld ms\n", testIf()); fflush(stdout);
printf("counter: %d\n", counter);
} 스위치 : 3740
경우 : 3980
(여러 번의 시도와 유사한 결과)
또한 케이스 / if 수를 5로 줄 였는데도 스위치 기능은 여전히 성공했습니다.
답변
MSVC와 같은 우수한 최적화 컴파일러는 다음을 생성 할 수 있습니다.
- 케이스가 좋은 장거리에 배치되면 간단한 점프 테이블
- 간격이 많은 경우 스파 스 (2 레벨) 점프 테이블
- 사례 수가 적거나 값이 서로 근접하지 않은 경우 일련의 if
- 경우가 근접한 범위의 여러 그룹을 나타내는 경우 위의 조합.
간단히 말해 스위치가 일련의 if보다 느리게 보일 경우 컴파일러는 스위치를 하나만 변환 할 수 있습니다. 그리고 그것은 각각의 경우에 대한 일련의 비교 일뿐만 아니라 이진 검색 트리 일 것입니다. 예를 보려면 여기 를 참조 하십시오 .
답변
2)에 대답하고 일반적인 의견을 제시합니다. 2) 아니요, 게시 한 어셈블리 코드에 점프 테이블이 없습니다. 점프 테이블은 점프 대상 테이블과 테이블에서 인덱스 된 위치로 직접 점프하는 하나 또는 두 개의 명령어입니다. 가능한 전환 대상이 많은 경우 점프 테이블이 더 적합합니다. 아마도 옵티마이 저는 대상 수가 임계 값보다 크지 않으면 로직이 더 빠르면 단순하다는 것을 알고있을 것입니다. 4가 아닌 20 가지 가능성으로 다시 예를 들어보십시오.
답변
나는 흥미를 느꼈고 스위치 문을 더 빨리 실행하기 위해 예제에서 무엇을 바꿀 수 있는지 살펴 보았습니다.
40 개의 if 문에 도달하고 0의 경우를 추가하면 if 블록은 동등한 switch 문보다 느리게 실행됩니다. https://www.ideone.com/KZeCz에 결과가 있습니다 .
0 건을 제거하면 https://www.ideone.com/LFnrX 에서 효과를 볼 수 있습니다 .
