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

まあ割とどうでもいいこと(はじめてのgcc -S)

Cでプログラムを書いているとよく出会う場面(いやCじゃなくてもよく出会う)

#define OPTION_A  (1)
#define OPTION_B  (2)
#define OPTION_C  (3)
#define OPTION_D  (4)
#define OPTION_E  (5)
int exec_command( int cmd, int args, char** argv ){
  switch(cmd){
  case OPTION_A:  do_a(args, argv); break;
  case OPTION_B:  do_b(args, argv); break;
  case OPTION_C:  do_c(args, argv); break;
  case OPTION_D:  do_d(args, argv); break;
  case OPTION_E:  do_e(args, argv); break;
  default: some_error(); break;
  }
}

これなんか気持ち悪いよねえとか思う程度です。

要はコマンドで数値が飛んでくるとそれに応じて処理を分けたいのです。でもコンパイラがどれくらい賢いのかよくわからないので、とりあえずgcc -Sしてみたら

.globl _exec_command
_exec_command:
LFB8:
	pushq	%rbp
LCFI12:
	movq	%rsp, %rbp
LCFI13:
	subq	$16, %rsp
LCFI14:
	movl	%edi, -4(%rbp)
	movl	%esi, -8(%rbp)
	movq	%rdx, -16(%rbp)
	cmpl	$5, -4(%rbp)
	ja	L14
	mov	-4(%rbp), %eax
	leaq	0(,%rax,4), %rdx
	leaq	L20(%rip), %rax
	leaq	(%rdx,%rax), %rax
	movl	(%rax), %eax
	movslq	%eax,%rdx
	leaq	L20(%rip), %rax
	leaq	(%rdx,%rax), %rax
	jmp	*%rax
	.align 2,0x90
L20:
	.long	L14-L20
	.long	L15-L20
	.long	L16-L20
	.long	L17-L20
	.long	L18-L20
	.long	L19-L20
L15:
	movq	-16(%rbp), %rsi
	movl	-8(%rbp), %edi
	movl	$0, %eax
	call	_do_a
	jmp	L22
L16:
	movq	-16(%rbp), %rsi
	movl	-8(%rbp), %edi
	movl	$0, %eax
	call	_do_b
	jmp	L22
L17:
	movq	-16(%rbp), %rsi
	movl	-8(%rbp), %edi
	movl	$0, %eax
	call	_do_c
	jmp	L22
L18:
	movq	-16(%rbp), %rsi
	movl	-8(%rbp), %edi
	movl	$0, %eax
	call	_do_d
	jmp	L22
L19:
	movq	-16(%rbp), %rsi
	movl	-8(%rbp), %edi
	movl	$0, %eax
	call	_do_e
	jmp	L22
L14:
	movl	$0, %eax
	call	_some_error
L22:
	leave
	ret
LFE8:

という感じのながーいアセンブラになってしまう。ふつう最適化ってアセンブラにするまでが勝負なので(そうだよね?)、こんだけいろいろ命令が入ってたら遅そうだよネェ。
というわけでオレオレ速くする方法(ジョーシキかもね?)。

typedef void(*dispatch_t)(int, char**);
static dispatch_t d[6]={ 0, do_a, do_b, do_c, do_d, do_e };

void exec_command2( int cmd, int args, char** argv ){
  d[cmd](args, argv);
}

配列作っといて、intなコマンドがダイレクトにその関数を見つけられるようにする。オラ、デザインパターンとかアセンブラとかよくわかんないけど、こっちの方がアセンブラコードが短けえぞ!!

_d:
	.quad	0
	.quad	_do_a
	.quad	_do_b
	.quad	_do_c
	.quad	_do_d
	.quad	_do_e
	.text
.globl _exec_command2
_exec_command2:
LFB9:
	pushq	%rbp
LCFI15:
	movq	%rsp, %rbp
LCFI16:
	subq	$16, %rsp
LCFI17:
	movl	%edi, -4(%rbp)
	movl	%esi, -8(%rbp)
	movq	%rdx, -16(%rbp)
	movl	-4(%rbp), %eax
	cltq
	leaq	0(,%rax,8), %rdx
	leaq	_d(%rip), %rax
	leaq	(%rdx,%rax), %rax
	movq	(%rax), %rax
	movq	-16(%rbp), %rsi
	movl	-8(%rbp), %edi
	call	*%rax
	leave
	ret

どうです?短いでしょ?きっと速くなってるはず。こういうのをディスパッチャパターンと名づけようかと。有能な上司は短い時間でディスパッチ先を探索して仕事をディスパッチしますが、無能な上司は「Aに頼んでダメだったらBに言ってみるか、いやBもタスク詰まってるからCかなぁ」とか考えたりします。間違った上司は常にAさんに仕事をディスパッチします。
アセンブリのシンタックスハイライトはやってくんない感じだ。みにくくてすいません。あれ、何のハナシだっけ。
あ、そうそう繰り返して試してみた。256*1024*1024回くらい。でも1~6で決め打ちなんだけど、値によって速度に差が出たり出なかったりで良く分からんですね。うーん。マシン語まで読めたらいいんだけどな。読める気がしないっていう

shuna:tmp kuenishi$ time ./a.out

real 0m2.503s
user 0m2.499s
sys 0m0.003s
shuna:tmp kuenishi$ fg
emacs sw.c

[1]+ Stopped emacs sw.c
shuna:tmp kuenishi$ gcc sw.c
shuna:tmp kuenishi$ time ./a.out

real 0m2.303s
user 0m2.298s
sys 0m0.003s

(追記)
もともとのコードがメチャクチャ速かったのは後者のバージョンがSEGVしてたからだったw(これはひどい)。つまり配列のインデックスを適当に入れてたからです。もっぺんセグフォしない版できちんとやったら、差は.2秒くらいでしたね。つまり、教訓として

  • switch文を使わないディスパッチャパターンによる高速化は長さにもよるけど、このケース最悪の場合では10%くらい
  • ディスパッチャパターンを使うときはバグを仕込みやすい(default: などと書けない上にジャンプ先のアドレスが不正になってしまい下手するとデバッガで追いかけにくい)
  • あー、あとインライン化されない。