Manhattan life

普段何も意識せずに使っている 4バイト整数の int 型ですが、 例えば int x = 0x7f000001 がどのようにメモリに格納されているか ご存じでしょうか？ この変数xのアドレスを無理矢理キャスト変換して このxがあるメモリ領域を char 型の配列で見てみましょう。

<br /> unsinged int x = 0x7f000001;<br /> unsigned char* ptr = (unsinged char*) &amp;amp;x;<br /> printf(&quot;%02x,%02x,%02x,%02x\n&quot;, ptr[0], ptr[1], ptr[2], ptr[3] );<br />

7f,00,00,01

01,00,00,7f

後者の結果が出た人は、それはあなたのマシンのCPUが little endian と呼ばれる メモリの扱い方をしているからです。たぶんあなたのマシンは Intel社製のCPUを 積んだパソコンか、DECのワークステーションなのでしょう。

int型などの複数バイト長の変数のメモリ上での取扱がCPUによって異ることは 普段はまったく意識しないのですが、異る種類のマシン間でデータを共有する ネットワークプログラムにおいては意識しなくてはなりません。 結論を言うと、4バイト長のIPアドレスと、2バイト長のポート番号は big endian でその数値を記述しなくてはなりません。このような決まりを network byte order と呼びます。この決まりにはたとえ同じ種類の マシン間で通信する場合でも従わなくてはなりません。

例えばIPアドレス "127.0.0.1" を long型変数に設定するには big endian のマシンでは

<br />unsigned long ip = 0x7f000001;<br />

<br />unsigned long ip = 0x0100007f;<br />

<br />unsigned long ip = htonl(0x7f000001);<br />

同様に short型の値であるポート番号は htons関数で big endian に統一します。

<br />unsigned short port = htons(80);<br />

逆に network order を host order に戻す ntohl, ntohs 関数もあります。

<br />printf(&quot;IP = %08x PORT=%u&quot;, ntohl(ip), ntohs(port) );<br />

IPやポートの値だけでなく、ネットワーク通信するデータの中身にも この endian の問題があります。異なるendianのマシン間で 2 bytes 以上の整数型、浮動小数点型のデータを 通信する際には、どちらかのendianにデータを統一するように変換しなくては なりません。htonlなどの関数はマシンがbig endianなら何もしないので、 byte orderを強制的にひっくり返すには自分でそのような関数を作成 しなくてはなりません。種々の基本型の byte orderをひっくり返す 関数 bswap は以下のようになります。

<br />inline void bswap( short&amp;amp; d ){<br /> short s=d;<br /> char *ps((char*)&amp;amp;s), *pd((char*)&amp;amp;d);<br /><br /> pd[0] = ps[1];<br /> pd[1] = ps[0];<br />}<br />inline void bswap( int&amp;amp; d ){<br /> int s=d;<br /> char *ps((char*)&amp;amp;s), *pd((char*)&amp;amp;d);<br /><br /> pd[0] = ps[3];<br /> pd[1] = ps[2];<br /> pd[2] = ps[1];<br /> pd[3] = ps[0];<br />}<br />inline void bswap( long&amp;amp; d ){<br /> long s=d;<br /> char *ps((char*)&amp;amp;s), *pd((char*)&amp;amp;d);<br /><br /> pd[0] = ps[3];<br /> pd[1] = ps[2];<br /> pd[2] = ps[1];<br /> pd[3] = ps[0];<br />}<br />inline void bswap( float&amp;amp; d ){<br /> float s=d;<br /> char *ps((char*)&amp;amp;s), *pd((char*)&amp;amp;d);<br /><br /> pd[0] = ps[3];<br /> pd[1] = ps[2];<br /> pd[2] = ps[1];<br /> pd[3] = ps[0];<br />}<br />inline void bswap( double&amp;amp; d ){<br /> double s=d;<br /> char *ps((char*)&amp;amp;s), *pd((char*)&amp;amp;d);<br /><br /> pd[0] = ps[7];<br /> pd[1] = ps[6];<br /> pd[2] = ps[5];<br /> pd[3] = ps[4];<br /> pd[4] = ps[3];<br /> pd[5] = ps[2];<br /> pd[6] = ps[1];<br /> pd[7] = ps[0];<br />}<br />

なお、マシンの byte order を簡単に調べるには以下のようにするのが良いでしょう。

<br />int n=1;<br />if( *(char*)&amp;amp;n ) printf(&quot;Little endian\n&quot;); else printf(&quot;Big endian\n&quot;);<br />

ネットワーク通信でデータの中身自身の問題には byte order の問題だけではなく、構造体型変数を通信する際の 構造体の構造自身の問題もあります。構造体のメンバ変数 がメモリ上でその構造体変数の先頭から何byte目に配置されているのか(offset)に 注意しなくてはなりません。構造体メンバのoffsetは以下のようにして確認できます。

<br />#define StructOffset(Object,Property) (&amp;amp;((Object*)NULL)-&amp;gt;Property)<br /><br />struct Test<br />{<br /> char c;<br /> int n;<br /> double d;<br />};<br /><br />printf(&quot;%d %d %d\n&quot;, StructOffset(Test,c), StructOffset(Test,n), StructOffset(Test,d) );<br />

<br />struct Test<br />{<br /> union{ char c; double dummy1; };<br /> union{ int n; double dummy2; };<br /> double d;<br />};<br />

#include <stdio.h>

int add(int a, int b){
	return a+b;
}

int sub(int a, int b){
	return a-b;
}

main(){
int (*fp)(int, int); // pointer to a function. 

	fp=add;
	printf("%d\n", (*fp)(10, 4) );

	fp=sub;
	printf("%d\n", (*fp)(10, 4) );
}

1. char *(*(*a[N])())();
   
   
2. 宣言をtypedefを使って段階的に作り出す。
   
   typedef char *pc; /* charへのポインター */
   typedef pc fpc(); /* charへのポインターを返す関数 */
   typedef fpc *pfpc; /* 上記へのポインター */
   typedef pfpc fpfpc(); /* …を返す関数 */
   typedef fpfpc *pfpfpc; /* …を指すポインター */
   pfpfpc a[N]; /* …の配列 */
   
   
3. プログラムcdeclを使う。cdeclは英語で書いた宣言をCの変数宣言 に変換し、またその逆変換を行う。
   
   cdecl> declare a as array of pointer to function returning pointer to function returning pointer to char
   
   char *(*(*a[])())()
   
   cdeclは、複雑な宣言をキャストを使って説明してくれるし、引数が どの括弧の組に入るか示してくれる(上記のような複雑な関数の定義 では)。いくつかのバージョンのcdeclがcomp.sources.unixのボリュー ム14に保存されているし(質問18.16参照)K&R第二版にも存在する。
   
   

プログラムを作っているときから最適化を考えるな！これが私の考え方です。最適化 (Optimization) を行うということは、プログラムの実行速度をより速くし、実行コードのサイズをより小さくすることです。よりというには何か比較するものがあります。それは以前のプログラムです。まず、どんなに遅くても正常に動くプログラムを作ってください。最適化は必要に応じてその後に行うべき作業です。

最適化という作業はあまりお勧めできません。プログラムのコードを読みにくくして、デバッグの手間を増やします。結果として出来上がったコードは、せいぜ い以前の 10%〜30% 程度の処理速度しか速くできないでしょう。せいぜい 50% あがったとしても、0.1秒が 0.05秒に変わるだけです。使っている人としてはあまり変化がありません。

むしろ使っている側としては、速くなった 0.05秒よりも、カリカリの最適化によってプログラムに入り込んだバグが気になると思います。右に私が考えている最適化の方法の手間と効果をグラフにし て見ました。もちろんこれはその手法を使うプログラムによりますので、一概には言えません。目安程度にしてください。手間というのは、その最適化によりバ グが入り込んだ場合のデバッグの手間も含まれています。

最適化をする場合というのは、プログラムを実際に実行してみて、速度があまりにも遅すぎたりファイルのサイズが大きくなりすぎたりしたときです。最 近では大容量の RAM になってきましたので実行コードのサイズというのはあまり問題にはならないでしょう。最適化が必要になるのは処理が遅すぎる場合です。たいして遅くもない のに最適化をしてはいけません。

あと、よくプログラミングの解説書で使われている『この方法のほうが速い』という言葉にだまされてはいけません。そりゃ速いです よ。だって読みにくいもん。読みやすさが同じなら速いほうが結構ですが、無理して速い方法を取ることはありません。解説書でいわれている文法的な速さとい うのはほとんどが小手先技です。プログラム全体の実行速度に対して数パーセントの違いも出ないでしょう。

ただ、アルゴリズムの解説書に乗っている速いはちょっと違います。実際に使ってわかる (時にはびっくりする) くらいの速い動作をするものがよくあります。実際、クイックソートはバブルソートに比べてびっくりするほど速くなります。これらはアルゴリズム系の最適化ですので、小手先技ではありません。

Level 1: 高性能コンピュータを使う

正しい答えを出すが、処理速度が１日かかる非常に遅いプログラムが出来上がりました。ただ、プログラムを実行して結果を出すのは１回で十分です (実験用のシミュレーションなどでよくあります)。そんな時どうしますか？プログラムが正しい答えを出しているなら、コードを修正しないで、もっと高性能 なコンピュータを使えないか考えてください。あなたのつてで一番速いコンピュータを持っているのは誰ですか？

この方法は非常に簡単です。実行ファイルをフロッピーに入れてもって行くだけで、たった１回きりの処理が劇的に速くなります。結果はまたフロッピーに入れて持ち帰りましょう。

そうです、プログラムの最適化のためにコード修正は避けるべきです。プログラムの格言にこんな物があります。

Level 2: まずはコンパイラから

最近のコンパイラには、優秀なオプティマイザをつんだものがたくさんあります。オプティマイザは自動的にあなたが作ったコードを最適化してくれるという便利な機能です。ループで使っている変数をレジスタに置いたり、似たようなコードをまとめてファイルを小さくしてくれたりします。先にいった小手先の最適化というのは、ほとんどこのオプティマイザが自動的にやってくれています。小手先最適化をするよりも、コンパイラのオプティマイザにやってもらうほうがはるかに簡単です。コードを変更しないで最適化。それが最良の方法です。

しかし、小手先の最適化があまり速度に影響が出ないように、コンパイラのオプティマイザを使用してもそれほど劇的な速さになることはないでしょう。 後で言いますが、昔ためした結果では 1割も速くなりませんでした。しかし、コードを変更しないで速度が速くなるのは魅力的です。まずはコンパイラの最適化機能を使ってみてください。それでも 遅ければいよいよコードの変更が必要になってきます。

コンパイラの最適化機能は、プログラムの処理の流れをコードとは違った具合に変更することがあります。コンパイラの最適化をしたプログラムに対して デバッガでトレースして行くと、突然処理が変な場所に飛んだりすることがあります。これは、コンパイラが『こっちの方が効率的』と判断した場所です。初め て最適化したコードをデバッグする場合には驚くかもしれませんが、そのジャンプが意味することを良く考えてみるのも面白いでしょう。

Level 6: アルゴリズムからの最適化

プログラムというのは、いくつもの実行モジュールの組み合わせです。各モジュールはそれぞれ目的を持っており、速度が遅すぎる場合というのはそれら のモジュールのうちのどれか一つが(場合によっては幾つかが)ネックになっています。まず、そのネックになっている部分を特定してください。

速度が遅くなっている部分を断定するには、プログラムのいたるところに "paper.cpp [243]: 通過" といったメッセージを表示させます。これでプログラムが現在どのファイルの何行目を処理しているかがわかります。Cならば、printf("%s [%d]: 通過\n", __FILE__, __LINE__); というコードでしょう。

プログラムを実行すると、たくさんのファイル名と行番号が出されます。そして、ある部分だけ表示されるまでの時間が遅くなる個所があるでしょう。そ こがネックです。その部分のコードを読んでみて、どうして遅くなっているか考えてみてください。そして、何か別の方法を使ってその部分を書き換えられない かを良く考えてください。

もちろん、モジュールや関数のアルゴリズムを変更する場合にも、なるべく読みやすくするように心がけることが大切です。プログラムの修正というの は、そのまま新しいバグを入れるということに直結します。最適化のためにコードが巧妙になればなるほど、新しく入れられるバグは増えて行きます。

よく、アルゴリズムの速さを考える場合にデータのソートが出される場合があります。ソートはたくさんのデータを整列させるためのアルゴリズムです。データが多くなればなるほどソートにかかる時間は莫大な量になってきます。

ソートのアルゴリズムにはバブルソートやクイックソート、ヒープソートなどさまざまな種類のものがありますが、大体私が使うのはわかりやすいバブル ソートです。そして、ソートの時間が気になるくらい大きなデータを扱うことになったらヒープソートやクイックソートを使います。もちろん、これは個人のわ かりやすさの問題です。『ヒープソートでも十分私にはわかりやすい』という人ならヒープソートをいきなり使っても良いでしょう。高度で速いアルゴリズムを 使うのが良いプログラムではなく、最終的に使える程度の速度で正確な結果を出すのが良いプログラムだと私は考えます。いくら最新のアルゴリズムを使ってい るとしてもちょっと使い方を誤って間違った結果が出されていては本末転倒です。

Level 6: 整数処理の威力

大学のプログラミングで『モンテカルロ法による円周率の計算』 という課題がありました。縦横の長さが 1の正方形に円の 1/4 があるものとしてランダムな座標に点を打ち、全部の点の数と円内の点の数の比を求めて、πが比の 4倍になることを利用した簡単なアルゴリズムです。いつもこの授業の課題は私にとってとても簡単だったため、自分でかってに『サブタイトル』をつけてこな していました。この円周率の計算もサブタイトルは『最適化の効果』というものでした。円周率計算もするのですが、プログラミングの勉強として最適化につい てのレポートもついでに作ったわけです。

最初に作ったプログラムは、私が考えうる限りの手法で最悪化(?)した物でした。数値計算で十分な精度が上がるまでに 40数秒かかったような気がします。ここから物語が始まります。この最悪なプログラムを、register を使ってみたり、ループを簡単にしたり、コンパイラの最適化をすべて ON にしたり、小手先だけの修正をしてなんとか 30秒程度まで押さえることができました。

さて、ここからが問題です。できうる限りの最適化はもうしてしまいました。さて、どうしよう。たったこれだけじゃ最適化をサブタイトルにした意味がないなぁ、と思っていたとき、すべての実数変数を整数値で置き換えられることに気づきました。

それまでのプログラムでは、辺が１の正方形の中に double 型の x, y を打っていたのですが、stdlib.h の乱数関数 rand() は 0〜RAND_MAX (32767) までの整数を返します。そこで、辺が 32767 の正方形に点を打っても同じことだということに気づきました (そのころは MS-DOS を使っていたので int は 16ビットでした)。rand() の値を double 型に変換していたので、結果的に整数に置き換えても同じ事です。

プログラムが出来上がって一回目は、実行してすぐにプログラムが終了してしまいました。おや、と思いコードを見てみたのですが別段変なところはあり ません。よく見ると正しい答えが出ています。これはかなり驚きました。それまでいろいろな最適化を加えても 30数秒かかったプログラムが、扱うデータをすべて整数 int に変えただけでわずか数秒まで最適化できました。もちろん私はこの衝撃的な事実をレポートに書きしるしました。

コンピュータはもともと整数演算を得意とするようにをするために設計されています。事実、プログラム内の処理のほとんどが整数処理です。float や double などの浮動小数点演算をコンピュータに行わせるには大きな負担をかけることになります。そのレポートを書いたころのコンピュータはまだ 486SX 25MHz でオーバードライブプロセッサをつんでいなかったので、実数演算がかなりきつい処理だったと思われます。コンピュータが一番処理速度の速いデータは C/C++ なら int か unsigned 型です。実数演算を多用する数値計算などでは、扱う実数が整数に置き換えられないかどうかも考えてください。

もちろん、講座の課題は『円周率を求めること』ですので最適化の必要はありませんでした。講座を取ったほとんどの人が優秀なコプロをつんだ大学の WS 上でプログラムを作っていたため、私が作ったものを同じ WS 上で動かしてもそれほど威力は見られないでしょう。実数型を使ったほうがコードがわかりやすいのであればそれを使うべきです。よっぽど遅いのでなければ、 無理してコードやアルゴリズムを難しくする必要はありません。ただ、技術計算やシミュレーションなどの実数演算を多用するプログラムでは、このような整数 化による最適化が威力を発揮することもあります。

私がこの時提出したレポートには、すべて『シュミレーション』と書いていました。英語では Simulation (シミュレーション) でシュミレーションではありません。そのレポートを書いたときにはそれに気づかずシュミレーションと書いてしまい、あとで誰かに指摘されました。紛らわしいので気をつけてください。

Level 4: ループ文

// C++ のループ文
for(int x=0; x<1000; x++){
    for(int y=0; y<1000; y++){
        // ここのコードは結果的に
        // 1000000(百万回) 呼び出される!
    }
}

プログラム内で時間がかかる処理というのは、ほとんどが膨大な回数のループを使っているところです。ループの回数が多くなればなるほど、ループの中の処理を最適化することが意味を持ってきます。１千回や１万回のループであれば、その処理の中の最適化の効果は１千倍にも１万倍にもなります。

たとえ一つのループが 100回程度でも、その中に更に 100回のループがあれば、結果的に一番深いループの呼び出し回数は 10000回になってしまいます。このようなループのネストが行われている場合には、最大でどれくらいの呼び出しになるかを考えてください。このような膨 大なループでは、小手先の最適化ですらかなり有効になることがあります。しかし、やっぱり最初は『遅いけど正しい結果を出すプログラム』を作ることに専念 しましょう。ループ内を最適化するのは、正常に動作することが確認されてからでも遅くはないはずです。

ループを最適化する方針の一つとして、ループの回数が少ないものを外に出すというのがあります。ループ文というのは、何か条件文を評価してループを 続けるかどうかを判定します。この条件判定というのがちょっとネックになります。for(..; <条件文>;...){} というやつです。

for(int x=0; x<1000; x++){
    for(int y=0; y<10; y++){
        // ...
    }
}

外側のループを 1000回、内側を 10回の処理を考えてみます。外側のループが１回行われるたびに内側の条件文は何回評価されるでしょうか。10回？違います。11回評価されます。これ は、ループ終了の場合の評価が含まれるためです。N回のループでは N+1回の条件評価が行われることに注意してください。さて、外側の 1000回ループが (1001回の評価を終えて)終了したとき、内側の条件評価の回数はどうなっているでしょうか。11000回行われています。このようなループ文では、 for() 内の条件文は合計で 12001回評価されたことになります。

さて、今度はその逆について考えてみます。外側が 10回で内側が 1000回です。外側１回につき内側は 1001回の評価となります。ループが終了してみると、外側 11回、内側 10010回の合計 10021回となります。つまり、外側のループを簡単にしたほうが 1980回分の条件文の評価が省略できます。

数学に強い人のために数式で表してみます。外側のループの回数を N_out、内側のループの回数を N_in としたとき、最終的にすべての条件文が評価されるのは

さて、多重ループをさせる場合、ループの外側を簡単にしたほうが条件評価の回数が少なくなるのが分かりましたか？私自身はこの最適化でそれほど目に 見えた結果を出したことがないのですが、これくらいの最適化はコードを読みにくくすることもないと思いますので、ちょっと注意してみてください。

Level 2: 条件文

C や C++, Java では if() 構文を使って条件分岐を行う事ができます。しかし、条件文の評価と言う作業はコンピュータにとってちょっとつらい作業です。なるべく条件の評価回数を減ら すと言うのも最適化の方法です。あなたのプログラムでどのようにしたら条件評価を減らせるか考えてみてください。

if('A' <= ch && ch <= 'Z'){
    printf("This is Upper Case Alphabet\n");
} else if('a' <= ch && ch <= 'z'){
    printf("This is Lower Case Alphabet\n");
} else if('0' <= ch && ch <= '9'){
    printf("This is Numeric\n");
} else {
    printf("This is other character\n");
}

たとえば、if/else を使用した構文を考えてみます。通常の if/else 構文は先頭の条件から順に評価して行き、条件が一致したところで評価を終了します。つまり、最終的に条件が一致する位置より前の条件評価も行わなければな りません。もしたくさんの if/else 構文のうち、一番最初の条件に一致すればそれが最良の場合だと言えます。逆に一番最後の条件に一致するのは最も効率が悪い場合と考えられます。

右のコードを見てください。もし ch が '4' だった場合、条件が一致する前に 'A'<=ch && ch<='Z' という評価と 'a'<=ch && ch<='z' という余分な評価が行われてしまいます。

たくさんの if/else を使用する場合には、もっとも一致する確率が高いものを先頭に持ってくるという最適化が行えます。もちろんどれが一番一致する確率の高い条件か分からない 場合もあります。しかし、プログラムの特性や確率論的にある程度予想がつく場合にはこの方法が使用できます。しかしこの方法も小手先技系の最適化です。確 率の高い条件文を先頭に持ってくる事でコードが読みにくくなるようであれば止めたほうがよいでしょう。この最適化が効果を表すのは膨大なループの中で行う ときなどだと思われます。

ディスク容量

プログラミングからちょっと離れます。Windows (MS-DOS) のハードディスク上でファイルがどのように存在するかの説明です。1バイトのファイルがハードディスク上で何バイト占有しているか知っていますか？御期待の通り１バイトではありません。

Windows や MS-DOS などのファイルシステムでは、ファイルをハードディスク上に 512バイト単位で割り当てます。この割り当て単位はセクタとよばれ、ハードディスク上のセクタごとにファイルのデータが書き込まれて行きます。したがって、１バイトのファイルをハードディスクに書き込んでも、実際には１セクタ(512バイト)を占有することになります。

昔、このような小さなファイルをたくさん作り出すプログラム (NIFTY-Manager) を使ったことがあります。そのころは (今も) 500MB のハードディスクをぎりぎりまで使っていたのですが、そのソフトを使い始めてからハードディスクの容量が極端に小さくなってしまいました。

ちょうどそのころ、NIFTY-Serve のプログラマーズフォーラムで、NIFTY-Manager の話題が出されていました。内容は Windows のファイルシステムにより NIFTY-Manager が実は膨大なディスク領域を食いつぶしているというものでした。驚いて調べてみたところ、１ヶ月分のログが 10MB(!) も食っていました。エクスプローラに実際に表示される大きさは 3MB 程度でした。原因はやはり NIFTY-Manager がたくさんの小さなファイルを作り出すことにありました。もちろん私はすぐに別のソフトに入れ替えました。いまだされている NIFTY-Manager は膨大なファイルを作り出すなんて行儀の悪いことはもちろんしていませんけど。

しかし、この事に関しては NIFTY-Serve は何も知らせてくれませんでしたね。それが話題に上って以来、プログラマーズフォーラムで NIFTY-Manager を使う人がかなり減ったと思います。

さて、またしても話がずれましたが、要は Windows や MS-DOS などで、膨大な細かいファイルを作ってはいけないということです。1バイトのファイルを 1000個作ったら、実際のハードディスクでは 512キロバイトが使用されます。DIR コマンドやエクスプローラなどで見ても、存在するファイルの合計値 1000バイトとしか表示されません。しかし、裏では 512バイト単位でディスクが消費されていました。私もこの事件が話題になるまで知りませんでした。

しかし、UNIX や Windows NT のファイル管理は違うようです。1バイトのファイルは１バイトのディスクを占有しています。UNIX を使っている人は安心してください。Windows NT でも Windows 95 とディスクを共有している (FAT形式) 場合にはこの問題が起こります。

Level 3: レジスタの使用

もう、ここから先は本当に小手先技です。まったく効果がなくてもしょうがありません。その小手先技の一つが register 変数の使用です。register は C/C++ で使うことができる機能です。他の言語にあるかどうかはわかりません。セキュリティの関係上 Java にはないです。

CPU が処理を行う場合、メモリからデータを読み出して、CPU 内のレジスタに 置きます。レジスタは CPU の中にあるいくつかの小さなメモリと思ってください。CPU が直接処理できるのはこのレジスタにおいてあるデータだけです。もちろん、メモリからレジスタにデータを転送するのにも、わずかですが時間がかかります。 そこで、よく使うデータはあらかじめレジスタ内に入れて置こうというというのが register の役目です。

register int i; などと宣言された変数は、CPU のレジスタ内に置かれます。ループカウンタなどの何度も使われる変数は register を使ってレジスタ内に記憶させておくと、ほんのちょっぴり処理が早くなります。ただし、実際にこれが効果を表すかどうかはわかりません。register を宣言してもレジスタ内に値が置かれない場合もあります。

CPU の中にある使えるレジスタの数はコンピュータによって違ってきます。PC では 2つですし、WS などの大型コンピュータでは 10以上、スーパーコンピュータにいたれば 100を超える数のレジスタが使用できます。もしその数を超えて register 変数を使った場合には、普通の変数と同じようにメモリ上に値が置かれることになります。

さらに、ループカウンタなどの変数はコンパイラのオプティマイザが自動的にレジスタに割り当ててくれることがほとんどです。いちいち変数を register に指定しても、コンパイラが既にレジスタに割り当てていれば処理速度は変わりません。まあ、小手先技の最適化の中では register 変数の使用は安全に修正できる部類だとは思いますが。

ただし、register 変数にしてはいけない変数というものも存在します。このような変数は Windows や UNIX などでマルチスレッド・マルチプロセスなどの複数の処理をしているときや、MS-DOS の割り込み処理に使われるものですが、ANSI C/C++ を使用している限りでは特に考えることもないと思います。

Level 3: 配列とポインタ

さて、だんだん私は楽しくなってきました。やっぱり最適化をするな、といっても自分のプログラムが速くなって行くのは (気持ちだけでも) 楽しいものです。私のようにパズルをじっくり解くのが好きな人は最適化が好きなのかもしれません。つぎは配列とポインタです。

ポインタを使うと配列を使うよりも処理が早くなると聞いたことはありませんか？確かにその通りです。ポインタに入れられている値は、対象となるデー タが存在するメモリアドレスなので、直接 CPU から使うことができます。一方、配列内のデータにアクセスする場合には array[10] などのようにします。配列変数 array も実はメモリアドレスが入っているのですが、こちらの場合は *(array + 10) というように、インデックスの加算処理が必要になってきます。

int i;
int array[10];
for(i=0; i<10; i++){
    array[i] = 0;
}

int *ptr;
int array[10];
for(ptr=array; ptr<array+10; ptr++){
    *ptr = 0;
}

左のコードを見比べてみてください。一方は配列にアクセスして、もう一方はポインタを使っています。見るべき点はループ内です。*ptr=0; では、ポインタのアドレスに直接 0を代入しています。しかし、array[i]=0; という命令は、コンピュータの内部で *(array+i)=0; という処理を行っていることになります。配列を使ってデータにアクセスするほうが、array と i を加算する分、理論的にコストが高くなります。

ただし、これもコンパイラのオプティマイザが受け持てる範囲です。実際、今私が適当にプログラムを作って比較してみた結果、同じ時間で処理が行われ ました。多分内部で最適化が行われているものと思われます。このような簡単なコードでは、オプティマイザによっておなじになってしまいます。

ポインタと配列の違いが出てくるようなコードというのは、もっと複雑なコードでしょう。こんな簡単なプログラムでは違いは出ません。そしてコードが 複雑になってくると、自然に配列よりもポインタを使ったほうが楽になってきます。現在のプログラミング環境を考えると、配列とポインタを比較するだけでは ほとんど同じ処理になると思われます。高速な CPU をつんで、優秀なコンパイラを使用すればこのような違いはほとんど目に見えることはありません。

もちろん、使っているのがあまり良いコンパイラでなかったり、多重ループの奥の奥で使うような場合にはポインタ使用の効果が現れてくるかもしれませ ん。しかし、結局のところの違いは配列のデータにアクセスする場合の加算だけです。あと、ループで配列にアクセスする場合には array[i] の i の変数空間が必要になる程度の問題です。この程度なら処理にして数ステップも違いが出ないでしょう。ポインタを無理に使う場合は、よっぽど悲惨な環境でプ ログラムを作る以外はあまり効果がありません。せめてポインタを勉強したい人だけにしてください。

Level 3: シフト演算とビット演算

C/C++, Java には整数のシフト演算子というものがあります。整数のビットを丸ごと右か左にシフトするものです。例え ば、01001101 を左に１ビットシフトすると 10011010 になり、右に１ビットシフトすると 00100110 になります。この処理は一般の整数乗除演算よりも速いことに注意してください。

1 を左に１ビットシフトすると 10 になります。10 は 10進数で２を表します。さらに 2を１ビットシフトさせると、100、つまり 4になります。どういう意味か分かりますか？整数値を左に 1ビットシフトさせると、2倍の値になります。10は２進数で 1010 です。これを１ビットシフトさせると 10100、つまり 20になります。さらに 2ビットシフトさせると 101000、40になります。

整数を２倍とか、４倍にする場合には、普通の乗算を行うよりも左シフト演算を使ったほうが効率が良くなります。同じように、整数を２や４で割るよう な場合には右シフト演算が有効です。特に、乗除算を行う数が 2のべき乗に決まっている場合にはこの方法は有効です。もちろんこれもオプティマイザの守備範囲ですが。よく C/C++ の参考書でシフト演算を解説するときには『シフト演算を使ったほうが乗除算が速い』と紹介されています。もちろんこれは本当です。コンパイラによる最適化 なしで比較するなら 2〜3倍程度は違うでしょう。しかし『シフト演算を使ったほうが乗除算を使うより３倍速い』という言葉は意味がありません。プログラム全体の処理速度から 言えばそんなのは誤差の範囲です。せっかくシフト演算を使っても、オプティマイザがすでにシフト演算に自動的に変換していてまったく効果がない場合がほと んどでしょう。最近の私のプログラムでも、整数をビットフィールドとして使用する以外にはシフト演算も消えつつあります。

さて、次に整数値を 8や 256などの 2のべき乗で割ったあまりを計算します。割った値については右シフト演算を使ってください。C/C++ で割り算の余り(余剰)を計算するには、演算子 % が使えますが、これも / と同様にちょっと遅い部類に入ります。しかし、割る数値が 2のべき乗のときは特別です。整数 n を 256で割った余りは、n & (256-1) で得ることができます。なんでか？自分で考えてみてください。

Level 5: バッファリング

バッファリングを使ったものでは、よくファイルへの入出力などが例としてあげられます。大きなデータのファイル入出力時には時間がかかりがちです。 ファイルから１文字ずつ読み込むよりも、一度にどれだけかのまとまったデータをメモリに読み出して、それを取り出していったほうがはるかに速くなります。 このような、メモリ上に一時的なデータを置くことをバッファリングといい、データを置いておく領域をバッファといいます。そして、バッファ内にまだあるデータをまとめてファイルに書き込んだりすることをバッファをフラッシュするといいます。

バッファリングをたとえるなら道端の小石を拾って箱に入れる作業です。普通の人なら小石を一個づつ箱に入れるようなことはしないでしょう。片方の手で拾 い、もう片方の手に持ちます。ある程度たまったら箱に入れます。バッファリングはこのような細かいデータを操作するときに威力を発揮します。

バッファリングを行う理由は、コンピュータがファイルを読み書きする速度よりも、メモリ上のデータをアクセスするほうがはるかに速いからです。まと めて読み込み、まとめて書き込む。これは遅くなりがちなファイルアクセスを速くするための方法です。バッファリングという概念はファイルアクセス以外にも 使うことができます。データを一個ずつ取り出して操作するよりも、ある程度まとめて処理したほうが速い場合が多くなります。もちろんそれも場合によります が。

少し前に URL エンコードされた文字を通常の文字に変換するモジュールを製作しました。その時、解析した文字を文字列に連結する個所では、実は１バイトずつの連結を行っていました。これは、簡単のために文字列連結部分から文字連結のメソッドをループして呼び出していくという単純なものでした。つまり、１文字ごとに文字列領域の再割り当て、全ブロックのコピーが必要でした。もちろん、この部分は作ったときから速度が遅くなることを予想していました。

製作してすぐのテスト段階ではたいした文字列を扱うこともなかったのですが、最終的なテスト段階にきて 1000バイトの URL エンコード文字を変換させようとしたとき、連結処理がなかなか終わらない事に気づきました。もちろんすぐに文字列連結処理がネックになっていることに気づ きました。

そこで、私は文字列連結部分に 256バイトのバッファを設けて、解析した文字をそのバッファにためて行き、256バイトごとに文字列を連結するようにしました。このバッファリングによ りプログラムの速度は使える程度まであがりました。時間にしてみれば劇的に速度が上がったほうでしょう。もちろん、以前のコードが悪すぎたのは言うまでも ありませんが。それでも、とりあえず動くプログラムを作ってから遅い個所を断定してそこを修正して行くという方針は変わりません。実際に作ったコードが遅 いかどうかというのは、プログラムが動き始めてからでないとわからないからです。というか、そのプログラムを作ったときに『多分ここは遅くなるな』と思っ た個所が幾つかあります。しかし、結果的に影響が出るのが、先に修正した部分だけだったで、他の部分は修正することもなく使いつづけています。

このように、あるたくさんのデータに対して処理を行う場合、そのデータを一つずつ操作するよりも、ある程度まとまったデータをまとめて操作したほう が処理が早くなることがあります。もちろんそれは行う処理によりますので一概には言えません。しかし、バッファリングという手段はこのページで紹介した中 でも効果のある部類に入る最適化法です。

Level 1: 空きメモリ容量

プログラムの処理速度は、コンピュータが持っている空きメモリの量にも関係してきます。同じプログラムを同じコンピュータで動かすのであれば、空き容量の大きいコンピュータのほうが速度が速くなるはずです。もちろんほとんど変わらない場合もありますが、少なくとも遅くなることないでしょう。

プログラムは起動されるとメモリ上にロードされます。つまり、実行コードの大きさを小さくして使えるメモリを増やすことも、プログラムの速度を速め る一つの方法といえます。Windows などではよく言うでしょう。メモリをたくさん積むと動作が軽くなるって。ついでに、メモリをたくさん積むと、今まで原因不明で使えなかったプログラムが使 えるようになることもあります。

プログラムが使用するメモリが足りなくなった場合、いくつかのプログラムは動作が不安定になって、場合によっては OS ごと停止してしまいます。メモリ不足を検知するデバッグというのは非常に難しいからです。最近の Windows 95 や UNIX などは仮想メモリを割り当てて対処していますが、MS-DOS を使っている場合には深刻です。せっかく作ったのにメモリが足りなくて結局使い物にならなかったというプログラムを私はいくつも作ってきました。話がそれ ましたが、空きメモリの容量はプログラムの処理速度に関係するということです。

もちろん、メモリを占有するのは実行コードだけではありません。プログラム内で使うデータの大きさもメモリを圧迫する原因になります。ファイルなど から一度に膨大なデータを全て読み出すよりも、何回かに分けて読み出して処理したほうが結果的に速度が速くなることもあります。プログラム内で使うデータ の領域を小さくすることも最適化の方法です。もちろんコンパイルして出来上がる実行ファイルのサイズを小さくすることもこの部類の最適化です。

さて、メモリはがんがん使いましょう。いってることが逆ですが。はっきりいって今時 100バイトを節約するプログラムを作るのは無意味です。コンピュータに詰まれている 32MB のメモリを使い切るようなプログラムは、意識して作るかよっぽど変なものを作らない限りほとんどありません。現在は膨大なメモリを使える環境が整っていま す。1バイトけちってコードを読みにくくするのは数十年前のことです。プログラムが 126MB もつんだスーパーコンピュータで使うことを前提としていればなおさらです。Windows 95 を対象にしたプログラムにしても、最近ではほとんどが 32MB 以上のメモリを積んでいるでしょう。500kB のファイルを一度に読み出しても屁とも思わないでしょう。実際にほとんどの Windows 95 のプログラムはそれくらいのことは平気でしています。とくにプログラミングを勉強中の人。メモリをけちる必要はありません。500個の整数配列を安心して 使ってください。

Level 3: アラインメントルール

拝啓

大変楽しくホームページを読ませていただきました。6、7年前日本の某電話会社の交
換器を作っていたころを思い出して一人で読みながら笑っていました、当時の上司に
教わった処理速度向上の技のひとつを披露させていただきます、それは

”奇数アドレスにデータの先頭を持ってこないデータ構造にすること”

つまりここで問題になるのは　char で、char データの直後もしくは直前に
（これはCPＵによるらしい、、）char のダミーを入れる。


当時聞いた時は信じて使っていましたが、本当にCPＵレジスタにデータをロードする
ときデータの格納先が奇数と偶数で違いが出るのかは知りません。またその当時使っ
ていたCPＵの特性かもしれません（そのCPＵは日本のN社が当時独自開発したイ社の
コピー”V　シリーズ”です。）ぜひ検証してみてください。

だいぶ前になってしまいましたが、Takeshi Takami さんよりメールをいただきました。アラインメントルールに関する最適化方法です。コンピュータに搭載されている CPU によってはある特定のアドレスに配置されたデータを効率的に読み出すように設計されているものもあります。特定のアドレスとは 2 の倍数とか 4 の倍数アドレスといったものです。

struct SomeStruct{
    char data;    // 1 byte data
    char dummy;   // padding
    int number;   // 4 byte data
};

構造体を 設計する場合、それに属するメンバをコンピュータのアラインメントルールに沿った配置にするという最適化方法が取られます。つまり、構造体のデータが 2 の倍数とか 4 の倍数のアドレスに配置されるように設計するということです。このため、char によるダミーデータを加える (パディング) ような方法が取られます。左のコードを見てください。2 バイト境界に配置されるようにダミーを加えてメンバを定義しています。

>ところで、ホームページを見たらちょっとハードウェアに詳しそう
>だったのでお聞きします。Intel x86 系の CPU って X68 のように
>アラインメントルールをもっているのでしょうか？最適化のページ
>にアラインメントルールでの速度の向上を話していなかったので、
>実際にどの CPU がアラインメントルールを持っているのか、ご存
>知でしたら教えてください。

　80286までは、分かるのですが386以降はほとんどノーチェック
　状態なんです。H8,ARM,SparcチップなどのCPUレジスタ構成などは
　一度まとめて調べた事があるのですが・・・

　80x86はアライメントルールは、ないと思います。が４の倍数
　アドレスにおいた方が高速に処理されるはずです。それよりも
　SEGMENT FALUTを出さない方がいいのかなあと思います。
　でも386以降は、わかりません、ごめんなさい。
　SEGMENT関係も変わっているかもしれないし、なんとも。

わたしはハードウェア関係には弱い人間なので、どの CPU がどのようなアラインメントルールを持っているか良く知りません。メジャーな CPU のアラインメントルールを知っている人がいたら、またはそのようなホームページを見かけたら教えてください。

Level 4: 自作関数

プログラム内で文字列を検索する場合、どのような処理を思い浮かべるでしょうか？普通の人なら string.h の strstr() 関数を呼び出すことを考えるでしょう。しかし、関数の設計のほとんどは『処理は速いけどメモリをつかう』ものと『メモリは少量だが少々遅い』とに分けられ ます。標準で組み込まれている strstr() 関数などは『速度もそこそこ、メモリもそこそこ』という感じで設計されているでしょう。

strstr() がプログラム内で何千回も呼び出されるようなプログラムを作ったとします。このような場合『そこそこな関数』を使うより『速度に重点を置いた関数』を自分 で作ったほうが処理速度が向上します。具体的には strstr() と互換性のある関数をレジスタ変数やインライン関数、マクロなどを使用して作ることになるでしょう。どの関数に速度の重点を置くかはプログラムの設計がしっかりされていれば自然と分かるはずです。

有 名なコンパイラだからといってその組み込み関数を信用してはいけません。この間、g++ で作ったプログラムでは大きなデータの処理が 2 分以上かかっていましたが、strstr() を自作のものに変更した所 1 秒もかからないで終了しました。苦労して突き止めた遅さの原因は g++ の strstr() の遅さにありました。私はこれで gcc 信仰主義をやめました。

Level -1?: その他の小手先技と嘘

C/C++ に関する小手先技はたくさんあります。また、いまだに信じられている嘘もたくさんあります。適当にいま思い当たるだけの非常に高度な(笑) テクニックを書いてみます。ちょっと詳しい解説書であれば関数呼び出しのコストや goto 文に関する非効率化が書かれているかもしれませんが、もしその他の事柄を強調しているような危険な解説書を持っていたら、いますぐ古本屋に持っていてくだ さい。また、ここに書いていない裏技を知っている人がいたらぜひ教えてください。検証してみたいと思います。

[×] ?: 構文を使ったほうが処理が速い

確かに、?: 構文を使ったほうが if() 文を使うよりも速くなるコンパイラもとても古いものには存在すると聞いたことがあります。しかし、?: 構文の速さが if() 文で使えないというのはおかしな事です。コンパイラメーカーも馬鹿ではありません。それくらいの最適化はとうの昔にやっています。

[○] goto 文はコンパイラの最適化機能を混乱させる

これは本当のようです。C/C++ で goto を使う人はほとんどいないため、goto によって最適化機能が失われる場合もあるようです。しかし、前にも言いましたけどコンパイラのオプティマイザに期待できる速度はそれほど強力ではありませ ん。goto を使ったから遅くなったということはまずないです。

[×] x=++y - z; のようにコード内でインクリメントさせたほうが効率的

そんなこたぁ最近のコンパイラは全部やってます。一行けちってインクリメントさせるよりも、オプティマイザに任せておけば良いのだ。だいたい、この処理で劇的に速度が変化するなんてありえません。

[×] if((ch=getch())=='A') のように条件文の中で代入したほうが効率的

これは単に一行けちっているだけです。代入文を前に出しても条件文の中に入れても、ほとんどのコンパイラは同じコードを生成するでしょう。だいた い、この人は何が効率的だと思っているのでしょうか。ソースファイルが小さくなれば実行ファイルも小さくなると思っているんでしょうか。なぞです。

[△] コメントはなるべく使わないほうがコンパイルが速い

まぁ、確かに事実ですけど...。ファイルが小さくなればコンパイルが速くなるのもうなずけます。しかしですよ、プログラムを作る目的は正しく処理 が行えるコードを作ることであって、開発時のコンパイル速度は関係ないはずです。コメント文はコンパイル時には無視されるとちゃんと規格で決まっていま す。コメントを多用したことで出来上がったプログラムが遅くなるとかサイズが大きくなるなんてことはありません。

[×] x=(ch=getch())-z++; のように 1コードにまとめたほうがサイズが小さくなる

これも先と同様に、短いソースが小さな実行ファイルを作るものと思っているのでしょうか。発想が貧弱ですね。サイズを小さくしたければアルゴリズムを変更すべきです。

[×] 変数名は短いほうが効率的

これは大嘘です。一体何が効率的なのでしょう。n とか s とかいう変数名をつけたことで、デバッグの手間が増えたというなら理解できます。長い変数名をつけたところで、プログラムが実行されているときに使用され るメモリ空間は int なら 4バイトに決まっています。何でこんな当たり前のことを力説しているのだろう。なさけね〜。

[追記] Java を使用する場合、クラス名やメソッド名、パッケージ名、変数名を短くすると、出来上がるクラスファイルのサイズを小さくすることが出来ます。これはクラス ファイル内に文字列としてこれらの名前を入れておく必要があるためです。普通のプログラムで気にすることはありませんが、携帯電話で動くプログラムを作る ときなどは注意してください。

[×?] float よりも double のほうが処理速度が遅い

確かにとても古いコンパイラでは double のほうが処理が遅くなることもある。しかし、ほとんどのコンパイラでは float の計算を行うとき、一回 double 型に変換して計算し、結果をまた float に変換するという作業を行っているのだ。大体 C 組込みの数学関数のほとんどが引数を double で取るだろう。sin() に float 値を渡しても結局内部で double に変換されて処理が行われるのだ。変換の分だけ処理が遅くなるってのが普通だろう。小さけりゃ速いってもんじゃないんだよ。

古籏一浩さんのメールより:

powerPCだとfloat,double演算ともに３ステートで終了しますし変換もしません。キャッシュミスヒットダメージからするとfloatの方が有利かなと。でも、そう思って実験しましたが全然変化なし(^^;

というメッセージをいただきました。ハードウェアに疎い私は何のことだかさっぱり分かりませんでしたが、どうやら float のほうが速い場合もあるようです。失礼しました。

[○] 関数を多用すると呼び出しのコストがかかる

これはまあ許せます。関数呼び出しに少々の時間がかかる上、スタックも使うことになります。実際、ソフトメーカーの人が製品を作るときには、余分な 関数呼び出しのオーバーヘッドが起こらないように注意しています。もちろん、これも劇的に速くなるようなことはまったくありません。C++ ならインライン関数を使いましょう。少々サイズが大きくなりますが、関数呼び出しのオーバーヘッドは減らすことができます。

[死] int よりも char のほうが処理速度が速い

万が一、こんな事を書いている本があったらすぐ私に送ってください。読み終わった後、丁寧に供養してあげます。はて、この人がいっているのは 8ビットのポケコンに詰まれたもののことでしょうか。なぞです。

								
 
				
								

					テーマ : プログラミング - ジャンル : コンピュータ