c - 「switch」は「if」より速いですか?

Question

ステートメントは実際にswitchステートメントよりも高速ですか?if

以下のコードを Visual Studio 2010 の x64 C++ コンパイラで/Oxフラグを付けて実行しました。

#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());
}

これらの結果を得ました：

Switch ステートメント: 5261 ミリ秒
If ステートメント: 5196 ミリ秒

私が学んだことから、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

アップデート：

ここで興味深い結果が得られました。ただし、なぜ一方が速く、もう一方が遅いのかはわかりません。

score 135 · Accepted Answer

コンパイラがスイッチに対して実行できる最適化はいくつかあります。ただし、よく言及される「ジャンプテーブル」は、入力が何らかの方法で制限できる場合にのみ機能するため、非常に役立つとは思いません。

「ジャンプテーブル」の 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はしごを見て、それを同等のスイッチに変換するか、そうする方が速い場合はその逆を行います。

score 49 · Accepted Answer

あなたの質問に：

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 ビットポインターまたはオフセットの場合、1 回のジャンプテーブルルックアップで実行可能ファイルのサイズがそれほど大きくなることはありません。

結論：コンパイラはそのようなケースを処理し、適切な命令を生成するのに十分賢いです:)

score 33 · Accepted Answer

コンパイラは、switch ステートメントを if ステートメントと同等のコードとしてコンパイルすることも、ジャンプテーブルを作成することも自由です。コンパイラオプションで指定した内容に応じて、最速で実行されるもの、または最小のコードを生成するものに基づいて、どちらか一方を選択する可能性があります。したがって、最悪の場合、if ステートメントと同じ速度になります。

私は、コンパイラが最善の選択をし、コードを最も読みやすくするものに焦点を当てることを信頼します。

ケースの数が非常に多くなると、ジャンプテーブルは一連の if よりもはるかに高速になります。ただし、値間のステップが非常に大きい場合、ジャンプテーブルが大きくなる可能性があり、コンパイラはそれを生成しないことを選択する場合があります。

score 14 · Accepted Answer

コンピューターがスイッチテストループ中にテストに関係のないタスクを実行しておらず、ifテストループ中に実行するタスクが少ないことをどのように知っていますか？テスト結果には、次のようなものは何も表示されません。

違いは非常に小さいです
一連の結果ではなく、1つの結果のみがあります
ケースが少なすぎる

私の結果：

追加しました：

printf("counter: %u\n", counter);

最後に、この例ではcounterが使用されていないため、ループが最適化されないようにします。なぜコンパイラーがループを実行するのでしょうか。すぐに、このようなマイクロベンチマークを使用しても、スイッチは常に勝っていました。

コードに関する他の問題は次のとおりです。

switch (counter % 4 + 1)

スイッチループでは、

const size_t c = counter % 4 + 1;

ifループで。それを修正すると非常に大きな違いがあります。このステートメントをswitchステートメント内に配置すると、コンパイラーは値を最初にスタックに配置するのではなく、CPUレジスターに直接送信するようになります。したがって、これはswitchステートメントに有利であり、バランスの取れたテストではありません。

ああ、テストの合間にカウンターもリセットする必要があると思います。実際、+ 1、+ 2、+ 3などの代わりに、ある種の乱数を使用する必要があります。これにより、そこで何かが最適化される可能性があります。乱数とは、たとえば現在の時刻に基づく数値を意味します。そうしないと、コンパイラーは両方の関数を1つの長い数学演算に変換し、ループを気にすることさえありません。

コードが実行される前にコンパイラが物事を理解できないようにするために、ライアンのコードを変更しました。

#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
if：3980

（複数回の試行で同様の結果）

また、ケース/ ifの数を5に減らしても、スイッチ機能は引き続き使用できます。

score 7 · Accepted Answer

以下は、古い (現在は見つけるのが難しい) ベンチ++ ベンチマークの結果の一部です。

Test Name:   F000003                         Class Name:  Style
CPU Time:       0.781  nanoseconds           plus or minus     0.0715
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 2-way if/else if statement
 compare this test with F000004

Test Name:   F000004                         Class Name:  Style
CPU Time:        1.53  nanoseconds           plus or minus     0.0767
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 2-way switch statement
 compare this test with F000003

Test Name:   F000005                         Class Name:  Style
CPU Time:        7.70  nanoseconds           plus or minus      0.385
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way if/else if statement
 compare this test with F000006

Test Name:   F000006                         Class Name:  Style
CPU Time:        2.00  nanoseconds           plus or minus     0.0999
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way switch statement
 compare this test with F000005

Test Name:   F000007                         Class Name:  Style
CPU Time:        3.41  nanoseconds           plus or minus      0.171
Wall/CPU:        1.00  ratio.                Iteration Count:  1677721600
Test Description:
 Time to test a global using a 10-way sparse switch statement
 compare this test with F000005 and F000006

このことからわかることは、(このマシンでは、このコンパイラ -- VC++ 9.0 x64 を使用して)、各ifテストに約 0.7 ナノ秒かかるということです。テストの数が増えると、時間はほぼ完全に直線的に変化します。

switch ステートメントを使用すると、値が密である限り、2 方向テストと 10 方向テストの速度にほとんど違いはありません。疎な値を使用した 10 通りのテストは、密な値を使用した 10 通りのテストよりも約 1.6 倍の時間がかかりますが、疎な値を使用しても、10 通りのif/の 2 倍の速度よりも優れていelse ifます。

結論: 4 方向テストのみを使用しても、 vs /のパフォーマンスについてはあまりわかりません。このコードの数値を見ると、4 方向テストの場合、2 つの結果がほぼ同じであることが予想される ( /の場合は ~2.8 ナノ秒、の場合は ~2.0ナノ秒) という事実を補間するのは非常に簡単です。switchifelseifelseswitch

score 7 · Accepted Answer

MSVC などの優れた最適化コンパイラは、以下を生成できます。

ケースが長い範囲に配置されている場合は、単純なジャンプ台
ギャップが多い場合は、まばらな (2 レベルの) ジャンプテーブル
ケースの数が少ない場合、または値が接近していない場合の一連の if
ケースが狭い範囲の複数のグループを表す場合は、上記の組み合わせ。

要するに、switch が一連の if よりも遅いと思われる場合、コンパイラはそれを 1 つに変換するだけかもしれません。そして、それはケースごとの単なる一連の比較ではなく、二分探索木になる可能性があります。例については、こちらを参照してください。

score 5 · Accepted Answer

2) について回答し、一般的なコメントをいくつか述べます。2) いいえ、投稿したアセンブリコードにジャンプテーブルはありません。ジャンプテーブルは、ジャンプ先のテーブルであり、テーブルからインデックス付きの場所に直接ジャンプするための 1 つまたは 2 つの命令です。切り替え先の候補が多数ある場合は、ジャンプテーブルが適しています。おそらくオプティマイザーは、目的地の数があるしきい値よりも大きくない限り、単純な if else ロジックの方が高速であることを認識しています。例を 4 ではなく 20 の可能性でもう一度試してください。

score 4 · Accepted Answer

私は興味をそそられ、switchステートメントをより速く実行するためにあなたの例について何を変更できるかを調べました.

40 個の if ステートメントに到達し、0 のケースを追加すると、if ブロックは同等の switch ステートメントよりも遅く実行されます。ここに結果があります: https://www.ideone.com/KZeCz .

0 ケースを削除した効果は、https ://www.ideone.com/LFnrX で確認できます。

score 3 · Accepted Answer

スイッチがジャンプテーブルにコンパイルされていない場合は、多くの場合、スイッチよりも効率的に if を記述できることに注意してください。

(1) すべての N に対する最悪のケースのテストではなく、ケースに順序付けがある場合は、上半分または下半分で if をテストする if を記述し、その各半分でバイナリ検索スタイルを作成できます...結果としてN ではなく logN になる最悪のケース

(2) 特定のケース/グループが他のケースよりもはるかに頻繁に発生する場合、最初にそれらのケースを分離するように if を設計すると、平均時間を短縮できます。

score 2 · Accepted Answer

ただし、なぜ一方が速く、もう一方が遅いのかはわかりません。

それを説明するのはそれほど難しいことではありません...誤って予測された分岐は、正しく予測された分岐よりも数十倍から数百倍もコストがかかることを覚えているなら。

この% 20バージョンでは、最初の case/if が常にヒットします。最近の CPU は、どの分岐が通常実行され、どの分岐が実行されないかを「学習」するため、ループのほぼすべての反復でこの分岐がどのように動作するかを簡単に予測できます。これが、「if」バージョンが飛ぶ理由を説明しています。最初のテスト以降は何も実行する必要がなく、ほとんどの反復でそのテストの結果を (正しく) 予測します。明らかに、「スイッチ」の実装はわずかに異なります。おそらく、計算されたブランチのおかげで遅くなる可能性のあるジャンプテーブルでさえあります。

バージョンでは% 21、ブランチは基本的にランダムです。したがって、それらの多くはすべての反復を実行するだけでなく、CPU はそれらがどの方向に進むかを推測できません。これは、ジャンプテーブル (または他の「スイッチ」最適化) が役立つ可能性が高い場合です。

最新のコンパイラと CPU でコードの一部がどのように実行されるかを予測することは非常に難しく、世代ごとに難しくなっています。最善のアドバイスは、「わざわざ試してはいけません。常にプロファイルを作成してください」です。そのアドバイスはますます良くなり、それをうまく無視できる人は年々少なくなっています。

つまり、上記の私の説明はほとんど推測です。:-)

score 2 · Accepted Answer

いいえ、これらはif then jump else if then jump else...ジャンプテーブルにはアドレスのテーブルがあるか、ハッシュなどを使用します。

速いか遅いかは主観的です。たとえば、ケース 1 を最初ではなく最後にすることができます。テストプログラムまたは実世界のプログラムがほとんどの場合ケース 1 を使用する場合、この実装ではコードが遅くなります。そのため、実装に応じて、ケースリストを再配置するだけで、大きな違いが生じる可能性があります。

ケース 1 ～ 4 の代わりにケース 0 ～ 3 を使用した場合、コンパイラはジャンプテーブルを使用した可能性があります。品数が少なかったのかもしれません。たとえば、0 - 15 または 0 - 31 にした場合、テーブルを使用して実装したか、他のショートカットを使用した可能性があります。コンパイラは、ソースコードの機能を満たしている限り、実装方法を自由に選択できます。そして、これはコンパイラの違いとバージョンの違いと最適化の違いに入ります。ジャンプテーブルが必要な場合はジャンプテーブルを作成し、if-then-else ツリーが必要な場合は if-then-else ツリーを作成します。コンパイラに決定させたい場合は、switch/case ステートメントを使用します。

score 1 · Accepted Answer

なし。アセンブラに入って実際のパフォーマンス測定を行うほとんどの特定のケースでは、あなたの質問は単に間違っています。与えられた例では、あなたの考えは決定的に短すぎます。

counter += (4 - counter % 4);

あなたが使用すべき正しいインクリメント式であるように私には見えます。

c - 「switch」は「if」より速いですか?

質問:

アップデート：

12 に答える 12

Related

Reference