max, min 関数の最適化と x86 の cmov 命令

max 関数や min 関数は C 言語だと自分で書かないといけないので

int max(int a, int b) {
	return a>b?a:b;
}

などと書いたりするのだが，比較を行っているので分岐が発生するから遅くなると思い，これって本当に速いのかと思って調べてみた．

実験

以下の５つのコードを用意した．これらをそれぞれ max 関数の実装とした．検証用のコードは最後に載せる．PHP でランダムな２数値を作ったデータを 1,000,000 組用意し，入力データとして配列に読み込んだあと，ループで max 関数を実行した．このループの前後で gettimeofday で時間を測り，所要時間を算出した．それぞれの実装に対し所要時間の５回の平均をとって比較した．コードは gcc version 4.2.1 (Apple Inc. build 5664) でオプション無しでコンパイルした．

(1) a>b?a:b;
(2) int c=a>b; return c*a+!c*b;
(3) if(a>b){return a;}else{return b;}
(4) (-(a>b))&a|(~(-(a>b)))&b;
(5) int c=a>b; (-c)&a|(~(-c))&b;

(1) は一般的な条件演算子を用いたコード．(2) は掛け算で大きい値を返すコード．(3) は if 文を使ったコード．(4) は @tokoroten 氏から「掛け算が遅いんじゃないのか」と頂いたコード．(5) はそれをある理由から改良したコード．

結果

２カラム目が所要時間で，これでソートしてある．

(1) 0.007195 a>b?a:b;
(2) 0.009754 int c=a>b; return c*a+!c*b;
(5) 0.009939 int c=a>b; (-c)&a|(~(-c))&b;
(4) 0.013394 (-(a>b))&a|(~(-(a>b)))&b;
(3) 0.015536 if(a>b){return a;}else{return b;}

(1) の条件演算子が圧倒的に速かった．(3) if 文は条件演算子の倍遅い．(2) の掛け算はそこそこ速いが，条件演算子に勝てず．(4) は if 文並に遅かった．

解析

(4) から説明すると，アセンブラを見るとなぜか cmp & jmp が入っていた．どうも a>b の計算結果を置く場所がないためにそういうコードになったらしい．なので変数を一つ用意してあげればジャンプが消えた．それが (5) である．(5) はそれなりの速度を出しているが，掛け算よりいつも若干遅かった．コードが長い分の命令数，クロック数の差だろう．

(3) はもちろん cmp & jmp が入っていたから圧倒的に遅かった．

なぜ (1) が異様に速いのかは以下のアセンブリを見てもらえばわかる．

_max:
	pushl	%ebp
	movl	%esp, %ebp
	subl	$8, %esp
	movl	8(%ebp), %eax
	cmpl	%eax, 12(%ebp)
	cmovge	12(%ebp), %eax
	leave
	ret

そうだ，cmov 命令だ．

cmov 命令

cmov 命令はある時期以降の x86 プロセッサに（たぶん）固有の命令で，条件に基づいて mov を行うものだ．cmov の後ろがその条件になっている．この例では cmovge なので greater/equal なフラグが立っていれば転送が行われる．つまり jmp する必要がないので高速なのだ．

じゃあ cmov 命令にしてしまえばいいのかというと，そういうわけでも無いらしい．

2008-08-19
cmov vs cmp+jxx across x86 CPU implementations

はてなの記事ではあこがれの cmov にしたら逆に遅くなったと言っている．

RedHat の ML では簡単なコードで cmov と cmp & jmp の比較をしている．Core2 Duo E8400 では倍近く速くなっているが，一部の CPU では逆に若干おそくなることもあるらしい．

手元の AMD なマシンで試してみた

Quad-Core AMD Opteron(tm) Processor 8354
$ time ./cmov2 
real	0m3.539s
user	0m3.540s
sys	0m0.000s
$ time ./cmp-jmp2 
real	0m4.930s
user	0m4.928s
sys	0m0.000s

まぁ，cmov の方が速かった．多分今の CPU ならほとんど cmov の方が速いだろう．

ただ，max, min のように単純な関数なら cmov が使いやすいのだが，その他の場面で cmov を使おうとすると，そう仕向けるためのコストが無視できなくなるように思う．使うときは注意したほうがいいのかもしれない．

有識者の意見求む．

2010/11/24 11:42 「最適化リファレンスより」を追記
2010/11/24 12:11 「TODO」を追記

TODO

それぞれのコードが最適化を有効にした状態ではどうなるかも調べないといけない．実験に時間を割く必要があるので後ほど検証．

最適化リファレンスより

インテル64アーキテクチャーおよびIA-32アーキテクチャー最適化リファレンス・マニュアルの「3.4.1 分岐予測の最適化」の「3.4.1.1 分岐の排除」で予測不可能な分岐の排除の手法として CMOV について触れられている．

条件分岐を CMOV または SETCC に変換すると、データ依存の制御フロー依存関係がトレードオフされ、アウトオブオーダー・エンジンの機能が制限される。チューニングの際は、すべてのインテル®64 プロセッサーとIA-32 プロセッサーが、通常は非常に高い分岐予測精度を持っていることを考慮する必要がある。一貫した予測ミスは一般的にまれである。これらの命令は、計算時間の増加分が、予想される分岐の予測ミスのペナルティーより小さい場合にのみ使用するべきである。

超重要な箇所だけ引用した．

参考資料

http://iwaohanma.web.fc2.com/MASM2/CMOVcc.html

検証用コード

#include <stdlib.h>
#include <stdio.h>
#include <sys/time.h>

#define N 1000000

int max(int a, int b)
{
	// ここにそれぞれのコード
}

double cur_time()
{
	struct timeval tp[1];
	gettimeofday(tp, NULL);
	return tp->tv_sec + tp->tv_usec * 1.0E-6;
}

int main(int argc, char *argv[])
{
	int a[N],b[N];
	int i;
	for(i=0;i<N;i++)
		scanf("%d%d",&a[i],&b[i]);
	double t0 = cur_time();
	for(i=0;i<N;i++)
		max(a[i],b[i]);
	double t1 = cur_time();
	printf("%f\n",t1-t0);
	return 0;
}

yuyarinの日記