読者です 読者をやめる 読者になる 読者になる

Mae向きなブログ

Mae向きな日記のブログ版。ようやくこちらに移行してきました。

ジャンプテーブルについて

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章だけになってきましたが,目から鱗になるような話がいろいろあって読んでいて面白いです。