L.Entisの日記 - Windows95 では動きません

提供されるAPIからみても安定性・サポートの面からみても、とてもWindows9x系を切り捨てたい気分なのですが、今のところ吉里吉里３で切り捨てるかどうかはどっちつかずでいます。

順調に予定が遅れていますので、まともに吉里吉里３が動き始めるのは早くて来年の今頃になりそうですが、そのときの状況をみて考えたいと追います。

吉里吉里２は今まで通りWindows98以降をサポートします。

ちなみにFiberはWindows 9x系ではWindows98以降で使用可能です。

やねうらお－よっちゃんイカ(ry ■[game] エロゲー製作は大変ナリよ(7)

なるほど。画像演出系みたいなわかりやすい部分では、みなさんどのエンジンがどうだなどと評価を盛んにしているようなのですが、内部の実装、つまるところユーザの目に見えない部分でのエンジンの評価をしてくださる方はなかなかいらっしゃらないので、それに言及してくださっているのはうれしいです。

やねうらお氏のエントリで出ていた個々の技術や出来事を年代順にまとめると以下の通りになります。

1999年6月

「自前のスクリプト言語」(TJS1の初版が乗った吉里吉里１。GCは参照カウンタ)

2000年10月

「早い段階でoggをサポート」(この時点ではlibvorbis post-beta2。ちなみにOggVorbisが正式に1.0になったのは2002年7月の話)

2003年4月

「月姫に採用」(ただし月箱。月姫そのものに採用されているかは…。ちなみに「幻視同盟」吉里吉里版は2002年だったと思います)

2004年4月

「自前の高圧縮率の画像圧縮フォーマットを実装」(TLG6の事だと思われる)

吉里吉里１が出たのが1999年6月で、それからベータ版の期間を経て、ようやく使い物になってきたのが1999年12月ごろの話ということになります。

で、「当時」(「1996年～1999年」)の事となると確実に吉里吉里１の話となりますが、その当時の吉里吉里１は確かに内部サーフェース(レイヤと呼んでいましたが)を 32bpp で持っておりましたので、やねうらお氏のご指摘通り、単純に考えれば 16bpp に比べて約半分の FPS しか出ないというのは十分考えられたと思います。

吉里吉里１に分割演算の機能がついたのは 2000年5月～7月の間です。吉里吉里２は吉里吉里１よりもより高速になっています。

で、この分割演算というのはどういう事かと申しますと (氏のさきほどのエントリでも「ななし」氏が言及していますが)、画像演算を細かい領域に分割して演算し、なるべくCPUキャッシュに収まる切る容量で演算を行おうとする物です。CPUとCPUキャッシュ間の転送は爆速なのですが、それに比べてメインメモリとCPU間の帯域は数倍～数十倍遅く、大量のデータを扱う局面では、如何にCPUキャッシュを効率的に扱うかが高速化の鍵となってきます。

吉里吉里２製の作品を起動中にShift+F11を押すとこのように更新矩形が表示されます。このように全体を細かくストライプ状に分割して演算を行っており、これにより合成バッファは小さくて済むうえに、描画パイプラインの各演算ステージで使い回しますので、CPUキャッシュに乗りやすくなるという事になります。

これがどれぐらい効果があるのかを、単純なクロスフェードで計測してみました。吉里吉里２のコマンドラインオプションで -gsplit=no と指定すると画像分割を行わせない事ができます。

計測環境は Athlon64 X2 Dual Core Processor 4800+ + NVIDIA GeForce 6800 LEです。単位はFPSです。

というわけで大体 1.37～1.47倍の効果があるようです。

さらにより複雑な演算を行う場合、たとえば表 (トランジション元) および 裏 (トランジション先) それぞれで前景３枚(裏表併せて６枚)がアルファ合成をしながら常に画面内を移動しているしている場合ですと

というわけで、大体1.77倍～1.88倍の効果があるようです。

あと、吉里吉里２ですと、演算が必要ない領域 (背景のうち、前景に覆われていない部分など) は演算をバイパスして画面に直接転送されるように描画パイプラインが構成されます。ですので、氏のコメントにあるような「バックサーフェース 32bpp→セカンダリサーフェース 32bpp→プライマリサーフェース 16bpp」の「単純な転送」という状況は発生しません。氏のおっしゃる「セカンダリサーフェース」(演算バッファ)を経由する場合は、「単純な転送」ではなく、なんらかの演算が発生する領域に対してのみとなっています(条件によってはそうならない場合もありますが)。

吉里吉里３は吉里吉里２である程度の成功を見ることができたとおもう描画パイプラインの仕組みをより抽象化し、様々な種類のレイヤを扱えるようにするつもり、、、ですが当分先の話になりそう。

これから、オブジェクト指向システムを完成させないとなりません。

現状のRisseはクラスやオブジェクトの概念がなくて、かろうじて匿名関数として作成した関数を呼べるぐらいです。Risse以外で実装された関数すら、簡単には呼べません。

これからクラス、オブジェクト等の機構を作っていかなければなりません。やっと前半戦終了と言ったところでしょうか。

コルーチンとBoehm GCとの相性の改善のためにWindows FiberのAPIを置き換えるコードを追加していったんコミットしました。

Boehm GCのマーキング処理をフックして、Fiberのスタックエリアやコンテキストをマークするようにしてあります。

ソースみてもどうもいやらしいスッキリしないコードが並んでおります。

Windows以外のプラットフォームへの対応も必要ですね。

ですがいったん中断します。というのもこういう機構を実装してもRisseから呼ぶ手段が無いのです。

そういやFiberと例外処理って相性悪そうだなぁーと思ってやってみたら案の定最悪でした。

static int end_count = 0;
VOID WINAPI FiberProc(LPVOID param)
{
    void * root_fiber = param;
    for(int i = 0; i < 3; i++)
    {
//        try
//        {
            printf("fiber %p : %d\n", GetCurrentFiber(), i);
            ::SwitchToFiber(root_fiber);

//            throw 0;
//        }
//        catch(...)
//        {
//        }
    }

    printf("fiber %p exiting\n", GetCurrentFiber());
    end_count ++;
    ::SwitchToFiber(root_fiber);
}
//---------------------------------------------------------------------------
void test()
{
    void * root_fiber = ConvertThreadToFiber(NULL);
    printf("root fiber : %p\n", root_fiber);
    void * fibers[2];
    for(int i = 0; i < 2; i++)
        fibers[i] =
            CreateFiber(0, static_cast<LPFIBER_START_ROUTINE>(FiberProc),
                        root_fiber);

    while(end_count < 2)
    {
        for(int i = 0; i < 2; i++)
            SwitchToFiber(fibers[i]);
    }
    printf("all fibers exited\n");

    ConvertFiberToThread();

    for(int i = 0; i < 2; i++)
        DeleteFiber(fibers[i]);
}

上記はFiberを使った簡単なコルーチンっぽいもののテストですが、これを実行すると

$ ../../build_output/bin/corotest.exe 
root fiber : 00244380
fiber 00246200 : 0
fiber 002464F0 : 0
fiber 00246200 : 1
fiber 002464F0 : 1
fiber 00246200 : 2
fiber 002464F0 : 2
fiber 00246200 exiting
fiber 002464F0 exiting
all fibers exited

となります。これは正常。

ですが、コメントされている部分 (例外の送出と受け取りをしている部分)のコメントをはずすと以下のようになります。

$ ../../build_output/bin/corotest.exe 
root fiber : 00244380
fiber 00246200 : 0
fiber 002464F0 : 0

ここでプログラムが終了してしまいます。

コンパイラはMinGWなのですが、MinGWはSjLj(setjmp/longjmp)で例外処理を行うようになっています。ここらへんの動作についてはJ - g++の例外を捕まえよう！！（素手で）に詳しいです。ただ、SjLjでは例外の情報はスレッドごとには持っていますが、さすがにコルーチンごとに持つようにはなっていません。

ちなみにVC++やBC++ではWindows SEH (Structured Exception Handling)で例外を処理していて、これはFiberでのコンテキスト切り替え時に例外の情報も自動的に切り替えるようです (FiberData内に例外ハンドラリストへのポインタを持っている)。

で、どうしようかと探していたところかそくそうち - [C++][Hamigaki][Coroutine]sjlj-exceptionsに解決法がありました。

というか、この郵便はみがき氏のHamigaki C++ ライブラリのコルーチンライブラリがとてもいい感じです。あー、これを使わせて頂こうかな。どっちみちBoehm GCとの相性改善の課題は残りますが、用途が合致して、良い物があるならばわざわざ作る必要はないですね。

boost.coroutineをみていると上記のような例外ハンドラの待避は一見行ってないように見えたのですが、上記のような実験を行ったら、実は大丈夫でした。見落としかな。もちろんhamigak::coroutinesは大丈夫でした。どうやってんだろう。

coroutineライブラリを自作の方向で検討中。

WindowsではFiber使うことになるのかなーとか思って調べていると、どうやらConvertThreadToFiberやCreateFiber、GetCurrentFiberはvoid*を返すだけで、その中身が何かが分かりません。

CPUレジスタがポインタを保持している場合はBoehm GCがそれを知らなければならないため、中断しているFiberのコンテキストから、なんとかレジスタの情報を見つけないとなりません。

調べているとwineの実装にヒントがありました。

17日に都内某所で、ノベル系ゲームにおける演出とスクリプトのあり方をテーマに座談会が開かれました(私も参加させて頂きました)。

経緯上、今回は吉里吉里関連の方のみの参加となりました。

ここでの内容はまとめられ、公開される予定とのことです(時期は未定です)。

いきなり挫折かよといわれると悲しいですが、挫折です。

いろいろ実装しているウチに欠点が見えてきて、

• メソッドの呼び出しコストが結構高そう(いったん仮想スタックに実行状態を積む必要があるので)
• エンジンの実装中、Risseメソッドを呼ぶためにいったん実行状態を保存して、現在の実行を中断してメインルーチンに制御を戻して……という処理を延々と書かなければならない(要するに書くのが面倒)

下側の問題は結構致命的です。エンジン内で閉じこめておける問題ならばいいのですが、プラグインなどを書くときもつきまとう問題です。

ここらへんの問題ってBoehm GCと相性のよい、マシンスタックをごっそり入れ替えて制御する系のコルーチン(あるいはContinuation)ライブラリがあれば解決する問題なんですよね。

ここでStacklessの利点としてあげた実行状態の保存とかホントにつかうんかね、という話もあります。

さーて

しばらくコルーチンライブラリを探しては見ましたが、おそらくBoehm GCと相性の良いライブラリは無いと思います。どこかのBoehmGCを使っている処理系の実装を参考に実装するか、あるいはライセンス的に問題がなければそこからコピーってくるか、あるいはそもそもBoehmGCではない何かを使うかと言ったところですね。

とりあえずStacklessをやらないとなると今週末の作業が無駄になったことになるのでブルーです。Stacklessの良いところと悪いところが本当に分かりかけたってところで良いことにしますかね。

結局の所Stacklessにしたほうが良さそうかも？という感じで実験的にスタックレスな実装をしています。よさそうならばこのままStacklessにしてしまおうかと思います。

Risseコード->C++コード->Risseコード->yieldのような実行をさせたいとき、間に挟むC++コードはスタックレスを考慮して(stackless-awareで)書く必要があります。具体的には呼び出しもとから呼ばれたContext(スタックや実行情報が格納されている構造体)を呼び出し先にも渡し、自分の実行状態もそこに置く必要があります。

逆にスタックレスを考慮しないC++コードの場合は、受け取ったContextを渡さずに普通に呼び出し先のRisseコードを呼び出せばいいわけですが、この場合はRisseコード内ではyieldできません。

なぜCoroutine(とかcontinuationとかいろいろ)の実装が面倒なのか。

ええと、まず現状のRisseはstacklessではありません。stacklessって何という方ははむ！氏の空想具現化プログラミング-[Lua] スタックレスってどういうこと？が良くまとまっていると思います。

TJS2のVMもそうだったのですが、RisseのVMは呼び出し先の関数/メソッドがなんの言語で実装されているかを今のところ区別していません。共通のインターフェース(具体的にはRisse::tRisseObjectInterface)を実装できる言語であればC/C++だろうがアセンブラだろうがRubyだろうが呼び出します。もちろんRisseで書かれた関数/メソッドはこのインターフェースを実装しています。このインターフェースで実装されるメソッドは実のところC++における仮想関数です。

このため、関数/メソッドの呼び出し履歴はマシンスタック(ホストCPUが使うスタック)上に蓄積されていきます。マシンスタック上に蓄積されていくということはどういうことかというと、コルーチンでコンテキストを切り替えるときに、単にVMのスタックを切り替えるのではなくて、マシンスタックごと切り替えないとならないということになります。

マシンスタックごとコンテキストを切り替えるのは確かに面倒な手法ではありますが、前に挙げたboost.coroutineなど、いくつかライブラリがありますのできます。ちなみにboost.coroutineは内部的にはWindowsの場合はFiber、Linux/Posixの場合はアセンブラによるスタックの切り替えかmakecontext/setcontext/getcontextによる切り替えを行うようです。

Boehm GCはマシンスタック上に置かれたポインタをスキャンします。実際は現在実行中のスレッドのマシンスタック上だけではなくて他のスレッドのマシンスタック、あとは保存されたCPUのレジスタも調べます。CPUのレジスタにポインタが入っている場合があるのでこれを見逃すわけにはいきません。

Boehm GCはどこにマシンスタックが配置されているかはBoehm GC自身で探すことができまし、マルチスレッドの場合は他のスレッドのマシンスタックも探し出すことができます(中にはスレッドライブラリにフックが必要なプラットフォームもあるようですが)。

しかしFiberやmakecontext系、あるいはmallocなどで自前でマシンスタックを確保して、それらを切り替える系はさすがに考慮外といった感じで、どのようにBoehm GCに他のコンテキストのマシンスタックや保存されたCPUレジスタなどを教えるかの方法を調査している段階です。

Boehm GCもソースコードをみていると相当泥臭いですが、マシンスタックの切り替え云々も泥臭い部分で、x86/Win32だけの話ならまだしも、汎用的にとなると、自分で作る気もメンテナンスする気もなかなか起きません。どこかによいライブラリが転がっているとよいのですが。

それともう一つ。そもそもRisseをstacklessにするとどうなるかというのがあります。

stacklessにするとどうなるかをちょっと考えてみると

欠点

• Risseコード→C++コード→Risseコードという呼び出しは困難(できなくはなさそうだが書きづらそう)
• 現状のVMに少し手を加える必要がある(が、やるなら今のうち)
• 例外処理機構がC++とVMで共通というわけには行かなさそう

利点

• 問答無用でマシンスタックの切り替え(コンテキスト切り替え)ができるstackfulなコードと比べ、yieldされたくないタイミングを厳密に指定できそう
• コルーチンをプラットフォームに依存しない形で実装できる
• Boehm GCとも相性がよさそう
• 実行状態の保存とかがやりやすくなりそう

となるんじゃないかなと。

ううむ、これはしばらく調査が必要ですね。

try-finallyの実装が終わったので、今度はコルーチンをどうしようかを見ています。

まずはC++用コルーチンの実装で、もしかしたらBoostライブラリの一員になるかもしれないboost.coroutineを見てみました。先ほどまであれほどboost + Turbo C++で格闘していてうんざりしていたところなのに、このコルーチンのサンプルコードはあっさり動作してしまい、なんかふぬけに。

これ自体は普通にC++で使うには使いやすそうなのですが、やっぱり一番問題になるには、いまのところRisseで使っているBoehm-Demers-Weiser conservative GC (Boehm GC)との相性です。

たとえば、コルーチンのコンテキストが破棄されるときに、サブコンテキストでexit_exceptionという例外が発生します。これをスクリプトで捕捉できるようにすると、コンテキストが破棄されるときになんらかのアクションを起こすことができます。ただし、Risseで考えているような使い方をすると(インスタンスの寿命管理をまるっきり忘れたい向きだと)、コンテキストが破棄されるときというのは、すなわちオブジェクトがGCで回収されるときです。GCで回収される際に例外が発生してスクリプトコードが動くということです。でも、基本的にGCが回収する際にスクリプトコードを駆動するようなことをやりたくないのでどうしようかなと。LuaやSquirrelをみていると、コルーチンのコンテキストが破棄されるときにこういった例外を投げる機能はないからRisseでもイラナイかな(ま、あればあったで便利だとは思いますが)。

あとはサブコンテキストのスタックフレームをBoehm GCに何らかの形で教えないとなりません。そうしないとGCはコルーチンのサブコンテキストのスタックなんか知りませんから、コルーチンのサブコンテキスト上に置いたオブジェクトが勝手に回収されてしまうという可能性があります。

もうちょっとよく調べるつもり。もしかしたら別のコルーチン実装を使うかもしれません。

参考

• かそくそうち 2006-08-21

吉里吉里２が、というよりはBoostライブラリが、なんですが、いきなりそこで躓きました。CVS版では直ってるのかな。cvs.sourceforge.netが死んでる(?)らしくてCVS版は見ることができませんでした。

そういえばまた付属のSTLが別の物に変わったんですね。

Risseはtry文でfinallyをサポートします。機能はほかの言語にもよくあるfinallyと一緒です。

try {
  // (A)tryブロック  ここでなにか処理
} finally {
  // (B)finallyブロック
}

多くの言語でもそうなのですが、finallyブロックはtryブロック中がどうなっても「必ず」実行されるブロックではありません (必ず実行される保証はありません)。

たとえばわかりやすい例で言えば、プログラムを強制終了(本当に強制終了)させるabortという関数があったとして

try {
  abort();
} finally {
  // ここはたぶん実行されない
}

と書くとfinallyブロックは実行されません。

このほか、スレッドやコルーチンがtryブロック中で停止したままスレッドやコルーチンが破棄された場合などもfinallyブロックは実行されないでしょう。

たとえばRubyだと

def test(c)
  begin
    p "before c.call"
    c.call
    p "after c.call"
  ensure
    p "ensure"
  end
end
p "before callcc"
callcc {|c| test(c) }
p "after callcc"

を実行すると

"before callcc"
"before c.call"
"after callcc"

と表示されてスクリプトが終了します。つまりensure 節で表示されるべき"ensure"は表示されないままとなります。Rubyの場合はensure節はこの場合「begin式が終了する直前に実行される」ということですが、そもそもbegin式が終了していないので呼ばれないままになるのでしょう。たぶん仕様だと思います。

なんかトラップっぽいですが、Risseでも仕様とします。

参考

• プロフェッショナルVB.NETプログラミング 第16回 例外処理を極める - Finally文の確実性
• Finally文が実行されないケースはあるか？

わーい

BorlandがTurbo Explorerを無償で公開とのことです。早速ダウンロードしてみました。無償とのことですが商用製品の開発は可能とのことです。

やっぱり一番気になるのはTurbo C++で吉里吉里２をコンパイルできるかどうかですね。すこしさわってみた感覚から言うと「コア(krkr.eXe)に関してはできそう」といった感じです。

コアのみ、というのは、「フォルダ/アーカイブ選択」画面などではサードパーティー製VCLコンポーネントを使用しているのですが、Turbo C++ Explorerではサードパーティー製のVCLコンポーネントをインストールできないのです。ただし「VCLコンポーネント」としてインストールができない(IDEから利用できない)だけなので、むりやりゴニョるとなんとかできそうな雰囲気ではありますが……。コアはサードパーティ製のzlibやらlibpngやらのライブラリは用いていますがサードパーティ製VCLコンポーネントは用いていないのでできそうだということです。

コンパイラのバージョンはbcc32の実行結果からみるに5.82です。ちなみにC++ Builder 5付属が5.5.1、C++ Builder 6付属が 5.6.4なのですが何が変わったのだろう。

他に付属している物は

• VCLのソースコードやRTL(CRT)のソースコード
• tasm32 (アセンブラ)
• CodeGuard (メモリリーク・バッファオーバー/アンダーラン・メモリ不正アクセス等の検出ツール)
• Object Pascal (Delphi言語)コンパイラ (IDE上からObject Pascalのコンパイルが可能)

付属のVCLコンポーネントは以前のDelphi Personal相当なのでしょうかね。

VCLのソースコードとかRTLのソースコードが付属しているのはありがたいです。

時間を取ってTurbo C++ Explorerで吉里吉里２コアをコンパイルできるように、ソースの調整をするかもしれません。これで、すくなくとも吉里吉里２コアに関しては、やっと無償の開発環境でコンパイルが可能になります。コア以外の部分のDLL等は吉里吉里２オフィシャルリリース内のDLLを引っ張ってくれば動くと思います。

ただし、オフィシャルのリリースはいままで通りC++ Builder5でいきます。吉里吉里２の仕様用途ではとくに問題がないことが分かっているからです。

ここしばらくは try ブロックや遅延評価ブロックからのreturnやらbreakやらgotoでの脱出を実装していました。

遅延評価ブロックは関数呼び出しと一緒に指定し、呼び出した関数から呼び戻されるブロックのことで、Rubyにおける「ブロック」のことです。

で、これらからの脱出が結構面倒くさいシロモノなのです。

関数repeat_4が以下のように実装されているとして

var repeat_4 = function () block {
  // ブロックを４回実行する
  for(var i = 1; i <= 4; i++) block(i);
};

そこで関数xをこう書きます。関数xの中ではrepeat_4が遅延評価ブロック付きで呼ばれています。

function x() {
  repeat_4() { |v| if(v == 3) return v; };
}

すると、v が 3 のときに関数xを抜けます。…と言うのは簡単なのですが、内部的はそこそこ厄介な処理をしています。return vにたどり着いた時点ではfunction x→function repeat_4→blockの順に呼び出しが行われていますが、ここでreturn vが実行されるとrepeat_4の実行を中断してfunction xから戻るのです。

実はreturn vが実行された時点で、制御構造用の内部的な例外が発生してfunction xまで脱出するのですが、これの実装がめんどくさかったわけです。

遅延評価ブロックからのgotoによる脱出は、ASTを全部スキャンしないとgoto先のラベルがどこにあるのかが分からないので、もうちょっと面倒でした。実際はASTをなめ回しながらon-the-flyでSSA形式を生成しているので、一通りSSA形式を生成し終わったあとでまだジャンプ先が分かってないラベルを全部配線するという方式を採っています。

ちなみに内部的にtryブロックは遅延評価ブロックとして実装されています。なんでかっていうとSSA形式と例外処理がどうやらエラく相性が悪くて、tryブロックの内側と外側でSSA形式が分離されているからなんですが……あまり自分は詳しくないから、語るとボロがでそうなので辞めておきます。

そもそもこういう動的な言語でSSA形式による最適化ってそれほどの意味はないような気がしなくもないのですが、きっと最適化を考え始めるとなにかありがたいことが起きるんだろうと思ってますので、今はあまり考えないことにします。

この日記に業者さんがコメントスパムを大量に投稿するようになったのでチェックアルファベットを導入しました。

表示されたアルファベット3文字を入力欄に書かないと投稿できないというやつです。しばらくの間はこれでなんとかなりそう。

吉里吉里掲示板の方はすでにかなり前に導入しています。

その関連で4日の23時から5日の1時ごろまでRSS配信がおかしくなってしまっていました(今はなおしましたのでなおっています)。すみません。

吉里吉里２で(たぶん吉里吉里３でも)利用可能な画像圧縮形式のTLG6ですが、このあいだしばらく改良に取り組んでみました。しかし、1%ぐらいしか圧縮率が上がらなかったので無かったことに。

複雑なアルゴリズムを使うならばあれよりも圧縮率が上がることはわかるのですが、展開速度をかなり重視する用途に使うのでそれができません。もうあれはあの形で完成かなとおもいます。

TLG5の方はもうちょっと展開速度が高速になて圧縮率が上がらない物かと思っていますが、どうにもアイディアが浮かびません。ちなみにTLG5は(R,G,B)->(R-G,G,B-G)変換のあとy方向への微分とx方向への微分をとり、LZSSの変形で圧縮をかけています。