PEACE CODE memorial 11

ここのところ更新がされてなかったのには理由がありました。とゆーか、これまでの更新速度が異常だったという噂もありますが(^^;。で、その理由というのが、「1クロックの差がよくわからない」のと、「コンパイラの最適化でいいんじゃないの？」という素朴な疑問を提示されたことです。で、当然(^^;「見てろよ～」となったわけですが(笑)、負けを認めます(爆)。みなさ～ん、ここで書いてあることを実践してもVisual C++には勝てませんよ～(笑)。という冗談だか本気だかわからない主張は置いといて、原因がよくわからんのですよ。命令を見てくと同じクロック数で実行されそうなんですが、実際にDirectDrawアプリに組み込んでFPSを表示させると違うんです。ただ、現状のプログラムだと処理が軽すぎてリフレッシュレートで頭打ちになるので、厳密なところ、実際にどちらが速いかを見極めることは難しいような気がします。ということで、どうも僕がやっていることは単なる自己満足なのかなぁ、という今日この頃。そのあたりのことはサンプルプログラムをいじくりまわして試してみてください。このプログラムはやねうらおさんが作成・公開しておられる yaneuraoGameSDK(通称ygs) を使用しています。DirectDrawでゲームを作ろうと考えている人、こーゆーSDKを使っといたほうがいいですよ～。ぎゃるぱにＸも当初は自前のラッパーで書いてましたが、冬コミ一ヶ月前にygsに移行しました。おかげでDirectX関連の謎の挙動に悩まされることはなくなりましたし。なにより、音楽再生が楽です。ソースコードも公開されているので、カスタマイズすることもできます。ぎゃるぱにＸでは256フルスクリーン専用に書き換えました。
そんなわけで、結論。コンパイラに最適化をかけたコードを吐き出させて、そのコードを最適化しよう。もしくは。MMXを使おう(^^;。さすがにMMXを勝手に使って最適化してくれるコンパイラはまだないと思うんですが、どうでしょう？
さて、某掲示板で僕が8bitスプライトルーチンの完全ペアリング～と騒いでいたんですが、「AGIストール受けてない？」という指摘を受けて考え直したところ、AGIストール受けてました。で、あちゃ～と思いましたが、こっちのページのネタが出来てラッキ～(笑)と思って文章を書いていて、いざコードを見なおすと・・・AGIストール受けてない・・・(爆)
実は、掲示板に書きこんだ後、コードを見ていたら実用性がまったくないことに気がついたのでした。というのも、 edxがスプライトデータを指していて、ebxがスプライトのバックになるデータを指しているわけです。で…、合成したデータをedxに書きこんでいました(笑)。そうです、毎回スプライトデータをつぶす必要のあるコードだったのでした。こりゃいかーんと思って、こっちのページに書きこむ際にそのあたりを修正したのですが、その結果、たまたまAGIストールが回避されていたのでした(笑)。
それはそれでいいのですが、その修正をすっかり忘れていて、おりゃ～と文章を書いてしまったのでした。そんなこんなで、書きなおしてます(^^;
で、せっかく書いたのでAGIストールについての説明を。知っている人は知っているわけですが、僕は勘違いしてコードを平気で書いていたわけで、間違えて解釈した人が間違えないように説明するというところで貴重かもしれません(笑)。ただし、Pentiumしかわかりませんけど(^^;
Pentiumでは命令を取り出し、命令を解釈し、実行するという各ステージが同時に実行されています。で、メモリに対するアクセスをする場合には当然のことながらメモリアドレスが必要になるわけです。しかし、このメモリアドレスとはプログラムが動作しているメモリ空間でのアドレスであり、プログラムが動作しているメモリ空間は実メモリ空間の一部であり、プログラムが動作しているメモリ空間は実メモリ空間のどこかに配置されています。このため、メモリに対するアクセスをする場合にはアクセスしようとしているアドレスを実メモリ空間でのアドレスに変換しなければなりません（はずです）。これはOSに依存する話ではなく、80486からの仮想メモリを扱う機能上の話です。したがって、プログラムのメモリ空間＝実メモリ空間（リニアアドレス）であったとしても、それはたまたま同じということであって、動作が変わることはありません（多分）。
で、Pentium/MMX Pentiumでは、プログラムのメモリ空間のアドレスをリニアアドレスに変換する計算に1クロックかかります。 Pentium Pro/Pentium IIではなぜか1クロックかかりません。よくわかりませんが、このために、とにかくPro/IIではAGIストールが発生しない、と書いてありました。
パイプライン処理は不測の事態が生じない（もしくは推測どおりの実行がなされる）ことを前提に並列処理されています。そのつもりで処理しているのに、実行直前に「アクセスする場所違うから。」といわれるわけで、「じゃぁ今までの処理、全部だめじゃん」となるわけです。これがAGIストール（Address Generation Interlock）というわけです。この結果、「最低7クロックのペナルティ」が課せられます。とりあえずパイプラインが無効になるわけで、その分はわかるとしてなんでこんなにペナルティが大きいんでしょうねぇ。
話を戻しましょう。 1クロックとはどういうことでしょうか。隣り合う命令の場合は駄目だということは簡単にわかります。それでは何命令開ければAGIストールは発生しなくなるでしょう？アドレスを変更する命令がuパイプで実行されたとすると、同じクロックのvパイプで1命令、次のクロックでuvパイプで2命令、そしてその次のクロックで実行すればAGIストールは発生しません。したがって、アドレッシングに使うレジスタに対する操作と、アドレッシングに使っている命令との間に3命令はさめば AGIストールは絶対に起きない、はずです。多分。逆にいえば、 3命令はさんでない場合にはペアリングの可能性をちゃんと考えないといけないということです。 ?はu/vパイプで実行、nはペアリングなしで実行として表記するとして、
-----------------------------------------------------------------------
1? ADD EAX, 1
2n BSWAP EBX
3u MOV ECX,[EAX] AGIストールなし
-----------------------------------------------------------------------
のように間にはさんでいる命令がペアリングできない命令ならAGIストールは発生しません。かならず１クロックはさむことになりますからね。
-----------------------------------------------------------------------
1? ADD EAX, 1
2u SHR EBX
2v MOV ECX, [EAX] AGIストールあり
-----------------------------------------------------------------------
これは一目瞭然ですね。2vに別の命令をいれましょう。
問題は次のようなコードです。
-----------------------------------------------------------------------
：
ADD EAX,1
MOV EBX, [EDX]
AND EBX, 0x7F7F7F7F
MOV ECX, [EAX]
：
-----------------------------------------------------------------------
こんな感じのペアリングが自由にできるような命令が続いている場合は要注意です。
-----------------------------------------------------------------------
1v ADD EAX,1

2u MOV EBX, [EDX]
2v AND EBX, 0x7F7F7F7F

3u MOV ECX, [EAX] AGIストールなし
-----------------------------------------------------------------------
このようにペアリングされればAGIストールは発生しませんが、
-----------------------------------------------------------------------
1u ADD EAX,1
1v MOV EBX, [EDX]

2u AND EBX, 0x7F7F7F7F
2v MOV ECX, [EAX] AGIストールあり
-----------------------------------------------------------------------
のようになればAGIストールが発生します。コードを逆に見ていって、ペアリングに制限のある命令を起点に順番にペアリングしていけば、こ～ゆ～場合にどうなるかはわかるはずですが、ループの繰返しで飛び込む場合にはやっかいです。なるべく3命令以上離すようにしたほうがいいでしょう。
ちなみに、僕が勘違いしていたのは同クロックでの実行だけだと思っていたところにあります。文章ちゃんと読めばそうでないことはあきらかなんですけどねぇ
今回は文章ばっかりで読みにくいっスね。次はなんとかしたいですなぁ。そりでは。

とりあえず、近況です。 D5.のメンバーのうち、僕を除く4人は時間が取れるようになったので、ぎゃるぱにＸの完全版へ向けて作業に入ったor入れるようです。僕はもうしばらく時間に余裕がないので、こうして現実逃避をしています(爆)。先日までは現実逃避にフリーセルもやっていたのですが(笑)、 58連勝の記録を更新すべく、現実逃避していたら、53勝あたりで気を抜いてしまって、連勝がストップしてしまったので、フリーセルは多分、もうしません(^^;。
そんなことを書いていたのは実は3/21だったのですが、内容的にアップできずにいたら、どんどんやばくなって(笑)。今日、これから学会発表なのに、ついさっきまでＯＨＰを印刷してました。といっても、時間がわからんですね。知りたいですか？そうですか。しょうがないですね。8:40に発表で、今6:20です。うゎ、こえぇ。まぁ、なんとかちゃんとした発表ができそうで、一安心したので今、これ書いてます(笑)。
前置きが長くなりました。本題に入りましょう。これまでの8bitマスク生成はスプライトの合成に使います。でも、今までのコードでは4dot単位でしか合成ができません。したがって、どうにかして1dot単位での合成ができるように改良しましょう。
一番手っ取り早いのは、それはもう、1dotごとに判定する方法ですが、こんなことをすればせっかくの8bitマスク生成・合成ルーチンが使えないので、それはそれは遅いに違いありません。せっかくですから、なんとかしてDWORD単位（MMXを使うならQWORD単位）でまとめて合成したいところです。
となると、合成の対象となるデータをシフトすればよいでしょう。この場合、スプライトデータと転送先データのどちらかのDWORD境界に合わせると速いはずです。さて、どちらの境界に合わせたほうが速くなるでしょうか。ということについて考察するのが今回のお題です。
シフト後のデータ合成部分に同じコードを使用するとすれば、両者の違いは、シフトによるデータを取得するところにあります。シフトによるデータの加工のコストを考えてみましょう。いきなりニーモニックで書いてもわけがわからなくなるので、まずC言語で書いてみます。話を簡単化するために、DWORDの一次元配列にDWORDの値2つを書き込むことについて考えます。 1byte(=1dot)ずれた場所に書き込む場合のプログラムは
void dwordWrite(DWORD *array, DWORD *value)
 {
    BYTE *dst = (BYTE *)array;
    BYTE *src = (BYTE *)value;
    for(int i = 0; i < 8; i ++)
     {
        if(src[i] != 0)
            dst[i+1] = src[i];
     }
 }
となります。エンディアンについては全然考慮に入れてませんし、無茶苦茶な書き方な気もしますが、ようするに、こうしたいわけですね。
まず、スプライトデータに合わせた転送の場合を考えてみましょう。上のプログラムで言えば、valueのアラインに合わせた転送です。
void dwordWrite(DWORD *array, DWORD *value)
 {
    for(int i = 0; i < 2; i ++)
     {
        array[i+0] = (array[i+0] & 0xffffff00) | (value >> 24);
		array[i+1] = (array[i+1] & 0xff) | (value << 8);
	 }
 }
こんなんでいいですかね。書き込む場所以外の部分を保存するためにマスクしないといけないのが面倒ですね。
次に、転送先に合わせた場合を考えてみます。
void dwordWrite(DWORD *array, DWORD *value)
 {
    for(int i = 0; i < 2; i ++)
     {
        if(i == 0)
            array[i] = (array[i] & 0xff000000) | (value[i] >> 8);
        else
            array[i] = (value[i] >> 8) | (value[i-1] << 24);
     }
 }
なんか、あってるのか不安なプログラムですな。
さて、この二つのプログラムを考察してみましょう。ってゆーか、プログラムがなくても考察できるんですけど・・・。ま、おいといて。
1dotずれた状態で転送する場合、転送元にしろ、転送先にしろ、基準となるほうのDWORDを処理するには、他方は必ず2つのDWORDにアクセスしなければなりません。スプライトデータに合わせた前者では、毎回書き込み側を参照しているので、その分命令数が多くなりそうです。これを回避するには、前のループで演算結果をどこぞに格納しておく必要がありますが、レジスタの本数を考えるとかなりきつそうな感じがします。
後者の場合を見てみると、if文がありますが、こんなのはスプライトデータの両脇に1DWORDのブランクを入れておけば回避できる問題なので、気にしてはいけません。となると、メインのプログラムはelse文の次の行です。う～ん、ビューティホー。というか、これならまぁ、ペアリングもわりと楽な気がなんとなくします。
というわけで、なんとなく書いてみたプログラムで比較すること自体ナンセンスな気がするのですが、書き込み側に合わせた方が速いと結論してしまいます。
という話の流れにしようと思ったのですが、どう考えても無理がありすぎ(笑)。なにしろ、僕がそう思って書いたプログラムですからねぇ。そんなわけなので、この検証については後日、ちゃんと実証コードなりで測定して論じたいですね。
え？なんでこんな中途半端な内容なのかって？それはね、今6:50を回ったところだからです。そろそろ用意し始めないと間に合わなくなっちゃうんですよ(笑)。でも、なんか、面白そうなので、更新したかったのです。そりでわ。

みなさん、お久しぶりです。いろいろある中で時間をみていろいろやってるんで、こっちの更新をする時間がとれてませんでした。
一時期、こっちのページをおりゃ～と更新しまくってたのですが、その口調がどうやら論文原稿を書いているときに出てしまったようで、「さ～くん、口語調じゃ駄目だよ」と言われてしまったのでした。で、ここんとこずっとそっちにかかりきりだったので、今度はこっちのページに影響が出るかもしれません(笑)。
さて、ぎゃるぱにＸはシューティング的な当たり判定を行う必要があるわけで、今のところ、if文でバカバカ判定してます。それをなんとかしようとふと思ったのです。というか、これは秘密ですがかすり判定ルーチンに微小なバグが存在している気がするので、これを修正したいわけですが、まんま修正しようとすると、どうも遅くなってしまう気がするので、ちゃんと高速化しとこうね、ということなのでぇす。
さて、二つの矩形に重なる部分があることを判定するにはどうすればいいでしょう。え？APIのIntersectRectを使う？う～ん、それではほかのページに行ったほうがいいかもしれません。(^^;
当然、ここで考えるのは矩形の重なりがあるかどうかで、 true/falseのbool値で十分ですから、重なっている矩形のサイズは問いません。このように限定すれば、ちょっとぐらい高速化できると思うのが人の常でしょう。話を戻しましょう。ただ単にif文で書いてみましょう。話を簡単にするため、まずx座標軸に関しての衝突判定とします。また、rect.leftに矩形の左端を、rect.rightには矩形の右端を格納しているとしましょう。ここで、rect.rightは矩形の外ということにします。
矩形の衝突が起こらない状態は二つ考えられます。

矩形１の左端よりも左側に矩形２の右端がある
矩形１の右端よりも右側に矩形２の左端がある
ということですから、プログラムとしては
bool collisionRect(LPRECT r1, LPRECT r2)
 {
    if(r1->left >= r2->right)
        return false;
    if(r1->right <= r2->left)
        return false;
    return true;
 }
こんなとこですか。等号を含むところに注意ですね。
IntersectRectを使えば、
bool collisionRect(LPRECT r1, LPRECT r2)
 {
    return (IntersectRect(r1, r2) == 0) ? false : true;
 }
となりますね。
これをなんとかしてみましょう。
    if(r1->left >= r2->right)
は、移項しましょう。
    if(r1->left - r2->right => 0)
おおお、これは素晴らしい。わかりやすく書き換えてみましょう。
    LONG a = r1->left - r2->right;
    if(a >= 0)
どこがわかりやすいかって？条件が成立している場合は a の最上位ビット（＝符号ビット）が 0 になっている、といえばわかりますね。さて、勢いにまかせてもう一つのif文も書き換えてしまいましょう。
    if(r1->right <= r2->left)
    if(0 <= r2->left - r1->right)
    if(r2->left - r1->right => 0)
となりますから
    LONG a1 = r1->left - r2->right;
    LONG a2 = r2->left - r1->right;
    if(a1 >= 0 || a2 >= 0)
        return false;
    return true;
符号ビットのことを気にかければ
    if(a1 >= 0 || a2 >= 0)
は
    if((a1 & a2) >= 0)
と書き換えることができます。これなら a1 と a2 のどちらか一方が正の数であれば、ビットorをとった結果の値の符合ビットが 0 になるので、条件が成立します。
あれ？よくよく考えてみましょう。判定は最上位ビットを見てるだけですね？そいじゃ、そいつを戻り値にしてしまえば if文なんていらないじゃないですかぁ～。 false =0、true =1 ということにしてしまえば話は簡単です。おりゃっとシフトしちまいましょう。
BOOL collisionRect(LPRECT r1, LPRECT r2)
 {
    LONG a = (r1->left - r2->right) & (r2->left - r1->right);
    return ((DWORD)a) >> 31;
 }
美しいっすね～。
さて、それでは二次元に拡張しましょう。
BOOL collisionRect(LPRECT r1, LPRECT r2)
 {
    LONG a = (r1->left - r2->right) & (r2->left - r1->right)
                   & (r1->top - r2->bottom) & (r2->top - r1->bottom);
    return ((DWORD)a) >> 31;
 }
なんて素晴らしいんだぁ～。ということで、プログラム14-rect.cpp (2543 bytes)を組んで計測してみました。

IntersectRect 自前のコード
2800 659
試行回数： 9999回 x1000ループ
PentiumII 333MHz使用ってな感じでした。４倍ってーとすごい気もしますが、 1000万回実行して3秒なら別に気になる量でもありませんな。なぁんて言ってしまったらみもふたもねぇ～ 第14+回：矩形衝突判定（2000/05/08）
どこぞの誰かさんが「よく読んでないけどよくわかりませんでした」とかほざいて(笑) いたので、やっぱ文字ばっかじゃいかんかねぇ、ということで図示してみることにしました。あ～ぁ、めんどくせ(爆)
さて、基本となるアイデアは
if(a < 0 || b < 0)
を一回のif文で処理してしまおうというところにあります。数値表現について考えましょう。符号付きで数値を表現する場合、最上位が符号bitになります（図１）。

32bit

符号
1bit 数値部
31bit

図１：数値表現
実際の値が入った場合について説明しましょう。符号bitが 0 の場合は、数値部がそのまま正の数を表します。 n>=0だとすると表現は図２のようになります。

0 n

図２：正の数 n の表現
一方、n<0の場合は数値部が２の補数をとった表現になります。具体的には n を全bitを反転し、1 を加えます。このように表現しておくことで、正の数と負の数を区別せずに演算できるわけです。例として n=7,-7 の表現を考えてみます。

0 000 0000 0000 0000 0000 0000 0000 0111

図３：n=7 の表現

1 111 1111 1111 1111 1111 1111 1111 1001

図４：n=-7 の表現
さて、最初に戻りましょう。
if(a < 0 || b < 0)
です。このif文が成立する場合を考えましょう。それは、

a

1 ??? ???? ???? ???? ???? ???? ???? ????

か、

b

1 ??? ???? ???? ???? ???? ???? ???? ????

のどちらかが成り立てばいいことになるわけです。ということで、符号bitを使えば二つの判定を一つにまとめることができるじゃないか、ということになります。
条件を見直してみましょう。少なくとも片方が負の数であればいいということは、言いかえれば少なくとも片方の数の符号bitが 1 であればいいということです。となれば、二つの判定を一つにまとめる演算子は or ですね。これなら少なくとも片方の符号bitが 1 であれば演算結果の数も符号bitが 1 になります。
この変形を経ると
if((a | b) < 0)
になりました。演算子がビット演算子の or であることに気をつけてください。
ほかの場合を考えてみましょう。
if(a < 0 && b < 0)
この判定はどうなりますか？
if( (a & b) < 0)
ですね。両方が負の数のときだけ演算結果が負になるようにすればいいのです。当然、条件を逆にすれば別の条件も含めることができます。
if(a >= 0 && b < 0)
ちょっといやらしいですが、がんばればいけます。
if( ((a ^ (1<<31)) & b) < 0)
無理矢理ですね。最上位の符号を反転してます。でも、計算量を考えれば1命令増えただけです。ベタに書けば1クロック増えますが(笑)
if( ((-a-1) & b) < 0)
これでもいけます。
a >= 0
-a <= 0
-a-1 < 0
このように変形しました。
ここからはマシン語レベルの話になります。先ほどのif文は、
if((a | b) < 0)
判定をする前に (a|b) を計算しているため、次の判定で計算結果を使うことができます。つまり、or eax,ebx を計算したとすると、計算後の eax に応じてフラグが立ちます。今、注目すべきは sign フラグです。名前のとおり、計算後の eax が負の数であったときに sign フラグが立ちます。したがって、
OR  eax, ebx
JNS  jump_point
と書くことができました。
このアイデアの注目すべき点は、複数の条件判断を1回ですませることができる点にあります。これを利用すると、矩形の衝突判定のように4回の判定を1回の判定にまとめることができます。このアイデア、誰かしら思いついててもおかしくないはずですが、どうなんでしょ。アセンブラを触っている人なら気がつきそうな気がするのですが。と思っていたのですが、実はこのアイデア、パイプラインがなければ遅くなるわけで、そーゆー意味で逆に古くから触ってる人は気がつかないのかもしれません。 Pentium II では分岐予測ミスに10クロック以上のペナルティがあるので、分岐を何回もするよりは多少計算してでも1回にすることに意味がありますが、 Z80なんかでは成立したらさっさとジャンプしてしまったほうが速いわけです。というわけなので、有効に高速化されるのは矩形判定のように、判定を全部しないとわからない場合ぐらいしかないのかもしれませんね。

やねさんからVisual C++6.0に付属のSTLはHewlett-Packard製であるとの指摘をいただきました。確かにそのとおりで、僕がlist.hと混同していたために間違えてしまいました・・・(2000/05/17)
そのうち調べようと思っていたところ、やねさんのページで内容的に似た感じ（僕的に）の話が載っていたので、ポイントをかせぐべく、急遽計測してみました。
ことの発端は当然ぎゃるぱにＸで、キャラクター管理にSTLのlistを使ってました。で、どうもキャラクター管理近辺にバグがあって、そのバグの原因がわからなく、プログラマにありがちな「これは僕が悪いんじゃない。システム側の原因だ。」という結論に至りました。結果から言うと、当然僕のほうが悪かったわけですが(笑)、その際にSTLのlistから自前のlistに書き換えたところ、動作が目に見えて速くなったのでした。僕がSTLの説明を読んだデイテル著の本には「普段はSTLを使用し、パフォーマンスが問題になったときにリプレースすればよい」とありましたが、まぁ、そんなに遅くはないだろ、と思っていただけにこれはショックでした。
ということで、今回は特に他にいうべきこともないので、プログラムを説明して終わりたいと思います(^^;
状況の設定はぎゃるぱにＸみたいなもので、弾を吐くわけですが、その弾は画面外に出るとリストから削除しなければなりません。ということで、Ccharaクラスがそれに相当します。で、Cchara::process内で画面外判定をして・・・とやるのも面倒なので、乱数によって挙動を制御することにしました。
class Cchara
 {
 public:
	bool process(void);
 };

bool Cchara::process(void)
 {
	int mode = rand( ) & 255;
	if(mode < 1)
		return false;
	else if(mode < 2)
	 {
		for(int i = 0; i < 100; i ++)
			if(objs.size( ) < MAX_OBJ)
				objs.push_back((Cchara*)new Cchara);
	 }
	return true;
 }
このキャラクタオブジェクトらしきものをリストに従って順番に呼び出していきます。もちろん、最初からオブジェクトが存在していないとなにも起きないので、最初に10個ほど生成してます。
	// using STL code
	for(i = 0; i < 10; i ++)
		objs.push_back((Cchara*)new Cchara);
で、何フレーム分かの処理を繰り返します。呼び出したときにfalseが帰ってきたらそのオブジェクトを削除します。それにしても、STLの削除はわかりにくいですなぁ。
	list::iterator itr;
	// estimate time
	for(itr = objs.begin( ); itr != objs.end( ); )
	 {
		if((*itr)->process( ) == false)
		 {
			delete *itr;
			itr = objs.erase(itr);
		 }
		else
			itr ++;
	 }
同様の処理を配列リストに関しても作ります。プログラマならちょちょいのちょいですね。・・・といいつつ、書いてみたところ、保護例外があったので(爆)、さくっとぎゃるぱにＸからカットアンドペーストしました(笑)。ちなみに、ぎゃるぱにＸで書いたときにもバグがありましたから・・・いけてねぇ～。これでもゲームが作れるのですから驚きです。
使用したプログラムはこちら16-chara.cpp (2703 bytes)です。結果はこうなりました。

配列リスト STLリスト
最大オブジェクト数 2000
処理フレーム数 6000
削除確率 1/256
発生確率 1/256 3ms 1180ms
最大オブジェクト数 2000
処理フレーム数 6000
削除確率 50/256
発生確率 2/256 1ms 6080ms

これだけ違えば確かに影響するわけです。ただ、ここに示した結果ははっきりと違いのわかる数字を示しているので、オブジェクト数の増減の頻度が少なかったりすると違う結果になるかもしれません。最大オブジェクト数を使用しているかどうかのチェックもしてませんし・・・。実際のゲームでどのくらいの頻度なのか、さっぱりわからないのでアレですが、ぎゃるぱにＸではかすりの破片もオブジェクトなので、自機の爆発時には300程度のオブジェクトを発生することもあります。それはそうと、このプログラムの正当性もチェックしていなかったりするので、その辺も問題になるかもしれません（だめじゃん）。配列リストの方は、ぎゃるぱにＸのプログラムから持ってきたので大きな間違いはないと思っていますが・・・あったらあったで大問題ですね。
さて、ここでふと気が付くのは、ボトルネックがどこにあるかということです。もし、リストの走査自体は遅くないとすれば、オブジェクトの増減がない場合に限ってSTLを使用することに問題はありません。ということで、初期状態でオブジェクト数1000とし、オブジェクトの増減をない状態にして試してみました。

配列リスト STLリスト
最大オブジェクト数 2000
処理フレーム数 6000
削除確率 0/256
発生確率 0/256 277ms 482ms

ということで、速度が問題になるような場合、STLはおすすめできません、という結論になりました。もちろん、STLと一口にいってもいろいろなメーカが出しているので（ヒューレットパッカードやシリコングラフィックスなど他に知らないなぁ）一概に遅いと言う気は全くありませんのでご注意ください。また、Visual C++にしても、もしかしたらSTLを爆速にする設定があるのかもしれません。ってゆーか、あったら教えてください(笑)。
いけてねぇ～補足(2001/03/04)
匿名感想でテスト方法がおかしくないですか～？との指摘を受けました。で、具体的な点についても書かれていたのでプログラムを見なおすことにしたのでした。
こ、これは････テスト方法がおかしいとは失礼な!!
プログラムがおかしいじゃないですか!!
でこまごまと適当に修正。今度は多分、ましになってるはず(笑)。使用したプログラムはこちら16-chara2.cpp (3282 bytes)です。結果はこうなりました。

配列リスト STLリスト
最大オブジェクト数 2000
処理フレーム数 6000
削除確率 4/256
発生確率 4/256 7700ms 4980ms
PentiumII 333MHzで実行

匿名希望さんも指摘していますが、この場合の処理の違いは STL の list で使われるセルに対する new（もしかしたら delete も含むんでは？）で、これが速度の違いに出ていることは第18回において巡回速度に違いがないことが明白チッくです。そのあたりの話題についてはそのうちふれることになるんじゃないでしょうか。
おまけ。高速な矩形衝突判定ですが、やしょくくんに強くすすめたところ、「if文の方が速いんじゃないですか？」と言われて、試したところ、 if文の方が速かったです(笑)。これはおそらく、状況設定が問題で、矩形の衝突がほとんどないような状況では、 if文でさっさと分岐してしまえば予測ミスのペナルティを加えても速い、ということだと一人で納得したのでした。その結果、ぎゃるぱにＸでは使わなくなったのですが(笑)。では。
*STL：Standard Templete Libraryの略。よく使うリスト構造などを C++ のテンプレート化することにより、開発効率をあげることができる。かなり標準になりつつあるので、プログラマの必修事項、らしい。

忙しいです・・・。それにしてもパーシャルレジスタストールの回避ができなくてすげ～困ってます。 Intel最適化マニュアルにも有用な情報は載ってないし・・・。ま、それはそれとして、きついループを書いているのですが、そんなときに困るのがレジスタが足りなくなることです。 DirectDrawSurfaceへのアクセスを考えた場合には、二次元配列としてアクセスせざるを得ないので、二重ループとなることは避けられません。こんなとき、ループカウンタにレジスタを使うと、それだけで二つのレジスタが使用できなくなってしまいます。極端な話、６重ループなんてことになったら、それだけでレジスタがなくなってしまいますねぇ。
そんなとき！、複数のループカウンタを一つにまとめることができれば、それはそれは助かります。複数の値を一つにまとめる、と言えば、ハードウェア的にできることがあります。 eaxレジスタにおける alとahレジスタです。それぞれに値を割り振れば、一つのレジスタで二重ループに対応できそうです。ところが、よくよく考えてみなくても8bitレジスタでは高々256回しかループできません。 640x480なんて画像どころか、320x240の画像でさえ、使えません。使えねぇ～。
さて次に考えるのは、任意のビットフィールドに分割し、 andをとってカウントする方法です。こんな感じですね。
--------------------------------------
    mov eax, HEIGHT<<16
 y_loop:
    or  eax, WIDTH
 x_loop:
    ....
    dec eax
    and eax, 0xffff
    jne x_loop

    sub eax, 0x10000
    and eax, 0xffff0000
    jne y_loop
--------------------------------------
上位16bitをyループカウンタ、下位16bitをxループカウンタとして使います。 xループを抜けたときには、下位16bitは0x0000になっていることを考慮すると、実は
    and eax, 0xffff0000
は必要なかったりします。とはいえ、パフォーマンスに大きく影響する内側のループで命令が多くなっているのはいただけません。なんとかしたいところです。
そんなあなたに！ビットフィールドの許す限り、多重ループに対応できる手法を使いましょう。いろいろ説明するよりも燃えろっという感じでコードを示してしまいましょう。
--------------------------------------
    mov eax, HEIGHT-1
 y_loop:
    or  eax, (WIDTH-1)<<16
 x_loop:
    ....
    sub eax, 0x10000
    jns x_loop

    sub eax, 0xffff0001
    jns y_loop
--------------------------------------
それでは説明です。この手法では上位から順番に内側からループカウンタを割り付けます。コード例では、xループが内側なので、上位16bitにxループカウンタを、下位16bitにyループカウンタを割り付けます。ループの終了条件にnon zero（0でない）を使うとマスクをとらなければならないので、 non positive（負でない）を使います。そのために初期値を-1しておくのは言うまでもありません。内側のxループではxループカウンタから1ずつ引いていき（0x10000引く）、負になったらループの外に出ます。
内側のxループから抜けた後を見てみます。抜けたときのカウンタの状態を考えると、負になったためにxループを抜けているので、上位16bitは 0xffff になっているはずです。一方、下位16bitを考えると、こちらにはyループのカウンタがそのまま入っていることになります。たとえば、こんな感じです。
eax : 0xffff 0013
さて、外側の終了条件を考えましょう。せっかく内側のループで無駄な演算なしで制御できたのですから、外側のループもそうしたいわけです。外側のループが終了するときのループカウンタの状態はこんな感じになっているわけです。
eax : 0xffff 0000
このときにうまく終了判定ができるようにしたいわけです。当然、下位16bitカウンタも-1したいので、とりあえず、
sub eax, 0x???? 0001
は決定です。そうなれば、あとは上位をクリアすることを考えて
sub eax, 0xffff 0001
とするのはもはや論を待たないでしょう。というか、説明のしようがないわけですが(笑)。
さて、これがうまく動くかを見ておきましょう。内側のループが問題ないのはいいですね。問題は外側のループです。外側のループが終了しない場合を考えます。
eax : 0xffff 0013
---------------------
sub eax, 0xffff 0001
---------------------
eax : 0x0000 0012
オッケーですね。では終了する場合を見てみましょう。
eax : 0xffff 0000
---------------------
sub eax, 0xffff 0001
---------------------
eax : 0xffff ffff
ばっちりです。演算結果が負になっているので、ループを抜けることができます。
さて、yループを抜けたときの状態を見てみると、 yループカウンタ部とxループカウンタ部の両方が 0xffff になっています。 yループに対するxループカウンタの動作を考えれば、多重ループに拡張することができます。それでは640x480x256の三重ループに拡張してみましょう。 640は10bit、480は9bitで表現できます。ということで、上位から10bit、9bit、残りという割付けをします。
--------------------------------------
    mov eax, DEPTH -1
 z_loop:
    or  eax, (HEIGHT-1) << (32-10-9)
 y_loop:
    or  eax, (WIDTH-1) << (32-10)
 x_loop:
    ....
    sub eax, 0x0040 0000
    jns x_loop

    sub eax, 0xffc0 2000
    jns y_loop

    sub eax, 0xffff e001
    jns z_loop
--------------------------------------
引く値がいやらしい気がしますが、こんな感じですね。実際問題として、レジスタ幅は32bitですから、三重ループが限界っぽい気がしますが、命令数の増加なしで、かつレジスタ数の増加なしで対応できるのは、それなりに価値がありそうです。
問題があるとすれば、すでに誰かやってて、何をいまさら、と言われることぐらいです(笑)。それでは。

前回の「STLは遅い」の回のすぐあとだと思いねぇ。
やねさんに「listが遅い原因を追求せよ」との指令を頂いてしまい、ってゆーか、指令がなくても不思議に思っていたのでlistが遅い原因を追求すべく、STLのソースを読もうとしましたが・・・わからん・・・。 templeteを使えない人が読むのは困難な気が(笑)。
そんなことを言ってあきらめても始まらないので、さーっと流してみました。当然のことながら読み始めは list からです。
STLのlistが単に走査するだけでも遅いことを考えると、まっさきに気になるのはiteratorです。こいつでいろいろ処理しているとすれば、走査が遅いのもうなずけます。さて、listのiteratorを定義している部分を見てみると、const_iterator classを継承しています。試しに、前回のコードを const_iterator にしてみましたが、結果はほとんどかわりませんでした。ということは、const_iteratorを使っていないことは特に問題ではないということです。一応、ソースを読む上での話を簡単にするため、const_iteratorの方を読むことにします。 ++演算子は
	const_iterator& operator++()
		{_Ptr = _Acc::_Next(_Ptr);
		return (*this); }
となってます。気になるNext近辺を見ると
	struct _Acc {
		typedef _REFERENCE_X(_Nodeptr, _A) _Nodepref;
		static _Nodepref _Next(_Nodeptr _P)
			{return ((_Nodepref)(*_P)._Next); }
です。Nodeprefを定義しているマクロは xmemory にありました。
 #define _REFERENCE_X(T, A)	T _FARQ &
なんのことはなく、単にキャストしているだけですね（違ったらやだな・・・）。つまり ++演算子では単にリンクをたどっているだけ、ということがわかりました。このプログラムを見る限り、なんら遅くなる原因はないようです。
次に気になるものといえば・・・そうです、 listに突っ込むオブジェクトへのポインタの扱いです。もし、listに格納されたオブジェクトのメソッドを呼び出す際にオーバーヘッドが存在していれば、遅くなることが十分に考えられます。
イテレータからの参照は、
 list＜object *＞::iterator itr;
 (*itr)->method( );
という形になるので、listのiteratorの定義を探します。
		const_reference operator*() const
			{return (_Acc::_Value(_Ptr)); }
さて、Valueの定義は
		static _Vref _Value(_Nodeptr _P)
			{return ((_Vref)(*_P)._Value); }
です。さらにVrefの定義は
		typedef _A::reference _Vref;
クラスAのreferenceは、
template ＜class _Ty, class _A = allocator＜_Ty＞ ＞
となっているところを見ると、デフォルトで allocatorクラスに referenceの定義があるようです。 referenceは xmemory で定義されていました。
template＜class _Ty＞
	class allocator {
public:
	typedef _Ty _FARQ& reference;
ようするに、クラスへのポインタにキャストしているだけということがわかりました。これですべての材料がそろったので見なおしてみましょう。・・・あれ？特に重そうな処理がありません・・・。おかしいです。いったい、何が原因なのでしょう。
ここで１ヶ月放置(笑)
ある日、やねさんのとこに遊びに（ラチられに？）いって話していて、原因が判明しました。このあたりの話しは、やねさんのホームページでばらされてしまいました。おそらく、僕の発言に危機感を持ったのでしょう(笑)。ところが、このやり取り、細部において僕の記憶と異なるのです。というわけで、一昔前のザッピングではありませんが、僕の記憶にあるやり取りをここに公開しておきます。
遊びに行った後に、自転車で雨の中１時間走ったり、馬車道で制服を楽しんだり、酒飲んだり、車で熱い走りを楽しんだりしたので、実際とは多少異なっているかもしれません(笑)
さ～「std::listの実装が双方向ポインタであることは関係ないと思うんですよ。イテレータで巡回するときに遅いわけですから」

やね「そうですね。実験で比較したときの要素は、いくらでしたっけ？」

さ～「１０００ぐらいだったと思いますが」

やね「んっ！？１０００ですか？双方向ポインタになっているということは少なくともサイズは８バイトありますよね。１０００あったら、8Kなので、すべての要素がL1キャッシュ(実験に使っていたMMXマシンでは8K)に入りますか？」

さ～「あっ。そうか！いけてねぇ（笑）」

やね「ホームページのほうどうしましょうか＾＾」

さ～「知らぬ存ぜぬで押し通しましょう（笑）」
このセリフが違うのです。正しくは
「こっそり消しときましょう(笑)」です。

やねさんは一瞬固まった後、
やね「もしそんなことしたら月にコロニー落としちゃうよ(笑)」

え？コ、コロニーですか？よりによって月に？そりゃかなわんなぁ～。う～ん、このまま引っ込むのもアレだしなぁ～。え～ぃ、いやがらせしてやれ(笑)

さ～「わかりました、先生(笑)。」

やね「それはやめてくださいよ～」

ということで、なかったことにはできなさそうなので(笑)、更新するわけです。でも、僕だってやねさんに言いたいことはあるのです。
めっさげ下さい。

さて、そんなこんなでやねさんに先に報告されてしまった以上、僕のほうでも書かざるをえません(笑)。書くためには一応計測をする必要があるので、１日１弾幕のノルマをこなしてから計測に入りました。
予定としては簡単です。要は std::list が双方向ポインタでセルサイズが大きいなら、自前のリストも双方向ポインタにしてセルサイズを大きくすればいいのです。早速構造体に
	struct tag_SObjectCell *prev;
と書き足して、実行してみました。 1000個の要素をリストに追加して、6000x(998回next)した結果です。

std::list 510
自前list 73
PentiumII 333MHz, Windows95 OSR2.5 ありゃ、おかしいです。サイズが原因ではなかったのでしょうか。アセンブリコードを見てみると・・・ほとんど同じです。厳密には、自前listの方が、構造体へのポインタからnextポインタを得るためにoffset値を加える命令分だけ、つまり１命令多くなっています。
となると、やはりサイズが原因なのでしょう。ためしに、構造体のメンバを増やして、同じぐらいの時間がかかるようにしてみました。具体的には、こうしました。
	#define N 4
	struct tag_SObjectCell *prev[N];
Nの値を増やすと構造体のサイズが大きくなる、ということです。

実行時間（ms） sizeof(SObjectCell)
std::list 510 ---
自前list N=1 74 12
自前list N=2 75 16
自前list N=3 320 20
自前list N=4 405 24
自前list N=5 459 28
自前list N=6 514 32
自前list N=7 514 36
自前list N=8 514 40
自前list N=9 515 44
自前list N=10 515 48
・・・
自前list N=20 515 88
PentiumII 333MHz, Windows95 OSR2.5 ・・・この結果は・・・。とりあえず、std::listのセルがかなりの大きさであろうことははっきりしました。それはいいとして、自前listのセルサイズが大きくなっても実行時間が変わらないのは何故でしょう？ PentiumIIのL1キャッシュはデータ16KByteですから、
16000/1000要素=16Byte
です。これで16Byteと20Byteのしきいはわかります。さて、キャッシュがいっぱいになった場合、次に読みこまれた値はキャッシュのどこに書き込まれるでしょう？ http://www.csl.sony.co.jp/person/fnami/pentopt.htmによれば、「キャッシュラインのうち最近使われていないほうに」とあります。今、listを順に見ているとすれば、最近使われていないほうは、「listの先頭のほう」ということになります。
このように考えると、ちょうどよいことに、 20Byte～28Byteまで徐々に遅くなり、 32Byteで飽和していることを説明できます。言葉で説明すると大変なので、図を示しましょう。
図で上段の棒がデータです。前からキャッシュに格納され、いっぱいになった分は再びキャッシュの前のほうから上書きしていきます。 n回試行した場合、２回目以降の試行ではキャッシュに入っていれば、ウェイトなしでアクセスできます。 16～28Byteまでは前回のデータが残っています。 32Byteは前回のデータはすべて上書きしていることになります。これで、16～32Byteの計測結果は説明できます。
さて、それでは、32Byte以上はなぜ同じ値になっているのでしょう？答は簡単です（といいつつ、少し悩みました）。試行プログラムでは構造体の中のメンバにはアクセスしていないので、構造体をまるごとは読みこんでいないからです。単に、nextポインタのある32Byte（キャッシュラインのサイズです）をごそっと読みこんでいるので、32Byte以上のサイズであっても、読みこむデータ量は32Byteと同じになるのです（おお！）。
ようやく計測結果の説明が終わったところでふと我に帰ってみると・・・なんか、無意味なこと説明しているような・・・(笑)。
本題に戻りましょう(爆)。では、std::listのセルはいったいどのくらいのサイズになるのでしょう？ということで、
sizeof(list)
を表示してみると、12でした。この書き方で得られるのかがかなり謎なんですが(笑)。 12という値と計測結果は異なるので、
class Cchara
 {
 public:
	bool process(void);
 };

	...

	Cchara *cP[3];
	cP[0] = new Cchara;
	cP[1] = new Cchara;
	cP[2] = new Cchara;
	printf("%x %x %x\n", cP[0], cP[1], cP[2]);

	objs.push_back(new Cchara);
	objs.push_back(new Cchara);
	objs.push_back(new Cchara);
	for(list::iterator itr = objs.begin( ); itr != objs.end( ); itr ++)
	 {
		printf("%x ", *itr);
	 }
	printf("\n");
としてみました。結果は、
760e30 760e20 760e10
760e00 760dd0 760da0
となりました。逆順になっているのは、スタックにとられたからでしょう（２分悩む）。問題はアドレスの飛びです。単に配列に放りこんでいる方は、クラスサイズがアラインされた結果だとすれば納得できます。一方、std::listに放りこんでいる方は、 48Byteも離れています。これは一体なんなんでしょう？ 16Byteは Cchara分だとして、双方向リストに32Byteも必要だというのは解せません。これについては結局わかりませんでした。
ここまでの結果からでも一応結論は導き出すことができます。

std::listはセルサイズが大きい。

さて、std::listは遅いのでしょうか？実際の利用を考えると、リストをただ見ていく、ということはそうそうありえません（n番目の要素、ということですから）。必ずセル内の要素へのアクセスがあります。そのことを考えると、キャッシュを考慮にいれた走査の話はかなりナンセンスな気がします。 prev/next部分のアセンブリコードを見ても、自前listと同等のコードを生成しているので。
これで、STLのlistについての話しは終了ですが、意見を頂きましたので、それについて。

std::listはiteratorで走査しながら、 size()を割り出します。毎回ループでsize()を行うとN^2時間がかかるわけです。 std::listをカスタマイズし、要素数を自前で管理すればよいでしょう。
カスタマイズするのは嫌だなぁと思い(笑)、listプログラムを読んでみました。
・・・
う～ん・・・。どうも走査はしていないようです。一応、確認してみました。
	for(i = 1; i < objs.size( ); i ++)
		itr ++;

	for(i = 0; i < 999; i ++)
		itr ++;
1000個の要素を追加した状態で、上の２つを計測・比較しましたが、実行時間は同じでした。もしかしたら、STLが新しく書きなおされているのかもしれません。毎回走査してsize( )を割り出すのが標準だったら、みなさん納得できないでしょう。僕は納得できません(笑)。ちなみに、使用した list はVisual C++6.0付属のHewlett-Packard製です。他の製品では異なるかもしれませんね。と、ここまで書いて、「そう言えば、SGIのSTL持ってたなぁ～」と思って、見てみると・・・
  size_type size() const {
    size_type __result = 0;
    distance(begin(), end(), __result);
    return __result;
  }
・・・おぃ、なんだよ distance って(笑)。あからさまに数えてねぇか？一応、確認しておくか・・・
inline void distance(_InputIterator __first, 
                     _InputIterator __last, _Distance& __n)
{
  __distance(__first, __last, __n, iterator_category(__first));
}
ここじゃないな・・・
#define __ITERATOR_CATEGORY(__i) iterator_category(__i)
う～ん、ITERATOR CATEGORYの定義が見つからない・・・。まぁ、でも近辺を見ると
inline void __distance(_InputIterator __first, _InputIterator __last,
                       _Distance& __n, input_iterator_tag)
{
  while (__first != __last) { ++__first; ++__n; }
}
とあるから、数えてるんでしょう。もう目が疲れたのでプログラム読むのはやめます・・・。
今回の結論。 SGIのSTLを使っている人はHewlett-Packard製に乗り換えましょう。終わり。
とか言ってると、SGIのSTLが書きかえられてたりするんだよなぁ(笑)。と思って、SGIのドキュメントを疲れた目をこすりながら開くと、トップページの下の方に
Copyright (C) 1994 
Hewlett-Packard Company 
の文字が・・・。なぜだぁ～なぜなんだぁ～。 SGIのSTLは1996年製なのになんで遅くしてるんだぁ～。 Design DocumentsのThread Safetyがその答えのような気はするのですが・・・。
The SGI STL implementation removes all nonconstant static data from container implementations.
もう疲れました。STLの話はこれで終わらせたいです。 STLは自己の責任の元に選んでください(笑)。僕は時代に逆行して自前で突き進み・・・ません。必要があればそうしますけど。
ちなみに、STLのソースコードはそれなりに面白いです。定義部分をたどるあたりが。勉強にもなるので、ある程度のデータ構造とアルゴリズムを知っているのなら眺めてみるのもよいかと。でわ。

やねさんからの仕事を「オーバーワークです」の一言で撥ね付け、一息ついていたところ、謎さんから「この羽、６枚動かしたいんだけど」と、ひょえぇ～となりつつも、プレーンの取り方を工夫することでなんとかしのいでいたのです。ところが、つい先日、ゲスト弾幕プランナーのいるまかみりさんからの弾幕案を見て・・・これ作るんかぁ～。とてもではありませんが、現状のトロい回転ではどうにもならなそうです。
ということで、ある程度遅くなる＋スペックを必要とするのはしょうがないとしても、話にならんのはいや～ん、ということで、アルゴリズムの再検討に入っていたのです。
で、いろいろ検討中でしたが、回転のテストプログラムを書いているところでふと気が付きました。ブレゼンハム使ったら、誤差あるんちゃう？
ここで話をはっきりしておきましょう。直線を描画する場合においては、誤差は含まれません（はずです）。その流れでブレゼンハムのアルゴリズムを使って拡大縮小、さらに回転までしてしまおう、ということなのですが、拡大縮小はともかく、回転にブレゼンハム使ったら、まずいだろ～、というのが、今回の主題です。
ブレゼンハムおよび、拡大縮小・回転については、 Fussyさんのページのアルゴリズムのページが詳しいのでこちらを参照してください。自分で書いてみたら、わけがわからなくなりました(笑)
ということで、具体例の説明です。まず、srcからdstへ回転する場合、 dstを基準にsrcへ逆回転を行って対応する点をとってくることはいいでしょうか。このようにすることで、dst側の画像に抜けがおこることを避けられます。
それでは説明に入りましょう。軸に平行な正方形を理想的に45度回転した場合を考えます。これは、図1のようになるでしょう。

図１：理想的な45度回転したときの矩形の輪郭

この回転は、４頂点の座標を変換し、それぞれの辺に対してブレゼンハムを適用することで、描画することができます。実際のプログラムでは変換の際の誤差がつきまとうので、このように回転することでさえも意外に難しかったりします。話を簡単にするため、このように回転できたとして、矩形の回転複写をするために、１ラインずつ複写を行います。このとき、dst側の１ラインは10ドットで構成されていますが、 src側の１ライン（斜めになっていますが）は、7ドットになっています。このため、1:1対応で複写することはできないので、この対応に関してもブレゼンハムを適用することになります。この結果を図2に示します。

図２：45度回転における１ライン目の複写結果

次に、dst側の複写ラインを１ライン上に移動します。これに対応してsrc側の複写ラインを移動しなければなりません。今、src側の複写ラインの始点・終点もブレゼンハムで決定しているとすると、始点・終点は必ず矩形の外縁上にのることになります。 1x0.707=0.707なので、src側は1dot進まないことにします（進んでも同じことになります）。複写ラインが決定したので、そのラインについても複写をしましょう。この結果、図3のようになります。

図３：45度回転における２ライン目の複写結果

さらにdst側の複写ラインを１ライン上に移動します。 src側の複写ラインは、2x0.707=1.414なので、src側がようやく1dot進みます。複写の結果を図4に示します。

図４：45度回転における３ライン目の複写結果

この作業を繰り返すことで矩形をすべて描画することができます。実際に手作業で繰り返したのですげぇ～疲れました(笑)。その結果を図5に示します。

図５：45度回転の複写結果

それでは考察に入りましょう。今までの過程をなぞると、複写に利用しないピクセルが存在することがわかります。逆に考えると、複写に利用しないピクセルはどんな色でも構わないわけですから、図6のような回転を行うことがありうるということになります。

図６：抜けている画像の45度回転の様子

ブレゼンハムでは誤差がないはずだったのに！
なぜなんでしょう？答は簡単です。src側の複写ラインを決定する際に、ドット単位にするため、値を切り捨てているからです。したがって、誤差をなくすためには、複写ラインをスキャンする際にも、複写ラインを決定するために使用した倍率を使用しなければおかしいのです。と言っても、わけがわかりませんね。
dst側の矩形を DstWidth x DstHeight 、src側の矩形サイズを SrcWidth x SrcHeight とします。 src側の複写ラインを決定するためには、基準となる点（0,0）から何ドット進んでいるかを決定しなければならないので、 DstHeightとSrcHeightの間でブレゼンハムを使用します。このとき、誤差をなくすためのスケーリングに大きい方の値、この場合はDstHeightを使用します。その後、複写ラインに沿って複写をするために、複写ライン上を何ドット進んだかを決めるために、 DstWidthとSrcWidthの間でブレゼンハムを使用します。このとき、単純に考えれば、誤差をなくすためのスケーリングにはDstWidthが使用されます。しかし、ほんとうに誤差をなくすためには、スケーリングは DstHeight x DstWidth でなければいけないのではないでしょうか？さらに、複写ラインの最初のドットから何ドット進んだかも、最初のドットがどこにあるかでオフセット値も変わってくるはずです。（せめて、用語の定義ぐらいしないと単語がどの値を指しているかもわかりませんねぇ。この段落はわかんなくていいです）
そんなこんなで、わけがわからなくなってきたので、プログラムを書こうかと思ったのですが、あまりに後ろ向きに面倒だったので、正直に回転するプログラム19-rotate.lzh (67709 bytes)だけ書いてみたので、誰か、ブレゼンハムで回転するプログラム、書いてください(笑)。全周回転する必要はありません。0-45度の範囲でＯＫです。
というような主張を考えたところで、 Fussyさんのページにある説明を読んでいたのですが、 4連結のアルゴリズムで複写すれば問題が回避されそうな気が一瞬だけしました。しかし、ブレゼンハムでの回転の一番の問題（だと勝手に思いこんでいる）は、チェック模様を45度回転したときに単色になることであり、その問題に付いては4連結でも回避できないので、やっぱりブレゼンハムを多重に使用する場合の誤算なのでしょう。じゃあ、どないせっちゅーんや、というわがままな人のために、次回は、ブレゼンハムに替わる誤差をほとんど考えなくて良く、さらにブレゼンハムよりも高速である可能性のある（ややこしいなぁ・・・）、手法について提案したいと思います。
と風呂敷を広げておいてなんですが、あんまり期待するとがっくりくるので期待しないように(笑)。でわ。

実は、この回は前回よりも先に文章ができていたりしたのですが、全体の流れとして、こっちが後だろう、ということで後回しにしたのでした。それはともかく、先日、定例会で車を放置していたところ、初心者マークもってかれました。う～ん、なんなんでしょうね。予備もあったし、もういらなくなったので、それ自体は別段痛くも痒くもないのですが、別件でダメージを受けていたのでした。それはともかく、１万４千円はちょっと高い気がしますな。
と、わけのわからない戯言はおいといて、本題に入ります。さて、前回はブレゼンハムを回転に用いる場合の問題点について、考察しました。その結果、ブレゼンハムを適用したからといっても、なんでもかんでも誤差がなくなるわけではないことがわかりました（って、こう書くとあたりまえだな・・・）。ちなみに、いくつか今回の内容を予想された方もいらっしゃいましたが、満点はいませんでした（偉そうやな・・・）。これについては、正解を示した後で説明しましょう(^^;。
そして、今回は、実用上、誤差をほとんど考えなくて良く、さらにブレゼンハムでは必須である条件判定を用いずに、ブレゼンハムと同様の扱いができる手法を提案するのです。それにしては、やけに腑抜けたタイトルですね。でも、このタイトルを得るまでに丸１日以上考えているのです（暇なんかなぁ、僕）。ちなみに、前回の文章を書ききるまでには４、５日はかかってたりします。なんでかって～と、布団の上でねっ転がって書こうとすると、２、３行書いて寝てしまうからなんですが。
ところで、ブレゼンハムの簡単な説明を思いついたので、ちょっとそちらを紹介してみましょう。多分、どこかで誰かがすでに同じ説明をしてると思いますが。まず、(0,0)-(dx,dy)へ線を引くとします。話を簡単にするため、0＜dy＜dxとします。つまり、傾きが0度より大きく、45度未満であるということです。
この線分をピクセルスクリーン上で表現するのですが、当然、ピクセル単位のつながりで表現しなければなりません。これを実装する例として、線分が通過しているピクセルを描画するという手法があります。ピクセルが無駄に多くなると線分が汚く見えるので（アンチエリアシングをかける場合は話が別です）、ピクセルの左端と線分が交差しているピクセルを描画するとします。これは図１のようになります。

図１：ピクセルスクリーンにおける線分の描画
これをプログラムで実現するにはどうしたらいいでしょう。簡単ですね。X=xの点は、 y=(dy/dx)*x（単なる直線の式です）ですから、(x, (dy/dx)*x)です。このときのY座標の小数部を切り捨てれば、どのピクセルかが決まります。 X=xにおけるY座標値yを整数部yiと小数部yfで表すとすれば、 y=yi+yfとなり、(x,yi)のピクセルが描画されるというわけです。
次に、二つの隣接するドットに注目してみます。 X=xの点が求まっているとして、X=x+1の点はどうなるでしょう？ X=xにおけるY座標y1は、

y1=(dy/dx)*x

ですから、X=x+1におけるY座標y2は、

y2=(dy/dx)*(x+1)
　=(dy/dx)*x +(dy/dx)*1
　=y1 +(dy/dx)

となります（あたりまえ）。
さて、y2=y2i+y2fとしたとき、 y2iの値はどうなるでしょう？ y1f+(dy/dx)>= 1.0であれば y2i=y1i+1、そうでなければ y2i=y1i ですね。つまり、小数部に傾きを加え、これが１以上であれば、ピクセルのY座標も１増えるということです。これをプログラムにすると、
01:float dy, dx;    // 終点座標
02:int   yi = 0;    // 描画ピクセルy座標
03:float yf = 0.0;  // y座標小数部
04:for(x = 0; x <= dx; x ++) {
05:    pset(x, yi);       // ピクセルを塗る
06:    yf = yf + (dy/dx); // 傾きを加える
07:    if(yf >= 1.0) {    // 小数部の累積が1になったら
08:        yi = yi +1;    // 1ピクセル上にあがる
09:        yf = yf -1.0;  // 小数部なので。
10:     }
11: }
となります。ここで、dy/dxの値に誤差が含まれる場合があることに気づいてください。これに誤差が絶対含まれないと思う人はブレゼンハムは必要ありません(笑)。ブレゼンハムでは、このdy/dxをどうにかしてしまうわけです。そのために、やねさん曰く、「物事をスケーリングしよう」なのです。
その方法が、dy/dxをどうにかしたいなら、dxをかけてしまおう、ということなのです。 dy/dxをどうにかするために、dy/dx*dxとして、分母をとっぱらってしまいます。さて、その影響はどこにでるでしょうか。プログラムでdy/dxを加えているのは、yfです。ということで、yfに関係している部分を修正しましょう。 yfに関係している行を見ると
03:float yf = 0.0;  // y座標小数部
06:    yf = yf + (dy/dx); // 傾きを加える
07:    if(yf >= 1.0) {    // 小数部の累積が1になったら
09:        yf = yf -1.0;  // 小数部なので。
ですね。 3行目はdx倍しても修正はいりません。厳密に言えば、 float型から整数型に変更するぐらいです。げたをはかせる場合は修正が必要です。 6行目は
06:    yf = yf + dy;
になったのでした。 7行目の比較対象の1.0は、スケーリングによって影響を受けています。では、何倍すればいいでしょう？はい、そこのアナタ、正解です。 dx倍です。dy/dxをdy/dx*dxにしたのですから、当然です。ということで、
07:     if(yf >= dx) {
になりました。 9行目で引いている値は、何倍にするかを考えるまでもなく、比較対象と同じ値ですから、
09:       yf = yf -dx;
となります。これで基本的なブレゼンハムは完成です。あとは四捨五入や特定角度における高速化など、好きに料理してください。
さて、ここでは線分を描画するためにブレゼンハムを使用しましたが、ちょっと見方を変えるといろいろな用途があるわけです。考え方は簡単です。要するに、２つの値があったとしたら、片方をdx、もう一方をdyにすればいいのです。
さて、ようやく本題に入れます。両端から線を引いていくアルゴリズムにしろ、ブレゼンハムを使う場合には条件分岐が必要になってきます。この条件分岐を回避したいのです。どうしても。ということでずっと考えていたのですが、簡単な結論がでました。話は実に簡単で、 0＜y＜xとして、(0,0)-(x,y)の直線を引く場合、スケルトンはこうなります。
int py = 0;
int c = -x;
for(int px = 0; px ＜= x; px ++)
 {
    pset(px, py);
    c += y;
    if(c >= 0)
     {
        c -= x;
        py ++;
     }
 }
この中のif文が問題なのですね。実際にこれがどれだけのネックになるのかはわかりません。なんとなく、PentiumPro以降の分岐予測では、ほとんど全部の場合が予測できてしまう気もします。まぁ、それはともかくとして、それでも分岐がないに越したことはありません。そうそう、余談ですが、何を加えて、何と比較して、何を引けばいいかですが、 x*yを思い浮かべると簡単です。 xをカウンタにしてループすると、最終的にx*yまで加算すればいいのです。ということで、加える数はyになります。一方、 Y軸方向への移動は、y回必要ですから、 x*y/yということで、 xと比較します。当然比較する値を引かなきゃいかんので、引く値はxになりますね。いじょ。
また話がそれました（それてばっかりだな・・・）。 if文での判定対象のxを2のn乗になるようにすれば、
py=c＞＞n;
として、シフトだけで求めることができるはずです。
それはまぁ、当然のことです。となると、自由な直線を引くにはどうすればいいでしょう。答は簡単です。2のn乗になるように値を変更すればいいのです。目的の地点までの線はループの回数を制御することで引くことができるはずです。たとえば、xを2の8乗＝256にするとしましょう。
x:y = 256:ny
として新しいnyを求めれば、if文なしでブレゼンハムを実行できます。というのが今回の提案です。もちろん、この場合は問題があり、誤差をうまく表現できない場合には nyが困ったことになります。
ある程度の限定をすれば少しはましになります。それは簡単、
x:y = 1024:ny
とすれば、４倍の精度になります。なぁんてことを考えていたのですが、この手法、よくよく考えると、 x/yを固定小数点で表現しただけの話なのでした(笑) いけてねぇ～
とはいえ、画面描画に限定するなら、-1024～+1023の範囲もあれば十分です。整数型を32bitとすれば、11bitを整数部に割り当てた固定小数点での表現です。小数点以下は(32-10-1)=21bitもあるので、実はかなりの精度を持っていることになります。ちなみに、1/21bitは0.00000048です。画面描画ならこれだけの精度があれば問題ない気がしますが、これに関しては実際に検証してみないとわからないですね。僕としては、ゲームに使うぐらいで、さらにリアルタイムでの動画なので、十分だと思ってます。
一応、プログラムで確認してみました。 (0,0)-(1023,y)までの直線を 0＜=y＜1023 の範囲において、

ブレゼンハムを使用
固定小数点を使用
の２通りで描画（実際には各x座標におけるy座標の値を求め）し、この線が同じ線であるかを検証してみました。プログラムはこちら20-btest.cpp (1166 bytes)です。
実行結果
0～1023の範囲において、小数点以下21bitの精度では、全く同じ直線が引けました。へへっ、燃えたろ？少しパラメータを変更してみたところ、小数点以下20bitではところどころでずれます。とはいえ、ずれるのは当然のことながら1dotなので、動画における回転・拡大・縮小にはほとんど問題がないでしょう。
しかし、このままでは、ブレゼンハム至上主義者（いるのか？）から、「始点と終点を通ることが保証できないではないか」と怒られてしまいます。始点は必ず通るとして、終点を通らない場合とはどのような場合かを考えてみましょう。
論点を間違わないように、前提をはっきりしておきます。 (0,0)-(x,y)の線分を引くのですが、四捨五入を省略するために、(0,0)からではなく、 (0,0.5)から引くように値を設定します。ですから、内部的には、 (0,0.5)-(x,y+0.5)に線分を引こうとし、画面にプロットする段階で小数点以下が切り捨てられて、 (0,0)-(x,y)の線分が得られるということにします。
さて、終点を通らない場合を考えていたのでした。それは、四捨五入の場合です。今考えている前提では、切り捨てによる場合となります。つまり、1.0となるところが、誤差によって0.9999とかいう値になり、切り捨てで0になってしまう場合です。となれば、これを回避することは簡単です。始点の位置をその誤差分だけずらしてあげれば必ず終点を通るようにすることができます。たとえば、2.0であるところが1.999になって終点を通らないのであれば、始点の位置を0.501から始めれば、1.999は2.000になるわけです。簡単ですね。
と書くと、絶対に
「初期値を加えすぎて、始点を通らなくなったらどうするんだ」
と、何も考えずに文句を言う人がいるはずです(いるのか？)。そのような人には、素晴らしい言葉を進呈させてもらいます。
「アホか～、誰がそんなに加えるんや～」
それでは、アホ１号の僕が、そのような考えがいかに間が抜けてるかについて説明しましょう(^^;。
初期値を加えすぎて、始点を通らなくなる場合はどのような場合でしょうか。答えは、「初期値の0.5が、1.0以上になった場合」です。あたりまえです。さて、今は、小数点以下21bit、整数部10bitの精度であるとして論じています。と、いうことは、初期値の0.5が1.0になるためには、固定小数点表現上の0.5、 32bit値において1＜＜20だけ誤差が累積する必要があります。
さて、命題「補正しすぎて始点を通らなくなる場合はあるのか」から、補題「誤差が1＜＜20以上になるのか」を論じればいいようになりました。そういえば、誤差はいつ発生するのでしょうか？そう、これはそもそも直線の傾きy/xを計算したときの値で、その割り算をしたときに発生するのでした。このとき、固定小数点に変換するので、実際には(y＜＜21)/xで求まるわけです。その結果に含まれる誤差が累積したときの話だったのでした。
誤差をεと置くと、固定小数点表現でε＜(1>>21)、 32bit値ではε＜1です。ということは、誤差が1＜＜20まで累積するには、誤差εを含んだ傾きを(1＜＜20)回以上加えなければいけません。ちょっと待ってください。 1＜＜20回ですか？整数部は10bitしかとっていないのに？いったい何ドットの線を引こうとしているのですか？ということで、「誤差が1＜＜20以上になるのか」の答えはNoであり、したがって、「補正しすぎて始点を通らなくなる場合はあるのか」の答えもNoになります。
あれ？なんかおかしいです。そうです。初期値に補正をかけた結果が0.5から1.0にはならない、のであれば、補正をかけないで線を引いたときに、 (x,y+0.5)が(x,y-0.000001)にはならない、ということです。したがって、符号1bit、整数部10bit、小数部21bitの固定少数点表現において、「補正は必要なく」、また、「線分は始点および終点は必ず通る」と結論づけることができます。
と、ここまで書いておいてアレですが、 1ドットの違いにこだわる人に対して、今のＣＧのことを簡単に紹介しておきたいと思います。現在のコンピュータにおいてでも、すべてのデータをリアルタイムで表示することは不可能です。で、どうするかというと、一部のデータをどうにかするわけです（どうにかってなんだよ～）。表裏のあるポリゴンについて法線方向が裏向きのポリゴンを非表示にしたり、視体積外のポリゴンを表示しない、といった方法が有名どころです。
また、本当に遠くの景色はテクスチャとしてバックグラウンドに表示することも、ゲームの世界でも一般的に行われています。このような流れで、表示する対象の簡略化ということも行われています。簡略化としては、画面上に表示される領域が小さくなった場合に、多少ごまかしたところで、どうせ見えないだろう、というところが根拠になっています。例としては、遠くのテクスチャは、解像度の低いテクスチャに変更することや、複数のポリゴンモデルをテクスチャに置き換えたり、複数のポリゴンモデルをより少ない数のポリゴンモデルに置き換えたり、モデルのポリゴン数を動的に変化させたりと、さまざまです。
これらの簡略化の結果、もとのモデルを表示した場合とはピクセルレベルで異なる画像が生成されますが、全体として同じように感じられる画像が、はるかに少ないコストで得られます。
このところ考えている回転の手法に関しても同じことです。確かに、局所的に見れば誤差が含まれているかもしれません。しかし、全体として見たときに、見える形であればＯＫでしょう。まして、ゲームに用いるのです。見た目は大事ですが、それ以上に大事なのは、スピードです。また、僕自身、どれだけ遅いマシンでも遊べるかというのは、プログラマとしての挑戦なのです（かっちょえぇ～）。そのためにも、1フレームの中の1ドットの表示の精確さにこだわるのではなく、「貴様も将校なら大局的にものを見んか！」なのです。ということで、 誤差ばんざいと言いたいですね（言うなよ・・・
そんなこんななので、バグの１個ぐらい、見逃してくれよぉ～（だめに決まってんだろ・・・）。
この手法の一番の問題点は、除算を必要とすることです。なにしろ、DWORDでの除算は41クロックもかかるらしいのです。しかし、ループ内部での除算ではなく、ブレゼンハム一回につき、除算一回なので、ループあたりのクロック数が１クロックでも少ないなら、ループ回数が増えたときに除算のコストを償却することができるはずです。
ということで、今回の結論は、好きな方を使ってくださいよ、ということで。回転に関して言えば、ブレゼンハムより簡単に実装できるので、それだけでもお得？なのかもしれないです。
さて、それでは採点です(笑)。

どのみちMMX codeでブレゼンハムを行うと最適化しにくいので整数部16ビット＋小数部16ビットで持って、スキャンして行くのが妥当だと思います。
ほとんど正解です。ただ、レポートとしては（レポートだったのか？）、なぜ16bitなのかを考察する必要があるでしょう。また、誤差についても、整数部16bitに対し小数部16bitでは、整数部に対する誤差の影響が少し響くかもしれません。とかいいつつ、ぎゃるぱにＸでは16-16の固定小数だったりします(笑)。ということで、正解。したがって、ぎゃるぱにＸも正解。う～ん、どっちが先だ。

多重ブレゼンハムを念頭において、初期値を変更する。
Y方向ブレゼンハムの初期値＝X方向のブレゼンハムの現在の値*y/x
一瞬、う～ん、あってるかも・・・と思いましたが(笑)、よくよく見ると、/xってなんだよ～。そこで誤差はいってるよ～。誤差を無視したとしても、スキャンラインごとに割り算一回かー。それはやだなー。どうやら本人も冗談のようなので、点数は、座布団１枚で。
2000/06/25
y/xは傾きのことで、定数なのでスキャンラインごとの割り算ではないと、ご本人から指摘を受けました。少し考えてみましたが、初期値の変更については正解でしょう。ただ、この方法で問題を回避するのは、そう簡単ではなさそうです。ということなので、実装していただければ正解に(笑)。完成したら見せてくださいね～。

さ～さんの次号は、これ
４５°倒したパターンを事前に用意する、で決まり！

ラクガキは-2。
最後にこんなことを書くのもアレですが。友達のプログラマにこの話をしたら、「え？回転にブレゼンハム使うんですか？ふつー、固定小数点でしょー」と言われました(笑)。あぁ、意味なかったんか・・・。そんなやしょくくんですが、整数部10bit＋小数部21bitでブレゼンハムと同じ線分が引けることに関しては新しい知見だったようなので、今回のメインはそこにします(笑)。でわ。
エンジンかからねぇ～と思って、いろいろ試して、いろいろ調べて、だめだこりゃ～となって、でも、朝5時じゃガソリンスタンドからの配達はしてくれなくて、結局JAF呼んで、30分まって、 JAFの兄ちゃんが「じゃぁ、ちょっとみせてくださいね」と言って、車の中にのぞいた瞬間に、「あ、これですね」とシフトレバーが REVERSEに入っているのに気がついて、PARKINGに入れたらエンジンかかっちゃって、僕、JAFに入ってなくて、JAFに入るなら入会金２千円＋年会費４千円＋今回の出張費１万２千円のところ、今なら１万４千円にまけるけど、 JAFに入らないなら１万２千円って言われて、入会しますよ、ってことで１万４千円払ったのはまぁしょうがないんだけど、なんでREVERSEに入ってんの気がつかなかったんだろ、オレ、ってことでアホやなぁ～と凹んでいたのでした。 JAFの兄ちゃん曰く、「よく鍵ぬけましたね」。試して見ましたよ、えぇ。サニーはそりゃもういくらでもすっぽぬけますがな～。あぁ、アホや。

	PentiumII 333MHz		MMX Pentium 120MHz
	縦スキャン	横スキャン	縦スキャン	横スキャン
WIDTH=64 HEIGHT=64	---	---	104	104
WIDTH=128 HEIGHT=128	258	148	609	435
WIDTH=256 HEIGHT=256	939	393	3970	1742
WIDTH=640 HEIGHT=480	4817	2041	24351	8148

Plain Code	Optimize Algorithm
263	92

	配列リスト	STLリスト
最大オブジェクト数 2000 処理フレーム数 6000 削除確率 1/256 発生確率 1/256	3ms	1180ms
最大オブジェクト数 2000 処理フレーム数 6000 削除確率 50/256 発生確率 2/256	1ms	6080ms

	配列リスト	STLリスト
最大オブジェクト数 2000 処理フレーム数 6000 削除確率 0/256 発生確率 0/256	277ms	482ms

	配列リスト	STLリスト
最大オブジェクト数 2000 処理フレーム数 6000 削除確率 4/256 発生確率 4/256	7700ms	4980ms

	実行時間（ms）	sizeof(SObjectCell)
std::list	510	---
自前list N=1	74	12
自前list N=2	75	16
自前list N=3	320	20
自前list N=4	405	24
自前list N=5	459	28
自前list N=6	514	32
自前list N=7	514	36
自前list N=8	514	40
自前list N=9	515	44
自前list N=10	515	48
・・・
自前list N=20	515	88