特集 1 加殤ムの高速化・最適化 ンク , 最終的に実行プログラムのイメージ を生成するというプロセスをたどります 開発の段階でデバッグの速度と容易性を重 要視し , 稼働用のコードをリリースする段 階で実行時の速度とサイズが最重要課題と なります。最小かっ最高速のコードが必要 な場合はアセンプリ言語を用いて書けばよ いのですが , 最初からすべてをアセンプリ 言語で記述するには , その作業コストとハ ードルがあまりにも高すぎます。なぜなら アセンプリ言語で書かれたプログラムは高 級言語で書かれたプログラムよりも複雑で ひと目ではなかなか理解しづらく , デバッ グ作業も困難になるからです。自分で書い たコードですら「えーっと , これは何をす る部分だっけ」ということにもなりかねま せん。プロジェクトが大きくなるにつれて その傾向も強くなります。 付録 CD-ROM<TOKUIYSrc}Sample> ディ レクトリに収録されている SampIe. cpp と Sa mple. asm を見比べてみてください。アセン プリ言語がいまひとつわからない読者もい るかもしれませんが , これらはまったく同 じ動作をするプログラムです。命令の数な どを一般的に見比べた場合 , どちらが理解 しやすいでしようか。同じ動きをするプロ グラムであるにもかかわらず , C 言語で書 かれたほうが ( 一部のアセンプリ言語信奉 者を除き ) 圧倒的にわかりやすいと思いま す。もしこのプログラムの結果に 1.47 倍し た数値を返すように改造しようとした場合 , 前者は最後の行に " * 1.47 " と記述すればよ いものを , 後者は複数の行にわたるアセン プリ言語を追加しなければならなくなりま す。この差は火を見るよりも明らかで , 作 業効率へダイレクトに響きます。 また , ショボショボのアルゴリズムをい くらアセンプリ言語で記述したところで , 最近の非常に優れたコンパイラによる強力 な最適化処理には遠く及びません。「アセ ンプリ言語で書いたコードよりも C 言語で 普通に書いたほうが高速だった」という最 悪の結果を招くことにもなります。 したがって , 何でもかんでもアセンプリ で圭けばよいというものではありませ 「コロロ E ヨ ん。最初のうちはなるべく高級言語で十分 最適化し , よりよいアルゴリズムを導いて それを実装してからアセンプリ言語で最適 化する , という手順を踏むのがもっとも作 業効率が高く , プログラム高速化への近道 だといえるでしよう。 高速化は適切な場所で行う プログラムはただ高速化すればよいか ? というと , 必ずしもそうとは限りません。 高速化が必要な場所と必要でない場所をよ く選んで高速化するべきです。 高速化が必要ない部分としては , たとえ ばキーストロークを判定するときなどです。 毎秒 60 フレームで画面表示されるゲームを 作ったとします。このゲームのキーチェッ クプログラムの部分を高速化して 1 / 600 秒 に 1 回チェックできるようになったとして も , ゲームとして画面に表示されるのは 1 / 6 0 秒に 1 回なので , この高速化は何の意味も ないことになります。 このような場合は速度を最適化するより も , プログラムサイズを優先した最適化を 行うべきで , より少ないコードで同じ処理 をすることが大切になります。逆に 3D の座 標計算や行列の計算など , プログラムの目 的に直接つながる部分で , 通常処理にも比 較的時間がかかり , かっ何度も使用される コードについては実行速度を最優先して最 適化するべきなのです。 C 言語での最適化 本特集のような内容を文章だけで説明さ れてもなかなか理解できるものではないし , こからはプロ おもしろくもありません。 グラム例を用いて解説していきます。 C 言語での最適化にはたくさんの方法が ありますが , もっとも一般的なものから順 に説明していきます。なお , 補足的な Tips のテキストファイルを付録 CD-ROM<TOKU IYfips> ディレクトリに収録してあります。 本文中に第 ps の存在を記しておくので , あ わせてご覧ください。 メモリアクセスを削減する List1 は , ループの終了条件をチェックす る際 , ケース 1 ではカウンタを 1 引いてその 結果をメモリと比べるのに対し , ケース 2 ではメモリにアクセスせずカウンタ ( たい ていの場合レジスタ ) から 1 を引いてそれが 0 かどうかをチェックするだけです。プログ ラムサイズでもケース 2 のほうが多少小さ くなるでしよう。ただ , この手の最適化は 今どきのコンパイラであれば ( ループ内に 複雑な計算を含まない限り ) , たいてい自 動的に行ってくれるでしよう。 理由 : 一般的にメモリアクセスよりレジ スタアクセスのほうが高速であるため 使用される場所 : メモリアクセスしそう な場所 ( ループ処理中の比較・条件分岐 など ) 計算方法の工夫 式の中で共通する部分を見つけ , 計算数 がなるべく少なくなるようにプログラムを 工夫します。 List2 のケース 1 はケース 2 と同 じ結果をもたらしますが , ケース 2 のほう fo ヨセ土 = 土く土十十 ) fo て ( int 土 = 新 ) void reduceAccess( int れ ) ・ケース 2 void reduceAccess( セ n ) ・ケース 1 1 IS メモリアクセスを削減する 旧 2 計算方法の工夫① ・ケース 1 int deformation( 加セ x, int Y, 土れセ響 , a ) て・に【 n X * ( 物十 a) 十 y * ( 響十 a) 十 z ま ( 響十 a); ・ケース 2 int fo て新は旦 on ( int も int int も蚯にに a ) て・セ u て n (x 十 y 十 2 ) ( 響十 a 特集 1 プログラムの高速化・最適化 21

が圧倒的に少ない計算量で解を導いていま す。さらにそのぶんプログラムサイズも小 さくなっているはずです。 List3 に示す例のように , 規則性のある 計算の場合にも演算回数を減らしてプログ ラムを高速化することができます。 理由 : ムダな計算をしないように改善す れば高速化が見込めるため 使用される場所 : 計算される場所すべて ( とくに複雑な計算が行われる場所 ) ポイント : アルゴリズムに気をつける ループをまとめる List4 はかなり強引な例ですが , ケース 1 はケース 2 のようにまとめることができま す。これはループの終了条件をチェックす る際に分岐が起こるため , チェック回数 ( 分岐回数 ) の少ないケース 2 のほうが速く 計算方法の工夫② 十 5*x*x*x*x 十 4*x*x*x 十 3*x*x 十 2 1 x*5 ( x * 4 十 ( x * 3 十 ( x * 2 十 て・ tu てれ ( 1 十 int defo て新 a 0n2 ( int x ・ケース 2 てれ ( int d ・ fo ェ ma 0n2 ( に x ・ケース 1 3 ループをまとめる lSt fo て ( int 土 = 土 < 丐土十十 = ⅵ幻 + 新 fo て ( int 土第 ・ケース 1 4 void mma 工臧ル 00P ( int *x, 加セ *y, int n ) 土十十 なります。また変数 i が配列のインデックス として用いられているため , データを参照 する回数も減らすことができます。ただし , こういったケースでは計算順序を間違えな いように注意しなければなりません。 理由 : 条件分岐やデータの参照回数を減 らすため 使用される場所 : 同じ条件でループする ような場所 命令の優先順位 ( その 1 ) 浮動小数点の計算では , 除算ではなくな るべく乗算を使います。世の中にあるほと んどのプロセッサでは除算は乗算に比べて きわめて低速に動作します。つまり List5 は ケース 2 のほうが高速ということになりま す。 List6 のような場合は , 乗算を加算で 置き換えたケース 2 のほうが速くなります。 加算は乗算よりも高速に動作します。 実行にかかる時間は「加算く乗算く除算」の 順であると覚えておいてください [ 1 い 01 ] 。 理由 : プロセッサの作業効率を上げるた め 使用される場所 : ループ中繰り返し実行 される計算が含まれる場所 命令の優先順位 ( 乗算・除算 ) void Array1( double *x, double d ) ・ケース 2 x[il / = の fO て ( int 土 = く 1000 十十 void Array1( do 地 *x, double d ) ・ケース 1 5 fo て ( 土れし i = 土《 1000 土十十 float rd = 1. Of / 命令の優先順位 ( 加算・乗算 ) List xti * 引 = fO て ( int = 1 く void Array2( int , int 日 , int れ ) ・ケース 1 6 命令の優先順位 ( その 2 ) 先ほどの優先順位の補足的な形になって しまいますが , データのシフトをうまく利 用して計算方法を工夫することもできます。 説明するまでもありませんが , データはバ イナリレベルで左にシフトされると値は 2 倍 , 4 倍 , 8 倍・・・・・・と増えていき , 右にシフ トすると値は 1 / 2 , 1 / 4 , ・・・となります。 ・ケース 2 void gumma 2 ・石 00P ( int *x, int *y, fO て ( int = 土く土十十 ) = x は = x は = ⅵ幻 * 新 int n VOid て ay2 ( え n セ社 , int 町 int n ) ・ケース 2 fO て ( 土れセ 1 = 土十十 ) = く土十十 , ゴ十 = 8 この性質をうまく使えば , List 7 のような乗 算も , シフトと足し算の命令に置き換える ことができます。 理由 : プロセッサの作業効率を考えるた め 使用される場所 : 簡単な計算が実行され るところ 条件分岐の順序 条件分岐 ( if 文 ) を使うときは発生しそう な条件から順番に並べます。 List8 のように 発生する確率が高いほうからチェックする ようにしておけば , 余分な条件分岐をしな くて済みます。また同じ分岐先であるのな ら , 論理演算を使ってそれぞれのフラグを ひとまとめにしてから分岐するというテク ニックもあります 理由 : 条件分岐をなるべく減らすため 使用される場所 : 条件が重なるような分 岐ポイント 条件分岐を減らす 最近の長いパイプラインを備えたプロセ ッサでは , 条件分岐がポトルネックになり ます。なぜかというと , プロセッサは実行 されるコードが命令プリフェッチによって 実行前にあらかじめパイプラインに読み込 まれてから処理される仕組みだからです このときプロセッサは条件分岐を予測する のですが , 読み込まれた命令はプロセッサ が命令ストリームを正しく予測できるとき にのみ機能することになります。実行時 , どこに分岐するかという予測をプロセッサ 0 0 ラインはいったんフラッシュされ , 正しい が誤った場合 , プリフェッチされたパイプ 22 c MAGAZINE 2001 10

特集工 加殤ムの高速化・最適化 てください。せつかく用意されている便利 で高速な計算手段を利用しない手はありま せん。 また筆者がユーザからいただく反応や , 世の中にあふれるソフトの様子を見ている と「 MN Ⅸ対応ソフト」「 SSE 向けにカスタマ イズされたソフト」など , そういった表示 自体が一種のステータスにもなっているよ うです。もちろん実際に対応していないと 何の意味もないので , もしこれらのことに 触れたことのない人 , 触れてみたいと思っ ている方や , 少しでも関心のあるプログラ マ諸氏は , これを機にチャレンジして , あ なたのプログラムをさらにすばらしいもの にしてみてはいかがでしようか。 アセンプリ言語 , 拡張命令など , なかな かとつつきにくい分野かもしれませんが しかし実際に始めてみるとそれほど難しい ものではなく , 必ず興味がわく ( おもしろ くなってくる ) 分野でもあると思います。 まとめ 初級編で主に C 言語レベルでの高速化手 法を , 中級編からアセンプリ言語にターゲ ットを絞って解説してきました。しかし何 度も何度も , しつこく口うるさく言います が , プログラムは単にアセンプリ言語で記 述するよりも , アルゴリズムを工夫するこ とがもっとも大切なポイントとなります。 ただやみくもにプログラムをアセンプリ言 語化するのではなく , アセンプリ言語にす る前にまずはアルゴリズムを研究すること から始めることがプログラム高速化の基礎 になるということだけは覚えておいてくだ さい。そのうえでアセンプリ言語化するこ とを考え , そして MMX テクノロジや SSE , SSE2 などの持つ特殊な命令を使うことで得 られる利益を考えたプログラムの組み方を すると , すばらしく高速なプログラムを書 くことができるでしよう ( もちろん最初か らそれらを考慮した設計ができればベスト です ! ) 。 実は , M 、Ⅸテクノロジと SSE2 のサンプ ルとして紹介した画像の合成プログラム は , アルゴリズムをほんの少し工夫するこ とでプログラムをさらに高速化することが できます。 C 言語レベルでも ( 実行環境にも よってしまいますが ) おそらくオリジナル の 10 ~ 20 % くらいは高速化が期待できるの ではないでしようか ヒントは次の式です。 / 256 ページ数の都合もあり詳しくは紹介しま せんが , とくに難しいことではないので , このあたりはみなさんへの課題ということ にしておきましよう。答えは付録 CD-ROM に収録してあるので , 興味を持たれた方は 探してみてください。 最後に かなり基本的なところから最新の SSE2 命 令を使ったサンカレ紹介まで , プログラムの 高速化方法について幅広く解説しました。筆 者は本業で「プログラマ」という肩書きを持 っている人間ですが , いたらない点が数多 くあり完璧ではありません。それにもかか わらず「プログラムの高速化」などと偉そう なタイトルが付いた記事を書かせてもらい ました。ですから今回の特集に不満を持た れる方もきっといらっしやることでしよう。 しかし , これをきっかけにプログラムの 高速化に 1 人でも多く興味を持たれる方が 出てきてくれれば筆者としては非常に喜ば しく思います。 今回紹介したものよりももっと ( 全然 ? ) 優れたアルゴリズムがあるぞ ! という方は 筆者までメールいただけると幸いです。次 の機会があれば筆者のホームページなどで ぜひ取り上げてご紹介させていただきたい と考えております。 Homepage: http://www din. or. jprch3/ mailto : ch3@mail.g00.ne.jp ・謝辞 本特集を執筆するにあたり , インテル株 式会社 , マイクロソフト株式会社から参考 資料などのご提供をはじめとした惜しみな いご協力を賜りましたことを心から感謝い たします。 とくにインテル株式会社・小林様からは 直接的なご協力を何度もいただきまして誠 にありがとうございました。この場を借り てお礼申し上げます。 ・免責 ・本特集で紹介している技術 , プログラム によって生じたいかなる損害も保証いた しません。 ・本特集で紹介しているサンプルプログラ ムはあらゆる環境のもとで期待どおりに 動作するという保証はまったくありませ ん。 ・本特集に掲載されている記事 , プログラ ム , 映像 , および付録 CD - ROM 収録ファ イルを含むすべてのコンテンツを CMAG AZINE 編集部と筆者の許可なく転載する ことはできません。 ご要望 , ご質問などにはできるだけ対処 していくつもりですが , 必ずしもそれが C MAGAZINE 編集部または筆者の責任に おいてなされるという保証はありません。 ・そのほか , 本特集に関する詳細について はメールで ch3@mail.g00.ne.jp までお問 い合わせください。 [ 参考文献 ] ・ -32 lntel architecture software develope rs manual. ・ lntel Pentium 4 Processor optimization re ference manual. WHITE PAPER: Enhanced 3DNow! Tech nologyfor the AMD Athlon Processor. ・ Micro so れ V1sual C + + Processor Pack doc ument. ・ MSDN library 2001 , 7 release. ・資料 (IntelPentium4 プロセッサにおける 特集 1 プログラムの高速化・最適化 ット表 ) 。付録 CD-ROM に収録 鳳 -32 命令セット・レイテンシとスループ イ 9

特集工 加ムの高速化・最適化 高速に , かっそれなりの精度を保った除算 ビットしか精度のなかったものが 22 ビット sqrtps / sq ホ s を実行したのと同じくらい時 を実行することができます ( List46 ) 。 (y* 精度の値を得ることができるようになりま 間がかかってしまいます。これではまった (l/x)) を計算することで , 除算命令を使う す。このコードも rcpps/rcpss と同じく ss 部 く意味がありません。 ことなしに除算の近似値を得ることができ 分を ps にすると 4 つ同時にパックド演算す そこで , 最初の計算過程に少しだけ手を ました。しかしやはりもっと正確でより確 ることができます。せつかくなので中級編 加えて逆数平方根から精度の高い平方根を 実な値を得たい場合は素直に d 師 s / divss 命 で説明した FPU 正規化べクターのプログラ 求めることにします (List 49 ) 。難しそうで 令を使用したほうがよいでしよう。なぜな ムを SSE 命令を用いたものに移植してみま すが , 実は前の逆数の項ですでに使ってい ら精度が上がったとはいえ , 近似はやはり した (Fig. 15 ) 。 List 48 のように SSE の命 る方法です。ポイントは灰色になっている 近似でしかないのです。近似値の精度向上 令で簡単に逆数平方根の近似値を求めるこ 2 行です。おそらくほとんどの方は説明す や計算方法は時と場合によるので , それぞ とができるので , FPU のときと比べてプロ るまでもなくおわかりいただけたと思いま れの場面に応じて ( 使用箇所をうまく判断 すが , よくわからない方は逆数の項の最後 グラムがとてもシンプルになりました。ま して ) 使い分けることが大切です。 に出てきた計算式を , レジスタの動きを見 た 128 ビットの XMM レジスタをフルに使っ また同じくニュートン・ラフソン法を用 て x, y, z, w の 4 つのべクトルをいっぺん ながらもう一度ご覧ください。これで高速 いれば , 逆数平方根の精度も向上させるこ かつ高精度に平方根の値を求めることがで に計算しています。 とができます。 SSE 命令にある逆数平方根 ところで , SSE のことを説明している We きるようになりました。 b サイトや資料にはよく「 sqrtps/sqrtss では を求める命令 rsqrtss/rsqrtps もまた精度が 分岐を除去する別の方法 なく rsqrtps/rsqrtss を使って平方根を求め よくありません。この命令の精度を上げる ためには , 中級編の正規化べクターで行っ たほうがよい」と書かれています。それは これまでさんざん話題にしてきた条件分 たのと同様の方法をとります。この方法に なぜかというと , sqrtps/sqrtss 命令はそれ を実行するのに divps/divss と同じかそれ以 岐の話をまた蒸し返すようで心苦しいので ついては次の項で解説しましよう。 すが , Pentium Ⅲからサポートされた命令 上のレイテンシがかかってしまうからです 最適化と精度のバランス を利用することでも分岐を除去できます (Li しかし , 逆数平方根の値を求めることがで きるのなら , さらにその逆数をとれば平方 st50)0 具体的には , cmov, setcc を使うと いう方法です ( 浮動小数点比較命令では fc 。 根の値を求めることもできるのでは ? そ さて , 中級編の正規化べクターサンプル のとおり。逆数の平方根から平方根の値を mi , fcmov で代用する ) [ 15 ] では逆数平方根の近似値を自力で計算しま 得ることができます。このように逆数の値 したが , SSE 命令には rsqrtss/rsqrtps とい データ構造のレイアウト からさらに逆数を求めることを「反逆数」と う 1 つの命令で逆数平方根の近似値を求め られる命令があるので話は簡単です。あと いいます。しかしそう説明すると一瞬 , 逆 はニュートン・ラフソン法を用いて逆数平 数平方根→逆数というステップを踏むのか 3D 変換や照明計算などのアルゴリズムに 方根の精度を上げてしまえばよいだけです。 な ? と思われるかもしれませんが , 単純 は , 頂点のデータを編集する基本的な方法 にその順序をたどっていたのでは , 普通に として , それぞれの頂点を 1 つの構造体で List 47 の方法を使うと rsqrtps/rsqrtss で 11 List Pentium Ⅲからサポートされた命令で分岐を除去 Fig. 16 構造体配列と配列構造体 ポ 構造体配列 (Array of Structures) 配列構造体 (Structure of A 「「 ays) SoA → Y Y Y . キャッシュミスの回避 , スルーブットの向上 ! 特集 1 プログラムの高速化・最適化 41

特集 1 加殤ムの高速化・最適化 Fig. 1 級数展開 sin(x) → x - ( 1 / 6 ) * xA3 十 ( 1 / 120 ) * ゞ 5 ー ( 1 / 5040 ) * ゞ 7 十 ( 1 / 362880 ) * 9 cos(x) → 1 ー ( 1 / 2 ) * ゞ 2 十 ( 1 / 24 ) * ゞ 4 ー ( 1 / 720 ) * x% 十 ( 1 / 40320 ) * 8 tan(x) → x 十 ( 1 / 3 ) * ゞ 3 + ( 2 / 15 ) * ゞ 5 ー ( 17 / 315 ) * ゞ 7 十 ( 62 / 2835 ) * 9 ゞ 3 十 ( 1 / 120 ) * 5 十 ( 1 / 5040 ) * 7 十 ( 1 / 362880 ) * ゞ 9 血 ( x ) → x 十 ( 1 / 6 ) * cosh(x) → 1 十 ( 1 / 2 ) * ゞ 2 十 ( 1 / 24 ) * ゞ 4 十 ( 1 / 720 ) * ゞ 6 十 ( 1 / 40320 ) * ヾ 8 tanh ( x ) → x ー ( 1 / 3 ) * ゞ 3 十 ( 2 / 15 ) * 5 ー ( 17 / 315 ) * x 7 十 ( 62 / 2835 ) * x 9 asin(x) → x 十 ( 1 / 6 ) * ゞ 3 十 ( 3 / 40 ) * ゞ 5 十 ( 5 / 112 ) * ゞ 7 十 ( 35 / 1152 ) * ゞ 9 x ー ( 1 / 6 ) * xA3 ー ( 3 / 40 ) * ヾ 5 - ( 5 / 112 ) * ゞ 7 ー ( 35 / 1152 ) * x 9 acos(x) → PI * ( 1 / 2 ) atan ( x ) → x ー ( 1 / 3 ) * xA3 + ( 1 / 5 ) * ゞ 5 ー ( 1 / 7 ) * ゞ 7 十 ( 1 / 9 ) * ゞ 9 しかしながら多くの場合 , プログラムの ログラムを高速化できる場合があります。 的にインライン展開してくれるのでとても - 簡単です (List 20 ) 。 実行速度を左右する要因はコンパイラによ テーブル化 理由 : プログラムの速度的なコスト削減 る最適化というよりは , むしろ使用される アルゴリズムや , 先ほど説明したようなプ 入力値がある程度限られた範囲であるこ のため ログラムの書き方にあります。時と場合に とがあらかじめわかっている場合は , それ 使用される場所 : 少しでも高速な処理が 応じたよりよいアルゴリズムを考え , 工夫 らをテープル化しておくことでプログラム 求められる場所 し , プログラムの書き方にも注意すれば , を高速化できます。 List 19 は theta が 1 度単 よりよいアルゴリズムを 位 , 0 ~ 360 度の範囲で変化することを前提 それだけで十分高速なプログラムを書くこ 求めることが重要 とができます [ 第 p ] 。 としてテープル化しています。 プログラムの実行速度を速くする方法は しかし「アルゴリズムは何度も見直した。 理由 : 比較的時間のかかる計算を省略す プログラムの書き方にも自信がある。もう こであげたもの以外にもたくさんありま るため 限界までチューニングした」というプログ す。もっとも手つ取り早い方法は , コンパ 使用される場所 : 範囲がある程度決まっ イラの最適化オプションを利用することで ラマが , それでもまだなおソフト的な最適 ていてそれほど正確な値も必要ない場合 す。近年 , コンパイラはプロセッサの発展 化 , 高速なプログラムを求める場合の最終 インライン関数展開 とともにだんだんと進化してきており , プ 的な手段としてアセンプリ言語があります。 ただ , アセンプリ言語はこの章の冒頭で紹 ログラムの書き方の違いなどもある程度う インライン関数展開でもサイズを犠牲に まく吸収してくれます。最適化オプション 介したとおりソースコードが非常に長く , して速度を改善することができます。イン しかも難解です。プログラムが巨大になれ は利用するそれぞれのコンパイラによって ライン関数展開とは関数本体をそのままコ ード中に埋め込むことで , 関数の呼び出し 異なりますが , マイクロソフトやインテル , ばなるほど把握できなくなります。一度ア GNU など多くのコンパイラでは -0 オプショ センプリ言語にした部分は , そうとう気合 命令とそれに伴うパラメータの引き渡しや , スタックの保持 , ジャンプによるオーバへ ンです [ 第 p 調。そのほか , ターゲットとなる を入れないとプログラムを読み返す気力が ッドといった速度的なコストを削減するこ プロセッサに合わせて CPU の持っているパ なくなってしまうので , そのあたりを覚悟 とができます。単純に関数の頭に一 in ⅱ ne と イプラインなども考慮したコードを生成し のうえで , 次の章からアセンプリ言語によ いう冠詞を付けるだけでコンパイラが自動 てくれるコンパイラもあります。 るプログラミングを解説したいと思います テープル化 インライン関数展開 0 ・ケース 1 int DivideAndSurplus( int a, セ b, セ ) ・ケース 2 - はれ 0 int DI 土 d ・ A れ dSu てが ( int 加し b, セ日 ) void yak ・で ( ) 土 n し theta; fO て ( theta 第に h ・に a く 36 theta 十十 ) t ー nco 日 . 日 [ 幻 = sin( theta * / 180.0 し一日 1n00 日 .0 は ] = 日 ( theta 事 PI / 180.0 = a 宅切 return a / b; 日 = a を b; て・ t れ a / 25 プログラムの高速化・最適化 特集 1

特集 1 プログラムはもっと速くなる 高速化・最適化 加ムの ch3 近年 , プロセッサ技術の進歩で CPU の速度 は飛躍的に向上しました。現在では標準とな りつつあるギガヘルツのプロセッサですが , ひと昔前までは夢のまた夢でした。おかげで 複雑な計算もずいぶん楽にできるようになり ました。プロセッサは十分速く , 日々進化し ていきます。だからもう高速化の必要はない のではないかと思うこともありますが , 計算 は速いにこしたことはありません。速く計算 できるということは , 同じ時間でそれだけ多 最適化の基本 C 言語での最適化にはたくさんの方法がありますが , くを実行できることになるからです。たとえ ば 3D ゲームでよりリアリティのある表現を したり , キャラクタの動きをもっとスムーズ にすることもできますし , 長時間かかってい た画像処理がたとえば半分の時間でできるよ うになれば作業効率も倍になります。また , ごく少数ではありますが , プログラムを高速 化することに喜びを覚えるような変人 ( 失礼 ) もいます。現在と同じ実行環境で時間に余裕 ができることはとても重要なのです。 の章ではもっとも一般的なものから順に説明していきま す。なかにはこんなものは当然だと考えられる方もいら っしやると思いますが , そのあたりはプログラミングを 再確認するといった感覚で眺めていってください。もち ろん , 当然のごとく使われているようなアルゴリズムな どはどんどん読み飛ばしてもらってかまいません。 20 C MAGAZINE 2001 10 最適化の概要 プログラマにとって理想的な世界は , プ ログラマの設定した仕様に従ってソフトウ ェアが自動的に実行プログラムのサイズを 縮小してメモリ消費量を最小限に抑え , た だちにコンパイルが完了し , 完成したソフ トウェアが常に最高速で動作する環境です。 しかし現実には , 開発者はプログラムを自 分で書く必要があります。 ほとんどのプログラマは , C 言語などの 高級言語を使ってコーティングし , アセン プリ言語にコンパイルして , それぞれをリ

ials> ディレクトリに収録されています ) 。計 以上の計算精度を得るには自力で精度を向 りよくないことになります。たとえば 1.0 の 測のため巨大なループを回るので , 実行 逆数 , つまり 1.0 / 1.0 を計算すると結果は 1.0 上させなければいけないことになります。 ( 測定 ) が完了するまでしばらく時間がかか となるはずですが , 実際には 1.0 になってく より精度の高い近似値を得る方法として れません ( 近い数値だが ) 。たいして計算精 る場合があります。 もっとも有名なニュートン・ラフソン法を 度を必要としないケースでは誤差というこ 使って , 計算精度を向上させることにしま 精度の問題 とで許容できますが , もっと高い精度を求 す。しかし , ニュートン・ラフソン法なん められるケースはよくあることです。 て , たいそうな名前を聞くと何だか難しそ SSE 命令には rcpps/rcpss という逆数を求 AMD の K 伝 2 や Athlon に搭載されている 3 うな感じがするし , そんなのを自前で用意 めるための命令があります ( rcpps はパック DNow ! テクノロジでは p 仕 cp という命令で逆 するなんてイヤだなあ・・ などと思って ド形式 , rcpss はスカラ形式の命令 ) 。実行 数の近似計算を行うことができますが , や しまいそうですが , 実はとっても簡単な計 されたときに比較的時間のかかる除算命令 はりこの p 斤 cp 命令も単体ではあまり精度は 算で済みます。 List45 をご覧ください。 を使わないで , 除算したときに求められる よくありません。ただ , これを補うために この計算で逆数の精度を向上させること 数値に近い値 , いわゆる近似値を高速に得 3DNow! テクノロジには pfrcpitl , pfrcpit2 と ができます。コードの ss 部分を ps にすると ることができるので , とても便利でよく利 いう逆数の計算精度を向上させる特別な命 4 つ同時にパックド演算することもできま 用される命令の 1 つだと思います。しかし , 令が用意されています。このような精度を す。ニュートン・ラフソン法を用いると単 この rCPPS/rCPSS 命令には弱点があります。 向上させる命令が SSE 命令にも用意されて 純に rCPPS/rCPSS 命令を実行した場合と比べ その弱点とは計算誤差が 1.5X212 となかなか いれば話は早いのですが , あいにく SSE に て倍近くの精度を得ることができます。蛇 大きいことです。要するに計算精度があま そのような命令はありません。つまりこれ 足ですが , この逆数の近似値を利用すれば , Fig. 13 期待する結果 Fig. 14 高速化されていることが確認できる z [ 0 ] = y [ 0 Ⅱ 0 ] * x [ 0 ] 十 y [ 0 ] [ 1 ] * x [ 1 ] 十 y [ 0 Ⅱ 2 ] * x [ 2 ] 十 y [ 0 Ⅱ 3 ] * x [ 3 ] 2 [ 1 ] =y [ 1 ] [ の * x [ 0 ] + y [ 1 ] [ 1 ] * x [ 1 ] + y[ 1 Ⅱ 2 ] * x [ 2 ] + y [ 1 ] [ 3 ] * x [ 3 ] z [ 2 ] = y [ 2 ] [ 0 ] * x [ 0 ] 十 y [ 2 ] [ 1 ] * x [ 1 ] 十 y [ 2 ] [ 2 ] * x [ 2 ] 十 y [ 2 ] [ 3 ] * x [ 3 ] Result 朝 ma セⅸ c らに u t Q-Q-a. C• version FPU versm SE v s 1 List 4 St 7 SSE の命令で逆数平方根の近似値を求める void pagtNormalizevector( VæTQ4 *pv, float x ) 00 れ日 t static ALIGNED 日 oa に一 0 ー 5 [ 41 = ( 0.5f , 0.5f , 0.5f , 0.5f 00n8t 日に a セ土 0 ALIGNED float -1-5 [ 4 ] = { 1.5f , 1.5f , 1.5f , 1.5f mov d 響 0 て d ptr[pvl mo 、 8 ー 0 movaps = 2 ー 0 て d ptr[eax] て日 q て tp 日一 1 , ー 0 ;anrox mulps = 0 , 1 0 , ー 1 ー 0 , ー響 0 て d P [ ー 0 ー 5 ] mulps mulpg 1 , 響 0 て d p [ ー 1 ー 5 ] ー 1 , ー 0 引 subps ゆ日 1 , 2 mov 叩日 ー響 0 て d ptr[eaxl, ー 1 ニュートン・ラフソン法を用いて逆数平方根の精度を上げる / / ニュートン・ラフソン法による逆数平方根の精度向上 逆数平方根から精度の高い平方根を求める 〃反逆数を用いて平方根を求める て gq て t 日日一 1 , ー 0 ;approx -2 / 05 を ck mulgs 冖 0 , ー 1 一日 ta 【に mulss 0 , 1 重 u 一日 8 冖 0 , ー 1 0 , 0 て d pt て [ ー 0 ー 5 ] ー 1 , 。て d pt て [ ー 1 ー引 u 地日 sub 日日 = 1 , 0 ;final 4 Fig. 15 SSE バージョンのほうが高速化されている Result of norm 引に e vector catculatnn SE). 0. 〕 207. -1 . 愈 414. -0. 0 7.0 価 2000 : OPU time = 111253 0.9 207. -1.8 414. -0.9 圓 7.0 旧 0 : OPU time = 197 @22x) verSlOn SSE version イ 0 C MAGAZINE 2 側 1 10

BorIand ムへ 次世代開発のメインストリー ・業界初、 Web サービスのビジュアル開発を実現 B2B をはじめ多くの分野で注目されている XML / SOAP をベースにした Web サービスのビジュアル開発を実現する BizSnap をはじめ、ダイナミックな Web システムを構築できる WebSnap 、多層分散システムを容易に構築できる DataSnap と、 e - business 開発を強力に支援する機能を備えています。 ・最新の Windows アプリケーションを迅速に開発 Windows 2000 / Me に対応した最新のユーザーインターフェースもビジュアルな操作で開発できます。もちろん、ビジュアル開発とソースコード開発を 連携させるユニークな 2Way - T00 や高速なネイティブコードコン ( イラなど、生産性と高速性を両立させる機能が充実しています。 ・すぐれたデータベーススケーラビリティとインターネット対応 dBASE/Paradox/Access をアクセスする BDE 、 ADO や ODBC による接続 sInterBase/MYSQL/OracIe/DB2 用の dbExpress ドライバなど広範な データをアクセスできます。また、旧や Apache 対応の Web サーノ←アプリケーションの開発やソースレベルデバッグもサポートします。 ・ Windows と Linux のクロスプラットフォーム開発を実現 クロスプラットフォーム開発を実現するコンボーネントフレームワーク CLX の Windows 版を提供します。 Linux 用のビジュアル開発ツール BO 月 and KYlix と併用すれば、単一のプロジェクトで Windows と Linux の両方のネイティプアプリケーションを開発できます。 ホーラント株式会社 〒 1 51-0073 東京都渋谷区笹塚 1 - 64-8 笹塚サウスビル TEL. 03-5350-9380 FAX. 03-5350-9369 ・インプライズ株式会社はボーランド株式会社に社名変更いたしました。 ・ボーランドの商品名は、 B ロ•ia ・ v atim の米国における商標または商標です・その他、記載されている会社名、製品名は、各社の商標または登録商標です。 C 叩ⅵ前 t ◎ 281B ar 8.. Ltd. A t 「日 v . for more information … WWW• bO 可れ d. 00 り p

中級編 X86 命令 , X87 命令 , MMX 命令を 用いたプログラムの高速化 初級編のまとめで , アセンプリ言語についてそうとうお どしてしまいましたが , アセンブリ言語で記述すること で得られる利益もたくさんあります。使い方しだいでは , C 言語で高速化したプログラムをさらに高速化できるよ うにもなります。ともあれ , この中級編ではアセンブリ ロ語 ( 主に X86 命令 , X87 命令 , MMX 命令 ) を用いたプ ログラムの高速化について説明していきます。 実行環境 筆者の開発・実行環境は次のとおりです。 ・プロセッサ : Pentium 41.7GHz Pentium Ⅲ 500MHz ・メモリ : 256M ノヾイト ( Ⅲ MM -800 ) 128M バイト (DIMM-IOO) ・ソフトウェア : Windows 2000 SPI V1sual C + + 6.0 Professional SP4 V1sual C + + 6.0 Professional Processor pack IntelVTune Performance Analyzer 5.0 この環境が絶対に必要ではありませんが Windows 98 もしくは NT4 (SP4) 以降の環境 と , なるべく新しい CPU ( 高速である必要 はない ) を用意してください。また , 中級 編の最後で説明する MMX 命令を使ったプ ログラムの実行には Pen ⅱ um MMX 以上が 必要です。さらに上級編では SSE 命令を使 用できる Pentium Ⅲ ( 新しいタイプの Celero n でも可 ) 以上が必要です。それぞれの命令 を実行できる環境かどうかは , 付録 CD-RO M に収録の Cpuid. exe を実行してみてくださ こからはインテル系のプロセッ なお , 26 C MAGAZINE 2001 10 サがターゲットとなりますが , インテル系 以外のプロセッサでマイクロコードを使っ て最適化する場合にもヒントになることが あるはずです。 インラインアセンブラ アセンプリ言語を記述するには「アセン プラ」が必要になります。有名なところで はマイクロソフトの「 MASM ( マクロアセン プラ ) 」などがあり , ( マニアックな店以外 ではあまり見かけることはないかもしれま せんが ) パソコンショップなどで販売され ています。しかし Visual C + + をはじめ , 多 くのコンパイラは「インラインアセンプラ」 というモノを使うことができます。「インラ インアセンプラ」とは , コンパイラの機能 の 1 っとしてアセンプリ言語とほば同等の 記述ができるものです。要するに , アセン プラをわざわざ用意しなくてもアセンプリ 言語のプログラムを書けることになります インラインアセンプラの記述は , 一般的に 命令の前に —asm のキーワードを付けます。インラインアセ ンプラは , 一般のアセンプラに慣れたプロ グラマからすると気がきかない部分が多少 あることも事実ですが , ちょっとしたアセ ンプリ言語のプログラムを書きたいときに は非常に便利です。 また , マイクロソフトからリリースされ ている Visual C + + 6.0 Processor pack (http:/ /www.microsoft.com/japan/developer/vstu dio/download/ppack/ から無料で入手でき る ) というⅥ sualC + + 6 用の拡張モジュール を導入すると , Pentium Ⅲからサポートさ れた Streaming SIMD Extension (SSE) , Pe ntium 4 から導入された Streaming SIMD Ex tension 2 (SSE2) と AMD の 3DNow! テクノロ ジといった拡張命令 [ 第” 06 ] のアセンプリコー ドが記述できるようになります。ちなみに lntel C + + 5.0 コンパイラであれば同社の命 令セットは ( 当然ですが ) すべて標準サポー トされており , 拡張命令の組み込み関数も 使用することができます。 X86 系プロセッサ ()A -32 ) 「 X86 」という言葉を知らなくても「 Pen ⅱ u m 4 」はおそらくご存じでしよう。インテル が誇る優れたアーキテクチャを備え持つパ ソコン用のプロセッサです。 Pentium4 も x8 6 系のプロセッサです。正式には「 32 ( 32 ビットインテルアーキテクチャ ) 」と呼びま す。 インテルは日々 CPU を進化させてきまし たが , 命令系統は旧世代のもの ( 80X86 ) と 互換性を保っています。つまり昔作られた プログラムの資産を今日でも利用すること ができます。それが X86 系のプロセッサと 呼ばれるゆえんです。 X86 は厳密にいうと整数演算の処理を担 当するコアを指します。浮動小数点の演算 は X87 というコプロセッサが担当します。「 x 86 系」 , 「 X87 」 , 「い 32 」など , 書き方がコ ロコロ変わるとややこしいので , 便宜上こ れ以降は基本的にこれらのプロセッサのこ とを総称して X86 と呼びます。浮動小数点 を説明する部分では X87 と記述します。 本特集は , これよりこの X86 系列のプロ セッサをターゲットとします。

特集 1 加殤ムの高速化・最適化 分岐から再度読み込む必要が出てくること ある条件のもとでは List 10 に示したように になってしまいます。この動作は命令を実 条件分岐をまったくなくすこともできます。 行する際 , 非常に大きなへナルティとなり また , List 11 の例では AND の論理演算を利 用して条件分岐をなくしています。ここで ます。 行っている , 変数 i を 1 増やして 16 ( 2 の X 乗 ) したがって最近のプロセッサを実行のタ 以上になったときに 0 に戻るような計算の ーゲットとする場合は , なるべく条件分岐 場合には , 1111b ( 16-1 ) でビットマスクして をさせない工夫を凝らします。 やれば値は 16 ( 10000b ) を超えることはあり List 9 のような場合 , 最小の数値が 0 にな るような数を足し , 符号なしの型にキャス ません。 理由 : 条件分岐をなるべく減らすため トすると , 2 回必要だった条件分岐が 1 回で 使用される場所 : マスク処理などの計算 済みます。整数を比較するときに使うこう によって条件を満たすことができる分岐 いったケースのキャストにペナルティはな いので , うまく利用すればプログラムの高 処理 速化に直接つながります [ 1 い 2 ] 。 バック演算 理由 : 条件分岐をなるべく減らすため 通常であれば 1 バイトずつ処理するとこ 使用される場所 : 条件の範囲がある程度 ろを , 複数バイト同時に処理することでパ 特定されている分岐 フォーマンスを向上させることができます 0 条件分岐をなくす List 12 では long ( 32 ビット ) 型を使って 4 ノヾ イト同時に計算しています。ただしループ 先ほどの応用といえなくもありませんが の数を 4 で割り切ることができる場合にの 命令の優先順位 ( データのシフト ) み使用できるという条件が付きます。ルー プ数が 4 で割り切れない場合は , なるべく 4 バイトずつまとめて処理した後 , 余りを 2 バイトまたは 1 バイト単位で処理すればよ いでしよう。この手の最適化は配列の数が 大きければ大きいほど効果があがります。 理由 : 複数の要素を同時に計算して高速 化させるため 使用される場所 : 比較的少ないビット数 で同じ計算が繰り返されるようなところ。 ただし計算結果がオーパフローまたはア ンダーフローするような場合は使用でき ない lSt 条件分岐をなくす① 2 ス ス ケ oB て anchl ( ) return (x = 100 ) ? true : falge; 引 0h1 ( ) return ! ( (l) (x - 100 リ List 条件分岐をなくす② 2 ス ス ケ ケ unsigned int 製 OB て anch2 ( ー日土 61 ・ d int 土 ) 土十 if ( 土》 = 16 ) 土 = の ェてれ新 新 gned 加に 8 て 50h2 ( int 土 ) て e 加工 n & ( 16 - 1St バック演算 1 ・ケース 1 void char ね [ 256 ] ) ・ケース 2 void packed( char ta [ 256 ] ) ng *lp = い 0n9 * ) data; fo で ( int 土 = 土く 256 / of い ong 土十十 ) ゆ [ 幻 & = 0X7f7f7f7 新 List 7 ・ケース 1 int de て Of io て土 ty ( int n ) return n * 32 ・ケース 2 int de て Of 土 or 址 y ( int n ) return ((n« 8 ) 十 ( れ 6 ) fo て ( int 土 = 土く 25 研土十十 ) data[il & = 0X7 新 List 不変式のループ外移動① 条件分岐の順序 8 ・ケース 1 void Out deO れ 00P ( に社第 int a, セ b ) fo て ( int = 土く 1000 土十十 ) て [ 幻 = a 十 ・ケース 2 void Outs 土 deO れ 00P ( int 社 , int int b ) int t = a 十 b; fO て ( れヒ土 = 土く 1000 土十十 ) ・ケース 1 void Branch( int seldom, int frequently ) ・ケース 2 void Branch( int se 0 叫 int ) 迂 ( frequently & & 日引 dom ) 不変式のループ外移動 何度も繰り返される List13 のようなルー プ内のコードには , ループ中に値が変化し 変数はレジスタに格納されます。一般的に ないこともよくあります。こういった式の レジスタへのアクセススピードはメモリへ ことを「不変式」といいます。このような不 のアクセススピードよりも高速なので , か 変式はループの実行前に 1 度だけ計算され なり効果があります [ 1 い 3 ] 。また List 14 のよ るようにしておくことで高速化することが うなケースもループ外に移動することがで できます。この例では t という一時変数を使 っていますが , ほとんどの場合こういった きます。 て [ 幻 = IS 9 条件分岐を減らす ・ケ - ス 1 void 土 n ヒ x if ( x く = 2 & & x -1 ・ケース 2 void Decreageranch( int x if ( ( int) (x 十 1 ) ← ( 2 + 1 ) 特集 1 プログラムの高速化・最適化 23