『Write Great Code〈Vol.2〉低いレベルで考え高いレベルで書く』の第14章を読んでいます。その中の「14.6.2 ジャンプテーブルと一連の比較」は，こんな書き出しで始まります。
switch/caseステートメントは，if..then..elseifのシーケンスよりも読みやすくて便利に思えますが，このステートメントがそもそも高級言語に追加されたのは，効率向上のためであり，読みやすさや利便性のためではありませんでした。
今まで，switch/caseとif..then..elseifはほとんど同じようなものだろうと思っていたので，この書き出しを読んで，ちょっとビックリしました。
switch/caseの効率向上の秘密の鍵は，「ジャンプテーブル」というものがにぎっているようです。
実際，どんなものか確かめようと以下のような簡単な例で，試してみました。
switch4.c
#include <stdio.h> int main(void) { int a; scanf("%d", &a); switch (a) { case 0: printf("a == 0\n"); break; case 1: printf("a == 1\n"); break; case 2: printf("a == 2\n"); break; case 3: printf("a == 3\n"); break; default: printf("others\n"); } return 0; }
アセンブリコードを見てみます。
$ gcc --version
gcc (Ubuntu 4.3.3-5ubuntu4) 4.3.3
Copyright (C) 2008 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.$ gcc -S switch4.c
switch4.s
ちょっと長いですが，以下に示します。アセンブラはあまり良く分かりませんが，Cのソースと照らし合わせてみるとなんとなく何をやっているのかは想像できます。しかし，ジャンプテーブルが使われているような感じではありません。むしろif..then..elseifをアセンブルしているような感じがします。
.file "switch4.c" .section .rodata .LC0: .string "%d" .LC1: .string "a == 0" .LC2: .string "a == 1" .LC3: .string "a == 2" .LC4: .string "a == 3" .LC5: .string "others" .text .globl main .type main, @function main: leal 4(%esp), %ecx andl $-16, %esp pushl -4(%ecx) pushl %ebp movl %esp, %ebp pushl %ecx subl $36, %esp leal -8(%ebp), %eax movl %eax, 4(%esp) movl $.LC0, (%esp) call scanf movl -8(%ebp), %eax movl %eax, -24(%ebp) cmpl $1, -24(%ebp) je .L4 cmpl $1, -24(%ebp) jg .L7 cmpl $0, -24(%ebp) je .L3 jmp .L2 .L7: cmpl $2, -24(%ebp) je .L5 cmpl $3, -24(%ebp) je .L6 jmp .L2 .L3: movl $.LC1, (%esp) call puts jmp .L8 .L4: movl $.LC2, (%esp) call puts jmp .L8 .L5: movl $.LC3, (%esp) call puts jmp .L8 .L6: movl $.LC4, (%esp) call puts jmp .L8 .L2: movl $.LC5, (%esp) call puts .L8: movl $0, %eax addl $36, %esp popl %ecx popl %ebp leal -4(%ecx), %esp ret .size main, .-main .ident "GCC: (Ubuntu 4.3.3-5ubuntu4) 4.3.3" .section .note.GNU-stack,"",@progbits
「switch文のコンパイル結果」によると，caseが5つ以上ないとジャンプテーブルにはならないということのようです。ということで，条件をひとつ増やして試してみました。
switch5.c
#include <stdio.h> int main(void) { int a; scanf("%d", &a); switch (a) { case 0: printf("a == 0\n"); break; case 1: printf("a == 1\n"); break; case 2: printf("a == 2\n"); break; case 3: printf("a == 3\n"); break; case 4: printf("a == 4\n"); break; default: printf("others\n"); } return 0; }
これをアセンブルすると，こんな感じになります。
switch5.s
.L8の部分がジャンプテーブルですね。以下で，どこのラベルに飛ぶかを求めているんだろうと思います。
movl .L8(,%edx,4), %eax jmp *%eax
このようにテーブル参照と間接ジャンプを使用すると，場合分けの数に関係なく，複数の位置の中のどこにでも一定の時間で制御を転送することが可能になるんですね。勉強になりました。
.file "switch5.c" .section .rodata .LC0: .string "%d" .LC1: .string "a == 0" .LC2: .string "a == 1" .LC3: .string "a == 2" .LC4: .string "a == 3" .LC5: .string "a == 4" .LC6: .string "others" .text .globl main .type main, @function main: leal 4(%esp), %ecx andl $-16, %esp pushl -4(%ecx) pushl %ebp movl %esp, %ebp pushl %ecx subl $36, %esp leal -8(%ebp), %eax movl %eax, 4(%esp) movl $.LC0, (%esp) call scanf movl -8(%ebp), %eax movl %eax, -24(%ebp) cmpl $4, -24(%ebp) ja .L2 movl -24(%ebp), %edx movl .L8(,%edx,4), %eax jmp *%eax .section .rodata .align 4 .align 4 ; ジャンプテーブル！ .L8: .long .L3 .long .L4 .long .L5 .long .L6 .long .L7 .text .L3: movl $.LC1, (%esp) call puts jmp .L9 .L4: movl $.LC2, (%esp) call puts jmp .L9 .L5: movl $.LC3, (%esp) call puts jmp .L9 .L6: movl $.LC4, (%esp) call puts jmp .L9 .L7: movl $.LC5, (%esp) call puts jmp .L9 .L2: movl $.LC6, (%esp) call puts .L9: movl $0, %eax addl $36, %esp popl %ecx popl %ebp leal -4(%ecx), %esp ret .size main, .-main .ident "GCC: (Ubuntu 4.3.3-5ubuntu4) 4.3.3" .section .note.GNU-stack,"",@progbits
追記(2009/08/07)
http://uw713doc.sco.com/cgi-bin/info2html?%28gcc%29Misc&lang=ja の `CASE_VALUES_THRESHOLD'を見ると，この値でジャンプテーブルを使用する or 使用しないという閾値を決めているような感じもします。
先を読んでみると…
『Write Great Code〈Vol.2〉低いレベルで考え高いレベルで書く』の「14.6.2 ジャンプテーブルと一連の比較」を読んで反射的に実験してみたのですが，第14章を最後まで読むと，switch/caseステートメントについて更に理解が深まります。
例えば，
- ケースの数がかなり多くてジャンプテーブルが大きくなりすぎる場合には，ケースをテストするための二分探索木が生成されるとか…
- 0,1,2,3,4,1000というケースに分かれている場合，単純に，
switch (a) { case 0: printf("a == 0\n"); break; case 1: printf("a == 1\n"); break; case 2: printf("a == 2\n"); break; case 3: printf("a == 3\n"); break; case 4: printf("a == 4\n"); break; case 1000: printf("a == 1000\n"); break; default: printf("other\n"); }
と書くより，以下のように書いた方がコンパイラが生成するコードが向上する可能性があるとか…。
switch (a) { case 0: printf("a == 0\n"); break; case 1: printf("a == 1\n"); break; case 2: printf("a == 2\n"); break; case 3: printf("a == 3\n"); break; case 4: printf("a == 4\n"); break; default: if (a == 1000) { printf("a == 1000\n"); } else { printf("other\n"); } }
- ジャンプテーブルによるswitch/caseステートメントの実装は，一般には，場合分けのケースの数がそれなりにあって，各ケースが成り立つ可能性が同程度である場合には，効率が良い方法ですが，1つか2つのケースが成り立つ可能性がほかよりはるかに高い場合には，if..then..elseifのシーケンスのほうが高速な場合があるとか…。
『Write Great Code〈Vol.2〉低いレベルで考え高いレベルで書く』も残すところ，第15章と第16章だけになってきましたが，目から鱗になるような話がいろいろあって読んでいて面白いです。
