ホーム
c

[解決済み】「switch」は「if」よりも速い？

2022-04-03 03:53:09

質問

は、以下の通りです。 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());
}

で、以下のような結果が得られました。

スイッチ文。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

更新情報

興味深い結果こちら . なぜ一方が速く、一方が遅いのか、理由はよくわからないが。

解決方法は？

コンパイラが行う最適化にはいくつかあります。 できること スイッチで作る。よく言われるquot;jump-table"は、入力が何らかの方法で束縛される場合にのみ機能するので、あまり有用なものだとは思いません。

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

ジャンプテーブルを使用していないことがわかります。

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 のラダーがあると、それを同等のスイッチに変換したり、その逆の処理をした方が高速になる場合は、その処理をします。

[解決済み】「switch」は「if」よりも速い？

質問

質問です。

更新情報

解決方法は？

関連

[解決済み】 switch case: error: case label does not reduce to an integer constant

[解決済み】「配列のイニシャライザーはイニシャライザーリストまたは文字列リテラルでなければなりません」と表示されるのですが？

[解決済み] B "の印刷が "#"の印刷より劇的に遅いのはなぜですか？

[解決済み] 要素ごとの加算は、結合ループよりも分離ループの方がはるかに高速なのはなぜですか？

[解決済み] Rubyのswitch文の書き方

[解決済み] Pythonのswitch文の代用品？

[解決済み] <は<=より速いのか？

[解決済み] switch文の中で変数を宣言してはいけないのはなぜですか？

[解決済み] Collatz予想の検証を行うC++のコードは、なぜ手書きのアセンブリよりも高速に動作するのでしょうか？

[解決済み] なぜ[]はlist()よりも速いのですか？

最新

nginxです。[emerg] 0.0.0.0:80 への bind() に失敗しました (98: アドレスは既に使用中です)

htmlページでギリシャ文字を使うには

ピュアhtml+cssでの要素読み込み効果

純粋なhtml + cssで五輪を実現するサンプルコード

ナビゲーションバー・ドロップダウンメニューのHTML+CSSサンプルコード

タイピング効果を実現するピュアhtml+css

htmlの選択ボックスのプレースホルダー作成に関する質問

html css3 伸縮しない画像表示効果

トップナビゲーションバーメニュー作成用HTML+CSS

html+css 実装サイバーパンク風ボタン

おすすめ

[解決済み】「ポインタから異なるサイズの整数へのキャスト」エラーが発生するのはなぜですか？

[解決済み] (.text+0x20): `main'への未定義の参照と関数への未定義の参照

[解決済み] clang: error: linker command failed with exit code 1が表示されるのはなぜですか？

[解決済み】エラー：イニシャライザー要素がロード時に計算可能でない

[解決済み】式は変更可能なL値でなければならない

[解決済み】Linuxでexeclp()がどのように動作するのか理解できません。

[解決済み] [Solved] .Cファイルをコンパイルしています。アーキテクチャ x86_64 の未定義シンボル

[解決済み】なぜか。"エラー: 配列型を持つ式への代入"

[解決済み] 整数の平方根が整数であるかどうかを判断する最速の方法

[解決済み] if-else文に対するswitchの優位性