More than 1 year has passed since last update.

if文とswitch文、どっち？

Last updated at 2022-12-10Posted at 2022-12-07

ISer Advent Calendar 8日目

↑他の記事もよかったら読んでみてください。

はじめに

if文とswitch文のどちらを使うか迷ったことはないでしょうか。インターネットで調べると、if文とswitch文の実行速度の違いについての記事もありますが、実行時間を調べているだけのものが多く、内部での処理がブラックボックス化してしまっています。
また、個人的に作成している、とあるプログラムで要素が70個ほどあるenumに対してswitch文を適用しているのですが、条件のマッチにどれぐらい時間がかかるのか(最大70回も比較を繰り返すのか？？)気になっていました。
これらを踏まえて、本記事では、if文とswitch文がどうコンパイルされるのかアセンブリを見ることで、両者を比較していきます。言語はC++を対象とします。

対象読者

プログラムの実行速度を少しでも上げたい方
if文やswitch文がどうアセンブリに変換されるのか興味がある方

比較方法

アセンブリを比較
Compiler Explorerを使用(コンパイラはx86-64 gcc 12.2、コンパイルオプションは-O2)

注)

思った以上に長くなってしまったので、結論だけ知りたい方はこちらから

1. 分岐が少ない場合

プログラム

今回用いるプログラムはこちら

※ヘッダやmain関数は省略します。

main

enum class Enum {
    AA, BB, CC, DD
};

void f(Enum); // プロトタイプ宣言(if文かswitch文)

void f(Enum e) {
    if (e == Enum::AA) {
        cout << "AA\n";
    } else if (e == Enum::BB) {
        cout << "BB\n";
    } else if (e == Enum::CC) {
        cout << "CC\n";
    } else if (e == Enum::DD) {
        cout << "DD\n";
    } else {
        cout << "default\n";
    }
}

switch

void f(Enum e) {
    switch (e) {
    case Enum::AA:
        cout << "AA\n";
        break;
    case Enum::BB:
        cout << "BB\n";
        break;
    case Enum::CC:
        cout << "CC\n";
        break;
    case Enum::DD:
        cout << "DD\n";
        break;
    default:
        cout << "default\n";
        break;
    }
}

コンパイル結果

if文の場合

.LC0:
    .string "AA\n"
.LC1:
    .string "BB\n"
.LC2:
    .string "CC\n"
.LC3:
    .string "DD\n"
.LC4:
    .string "default\n"
f(Enum):
    test    edi, edi     ; (edi & edi) == 0 ならZFフラグを1に
    je      .L7          ; ZFフラグが1(つまりedi == 0)なら, ラベル.L7へジャンプ
    cmp     edi, 1       ; edi - 1の結果をフラグレジスタに格納
    je      .L8          ; edi == 1なら.L8へ
    cmp     edi, 2
    je      .L9          ; edi == 2なら.L9へ
    cmp     edi, 3
    je      .L10         ; edi == 3なら.L10へ
    mov     edx, 8       ; 以下4行はdefaultの場合の処理
    mov     esi, OFFSET FLAT:.LC4
    mov     edi, OFFSET FLAT:_ZSt4cout
    jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L7:                     ; eがEnum::AAの場合
    mov     edx, 3
    mov     esi, OFFSET FLAT:.LC0
    mov     edi, OFFSET FLAT:_ZSt4cout
    jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L9:                     ; eがEnum::CCの場合
    mov     edx, 3
    mov     esi, OFFSET FLAT:.LC2
    mov     edi, OFFSET FLAT:_ZSt4cout
    jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L10:                    ; eがEnum::DDの場合
    mov     edx, 3
    mov     esi, OFFSET FLAT:.LC3
    mov     edi, OFFSET FLAT:_ZSt4cout
    jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L8:                    ; eがEnum::BBの場合
    mov     edx, 3
    mov     esi, OFFSET FLAT:.LC1
    mov     edi, OFFSET FLAT:_ZSt4cout
    jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)

switch文の場合

.LC0:
    .string "AA\n"
.LC1:
    .string "BB\n"
.LC2:
    .string "CC\n"
.LC3:
    .string "DD\n"
.LC4:
    .string "default\n"
f(Enum):
    cmp     edi, 2
    je      .L2
    jg      .L3
    test    edi, edi
    je      .L4
    cmp     edi, 1
    jne     .L6
    mov     edx, 3
    mov     esi, OFFSET FLAT:.LC1
    mov     edi, OFFSET FLAT:_ZSt4cout
    jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L3:
    cmp     edi, 3
    jne     .L6
    mov     edx, 3
    mov     esi, OFFSET FLAT:.LC3
    mov     edi, OFFSET FLAT:_ZSt4cout
    jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L2:
    mov     edx, 3
    mov     esi, OFFSET FLAT:.LC2
    mov     edi, OFFSET FLAT:_ZSt4cout
    jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L6:
    mov     edx, 8
    mov     esi, OFFSET FLAT:.LC4
    mov     edi, OFFSET FLAT:_ZSt4cout
    jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L4:
    mov     edx, 3
    mov     esi, OFFSET FLAT:.LC0
    mov     edi, OFFSET FLAT:_ZSt4cout
    jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)

アセンブリの解説はこちら

とても長いですが、上から順番に見ていきましょう。

まずは、アセンブリコードの先頭から。

.LC0:
    .string "AA\n"

↑coutに必要なデータが配置されています。

f(Enum):
・・・(以下略)

↑関数fの本体部分です。大まかな流れとしては、testあるいはcmp命令でオペランドを比較して結果をフラグレジスタに格納し、その結果によりjamp系統の命令の分岐方向が決定されます。細かい挙動まで見なくても、test / cmp命令(比較)とje / jg / jne命令(分岐)が繰り返されているのが読み取れると思います。

.L4:
    mov     edx, 3
    mov     esi, OFFSET FLAT:.LC0
    mov     edi, OFFSET FLAT:_ZSt4cout
    jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)

↑今回の話題とは関係ないので詳細は省きますが、4行合わせてcout << "AA\n";の処理を実行しています。

長くて読む気のしないアセンブリコードですが、各ブロックごとに分けて追ってみれば、繰り返しの部分も多く、実は大して中身がないことがわかります。

比較した結果

if文、switch文のどちらも条件と合致するかを一つずつ順番に比較しています。ただし、switch場合には、比較する順番がややこしいため、以下に疑似コードを示します。

switchの比較順序

if (edi == 2) {
    cout << "CC\n";
} else if (edi > 2) {
    if (edi != 3) {
        cout << "default\n";
    } else {
        cout << "DD\n";
    }
} else {
    if (edi == 0) {
        cout << "AA\n";
    } else {
        if (edi != 1) {
            cout << "default\n";
        } else {
            cout << "BB\n";
        }
    }
}

どちらの場合も愚直に比較しています。比較とジャンプ命令の実行回数の期待値を求めてみましょう。

if

入力値	回数
AA	2
BB	4
CC	6
DD	8
その他	8,8

switch

入力値	回数
AA	5
BB	7
CC	2
DD	5
その他	5,7

これより、期待値はif: 6回、switch: 5.2回であることがわかります。
よって、僅かながらswitchの方が速いと結論づけることができます。
(2022/12/10修正)

2. 分岐がたくさんある場合

プログラム

先ほどと比べてenumの要素が増えただけです。

プログラム

main.cpp

enum class Enum {
    AA, BB, CC, DD, EE, FF, GG, HH
};

void f(Enum e);

if文

void f(Enum e) {
    if (e == Enum::AA) {
        cout << "AA\n";
    } else if (e == Enum::BB) {
        cout << "BB\n";
    } else if (e == Enum::CC) {
        cout << "CC\n";
    } else if (e == Enum::DD) {
        cout << "DD\n";
    } else if (e == Enum::EE) {
        cout << "EE\n";
    } else if (e == Enum::FF) {
        cout << "FF\n";
    } else if (e == Enum::GG) {
        cout << "GG\n";
    } else if (e == Enum::HH) {
        cout << "HH\n";
    } else {
        cout << "default\n";
    }
}

switch文

void f(Enum e) {
    switch (e) {
    case Enum::AA:
        cout << "AA\n";
        break;
    case Enum::BB:
        cout << "BB\n";
        break;
    case Enum::CC:
        cout << "CC\n";
        break;
    case Enum::DD:
        cout << "DD\n";
        break;
    case Enum::EE:
        cout << "EE\n";
        break;
    case Enum::FF:
        cout << "FF\n";
        break;
    case Enum::GG:
        cout << "GG\n";
        break;
    case Enum::HH:
        cout << "HH\n";
        break;
    default:
        cout << "default\n";
        break;
    }
}

コンパイル結果

Compiler Explorerでプログラムをコンパイルしたところで衝撃の事実が発覚。if文とswitch文で1文字たりとも違わない、全く同じアセンブリコードが生成されたのです。あれれ、最適化の面ではif文よりswitch文の方が優れていると思っていたのに。。

アセンブリ

.LC0:
        .string "AA\n"
.LC1:
        .string "BB\n"
.LC2:
        .string "CC\n"
.LC3:
        .string "DD\n"
.LC4:
        .string "EE\n"
.LC5:
        .string "FF\n"
.LC6:
        .string "GG\n"
.LC7:
        .string "HH\n"
.LC8:
        .string "default\n"
f(Enum):
        cmp     edi, 7
        ja      .L2        ; edi > 7の場合(defaultの場合)は.L2へ
        mov     edi, edi
        mov     edx, 3     ; coutで出力される文字数(=3)をedxに格納
        jmp     [QWORD PTR .L4[0+rdi*8]]
.L4:
        .quad   .L11
        .quad   .L10
        .quad   .L9
        .quad   .L8
        .quad   .L7
        .quad   .L6
        .quad   .L5
        .quad   .L3
.L5:
        mov     esi, OFFSET FLAT:.LC6
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L3:
        mov     esi, OFFSET FLAT:.LC7
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L11:
        mov     esi, OFFSET FLAT:.LC0
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L10:
        mov     esi, OFFSET FLAT:.LC1
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L9:
        mov     esi, OFFSET FLAT:.LC2
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L8:
        mov     esi, OFFSET FLAT:.LC3
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L7:
        mov     esi, OFFSET FLAT:.LC4
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L6:
        mov     esi, OFFSET FLAT:.LC5
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L2:
        mov     edx, 8
        mov     esi, OFFSET FLAT:.LC8
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)

↑長いですが、大事なポイントは後述する1行です。

読み解いてみる

先ほど(分岐が少ない場合)と違って、今回は分岐命令がほとんど見られません。どのように分岐先が決定されているかというと、大雑把に言って、

jmp     [QWORD PTR .L4[0+rdi*8]]

において、.L4以下に並べられた8つのラベルのうち、上から(ediの値)番目のラベルが分岐先と決まり、そこにjmp命令で飛んでいきます。つまり、ediの値が条件に合うかを比較していくのではなく、ediの値を用いて直接分岐先に飛んでいることになります。
先ほどの場合は分岐の数に比例した比較演算をする必要があったのに対し、今回は分岐の数によらずに1回の比較演算のみで済んでいます。このことから、switch文で大量に分岐があっても、最悪の場合に分岐の数だけ比較をする必要がある、というわけではないことがわかります。
ちなみに、この方法では分岐の個数*8byte分のメモリ領域を使う必要があり、例えば120個の分岐の場合には約1KBもの領域が使われてしまいます。

細かい説明

前提知識として、ラベルはアドレスに名前をつけたものにすぎず、機械語に変換される際にはラベルは実際のアドレスに置換されます。ラベルはアドレスを指す変数名と考えることでアセンブリが理解しやすくなると思います。
.L4以下には、.quad (ラベル)が8つ連続していますが、.quadは後に続く8byteのデータをメモリにロードさせる指令です。つまり、メモリ上には、アドレス.L4から8バイト幅のデータが8つ連続して配置されます。
最初に、.L4[0+rdi*8]は、アドレス.L4+rdi*8(:=addr)の計算を表し、これは.L4がベースアドレス、rdi*8がオフセットであると解釈できます。そして、QWORD PTR .L4[0+rdi*8]においてアドレスaddrからqword(=8byte)分のデータをメモリから取ってきています。最後に、取ってきたデータが指すアドレス[QWORD PTR .L4[0+rdi*8]]にjmp命令でジャンプしています。

3. 取りうる値が連続でない場合

もう飽きてしまった方も多いとは思いますが、もうしばしお付き合い願います。
さて、enumの取る値がステップ幅1で規則正しく並んでいる場合には値をオフセットとして計算することができましたが、enumの取る値がバラバラで取りうる値の幅も大きい場合にはどのようになるのでしょうか。

enumを次のように変更して検証しました。

enum class Enum {
    AA,
    BB = 13,
    CC = 41,
    DD = 79,
    EE = 131,
    FF = 251,
    GG = 313,
    HH = 419
};

結果

アセンブリコード

f(Enum):
        test    edi, edi
        je      .L11
        cmp     edi, 13
        je      .L12
        cmp     edi, 41
        je      .L13
        cmp     edi, 79
        je      .L14
        cmp     edi, 131
        je      .L15
        cmp     edi, 251
        je      .L16
        cmp     edi, 313
        je      .L17
        cmp     edi, 419
        je      .L18
        mov     edx, 8
        mov     esi, OFFSET FLAT:.LC8
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
(以下略)

↑.L11~.L18には、ediの値に応じた処理が書かれています。

switch

f(Enum):
        cmp     edi, 131
        je      .L2
        jg      .L3
        cmp     edi, 41
        je      .L4
        jle     .L14
        cmp     edi, 79
        jne     .L8
        mov     edx, 3
        mov     esi, OFFSET FLAT:.LC3
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L3:
        cmp     edi, 313
        je      .L10
        cmp     edi, 419
        jne     .L15
        mov     edx, 3
        mov     esi, OFFSET FLAT:.LC7
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L14:
        test    edi, edi
        je      .L6
        cmp     edi, 13
        jne     .L8
        mov     edx, 3
        mov     esi, OFFSET FLAT:.LC1
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L15:
        cmp     edi, 251
        jne     .L8
        mov     edx, 3
        mov     esi, OFFSET FLAT:.LC5
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L2:
        mov     edx, 3
        mov     esi, OFFSET FLAT:.LC4
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L4:
        mov     edx, 3
        mov     esi, OFFSET FLAT:.LC2
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L8:
        mov     edx, 8
        mov     esi, OFFSET FLAT:.LC8
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L10:
        mov     edx, 3
        mov     esi, OFFSET FLAT:.LC6
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L6:
        mov     edx, 3
        mov     esi, OFFSET FLAT:.LC0
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
(以下略)

ついに(!)、if文とswitch文で異なるコンパイル結果が得られました。
if文では愚直に値が一致するかを比較しています。最悪の場合には分岐の数だけの比較演算が必要になります。
一方、switch文では、分岐の決定方法は以下の通りとなります。

疑似コード

if (edi == 131) {
    // Enum::EEの場合
} else if (edi > 131) {
    if (edi == 313) {
        // Enum::GGの場合
    } else {
        if (edi != 419) {
            if (edi != 251) {
                // Defaultの場合
            } else {
                // Enum::FFの場合
            }
        } else {
            // Enum::HHの場合
        }
} else {
    if (edi == 41) {
        // Enum::CCの場合
    } else if (edi < 41) {
        if (edi == 0) {
            // Enum::AAの場合
        } else {
            if (edi != 13) {
                // Defaultの場合
            } else {
                // Enum::BBの場合
            }
        }
    } else {
        if (edi != 79) {
            // Defaultの場合
        } else {
            // Enum::DDの場合
        }
    }
}

一目瞭然、二分探索的なコードが生成されています。最悪の場合でも分岐数の対数時間で済むため、最悪の場合で線形時間かかるif文よりも効率よく分岐が行われることがわかります。

4. その他

C++(switch文のみ)とアセンブリの対応だけ載っけます。

等差数列($d\neq1$)パターン

C++

enum class Enum {
    AA,
    BB = 4,
    CC = 8,
    DD = 12,
    EE = 16,
    FF = 20,
    GG = 24,
    HH = 28
};

asm

f(Enum):
        cmp     edi, 14
        ja      .L2
        mov     edi, edi
        jmp     [QWORD PTR .L4[0+rdi*8]]
.L4:
        .quad   .L11
        .quad   .L2
        .quad   .L10
        .quad   .L2
        .quad   .L9
        .quad   .L2
        .quad   .L8
        .quad   .L2
        .quad   .L7
        .quad   .L2
        .quad   .L6
        .quad   .L2
        .quad   .L5
        .quad   .L2
        .quad   .L3

ediが奇数の時は全てdefaultに飛ばされていますね。

部分的に遷移テーブル生成パターン

C++

enum class Enum {
    AA,
    BB = 1,
    CC = 3,
    DD = 7,
    EE = 10,
    FF = 130,
    GG = 150,
    HH = 200
};

asm

f(Enum):
        cmp     edi, 10
        jg      .L2
        test    edi, edi
        js      .L3
        cmp     edi, 10
        ja      .L3
        mov     edi, edi
        jmp     [QWORD PTR .L5[0+rdi*8]]
.L5:
        .quad   .L9
        .quad   .L8
        .quad   .L3
        .quad   .L7
        .quad   .L3
        .quad   .L3
        .quad   .L3
        .quad   .L6
        .quad   .L3
        .quad   .L3
        .quad   .L4
.L2:
        cmp     edi, 150
        je      .L10
        cmp     edi, 200
        jne     .L14
        mov     edx, 3
        mov     esi, OFFSET FLAT:.LC7
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L14:
        cmp     edi, 130
        jne     .L3
        mov     edx, 3
        mov     esi, OFFSET FLAT:.LC5
        mov     edi, OFFSET FLAT:_ZSt4cout
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
(以下略)

edi < 10の場合には遷移テーブルを用い、それ以上の場合には単純に比較しています。

遷移テーブル2つ生成パターン

C++

enum class Enum {
    AA,
    BB,
    CC,
    DD,
    EE,
    FF = 100,
    GG,
    HH,
    II,
    JJ
};

asm

f(Enum):
        sub     rsp, 8
        cmp     edi, 4
        jle     .L21
        lea     eax, [rdi-100]
        cmp     eax, 4
        ja      .L4
        sub     edi, 101
        cmp     edi, 3
        ja      .L5
        jmp     [QWORD PTR .L7[0+rdi*8]]
.L7:
        .quad   .L10
        .quad   .L9
        .quad   .L8
        .quad   .L6
.L21:
        test    edi, edi
        jns     .L22
.L4:
        mov     edx, 8
        mov     esi, OFFSET FLAT:.LC10
        mov     edi, OFFSET FLAT:_ZSt4cout
        add     rsp, 8
        jmp     std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
.L22:
        mov     edx, 3
        cmp     edi, 4
        ja      .L11
        mov     edi, edi
        jmp     [QWORD PTR .L13[0+rdi*8]]
.L13:
        .quad   .L11
        .quad   .L16
        .quad   .L15
        .quad   .L14
        .quad   .L12
(以下略)

結論

if vs switch

ステップ幅1のenumに対して分岐させる場合には、if文でもswitch文でも同じで$O(1)$で分岐先へ飛べる(要素数70までは確認済み)
要素がバラバラで、取りうる値の幅も大きい時には二分探索的なswitch文の方が効率がいい
- 取りうる値の幅が小さい時には遷移テーブル使用で$O(1)$

switchの処理

分岐数の違いによって、条件の逐次比較と遷移テーブル、二分探索比較を使い分けている
- コンパイラが適当なものを選んでくれている
- enumの各要素がある程度まとまった値を取る場合には、まとまりごとに遷移テーブルを作るべきか判断

これから

今回はC++の中のenumという、とてつもなく狭い範囲において、if文とswitch文の違い、あるいはswitch文のアセンブリへの変換のされ方を調べました。しかし、C++の中でも他の場合にはどうなのか、ましてや他の言語の場合は未知であるので、どうなっているのか調査してみる価値はあると思います。言語によってはswitch文で文字列も使えるので、それもどうなっているのか気になりますね。

参考文献

第12回小手先チューニング -- 条件分岐の高速化

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up