プログラムのアルゴリズムや内容より 実行の高速化を重視しがちなのは どちらかというと阿呆なモデル屋である． Don Knuth も言っている； プログラミングにおいては ``premature optimization is the root of all evil'' と． 何が重要なのかを見失い， 拙劣な小細工にのめり込む愚を戒めている． ところで， わが国に 満ちあふるる こういった賢明ならざる人々を 見つけだしては それを冷笑する趣味を有する人物が ── 他ならぬ自分自身もまた その一部にすぎぬ， と気づいてしまう体験は 彼に何をもたらすのであろうか? 麻薬のごとき魅力と危険をあわせもつ禁断の遊戯 「高速化」 の世界をさまよい続けて 何週間も「帰ってこない」モデル屋， 以下はその記録の一部である．
「あまり速くないね」
そのプログラムの発注者たる教授がいった．
「これでは
単木ではなく樹木集団──
森林という状況は計算できそうにないね」
うう，
まぁ，
その今までの作業では
あまり高速化は重視しておりませんから，
ええ．
現段階では，
拡張性のある設計や
可読性に配慮したコーディングを．
いえいえ，
高速化だけを狙うのでしたら，
それは，
もう．
はい．
「じゃあ，
一本の樹木ではなく，
1000 本ぐらい
まとめて計算できるの?」
1000 本ですか……
ははは．
うーむ，
もっと高速化しろという要求がでちゃいましたよ
……
モデリングおよびモデル屋という現象に対して
実測をとおして理解をふかめつつある
某女性大学院生は，
それを聞くと
にっこりと微笑み
極悪非道なことを口走った．
「高速化?
ああ，
つまり
また手抜きをするんですね」
──
いやはや，
師も師なら，
弟子も弟子だ．
手抜きをして高速化をはかるぐらいなら，
何もしないほうがマシ．
結果は同じままに速度だけ向上させる職人芸こそが
……
よーし，
見せてやる．
今までは自制していた
「高速化」
という
古代魔法を復活させてやる．
どうなっても知らないぞ．
この危険なパンドラの箱の蓋の封印をやぶったのは，
こちらではなく
あなたたちなんだから．
ええ，
ええ，
そうですとも．
さぁて， 猟犬たちを野に放ち 狩りを始めよう．
高速化を実施するにあたって， まず重要なのは「攻撃の重心」を探り当てることにある． すなわち， プログラム実行中にもっとも時間を使っている箇所を発見し， それに集中的な改良を加えることで 一挙に全体の効率化を狙う．
「プログラムのどの部分が『足を引っ張って』いるのか?」
この疑問に解答を与えるのは
プロファイラーと呼ばれるツールだ．
フリーウェアのプロファイラー gprof を使って
索敵開始．
走り回る猟犬たち．
ふむ
そーか，
やはりこの樹木動態モデルの場合
「光量
(開空度)
の計算」
が全実行時間の 90% ちかくを占めている．
ならば，
ここが「重心」だ．
狩られるべき獲物たちはここに潜んでいる．
もっとも簡便でよく用いられる高速化技法は 「言語仕様を利用」 である． たとえば C++ の場合 inline というキイワードが 効率化のために用意されている． これを適切に用いれば格段に速くなる．
さてさて， 便利な inline 呪法を どこに埋め込んでやろうかなぁ…… 標的たる 「光量の計算」コードをながめつつ 頭のなかでそれを「実行」． オーヴァーヘッドが多量に生じそうなのは． ここだ． この 「世界の秩序を形成する」 ``<'' 演算子の多重定義を inline 化すれば…… 試験運転再開． よし． 実行時間が 50% ほど短縮された． つまり二倍も速くなった． 簡単簡単…… 簡単だけど言語仕様を利用して 高速化できる部分はすぐにつきてしまうなあ．
よーし 次は計算総量を減じる等価な論理構造というやつを検討してみよう． 書き方を少し工夫することで高速化できるそうなのは． さきに inline 化した演算子． 下のように 「無理やり短くまとめて」 しまったコーディングってのは……
inline
const bool operator<(const Grid& lhs, const Grid& rhs)
{
return (
(
lhs.gz < rhs.gz
) ||
(
lhs.gz == rhs.gz &&
lhs.gy < rhs.gy
) ||
(
lhs.gz == rhs.gz &&
lhs.gy == rhs.gy &&
lhs.gx <= rhs.gx
)
) ? true : false;
}
|
…… よく考えると， 実はまったく余分な計算ばかりやることになるので， むしろ一見 「ムダばっかり」 に見える……
inline
const bool operator<(const Grid& lhs, const Grid& rhs)
{
if (lhs.gz < rhs.gz)
return true;
else if (lhs.gz > rhs.gz)
return false;
else if (lhs.gy < rhs.gy)
return true;
else if (lhs.gy > rhs.gy)
return false;
else if (lhs.gx < rhs.gx)
return true;
else
return false;
}
|
……という書き方に直すと この部分の平均計算量は半分以下ですむ． このように変更しただけで 全体の実行速度が 20% ほど向上． いいねえ， いいねえ． なにしろ この演算子はプログラムの中の樹木がちょっと成長するたびに， 数百万回以上も呼び出されているからなあ．
「論理的な問題」は 考えさえすれば必ず解ける． したがって問題解決全体の中では もっとも容易なものである． 対照的に 「難しい問題」 とは論理的に考えても答えが出ないから， 試行錯誤によって解を探索しなければならないものなのである． しかも「正解」が存在するかどうか まったく保証されない．
うーん， だけど 論理的な高速化をハマると 次第にプログラムの読みやすさが損なわれがちかも． たとえば STL の 「重複をゆるす連想コンテナー」 ``multimap'' クラスを検索しようとすると (ここでは gridmap というインスタンスになっている)， 教科書的にわかりやすく書くならば……
voxel = gridmap.lower_bound(target);
goal = gridmap.upper_bound(target);
while (voxel != goal) {
//... (doing something) ...
voxel++;
}
|
…… ここで 「じゃんく」な高速化を追求しだすと， lower_bound と upper_bound の それぞれで時間のかかる二分木検索をやっていることが 気になってしょうがない． これを一回ですませたい． そこで「読みやすさ」が損なわれることには目をつぶり (つまりmultimap で実現している「並び方」を 読む人が知っていることを前提にして) ……
voxel = gridmap.lower_bound(target);
if (voxel->first == target) {
do {
//... (doing something) ...
} while ((++ voxel)->first == target);
}
|
……と書くと…… そう， 速くなってしまうのである． いやいや， こんなことばかりやっていてはいけない． たしかに 論理的には上の例も下も同値だ． しかし， コードがどんどんわけのわからないものになっていくかもしれない． 自分でも理解できないものになりかねない． そうでしょう． 知性あるプログラマーは こんな姑息な高速化を喜んだりはしない． そうとも…… ああ， だけど後学のために ちょっと試験運転して 結果を比較 …… え， 10% 以上も全実行時間が短縮される? いかんいかん． たかが 10% じゃないか． せいぜい 10 秒が 9 秒になるだけ． ははは， ばかばかしい． こんなことやっちゃいかん． 高速化なんてくだらないことだ． なにしろ， せいぜい 100 秒が 90 秒に …… うう …… 100 分が 90 分に …… よーし． ここだけにしよう． ここだけはコードを……
高速化という遊戯は徹夜頻度を向上させる． なぜならば， 「ハマってしまう」 からである． 高速化には 「考えれば解けてしまう」 問題が多々存在する． それでは， このような (たとえば 入学試験に出題できるような) 答えがあるとわかりきっている問題 は重要なのだろうか? 実務上はともかく， ほとんどの場合 それらは創造的な研究対象としては重要ではない． このあたりの見きわめが研究者としてのセンスなのである． しかしながら， 人はこういった種類の問題にかぎって ついつい没入してしまいがちである． 「どらごんくえすと」 や 「ふぁいなるふぁんたじー」 みたいに 最後に素晴らしいエンディングが待っていると保証されている (そもそも， 終りがあるということ自体が 幸福とも言える) 超大作ロールプレイングゲイムに何日も挑み続けるゲイマーと プログラム高速化を幾夜も追求するモデル屋の間には まったく変わるところはない． 「正解」が存在する安心感あればこそ 何日も寝る間も惜しんで 「労働」 に従事できているのである． そして そのような自分の姿勢だの 「労働」とそれに付随する消耗だのを 正当化するようになれば もはや末期的といってよいだろう．
…… ふう， 疲れたなぁ． 論理構造の等価な書き換えで実現する高速化策もつきてきたか． ならば次なる一手は アルゴリズムそのものの高速化か． 「光量 (開空度) の計算」 ── どのアルゴリズムをどう高速化してやろうか． やはり， めんどーな浮動小数点数の計算を減らすか．
その名称とはうらはらに， 計算機は必ずしも「計算」が得意なわけではない． 整数の足し算・引き算は精確で速い． しかし実数の近似値たる 「浮動小数点数」 の計算は 不精確になりがちであり， しかも かなり遅い． したがって， 実行時に何度も繰り返して呼び出されるモジュール内における 浮動小数点数の計算を少なくしてやれば速くなる． そのためには 計算を可能なかぎり整数の世界で実施すればよい． むろん 整数計算への置換によって 結果が不正確になることがあってはならない．
「光量の計算」 という計算部品 (モジュール) は さらにいくつかの小部品からできている． プロファイラーで調べると 「光子」 の三次元内の動きを計算するところで時間を取られている． そこで浮動小数点数の計算を繰り返しているからなぁ． さらに光子をちょっと動かすたびに 何かにぶつかっていないかどうか 「当たり判定」 もやってる． 当たり判定のために面倒な割り算が何度か実行される． 連続空間内の光子の位置を離散化するためだ．
こいつを高速化するためには いちいち連続空間と離散空間の間を行き来するのをやめてしまえばいい． そうだろう． 離散空間だけ── すなわち整数だけで扱える三次元空間だけで終始すればよい． そして， そのような世界でモノを「なめらかに動かす」手法がある． Bresenham のアルゴリズムだ．
Bresenham のアルゴリズムについては， 例えば Michael V. Capps 先生 (米海軍 Postgraduate School) の卓抜なる解説などを参照されたい．
まずは「光子」の動きをすべてBresenham 化してみよう ……(16 時間経過)…… よーし， 30 % 以上の実行時間短縮． やはり整数計算． ならば 葉っぱや幹の「グリッド化」の計算から 可能なかぎり浮動小数点数計算を排除して 整数計算化してみれば． 邪悪な浮動小数点の 演算という演算を見つけ出しては ことごとく． あたかも魔女狩りのごとく ……(64 時間経過)…… はぁはぁ， もう朝か． これで新アルゴリズム適用によるバグは全部取れたな． はい， 試運転， と． うん． また 25 % 速くなった．
しかし何日も苦労したわりにはあまり改善されていないような． そろそろ高速化の限界かな． 一週間前と比較して， 全体に 3-4 倍以上速くなったけど …… 面倒はどんどん増大している． そればかりやってて， 報告もしばらく書いていないし． いやいや， でももうちょっと頑張れば， きっともう少し速くなるに違いない． うん， きっとそうにちがいない． だから， もう， ちょっとだけ．
…… 暴走の原因は何であり その対策は何なのか． 不眠不休で修復しているつもりなんだけど， どこまで直して どこをまだ直していないのか． どうすれば速くなり どうすれば遅くなるのか． 何が正しくて 何が正しくないのか ……
いつの間に このプログラムは始動してすぐに core ファイルを吐いて止るようになってしまったのか．
いや， それはまだいい． core をまき散すような プログラムのバグ解析は容易だから． 吐瀉物を拾い集めて ディバッガーに放り込むだけでいい． backtrace． 原因の特定． 安直だ．
なのに， ディバッガーは 毎回毎回異なる箇所に問題があると指摘するようになっている． しかも それらは何度読み直しても問題ない． 何か変だ． 絶対に変だ． 変だ変だは工夫が変だ． ディバッガーも壊れているのか．
コードにもいつしか 見覚えのない行が増えている． 誰がこんな変更したんだ． 「じゃんく」な高速化を追求しすぎた結果なのか． 三日ほど前によく考えないで， 全ソースファイルに一括置換をかけたなあ． 何のためにやったことであったか． あれが悪かったのか． よく理解していない 言語特性を利用した 高速化コードを実験的に導入したこともあった． でも 試運転の結果が良くなかったから， すぐに復旧はしたはず． ああ， あのときも面倒だったので， 自動変換しちゃったなぁ．
もう一度， 試験運転． core げろげろ．
うん?
そういえばエラーメッセイジが よくある Segmentation fault に非ず．
Out of memory．
気づかなかった．
いつごろから
こうなっていたんだ．
なぜ
この段階で
メモリーを使いきってしまう?
まだメインループにも到達していないうちに
止っているんだぞ
……
原因が，
わかった．
常識をくつがえすエラー．
ディバッガーを普通に使ってもなかなか見つからんはずだ．
そもそも，
「この世界」
はこういうふうに階層下されている
森林 ┬ 樹木 ┬ パイプ ┬ 葉群 (←森林への連絡経路を持つ)
├ 樹木 ├ パイプ ├ パイプレット
├ 樹木 ├ パイプ ├ パイプレット
├ 樹木 ├ パイプ ├ パイプレット
│ 樹木 │ パイプ │ パイプレット
└ 樹木 └ パイプ └ パイプレット
|
大なるものの中に小なるものが宿る，
まぁごく普通のモデリングだ．
末端の葉群のひとつひとつは
一番上の階層たる森林に直結している
「連絡経路」というのを持つ．
葉っぱは
たとえば
光合成したいときには
「あのう，今こういう座標まで来てるんですけど，
ちょっとこのあたりの光量を教えてもらえませんか?」
という要請を
この経路を通じて森林に送りつけている．
しかるに
この呪われプログラムは，
いつのまにか，
いつのまにか，
こんなふうに書き換えられていた．
いったい誰がやったんだ．
森林 ┬ 樹木 ┬ パイプ ┬ 葉群 ─── 森林 ┬ 樹木 ┬ パイプ ┬ 葉群 ──……
├ 樹木 ├ パイプ ├ パイプレット ├ 樹木 ├ パイプ ├ パイプレット
├ 樹木 ├ パイプ ├ パイプレット │ 樹木 │ パイプ │ パイプレット
├ 樹木 ├ パイプ ├ パイプレット └ 樹木 └ パイプ └ パイプレット
│ 樹木 │ パイプ │ パイプレット
└ 樹木 └ パイプ └ パイプレット
|
ひとつひとつの葉群において
「森林への連絡経路を確保する」
という部分がいつの間にか
「新しい森林を作る」
というコードに置き換わっている．
わずか一文字の違いで．
葉群の数だけ
森林
ができてしまう．
いや
それだけではない．
…… いやぁ， これ， ちょっと見てくださいよ． ほらほら， この部分にちょっと手を加えるだけで さらにさらに 二倍もの高速化を実現しちゃいましたよ． ええ， ええ， それはもう． 結果は改造前と全く同じですとも． いやあ， われながらすごい． え? いやいや， まだまだ改良の余地はあるはずなんです． というのは， 理論上は O(log N) に収まる計算時間が まだまだO(N) に近くてですねえ． そのあたりの原因と対策についてちょっとしたアイデアを 昨日よる遅くに， というか今日の明け方に ……
「愚か者は経験に学び， 余は歴史に学ぶ」 ── フリードリヒ大王とて 時には愚かになりがちな自身を省みているからこそ この言葉を発したような気がしてならない． ましてや自らの経験にすら学べない凡人が何をか言わんや．