yuyarinの日記 このページをアンテナに追加 RSSフィード

プログラミングの話題は「yuyarinのtopcoder記」で!

僕を追いかけたい方は Twitter へ!

2010年11月24日

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

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

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

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

実験

以下の5つのコードを用意した.これらをそれぞれ max 関数の実装とした.検証用のコードは最後に載せる.PHP でランダムな2数値を作ったデータを 1,000,000 組用意し,入力データとして配列に読み込んだあと,ループで max 関数を実行した.このループの前後で gettimeofday で時間を測り,所要時間を算出した.それぞれの実装に対し所要時間の5回の平均をとって比較した.コードは 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) はそれをある理由から改良したコード.

結果

2カラム目が所要時間で,これでソートしてある.

(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 命令にしてしまえばいいのかというと,そういうわけでも無いらしい.

あこがれの cmov を使ってみた - 当面C#と.NETな記録

cmov vs cmp+jxx across x86 CPU implementations

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

RedHatML では簡単なコードで 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 プロセッサーが、通常は非常に高い分岐予測精度を持っていることを考慮する必要がある。一貫した予測ミスは一般的にまれである。 これらの命令は、計算時間の増加分が、予想される分岐の予測ミスのペナルティーより小さい場合にのみ使用するべきである。

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

参考資料

404 Error - FC2ホームページ

検証用コード

#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;
}

herumiherumi 2010/11/25 16:49 オプション無しでコンパイルしているため,(1)と(3)の所要時間が異なっているのでしょう.
少なくとも(1)と(3)が同一になる程度の最適化オプションは必須だと思います.

1,000,000個のデータの比較で0.007195秒かかっているとしたら,一つの比較処理あたり約7.2nsec(10^9nsec=1sec)かかっていることになり,Opteronの2GHz程度のCPUで換算すると
14cycleかかっていることになります.cmovは2cycle程度で処理できるので,それ以外の要因(メモリやもしかしたら関数呼び出し?)が大半を占めていることになります.

現時点では「cmovとjmpのどちらが速いか」を考察するにはノイズの多すぎる実験であり,これだけでは意義ある結論が出せないと思われます.

hayamizhayamiz 2010/11/27 18:23 とりあえず手動ループアンローリングしておいたほうがいいんじゃないかね。

yuyarinyuyarin 2010/11/27 23:14 >herumiさん
外部要因はたしかにあると思います.
今回はメモリ操作や関数呼び出しまで含めたmax/min関数の実装の違いであって,cmov,jmpの命令レベルの比較ではないのでこれでよいと考えています.また,cmov,jmpの命令レベルの速度は記事中でも検証しています.

>hayamiz
ループの終了判断の分岐予測とかは多分影響しないと思うけど,まぁしておいたほうが無難か.ありがとう.

hayamizhayamiz 2010/12/04 16:46 > ループの終了判断の分岐予測とかは多分影響しないと思うけど
どこまで精緻な測定をしたいかによるけど、サイクル単位の精度がほしかったらループの終了判断とかjmp命令は無視できない誤差になる。

ef3ef3 2011/12/12 12:02 CMOVに相当する命令は、モダンなプロセッサの多くにあるようです。

特にベクトルプロセッサやSIMDでは、一番内側のループに条件処理がある行列演算のベクトル化に不可欠です。
またARMプロセッサは、全命令でコンディションコードにる実行/否の制御ができます(最初の実装から)。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証