無駄にてくてく
だいぶん涼しくなってきました．日が暮れてから歩いて帰るのにTシャツ＋短パンはちょっと寒かったので，いつものように着替えたりせずに今日は仕事着（ってただのポロシャツ＋ジーンズですが）のまま帰宅．そのせいで忘れ物．マンションの玄関で気づきましたよ，家の鍵忘れてきたことに…あぅ．
しゃーないので，大学まで一往復．10km近く無駄に歩くはめになりました．くやしいからスピード出したら結局汗だくやし．そういうわけで今日は無駄に 24km も歩いてしまいました．あ，いつも無駄に一日15kmくらい歩いてるし，無駄に エクストリーム登校32km - まんぼう日記 とかしてるんやから，今さらか．
共用体による擬似SIMDで高速化？
いくら無駄な日記やからって上の話だけではあんまりなので，昔話を少々．
かれこれ16,7年前，博士課程の院生やった頃，画像圧縮の研究をちょっとお手伝いしてたことがありました．そのからみで，カラー画像の画素値をいじる演算を高速化したくて，「unsigned int（32ビット）一つとunsigned char（8ビット）四つを重ねた共用体を作って，RGB各8bitの値を格納するようにしたら，unsigned int 一つの加減算でRGBの値をまとめて加減算できるやん」ってことを思いつきました．当時のMMXとかSSEとかのSIMDののりをソフトウェアでって感じですね．こんなの．
#include <stdio.h>
// 画素値を表す共用体
typedef union{
unsigned int val;
unsigned char rgba[4];
} PIXEL;
int main(void)
{
unsigned char xR, xG, xB, yR, yG, yB, zR, zG, zB;
PIXEL x, y, z;
// uint が4バイト = unsigned char 4つ分であることの確認
printf("sizeof(uint) = %lu\n", sizeof(unsigned int));
xR = x.rgba[0] = 0; // Rチャンネル
xG = x.rgba[1] = 64; // Gチャンネル
xB = x.rgba[2] = 128; // Bチャンネル
x.rgba[3] = 0; // （アルファチャンネル）
yR = y.rgba[0] = 1;
yG = y.rgba[1] = 1;
yB = y.rgba[2] = 1;
y.rgba[3] = 0;
// RGB を unsigned char 3つで表すなら unsigned char の加算3回
zR = xR + yR; zG = xG + yG; zB = xB + yB;
// PIXEL型の場合は int の加算1回
z.val = x.val + y.val;
printf("%u %u %u\n", zR, zG, zB);
printf("%u %u %u\n", z.rgba[0], z.rgba[1], z.rgba[2]);
return 0;
}
実際に実行してみたら，次のようにちゃんと動きます．オーバーフローのことどうすんねんってつっこみはちょっとおいといてください (^^)
sizeof(uint) = 4 1 65 129 1 65 129
それで，「8ビットの加減算3回よりも32ビットの加減算1回の方が少ないクロックサイクルで実行できるかもしれへんから，こののりで処理が高速化できるんちゃうか」と考えて，実行時間を計測する実験をしてみたら，超速かったんですね．
ところが，その話を聞いた某エンジニアの方はひとこと，「最後に計算結果を表示するようにして実行してみてください」と…．その通りにしたら普通に計算するより遅くなった…なんやぁ，そういうことかぁ．
コンパイラによる最適化のせいでした
とまあ，このタイトルだけでわかる人にはわかるわけですが．無駄な話を続けますと，超速かったのは，計算結果を出力する処理がないせいで，コンパイラが最適化をかける際に「この計算無駄や」って判断して，計算そのものをやらずに済ませるようなコードを吐いてたからでした．
例えばこんなプログラム：
#include <stdio.h>
#include <stdlib.h>
#define N (1<<20)
int sum(int x[], int n);
int main(void)
{
static int a[N], v, i;
srand48(0);
for(i = 0; i < N; i++){
a[i] = lrand48() % 32;
}
for(i = 0; i < 1000; i++){
v = sum(a, N);
#ifdef PRINT_VALUE
printf("%d %d\n", i, v);
#else
printf("%d\n", i);
#endif
}
return 0;
}
int sum(int x[], int n)
{
int i, s = 0;
for(i = 0; i < n; i++){
s += x[i];
}
return s;
}
実験してみると，こんな風になります．
$ cc --version Apple LLVM version 4.2 (clang-425.0.27) (based on LLVM 3.2svn) Target: x86_64-apple-darwin12.5.0 Thread model: posix $ cc hoge2.c; time ./a.out ★ デフォルトのコンパイルオプションで （出力は省略，以下同様） real 0m2.240s user 0m2.233s sys 0m0.007s $ cc -DPRINT_VALUE hoge2.c; time ./a.out ★ 同様，ただし v の値を出力する real 0m2.250s user 0m2.244s sys 0m0.005s $ cc -O3 hoge2.c; time ./a.out ★ 最適化オプション付き，v の出力なし real 0m0.008s user 0m0.005s sys 0m0.003s $cc -O3 -DPRINT_VALUE hoge2.c; time ./a.out ★ 同様，ただし v の出力あり real 0m0.441s user 0m0.437s sys 0m0.004s
最適化オプションなしのデフォルトのコンパイル条件やと，v の値を出力するしないに関わらず真面目に関数 sum を呼び出して合計の計算してるけど，最適化レベル 3 やと，v の値を出力しない場合は sum の計算そのものをさぼってそうやし，さらには配列 a の要素への値の代入すらさぼってそうですね．
ついでに，このコンパイラの場合の最適化レベル毎の違いも調べてみると（オプションなしと -O3 は上にあるので省略）…
$ cc -O0 hoge2.c; time ./a.out real 0m2.243s user 0m2.238s sys 0m0.004s $ cc -O1 hoge2.c; time ./a.out real 0m0.008s user 0m0.005s sys 0m0.002s $ cc -O2 hoge2.c; time ./a.out real 0m0.008s user 0m0.005s sys 0m0.002s
デフォルトで -O1 くらいの最適化すると思ってたら，そうやないんですね．どうやら-O0 がデフォルトぽい．
無駄無駄いうてたら何か自分の人生そのものが無駄な気が…この20年近くに最適化かけたら…いや，無駄でも楽しきゃええんですが…ああ，なんか怖い考えになってしもた (^^;
無駄話はこの辺で．
