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

まんぼう日記

takataka's diary

無駄なことを…共用体による擬似SIMDとコンパイラの最適化

無駄にてくてく

だいぶん涼しくなってきました.日が暮れてから歩いて帰るのに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年近くに最適化かけたら…いや,無駄でも楽しきゃええんですが…ああ,なんか怖い考えになってしもた (^^;  

無駄話はこの辺で.