2004-05-10

難しいお話はなしよ，っと

その他

2002年月刊アスキー６月号竹内郁夫、山形浩生対談「ハッカーたちの言葉遊び」 P.188

物理シュミレーションがからむグラフィックスのような世界では、今でも魔法使いがいっぱいいますよ。IPAの未踏プロジェクトってあるじゃないですか、あれに関わった人でね、天才肌のすごいハッカーがいる。変人でね、歌舞伎町に住んでいたんですけど。彼の部屋には病人介護ベッドがあるんですよ。食べる時に半分身体をガーッと起こしてくれるベッド。目が覚めてガーッと起きるとそこに画面とキーボードがあるわけですよ（笑）。夢中でプログラミングをやって、眠くなったら、またガーッとベッドにして寝るという生活。彼は真性ハッカーだと思うな。ポスドクで原子力研究所にいたような人で、とにかく腕が立つ。仮想物理シミュレーションって魔法を使わないとできないんですよ。まともに実世界の現象なんて計算できませんから。彼の作るデモって、何でこんなコトができるのってみんなが驚くものばかりです。たとえば髪の毛を2000本の曲線にモデル化して、首をマウスで揺らすと、ふわーっふわーっと2000本の髪がなびくようなデモがあるんですけど、これがね、ホントにリアルに動く。リアルなんだけど実は１本の髪に３つほどしかシミュレーションされている点がないんです。物理シミュレーションとしてはすごい大胆な抽象化なんだけど見た目はリアルそのもの。SIGRAPHに論文を出すような専門家の目から見たらね、それは目新しくはないそうなんですよ。で、その手のCGプログラムをね、Webでアルゴリズムを調べて「ふむふむそうか」といって、数時間でさかさかっと書きあげる、これはスーパーハッカーだと思います。彼みたいな人が未踏プロジェクトに結構集まりましたね。

（竹内氏談）

氏のやったことに対して，私は賛否を論じられるほど物事を知っているわけではありませんし，ましてや，今はまだ賛否を決することが出来る時期ではないでしょう．ただ，駆け出し（駆け出してさえもいないかもｗ）Engineerとしての私が，氏のEngineerとしての面だけを純粋に評価することが許されるとするなら，言えることはたった一つ．
「氏は最大級の尊敬に値するし，これまでも，そしてこれからも自分が目標とする人の一人．」
それだけですね．

2004-05-10

Expression Template（式テンプレート）の効果

C++ Template MetaProgramming

id:Cryolite:20040507#p1より続きます．
というわけで，今回はETの効果について検証します．今回検証に用いるのは以下の高次元のvectorの和の計算についての速度です．
t = u + v + w;
これを，ETによって和を実装したvectorクラスet_vector.hppを用いて実装してみます．
一方で，比較対象としてETを用いない単純なvectorクラスsimple_vector.hpp（id:Cryolite:20040506において書いたもの）を用いた実装と比較します．
単純なvectorクラスは，色々比較するために以下の3つの使い方で実装してみます．
一つ目は単純にoperator+を使ったもの(Simple)

for(size_t i = 0; i < n; ++i){
  t = u + v + w;
}

二つ目は代入演算子を使ったもの(Assignment)

t = u;
t += v;
t += w;

三つ目は各要素に対して陽にloopを使うもの(Explicit)

for(size_t i = 0; i < n; ++i){
  t[i] = u[i] + v[i] + w[i];
}

実験に用いたソースコードはet_vector.hpp, simple_vector.hpp, et_test.cppです．簡単なことにしか使って無いですが，一応boostを必要としています．
明らかにしておくべき実験環境は以下です．

CPU: Athlon 1.4GHz 2次キャッシュサイズが分からないのですが恐らく256KBと思われます
Memory: 3.0GB　PC100・・・多分（をいをい
OS: RedHat Linux 9
Compiler: Intel C++ Compiler 7.1
Compiler switch: -O3 -i_dynamic

これで，vectorの次元数を変えながら，同じ計算を繰り返して速度を見ます．
以下が結果です．単位は秒．

次元数*繰り返し回数	Simple	Assignment	Explicit	ET
10*10000000	8.47	1.54	0.73	0.79
100*1000000	2.57	1.09	0.74	0.61
1000*100000	1.86	1.04	0.73	0.58
10000*10000	13.12	3.68	2.35	2.42
100000*1000	15.70	7.85	4.15	4.23
1000000*100	16.01	8.05	4.68	4.67
10000000*10	15.42	7.82	4.17	4.23

結果を検証します．
まず，分かるのはETが陽にloopを書いたコードと同等の性能を示していることです．
一方，Simpleは一時オブジェクトを生成し（そのためにヒープの確保も要求し），要素のコピーを行うので遅いということが結果に明らかに出ています．
自分がちょっと想定外だったのがAssignmentがExplicitやETに若干劣っている点で，これは代入先のtの要素を時間間隔を置いて複数回参照するからでしょう．見落としていました．
後,もう一つ分かるのは全て計算量としては同じ実験のはずなのに，vectorの次元が10000次元を超えるぐらいから全体的にがたんと遅くなっている点で，これは演算に使うvector全部がキャッシュに乗り切らなくなっているためでしょう．
ということで，ETは直感的なコードを維持したまま効率的な実装を提供できるということができます.
で，次にGCCでコンパイルしたコードでの実験結果を見ます．実験条件はコンパイラ以外同じです．

Compiler: GCC 3.2.2
Compiler switch: -O3

結果です．

次元数*繰り返し回数	Simple	Assignment	Explicit	ET
10*10000000	9.51	1.98	0.93	1.77
100*1000000	3.28	1.58	0.88	1.60
1000*100000	2.71	1.54	0.80	1.60
10000*10000	13.36	3.76	2.68	2.78
100000*1000	15.55	7.81	4.13	4.23
1000000*100	15.81	7.97	4.67	4.68
10000000*10	15.40	7.77	4.14	4.23

全体的にICCのと比較すれば，さすがにICCは良いコンパイラだなと思わせますが，これを載せた意図はそこではないです．
基本的にはICCと同じ傾向の結果ですが，一つだけ次元が小さいときのETの結果が思わしくありません．
ETは，説明したように，各演算で小さな式オブジェクトを生成します．それらは最適化されれば消去してしまうことができるオブジェクトですが，このような積極的な最適化を行ってくれるC++コンパイラはまだまだ少ないです．そして，そのような最適化が行われないコンパイラでは式オブジェクト生成のコストがかかってしまう場合があります．このGCCの結果も恐らくその影響かと思われます．
なお，次元が大きい領域ではそのようなoverheadがメモリアクセスのoverheadに償却されて，Explicitと同等の性能をみせています．
いずれにせよ，Simpleに比べれば，ETは非常に良い性能を発揮することが分かります．
正直，こんな簡単な実装でここまでの結果が出るとは思っていませんでした．
というわけで，次回はETの負の面について少々議論します．
id:Cryolite:20040513#p1へ続きます．

2004-05-10

おまけ

C++ Numerical Calculation

以下は上の欺瞞に満ちた実験に対する言い訳ですｗ．数値計算の泥臭い話で，ETの本筋の話から外れるのであんまし読まないでくださいｗ．
まず最初に，Explicitの書き方は毎回の演算ごとにindexingするあんまりよろしくない書き方で本来は以下の書き方が適切と思われます．

double *pt, *pu, *pv, *pw, *e;
pt = &t[0]; pu = &u[0]; pv = &v[0]; pw = &w[0]; e = pt + n;
while(pt != e){
  *pt++ = *pu++ + *pv++ + *pw++;
}

が，これに対応するETを実装しようとすると式オブジェクトにiteratorを定義しないといけなかったりして時間無いし，面倒くさいし，分かりにくいしでやりませんでした．
次にもう一つ，VC++7.1で実験した結果を載せておきます．

CPU: Athlon XP3200+ 2次キャッシュ 512KB
Memory: 512MB　PC3200
OS: Windows XP Professional Edition
Compiler: VC++ 7.1
Compiler switch: /Ox /G7 /EHs /I(boostのインクルードパス)

結果です．

次元数*繰り返し回数	Simple	Assignment	Explicit	ET
10*10000000	11.68	0.87	0.14	0.96
100*1000000	3.20	0.60	0.14	0.85
1000*100000	2.71	0.57	0.14	0.85
10000*10000	3.89	0.96	0.48	0.87
100000*1000	14.28	5.15	3.01	3.11
1000000*100	14.31	5.14	2.96	3.01
10000000*10	（メモリに乗り切らないのでやめました）

どうもExplicitのコードにunrollingをかけやがったみたいです．正直，VC++舐めてました・・・．この結果さえ見なければ，「ETはやっぱりすごい！えへへ」で済んでいたのに・・・orz．数値計算ってこういうさじ加減一つで大きく性能が変わるのが嫌いなんですよね・・・．