或曰

水曜日, 11月 12, 2008

ゲームプログラマになる前に覚えておきたい技術

ひらしょーさんの書かかれたゲームプログラマ入門書。ちょっとだけお手伝いさせていただきました。

「一人で最初から最後までゲームを作れる」ことが目標になってます。実際の仕事になると規模の問題が出てきて他にも気にしないといけないことが多々出てきますが、そのへんはバッサリ削ってます。

ラベル: プログラミング

火曜日, 10月 21, 2008

Working Draft, Standard for Programming Language C++

プログラミング言語 C++0x のドラフト。ぼちぼち読むかね。

ラベル: プログラミング

水曜日, 7月 30, 2008

Dual-stack lite broadband deployments post IPv4 exhaustion

そろそろ秒読みに入ってきた IPv4 アドレス枯渇への対応策として、新たに提案されている手法。キャリアグレード NAT の一つ。

概要

ISP からは IPv6 アドレスのみを割り当てる。
Home router は IPv4/IPv6 dual stack。
ISP edge router と Home router の間で IPv4-IPv4 tunnel over IPv6 を張る。
これにより、現在は Home router で行っているアドレス変換処理を ISP 側に持っていく。
ISP edge router では Home router の IPv6 アドレス、Home network 上のデバイスの内部 IPv4 アドレスを用いて NAT 対応表を作成。

特徴

Home network は従来どおり IPv4 プライベートアドレスの使用可能で、同一キャリア内での IPv4 プライベートアドレス割り当て調整なども不要。
IPv4 only のレガシーデバイスがあっても Home router さえアップグレードすれば OK。
IPv6 と共存可能、その際 IPv6 は NAT せずに直接接続となる。

読んでいる途中で full-cone NAT with hair-pinning という単語が出てきて何かと思ったけど、NAT の分類なんですね。

full-cone NAT は「NAT 下の同一 IP アドレス/ポート番号が、通信相手のIPアドレス/ポート番号によらず同じ外部IPアドレス/ポート番号に割り当てられる」NAT、hair-pinning は「同一 NAT 下のデバイスが外側 IP アドレスで通信できる」こと。詳細は RFC3489 section 5 参照。

ところで symmetric NAT （NAT 下の同一 IP アドレス/ポート番号が、通信相手のIPアドレス/ポート番号によって異なる外部IPアドレス/ポート番号に割り当てられる)だと、複数同時接続を使うアプリケーションが動かなくなる可能性があるそうだけど、具体的にどういうケースを想定しているんだろう？　外側 IP アドレスが異なると、サーバからは異なるホストから複数接続が来ているように見えるので、アプリケーション設計によっては対応できないってことかな。

ラベル: プログラミング

luabind

組込用途のスクリプト言語 Lua と C++ の間で、関数相互呼び出しを実現するためのライブラリ。

ドキュメントから抜粋。

class testclass
{
public:
 testclass(const std::string& s): m_string(s) {}
 void print_string() { std::cout << m_string << "\n"; }

private:
 std::string m_string;
};

上記の C++ クラスを Lua から呼び出すため lua_State* L に登録するコード。

using namespace luabind;
module(L)
[
   class_<testclass>("testclass")
       .def(constructor<const std::string&>())
       .def("print_string", &testclass::print_string)
];

ソース眺めてみたら Boost MPL を使って、バリバリのテンプレートメタプログラミングになってる。やるなぁ。ちょっとまじめに読んでみるか。

ラベル: プログラミング

月曜日, 2月 25, 2008

参照カウント管理

昔ゲーム屋さんやってたときは、侵入型参照ポインタで統一してました。

具体的には boost::intrisive_ptr と、参照カウントを実装するのを補助するマクロ(こんなの)組み合わせて使ってました。

ついでにメンバ変数を持つ普通のクラスは外からは new させず、インスタンスの生成はファクトリ経由にするとスッキリします。

ラベル: プログラミング

土曜日, 2月 09, 2008

FORTRAN

FORTRAN と C/C++ のコードはリンク可能です。

FORTRAN から C/C++ の関数を呼び出す場合、

引数が全てポインタ渡しになる
環境依存だが、シンボル名が変わる
確か gcc だと、C/C++ 側関数で foo_ と定義しておくと FORTRAN 側から FOO として見えたはず。(全部小文字 + 最後にアンダースコア)

といった点で注意が必要だったと思います。シンボル名やデータ型の対応は環境依存なので、詳しくはマニュアル参照ですね。

そのついででFortranについて調べたけど、この言語、嫌い。コンピュータ黎明期に誰かが適当に作ってそのまま既成事実になってるんじゃないかと思うような書式が嫌だ。

歴史的なことをいうと、FORTRAN は世界で初めて作られた高級言語です。

プログラミング言語に関する体系的な理論・道具も無い (*) 状況で、かつコンピュータが高価・低性能で｢高級言語で書いたプログラムなど実行効率が落ちて使い物にならないだろ？」と思われていた時代に試行錯誤しながら開発され、アセンブリ言語でコーディングするのに劣らぬ効率のコード生成を実現しました。これによって以後のプログラム開発はアセンブリ言語から高級言語にシフトし、(主にIBM製) コンピュータの普及と、開発効率の向上に大きく貢献しました。

(*)
いまだとプログラミング言語の文法仕様を記述する際に BNF という記法を使いますが、たとえばこれも FORTRAN の生みの親である John Backus 氏が後に作ったもので、FORTRAN 開発当時には存在しませんでした。BNF もなければ LL, LR といった構文解析アルゴリズムもない状況で高級言語を開発するというプロジェクトを率い、成功させた苦労は並大抵のものではなかったと思います。

今から見ると確かにダサい仕様だと思うことは多々ありますが、歴史的背景を踏まえず「適当に作った」と言ってしまうのは、ちょっと先駆者に対する敬意が足りないかなと。

ラベル: プログラミング

金曜日, 2月 01, 2008

Google File System

入院中に読んだ paper, 今さらだけど覚書。

Google のデータ処理アプリケーションによるファイルシステム利用特性を踏まえた上で、分散ファイルシステムを再設計してみましたという話。

利用特性

ファイルサイズは100MB～数GB程度が中心。小さなファイルも使用できる必要はあるが、最適化の対象外。
読み出しのワークロードは、主に大きな連続読み出し（一度に数100KBから1MB以上、往々にして連続して次の領域読み取りが続く）と、小さなランダム（指定オフセット値からの数KB)読み出し。
更新のワークロードは、主に大きな追記（一度に数100KBから1MB以上、往々にして連続して次の追記が続く）。
複数クライアントからの同時アクセスが多く、特に同一ファイルへの並列追記処理を効率的に行う必要あり。
帯域重要、レイテンシはさほど重要ではない。

この前提の下、さらに使用するハードウェアは低価格な汎用品、具体的には一般的なPCとローカルHDD, あとは Fast Ethernet, GbE の組み合わせて実現したいというリクエストあり。

利用特性を見ると、確かに一般的なファイルシステムへの要求とはずいぶんと違っている。

汎用のファイルシステム、たとえば NTFS とか FFFS だと、既存の API (Win32 API, POSIX) をサポートすることや大量の小さなファイルを効率的に扱うことやレイテンシなどが重要になる一方で、同時に複数クライアントから追記要求がきた場合に効率的に処理することなどは想定外。また、対障害性などはファイルシステムレベルでも当然考慮はするが、ある程度以上となったら、その下のハードウェア層でもRAIDを組むなどの対策を組むことが前提となる。

私は分散ファイルシステムはあまり知らないのだけど、ローカルファイルシステムのセマンティクスをなるべく崩さずにネットワーク対応させた NFS, CIFS なんかとは明らかに違うし、最初から壊れるマシンがいること前提なあたり AFS とも大分違う。対故障性や帯域重視というと RDBMS も考えられるが、今度は想定されるワークロードにズレがある。

paper では、以上の前提を述べた上で GFS のアーキテクチャと設計について解説している。前提が違うので、結果としてアーキテクチャもラディカルに違ったものになっているが、利用している個々の技術やアルゴリズムはきわめて一般的。読んで難しいところは何もない。

アーキテクチャ設計とバランス感覚が秀逸だね。個人的には、こういうシステム好きだ。

追記

読みかけの「Distributed Systems: Principles and Paradigms 2nd Ed.」 Chaper 11 で分散ファイルシステムが取り上げられているので、ちょっと途中スキップして覗いてみたら 11.1.2 Cluster-Based Distributed File Systems で Google File System (GFS) 取り上げてる。

タネンバウム本に載ってるということは、分散屋さんの間ではもはや常識なのか。

ラベル: プログラミング

木曜日, 1月 03, 2008

GameObj: ヒット判定

ヒット判定の設計と実装。考えるポイントは 1. ヒット判定を誰がどのように行うか、それから 2. ヒットしていることが判明した場合の処理をどうするか。

ヒット判定用にインターフェース IHitter, IHittable を用意し、それだけを用いてヒット処理を行う HitManager クラスを作成。インターフェースを細分化して、依存関係を極力減らしておく。
ヒット時にはヒット側から被ヒット側に宛てたメッセージをキューにポストし、後で被ヒット側が実行されるタイミングでキューからメッセージを取り出して処理する方針で。
一般的に、複雑な状態を持つオブジェクトに対して外から不特定のタイミングで状態を変更させるとハンドリングが難しくなるので、そのオブジェクトが自発的に処理するようにした方が楽 (たとえば POSIX スレッドライブラリの API pthread_cancel() とか UNIX プロセスに送られたシグナル処理も似たような方法を使っている)。

そのへんまで方針を決めたら、UML モデリングツールを使ってクラス図を描いて検討し、だいてい行けそうだとなったらシーケンス図も起こしてみる。

だいたい行けそうだとメドが立ったところでコーディング始めて、最後に今後のためにドキュメントをコードにあわせて修正しておしまい。

私は C でプログラムを書く場合にはドキュメントはそれほど重視しないけど、C++ だと多少書いておく。C++ でインターフェースを細分する書き方をしていると必然的に基底クラスの仮想関数を介しての呼び出しが増えるため、ソースコードだけだと後で見て実際にどの関数が呼ばれているかを追うのが大変になるので。

あと Visual C++ 2008 Express Edition で動くように一部修正。_com_ptr_t も使えるのね。

ラベル: プログラミング

火曜日, 12月 25, 2007

Sequoia

メモリ階層をプログラミングモデルに取り込もうという話。スタンフォード、面白いことやってるね。

今後マルチコアプロセッサシステムが一般的になると同時に、ネットワークが張り巡らされて多数のシステムが連携して動作する Grid/Cloud computing が浸透してくると、今のようにプリミティブな API 呼び出して排他制御・分散処理を制御していくのは難しくなってくる。

これまでは HPC やシステムプログラミングのような一部の分野でだけ意識されていたような話が広範な領域で必要になり市場が一気に拡大するわけで、そうなるとこの領域への資金や優秀な研究者といったリソース投入量も増える。しばらくはこの周辺、ホットな話題が多そうだ。

そういえば、個人的には面白いけどあまり使い途がなかった分散アルゴリズムの知識とかも（動的ルーティング制御の理解に役に立ったぐらい）、今後は役に立つ場面あるのかな。

ラベル: プログラミング

日曜日, 12月 23, 2007

Good-bye ATL

ATL/WTL に依存していた部分を素の C++ で書き直し。これで VC++ Express Edition でも動くかな。

Windows プログラミングを C++ で行う際に面倒なのは、ウィンドウプロシージャに this ポインタを渡すこと。SetWindowLongPtr(), GetWindowLongPtr() を使ってウィンドウハンドルに this ポインタを関連付けるにしても、CreateWindowEx() した時点で WM_MINMAXINFO などいくつかのメッセージが飛んでくるため、それをメンバ関数で処理しようと思うと、結局は一度 this ポインタをグローバルな領域に書いておく必要がある。

ATL では一度グローバル変数 _Module からたどれるデータ構造にスレッドIDをキーにして this ポインタを書き込んでおいて、後でウィンドウプロシージャを thunk に差し替えるという方法を採用している。

あそこまで作りこむのは面倒なので、多少パフォーマンスが落ちるがお手軽なところで手を打っておく。次のような内容の thunk を作成し、これを最初からウィンドウプロシージャとして登録。

第一引数に渡ってくるウィンドウハンドル (hWnd) をメンバ変数に保存
hWnd を this ポインタに差し替え

二回目以降は最初の処理が無駄になる。第一引数の hWnd は、関数が呼ばれた時点では %esp + 4 の位置にあるので、コードはこんな感じになる。

push %eax
movl 8(%esp), %eax ; %eaxをスタックに退避した分だけ +4 ずれてる。
movl %eax, pThis->m_hWnd
pop %eax
movl pThis, 4(%esp)
jmp WndProc

IA32 のコードをハンドアセンブルする気にはなれなかったので、それっぽいコードを書いて GNU as でアセンブルし、出力を逆アセンブルして thunk の雛形に。

WndProcThunk.cpp

IA32 だと scratch register どれか忘れたので、とりあえずスタックに保存して %eax 使用。%eax, %ecx あたりは呼び出された側で値壊して OK だったような気がするけど、資料どこにいったかなぁ…。

2007/12/25 追記

ABI の資料を HDD から発見。eax, ecx, edx は callee 側で破壊して OK ということで、私が書いた thunk は push, pop 命令を消して、その間に挟まれている 8(%esp) を 4(%esp) にすれば良いね。

ABI は今だと SCO のサイトからダウンロードできる。Intel386™ Architecture Processor Supplement Fourth Edition の p.37-38 あたり。

ラベル: プログラミング

日曜日, 11月 11, 2007

お買い物

「Foundation of F#」 Robert Pickering (Apress)
「BSDカーネルの設計と実装 -FreeBSD詳説-」 Marshall Kirk McKusick, George V.Neville-Neil (ASCII)
「ヘルシング (9)」平野耕太 (少年画報社)

F# は Microsoft の研究チームが開発中の .Net Framework 上で動く関数型言語。

関数型言語は原則として副作用のないプログラムを記述することになるため、並列処理や分散処理に向いてる面がある。今後 multi-core processor が主流になり、組み込み系やデスクトップアプリケーションでも並列処理を意識せざるを得ない以上、関数型言語の現状を知っておくのも良かろうということで。

ラベル: お買いもの, プログラミング

月曜日, 10月 29, 2007

C++: 自動ロック

あたくし思うに、ロックというのは本来はエラー処理なんかと同様に、プログラムの本質とは何にも関係ない部分なんだから、たとえば C++ の例外のように、プログラミング言語のレベルでもっと裏に隠せるような良い仕組みを用意できねえもんかなぁと、そんな気がしますな。

最近パラパラと paper 漁った感じだと Software Transactional Memory が有望な感じです (参考)。

Many Core Processor 時代がそこまで来てるけど、正直、ロック処理や並列プログラミングの高レベルなサポートがないとプログラマが付いてこない気がしてます。基本的なロックプリミティブやスレッドライブラリを使ってプログラムを組むのは、どちらかというと state of the art の領域。

ラベル: プログラミング

火曜日, 10月 23, 2007

FPU を FreeBSD カーネルで使う話

FreeBSD-hackers ML を読んでいたら、

FPU を kernel 内で使いたいのでコード書いてみたけど、trap 22 が起きて使えず困ってる

という話が。

i386だと FPU のコンテクスト切り替えは遅延処理されてて curthread と同期してないから、単に FPU 使用部分を npxgetregs(curthread, ...), npxsetregs(curthread, ...) で挟んでもうまく動かないのよ。さくっと解説のメールだけ書いて送っておく。

しかし久しぶりに /sys/i386/isa/npx.c 読んでみたら、なんか場合分けがいろいろ増えてるね。amd64の同等のコードと比べると背負ってる歴史的遺物の重さが一目瞭然だ。

  1121    5060   32459 i386/isa/npx.c
  580    3135   18245 amd64/amd64/fpu.c

ラベル: プログラミング

水曜日, 9月 19, 2007

ico for win32 (2)

ザルガラー多面体表示初期パラメタをスクリプトで指定できるようにした [638:f0e586985b62]。

スクリプトで動作をカスタマイズしている様子

よしよし、想定通りにスクリプト追加するのも、スクリプトを修正して実機側プログラムで再実行かけるのも楽だ。この辺の作業は大量かつ頻繁に発生するから、作業効率を上げられるように準備しておかないと、後で苦労する。

あとはアーカイブファイル読み込み時の処理でヒープ使わないようにしたりとか、ハンドルの閉じ忘れバグ直したり、細々とした変更。

ラベル: プログラミング

木曜日, 9月 13, 2007

ico for win32 (1)

ザルガラー多面体の 3D 表示実装中。

ザルガラー多面体の頂点データを頂点バッファに書き込める形にコンバートするツールを作成し、出力したデータをアーカイブファイルに組み込み。メインプログラムに、アーカイブファイルを読み込んでモデルを表示する処理を実装。

よし、とりあえず動いてるな。

表示色・回転速度・移動速度あたりをスクリプトで調整可能にして見栄えを良くする
他のザルガラー多面体も選択可能に
ザルガラー多面体の情報（名前とか）を画面表示

まずは、ここまでやるか。あと WM_CLOSE の処理をマジメに見直す必要ありだが、ちょっと面倒なので後回し。

アプリ動作ムービー

ラベル: プログラミング

月曜日, 9月 03, 2007

スクリプト D&I (Fin) 組み込み

Win32 版のスクリプトコンパイラ (cscrc.exe), 逆アセンブラ (cscds.exe), C++グルーコード出力プログラム (sysdecl.exe) の実行ファイルを作成して commit すると共に、GameObj.exe 本体に VM インタプリタ組み込み。これで、ひとまずスクリプト言語処理系は終わり。

CScript 実行部を組み込み

組み込み前に簡単な最適化をいくつか追加して、実行ファイルに定数プールセクションを出力できるようにした。

Win32 版の実行ファイルは FreeBSD 上で MinGW gcc version 4.2.0 を使って作成。FreeBSD システムコンパイラの gcc 3.4.6 や、Cygwin 版の gcc 4.1.1 だと、意味不明のコンパイルエラーになる。なんか微妙なバグを突いてしまった雰囲気。

関係ないけど Lua は 5 から仮想マシンがスタックマシンではなくレジスタマシンになってるんですね。レジスタマシン流行りなのかなと思って調べてみたら、いくつか paper 発見。

現実のレジスタマシンだと、レジスタの割り当てと、関数呼び出し時の引数設定・破壊されるレジスタの退避・復元処理なんかが面倒。どう処理してるのかと思ったら、レジスタの本数を多めにとるのと、レジスタウィンドウ的なアーキテクチャを採用してレジスタの退避・復元処理をインタプリタ側で手助けする形になってる。なるほどね。

あと Lua 5 の VM 命令セットはシンプルで素敵。さすがによく考えられてる。

ラベル: プログラミング

日曜日, 8月 19, 2007

CScript 定数畳み込み

定数畳み込み (constant folding) 最適化の実装。

スクリプトソースコード中でコンパイル時に計算できる式を先に計算して、コンパイル済バイナリには結果を書く。例えば 1 + 2 というコードに対して push 1, push 2, iadd の 3 命令を出力にする代わりに push 3 としたい。

理屈は簡単で、元々は文法に付随するアクションで直接 VM のコードを出力しているが、これを構文解析した結果を後で参照できる形で保持しておき必要な情報が揃ったところで VM のコードを出力するように変更すれば OK。ただし、実装するに当たっては決めるべき詳細がいくつか出てくる。

中間解析結果として保持する内容。
中間解析結果を保持するデータ構造。
コード生成を行うタイミング。完全にプログラム全体の解析完了後にコードを出力させるのか、それとも途
中で出力させてしまうか。

本気でフロー解析や最適化を行なおうと思ったら、ソースコードをそのまま木構造に変換した構文木 (parse tree) tree もしくは以降の処理に必要なトークンのみに絞りこんだ抽象構文木 (AST: abstract syntax tree) を作り、次にその構文木を基本ブロックに分割し最適化を行ない、最後にコードを生成する。

ただ、そこまでやると、ちょっと文法に手を入れるだけでも

文法の修正
文法に付随する AST ノード作成ルーチンの修正
AST を辿って最適化を行なうルーチンの修正
AST を辿ってコード生成を行なうルーチンの修正

と変更箇所が分散して面倒なことになりがちな上、現状のコード生成ルーチンを破棄して作り直す必要がある。漸進的に開発を進めるため、次の方針でいくことに。

式の段階ではコードを生成せず必要な情報を保持するに留め、文が出てきたタイミングでコード生成を行う。
構文解析の結果として保持する情報は次の 4 つ。
- 型
- 定数かどうか
- (定数であれば) 値
- コード生成ルーチン

コード生成は元々 Comp クラスのメンバ関数を呼び出すことで行なっているので、その場でメンバ関数を呼び出す代わりにメンバ関数ポインタを std::vector に入れておき、後でまとめて呼び出せるようにする。型チェックやエラー処理などを除いた骨格部分は、こんな感じになる。

/*
 * 変更前
 */
node_primary_expression:
 TOK_INT {
  vm_int_t val = boost::any_cast<vm_int_t>($1);
  p_comp-<genCodePUSH_I(val);
  $$ = Cast::INT;
 }

node_assignment_expression:
 node_primary_expression
 | node_assignment_expression '+' node_assignment_expression:          {
  p_comp->genOprADD_I();
  $$ = $1;
 }

/*
 * 変更後
 */
node_primary_expression:
 TOK_INT {
  vm_int_t val = boost::any_cast<vm_int_t>($1);
  ExpressionInfoP expr(new ExpressionInfo(val));
  expr->addGenCode(boost::lambda::bind(&Comp::genCodePUSH_I, boost::lambda::_1, val));
  $$ = expr;
 }

node_assignment_expression:
 node_primary_expression
 | node_assignment_expression '+' node_assignment_expression
 {
  // 定数同士の加算の場合は、この場で計算して結果に置き換え
  ExpressionInfoP expr1 = boost::any_cast<ExpressionInfoP>($1);
  ExpressionInfoP expr2 = boost::any_cast<ExpressionInfoP>($3);
  if (expr1->isConst() && expr2->isConst()) {
   vm_int_t val = expr1->getVal<vm_int_t>() + expr2->getVal<vm_int_t>()
   ExpressionInfoP expr(new ExpressionInfo(val));
   expr->addGenCode(boost::lambda::bind(&Comp::genCodePUSH_I, boost::lambda::_1, val));
   $$ = expr;
  }
  // 定数たたみこみできない場合は、それぞれの命令出力後に add 命令を出力するように
  else {
   ExpressionInfoP expr(new ExpressionInfo());
   expr->setCast(Cast::INT);
   expr->addGenCode(*expr1);
   expr->addGenCode(*expr2);
   expr->addGenCode(boost::lambda::bind(&Comp::genOprADD_I, boost::lambda::_1));
   $$ = expr;
  }
 }

コード生成ルーチンに関しては、構文解析直後では確定できない情報 (コードが配置されるアドレスなど) の解決を遅延させる必要がある。boost::lambda::bind をネストして合成関数にしてしまうか、それだと書けない場合にはファンクタを用意して使う。

// 三項演算子
typedef boost::function<void (Comp* comp)> GenCode;
typedef std::vector<GenCode> GenCodeList;

struct GenCode3Op
{
 GenCode3Op(ExpressionInfoP expr_cond, ExpressionInfoP expr_true, ExpressionInfoP expr_false)
 {
  expr_cond->gt;swapGenCode(m_gen_cond);
  expr_true->gt;swapGenCode(m_gen_true);
  expr_false->gt;swapGenCode(m_gen_false);
 }
 /*
   [expr_cond]
   jump_if0 L_false
   [expr_true]
   jump L_exit
 L_false:
   [expr_false]
 L_exit:
 */
 void operator()(Comp* comp) const
 {
  _genCode(comp, m_gen_cond);
  vm_taddr_t taddr1 = comp->gt;genCodeJUMP_IF0();
  _genCode(comp, m_gen_true);
  vm_taddr_t taddr2 = comp->gt;genCodeJUMP();
  comp->gt;backpatchJUMP_IF0(taddr1, comp->gt;getCodeSize());
  // L_false
  _genCode(comp, m_gen_false);
  // L_exit
  comp->gt;backpatchJUMP(taddr2, comp->gt;getCodeSize());
 }

private:
 GenCodeList m_gen_cond;
 GenCodeList m_gen_true;
 GenCodeList m_gen_false;
};

ファンクタだろうがメンバ関数ポインタだろうが気にせず扱える boost::function と、既存のメンバ関数を簡単にカリー化できる boost::lambda::bind 万歳。

parser.y のコンパイルで実メモリが不足してスワップ領域使いだしたので、とりあえずデバッグビルドではコンパイル時に最適化しないように変更。調べたら 500MB ぐらいメモリ消費してるけど、何が原因なのやら。

/usr/bin/time -l の結果

最適化なし

       25.06 real        11.60 user         2.51 sys
    275828  maximum resident set size
      4008  average shared memory size
     20237  average unshared data size
       203  average unshared stack size
     81429  page reclaims
         0  page faults
         0  swaps
         0  block input operations
        74  block output operations
         0  messages sent
         0  messages received
         0  signals received
      1121  voluntary context switches
       418  involuntary context switches

最適化 -O

       27.06 real        23.48 user         4.56 sys
    493700  maximum resident set size
      4221  average shared memory size
     87521  average unshared data size
       220  average unshared stack size
    151172  page reclaims
         0  page faults
         0  swaps
         0  block input operations
        42  block output operations
         0  messages sent
         0  messages received
         0  signals received
       826  voluntary context switches
       670  involuntary context switches

最適化 -Os

       24.05 real        21.79 user         3.14 sys
    493684  maximum resident set size
      4226  average shared memory size
     91473  average unshared data size
       225  average unshared stack size
    151171  page reclaims
         0  page faults
         0  swaps
         0  block input operations
        69  block output operations
         0  messages sent
         0  messages received
         0  signals received
       832  voluntary context switches
       581  involuntary context switches

最適化 -O2

       31.42 real        23.95 user         8.32 sys
    493700  maximum resident set size
      4268  average shared memory size
    109638  average unshared data size
       230  average unshared stack size
    151169  page reclaims
         0  page faults
         0  swaps
         0  block input operations
        67  block output operations
         0  messages sent
         0  messages received
         0  signals received
       831  voluntary context switches
       602  involuntary context switches

関連 commit

ラベル: プログラミング

木曜日, 8月 02, 2007

Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation

ACM SIGPLAN (プログラミング言語に関する研究部会) による「プログラミング言語の設計と実装」に関するカンファレンスの proceeding。

全部読む時間はないから、abstract だけ目を通して最新動向把握するのと、面白そうなものだけいくつかピックアップして読むか。身近にこの手の paper 読める人がいると、手分けして作業できて効率良いんだけどねぇ。

ラベル: プログラミング

土曜日, 7月 28, 2007

お買いもの

「Binary Hacks ―ハッカー秘伝のテクニック100選」高林哲、鵜飼文敏、佐藤祐介、浜地慎一郎、首藤一幸 (オライリー・ジャパン)

gccの例外処理について調べてたところ、目次に記載があったので購入。MinGW の GCC は SjLj 使ってるけど、これは try - catch があるだけで（実行時に例外が発生しなくても）コストかかるのか。ちょっと気をつけて書かないと性能に影響出るな。

まだ目次をざっと眺めた程度だけど、ハードや実装よりの面白そうな項目がちらほら。

ラベル: お買いもの, プログラミング

PC環境再構築

Socket 939 版の Athlon 64 X2 もだいぶ値が落ちたので、Athlon 64 X2 4200+ と 1GB RAM x 2 を購入。開発用の FreeBSD 環境を Athlon XP 1600+ マシンから、VMWare Player 2.0 on Windows Vista x64 に移動。

issei@vmbsd[~/work/GameObj/tool/src/cscript] sysctl hw.model
hw.model: AMD Athlon(tm) 64 X2 Dual Core Processor 4200+
issei@vmbsd[~/work/GameObj/tool/src/cscript] time gmake -j2
111.693u 43.318s 1:29.89 172.4% 5034+23476k 132+1783io 127pf+0w

以前の環境では3分半以上かかっていたのが半分以下になった。よしよし。

VMWare Player 2.0 がインストールされたディレクトリを覗いたところ freebsd.iso というファイル名で、VMWare Tools のイメージファイル発見。VMWare Workstaion 入手しなくても VMWare Tools 使えるようになったのね。

ports の emulators/vmware-guestd6 を使ってインストール。/etc/rc.conf を設定して /usr/local/etc/rc.d/vmware-guestd.sh start したところ、vmmemctl.ko にシンボルがないと言われて kernel panic。

${INSTALL_PROGRAM} ${WRKDIR}/vmmemctl-only/vmmemctl.ko ${VMWARE_KMODDIR}

emulators/vmware-guestd6/Makefile の上記の行、INSTALL_PROGRAM だとシンボル情報を strip してしまうので、STRIP を空文字列にするか INSTALL_DATA にしないとダメじゃないかなぁ。とりあえず手でコピーして対処。後で port メンテナの人に話振っておこう。

ラベル: プログラミング

金曜日, 7月 20, 2007

Graphvizによるファンクション・コールの視覚化

プログラム中の関数呼び出しを可視化する話。

面白そうだなと思って実行してみたら pvtrace コマンドがマトモに動かない。

シンボル検索に線形検索を使っている
関数アドレスからシンボル名への変換に、毎回 popen("addr2line .."); を実行している
関数呼び出しの相関関係の記録に、二次元配列を使っている

小規模な C プログラムなら動くけど、シンボル数が増えがちな C++ プログラムに使うには根本的にデータ構造作り変えないとダメだ。あと C++ だと全部の関数シンボルを図に書こうとすると STL コンテナなども出てきて数が多すぎなので、端折れるようにした方が良い。

nm コマンドと Perl 使って書いてみるか。まず Graphvis 用のファイルではなく、関数のコールシーケンスそのまま書き出すプログラム。

#! /usr/bin/perl

use strict;
use vars qw($NM_CMD %SYMBOLS);

$NM_CMD = "/usr/bin/nm -S";

my $file_sym = $ARGV[0] or die;
&read_symbol($file_sym);
my $file_inst = $ARGV[1] or die;

open(F, "$file_inst") or die "$file_inst";
my $depth = 0;
while (<F>) {
 chomp;
 /^([EX])0x([\da-f]+)/ or next;
 my ($ex) = $1;
 my ($addr) = hex($2);

 $ex eq 'E' and ++$depth;
 $ex eq 'X' and --$depth;
 next if $ex eq 'X';
 next unless exists($SYMBOLS{$addr});
 print ' ' x $depth, $SYMBOLS{$addr}, "\n";
}
close(F);

sub read_symbol
{
 my $file = shift;

 open(P, "$NM_CMD $file |") or die "$NM_CMD $file";
 while (<P>) {
  next unless /^([\da-f]+)\s+([\da-f]+)\s+[tTW]\s+(\w+)$/;
  my ($begin, $size, $symbol) = ($1, $2, $3);

  local($_) = $symbol;
  next if /^_ZNK?5boost/;
  next if /^_ZN?K?S/;
  next if /^_ZNK?9__gnu_cxx/;
  next if /^_Z41__static_/;
  next if /^_ZNK4mpl/;
  next if /^__tcf_/;
  next if /^_Z8__istypeim/;
  next if /^_GLOBAL__/;
  next if /^_Z10__maskruneim/;
  next if /^_Znw/;
  next if /^_Zdl/;
  next if /^__cyg_/;

  $SYMBOLS{hex($begin)} = $symbol;
 }
 close(P);
}

実行結果

main
 _ZN7CScript7SysDeclC1Ev
  _ZN7CScript7ICtxLexC2Ev
  _ZN7CScript7SysDecl4ImplC1Ev
 _ZN7CScript9LexHolderC1EPNS_7ICtxLexEPSi
  _ZN7CScript9LexHolder4ImplC1EPNS_7ICtxLexEPSi
   _ZN11yyFlexLexerC2EPSiPSo
    _ZN9FlexLexerC2Ev
 yyparse
  yylex
   _ZN7CScript9LexHolder5yylexEv
    _ZN7CScript9LexHolder4Impl5yylexEv
    (以下略)

よしよし。シンボル名は c++filt に通せば見やすくなる。

週末に Graphivis の文法調べて図にしてみよう。

追記

週末待たずにできた (callgraph.pl)。

#! /usr/bin/perl

use strict;
use vars qw($NM_CMD %SYMBOLS %CALLS %TOTAL);


$NM_CMD = "/usr/bin/nm -S";

# --------------------------------------------------------------------
my $file_sym = $ARGV[0] or die;
&read_symbol($file_sym);
my $file_inst = $ARGV[1] or die;

my (@stack);
open(F, "$file_inst") or die "$file_inst";
my $depth = 0;
while () {
 chomp;
 /^([EX])0x([\da-f]+)/ or next;
 my ($ex) = $1;
 my ($addr) = hex($2);

 if ($ex eq 'E') {
  push(@stack, $addr);
 } elsif ($ex eq 'X') {
  pop(@stack);
 }
 next if $ex eq 'X';
 next unless exists($SYMBOLS{$addr});

 my $sym_callee = $SYMBOLS{$addr};
 my $sym_caller = &find_caller(\@stack);

 next unless $sym_caller;

# print "$sym_caller -> $sym_callee\n";
 ++$CALLS{$sym_caller}{$sym_callee};
 ++$TOTAL{$sym_caller};
 exists($TOTAL{$sym_callee}) or $TOTAL{$sym_callee} = 0;

# print ' ' x $#stack, $sym_callee, "\n";
}
close(F);

# --------------------------------------------------------------------
print "digraph G \{\n\n";
# vertecies
foreach (keys %TOTAL) {
 my $caller = $_;
 if ($TOTAL{$caller} > 0) {
  print "  \"$caller\" [shape=rectangle];\n";
 } else {
  print "  \"$caller\" [shape=ellipse];\n";
 }
}
# edges
foreach (keys %CALLS) {
 my $caller = $_;
 foreach (keys %{$CALLS{$caller}}) {
  my $callee = $_;
  my $count = $CALLS{$caller}{$callee};

  print "  \"$caller\" -> \"$callee\" [label=\"$count calls\" fontsize=\"10\"];\n";
 } 
}


print "}\n";

# --------------------------------------------------------------------
sub read_symbol
{
 my $file = shift;

 open(P, "$NM_CMD $file |") or die "$NM_CMD $file";
 while () {
  next unless /^([\da-f]+)\s+([\da-f]+)\s+[tTW]\s+(\w+)$/;
  my ($begin, $size, $symbol) = ($1, $2, $3);

  local($_) = $symbol;
  next if /^_ZNK?5boost/;
  next if /^_ZN?K?S/;
  next if /^_ZNK?9__gnu_cxx/;
  next if /^_Z41__static_/;
  next if /^_ZNK4mpl/;
  next if /^__tcf_/;
  next if /^_Z8__istypeim/;
  next if /^_GLOBAL__/;
  next if /^_Z10__maskruneim/;
  next if /^_Znw/;
  next if /^_Zdl/;
  next if /^__cyg_/;

  $SYMBOLS{hex($begin)} = $symbol;
 }
 close(P);
}

sub find_caller
{
 my $stack = shift;
 my $depth = scalar(@$stack);

 local($_) = $depth - 2;
 for (; $_ >= 0; --$_) {
  my $addr = $stack->[$_];

  return $SYMBOLS{$addr} if $SYMBOLS{$addr};
 }
}

プログラムの実行ファイル名を cscrc, 実行時トレースファイルを cscrc.sym とすると、下記コマンドで Graphvis 入力ファイルを作成できる。

% ./code/callgraph.pl cscrc cscrc.sym | c++filt > cscrc.dot

CScriptのコンパイラ・仮想マシン実行の様子を図にしてみた。

ラベル: プログラミング

水曜日, 7月 18, 2007

続々ゲームプログラミングについて各分野で60点を取れるくらいの感じの本

だだもれ経由或曰: ゲームプログラミングについて各分野で60点を取れるくらいの感じの本

何冊かお勧めが追加されてる。私も読んでないのがあるから、あとで注文しときます。

ドラゴンブックが最適化に入れてあるのは、確かに少し違うかもしれません。でもコンパイラ屋さんで食っていくのでなければ、処理系が行う最適化についてはドラゴンブックで取り上げられているレジスタ割り当て、ヒープホール最適化、共通部分式除去、ループ最適化ぐらいを理解しておけば、とりあえずは間に合うかなと思ってます。

あと最適化に関しては、広く言うと記憶域と速度のトレードオフ、データの事前計算 (コンピュータグラフィックスだと PRTとか) なども含まれると思いますが、そのへんも包括的に扱ってる本はまだ見つけてません。

http://www.page.sannet.ne.jp/hirasho/diary/diary0707.html#17p2

本というのはどこか本を作る会社が作るわけで、どうやってそういう所とそういう話になるんだろう、とかいうあたりがまるで想像できません。

大きな会社なら出版社とも付き合いがあると思いますから、その編集さん通して企画に適した分野の編集さん紹介してもらえると思います。

私は学生時代にテクニカルライティングをやっていたことがあり、その時に一緒に仕事した編集さんがいたり（しばらく連絡取ってないので、もしかしたら辞めてしまってるかもしれませんが）、あとは今の会社で付き合いがある出版社があります。まったく人間関係がないところから企画を持ち込んだことはありません。

仕事の立ち上げ方は会社によって差があると思いますが、私の場合はこちらから案をいくつか出して編集さんが見込みありそうなものを絞り込み。メールベースで粗い企画内容を打ち合わせして、それをもとに編集さんが企画書を起こして社内の編集会議通してスタートって感じでした。小説などは違うかもしれませんが、実用系の書籍の場合はこんなものかと。

ラベル: プログラミング

火曜日, 7月 17, 2007

Cooperative Task Management without Manual Stack Management (2)

先日の続き。覚書。

理論的な話。このあとで Win32 の Fiber 使った Design & Impl. の話が出てくる。

読むのは section 4 まで終わってるんだけど、メモをそこそこ見られる形に起こすのが面倒だ。なんか適当なツール使わないと時間がもったいないな。

1. Introduction

プロジェクトにおいて、並行性に関して提供すべきプログラミングモデルを決める

プロジェクトメンバーが過去に経験したバグ

再現が難しい
発見と修正はさらに難しい

コミュニティの叡智⇒イベントドリブン

このモデルによって次のような問題発生の機会自体が減る

競合 (race condition)
デッドロック

経験を積むにつれて "イベントドリブン" という用語が複数の個別コンセプトをまとめたものと判明。もっとも重要なこととして、"イベントドリブン" という用語が、並行性に関する推論において、利益はやっかいな手動スタック管理なしには実現できないということを示唆している。

Section 2

まとめると問題になる 2 つの個別コンセプトを定義
主要なアイデアと混乱しないよう 3 つの関連するコンセプトについて触れる

Section 3

手動スタック管理 vs 自動スタック管理
自動スタック管理における最大の問題を緩和する方法を示す

Section 4

混在スタック管理モデル
単一プログラムで、自動スタック管理と手動スタック管理の混在/相互運用を可能に

Section 5

2つのシステムに実装した経験談

Section 6

Related work

Section 7

結論

2. Definitions

コンセプト

タスク管理
スタック管理
I/O 応答管理
衝突管理 (conflict management)
データ分離 (data partitioning)

すべてが直交しているわけではないが、個別に考えることが、全システム中でどのように相互作用しているかを理解するのに有用。

2.1 Task management

タスク

個別の制御フローを持つ
共有状態へのアクセスを行う

タスク実行の3モデル

preemptive task management

タスク側が検知しないタイミングで実行を中断される
マルチプロセッサへのタスク分散可能

serial task management

次のタスク実行前に、一つのタスクが実行を終了する
共有状態へのアクセスで競合が発生しない
共有状態に対してタスク間不変性の定義と保証 (assure)
マルチプロセッサで並列処理できない
遅いタスクが長時間他のタスクを待たせてはいけない

cooporative task management

タスクは明確に定義された地点でのみ、実行を中断して他のタスクに制御を渡す。一般には長時間かかる I/O 処理が制御切り替えポイント。
タスクが I/O 処理を待たずに処理をインターリーブ (交互実行) するには適しているが、マルチプロセッサ並列性を利用してアプリケーション性能向上はできない。
グローバルな共有状態の不変性は、タスクが明示的に切り替わるタイミングでのみ保証すれば良い。タスクが再実行 (resume) したときには整合性が保たれていると想定できる。
タスク切り替え前に、グローバルな状態に依存するタスク固有の状態があった場合は、実行再開後に無効になっている可能性がある (同様の問題が preemtpvie マルチタスクでロックを開放する場合にも発生する)
I/O ライブラリ関数呼び出しをラップして、I/O の初期化を行い制御を他のタスクに移すようにする必要あり。
I/O 処理終了後に、関連するタスクをスケジュール可能にする必要あり。

2.2 Stack management

協調的タスク管理を実現するための一般的な方法: プログラムをイベントハンドラの集合として構成する。この手法を「手動スタック管理」と呼ぶことにする。
点:
概念的に1つのタスクの制御の流れ、ならびにタスク固有の状態が複数の手続きに分割される。プログラミング言語のスコープ機能を無意味にする。これがソフトウェアの発展にともなうほとんどの問題を発生させるので本質的。
重要：構造化プログラミング言語が提供する自動スタック管理を利用しつつ、協調的タスク管理を使うことも可能 (section 3.3)
いくつかの言語では、言語組み込みの機能として透過的な closure 作成可能 (例; scheme の call-with-current-construction) で、手動スタック管理の考えを未然に防ぐ。
この peper では洗練された closuer がない伝統的なシステム言語でのスタック管理問題に焦点

2.3 I/O management

synchronus I/O management: I/O 処理終了まで呼び出し側タスクがブロックされる
asynchronism I/O management: 呼び出し側に即座に戻る。重複する非同期処理を開始して、結果が返ってくるのを待つ。

I/O の並行性はタスク実行の並行性とは独立。なぜなら、I/O 処理は計算の共有状態にアクセスしないため。

適切なプリミティブがあれば、非同期 I/O をラップして同期 I/O を提供する、あるいは逆を提供することも可能。

2.4 Conflict management

タスク管理方法によって、共有状態に対する原子性 (atomicity) 保証方法が異なる

conflict management: 使用可能な原子性からリソース衝突を回避する意味のある手段に変換する方法についての考察

serial task management
- タスク全体が共有状態に対する原子的操作
- タスク間の衝突回避のための明示的なメカニズム不要
preemtpvie task management
- 他のタスクが並列で実行されているため、常に共有状態の不変性を保証する必要がある

一般的な解決策: 同期プリミティブ (e.g. ロック、セマフォ、モニタ)

ハードウェアもしくはランタイム環境により提供される小規模な原子的操作を基礎として、共有状態が常に保つべき複雑な不変性を維持するメカニズムを構築する。

pessimistic synchronize mechanism: 処理を完了するのに必要なリソースから他のタスクを締め出す
optimistic synchronize mechanism: 投機的に結果を求め、他のタスク処理と衝突していることを検出したら再実行、もしくはそれ以上進められたない場合には pessimistic synchronize mechanism に移行する。

協調的マルクタスクでは任意の大きな原子的操作を効果的に提供できる。
明示的に指定された任意の yield 替えポイント間は原子的に (他のタスクに途中で切り替わることなく) 実行。
単一プロセッサ用 OS カーネルにおいて、割り込みをマスクすることで原子的シーケンスを構築するのと類似。

ラベル: プログラミング

続ゲームプログラミングについて各分野で60点を取れるくらいの感じの本

各分野をつまみ食いさせて興味を持たせるきっかけにしつつも、最悪そこに書いてあることだけでもとりあえずゲームが作れる、というぐらいの本があると便利な気がするのです。

その点は同感です。新人プログラマ向けの研修で使用している資料を整理すると、ちょうど良さそうなんですけどね。

実際に文章を書く場合の話ですが、本当に1から書くとかなり大変ですが、概説的な内容なら、

対象読者層を決める
章立てを決める
各項目について、参考文献を探してくる
詳細は参考文献に当たってもらうことを前提として、各項目について必要最低限の内容を絞って記述する。

その際の記述のベースとして、参考文献を活用する。Copy & Paste はもちろんまずいですが、内容を咀嚼した上で自分が必要と思うことを補って利用するのは問題ありませんので。
詳細は専門書に当たってもらうこととして、リファレンスを充実させる。

というような作り方をすると、比較的短期間で筋が通ったものが作れると思います。

同人でやってると〆切が曖昧になってなかなか話が進まないので、可能なら仕事にしてしまった方が良いと思います。会社と、著作権や印税収入は会社に帰属させる形にするから時間使わせてくれ、というような交渉はできません？

私はひらしょーさんがいっているような書籍は社会的にも出す意味があるし、きちんと書ければ、それなりに売れ行きも見込めると思います。

ラベル: プログラミング

土曜日, 7月 14, 2007

ゲームプログラミングについて各分野で60点を取れるくらいの感じの本

ゲームプログラミングについて各分野で60点を取れるくらいの感じの本が私の知る限りない。幾何、ライブラリ設計、アプリケーション設計、通信、素材管理、ツール、AI、モーション、最適化、デバッグ体制、描画技術、ハードウェアアーキテクチャ、アルゴリズム、などなどの全分野についてそれなりな知識を得られるような本。

一冊ではなく、既存の書籍をワンセットにしてくれということなら簡単にリストを作れそうです。ゲームプログラミング固有の知識分野は、ほとんど無いと思いますので。

実際、私が入社後、ゲームプログラミングのために読んだものは開発機材のマニュアルとサンプルコード(PS2 Linux の DVD-ROM に大半入ってる) 、実際のゲームのコード。あとはメモリや素材管理についてリードプログラマに聞いた程度、それ以外に関しては当時すでに読んでいた書籍, paper やコードで間に合いました。

というわけで、分野別に役立った本リスト。一部を除いて入社前の学生時代に読んでたものなので、別に経験何年の職業プログラマでなくとも読めるはず。

物理/幾何/モーション/描画系

大学教養課程の力学の教科書
RealTime Rendering (ここから参考文献をいくつか辿って追加で読んだ)

ハードウェアアーキテクチャ

コンピュータの構成と設計
計算機設計技法

アルゴリズム

定本 Cプログラマのためのアルゴリズムとデータ構造
STL の <algorithm>, <numeric>
珠玉のプログラミング
The Art of Computer Programming

最適化

コンパイラ　原理・技法・ツール
Inside the C++ Object Model

デバッグ

Code Complete
Writing Solid Code
Debuging the Development Process

素材管理

ゲームクリエーターズバイブル

通信

TCP/IPによるネットワーク構築
詳解 TCP/IP
UNIX Network Programming

ライブラリ設計/アプリケーション設計

ソフトウェア作法
プログラム設計の着想
プログラマの打ち明け話
Lions' commentary on UNIX
4.4BSDの設計と実装
デザパタ本とか UML 本は、共通言語として使うために読んでおいたほうがいいかも
その他、ソースコードいろいろ (FreeBSD, Apache, Emacs, etc...)

AI

AI Programming Wisdom

あとは全般的な Tips として Geme Programming Gems シリーズ。オンラインゲームやるなら RDBMS 関連も追加、プログラミング言語として C++ 関連とツール用に Perl, Ruby, Python, C# どれかは押さえておきたい

CG, 代数, アルゴリズム, コンパイラ理論など、学問的に専門分野が確立しているものは、書籍で大枠を押さえて、先端の話は paper 探してくるのが手っ取り早い。今だと Internet で探すと PDF で掲載されている場合も多いし、理工系の論文誌だと有名どころは東工大の付属図書館にあるので、大岡山まで足を延ばせば有料でコピーできる。

ラベル: プログラミング

水曜日, 7月 11, 2007

Coroutines in Lua

組込用として広く使われている言語に Lua があるが、これは複数の制御の流れを扱うために（CScript のような明示的なスレッドではなく）非対称コルーチンを用いている。それに関する paper。自分で協調的マルチスレッディング処理を設計/実装してみて多少理解が深まったところで、読んでみようということで。

しかコルーチンの話って 1963 年に Conway, M. が既に paper 出してるのね。何年遅れでトラッキングしてるんだか＞私

追記

paper 覚書。

2. Lua Coroutines

コルーチンの方式二つ。プログラムの記述能力は変わらない（paperにサンプルコード有り）。Lua では asymmetric coroutines を採用。理由は単純さならびにポータビリティ。

symmetric coroutines

指定したコルーチンに制御を移すという、単一の操作のみがある。
すべてのコルーチンが対等なため、制御の流れが分かりづらい。

asymmetric coroutines

コルーチンの起動・停止という2つの異なる操作がある。
一般のサブルーチン呼び出しと振る舞いが似ており、制御の流れが分かりやすい。

コルーチンは、本質的には独立したプログラムカウンタとレジスタをリソースとして持つプログラム実行状態。Lua ではスクリプト言語と C 言語の関数を相互呼び出しできるため、リソースとして含まれるスタックには仮想マシンの関数呼び出しとCの関数呼び出しが含まれる。

Cスタックを退避・復元するポータブルな方法はないため、Lua ではコルーチンスタックにC関数が含まれている場合にはコルーチンの中断(yield)を不可としている。この目的のためにも asymmetric coroutines が適している。

2.1 Lua Coroutine Facilities

coroutine.create: コルーチン作成
coroutine.resume: コルーチン再開
coroutine.yield: コルーチン中断
coroutine.wrap: コルーチン補助関数

機能的には create, resume, yield ですべて。wrap はコルーチン呼び出し、停止をあたかも通常の関数のように使えるようにするためのラッパーを作成する。

コルーチンとの通信方法

既存の関数 f() から coroutine.wrap() を使ってコルーチンを作成した場合。

メインルーチン⇒コルーチン

メインルーチン側から見て（実引数）
コルーチン呼び出しの引数
コルーチン側から見て（仮引数）
- 初回：f() の引数
- 二回目以降：coroutine.yeield の戻り値

コルーチン⇒メインルーチン

コルーチン側から見て
yield() の引数

メインルーチン側から見て
コルーチンの戻り値

2.2 An Operational Semantics for Lua Asymmetric Coroutines

プログラム意味論の議論。要は coroutine.create, coroutine.resume, coroutine.yield というオペレータがどういう動作をするのかを形式的に定義してるだけ。特記する内容は特になし。

3 Programming With Lua Asymmetric Coroutines

Lua コルーチンを使ったプログラム例。

generator: 一連の値を作り出し、起動するたびに呼び出し側に新しい値を返すもの。

コルーチンを generator として使い、二分木の pre order で走査する iterator を実装する例。関数再帰呼び出しを用いて、非常に直感的かつシンプルに実装している。

ちなみに gcc 3.4 付属の STL で使っている赤黒木のノード。

  struct _Rb_tree_node_base
  {
    typedef _Rb_tree_node_base* _Base_ptr;
    typedef const _Rb_tree_node_base* _Const_Base_ptr;

    _Rb_tree_color      _M_color;
    _Base_ptr           _M_parent;
    _Base_ptr           _M_left;
    _Base_ptr           _M_right;
  // 以下略

イテレーション処理のコード。FreeBSD だと /usr/src/contrib/libstdc++/src/tree.cc にある。

  _Rb_tree_node_base*
  _Rb_tree_increment(_Rb_tree_node_base* __x)
  {
    if (__x->_M_right != 0)
      {
        __x = __x->_M_right;
        while (__x->_M_left != 0)
          __x = __x->_M_left;
      }
    else
      {
        _Rb_tree_node_base* __y = __x->_M_parent;
        while (__x == __y->_M_right)
          {
            __x = __y;
            __y = __y->_M_parent;
          }
        if (__x->_M_right != __y)
          __x = __y;
      }
    return __x;
  }

親ノードへのリンクがあるのが大きな違い。コルーチンだと「どこまで辿ったか」「このノードはどこから辿ってきたのか」という情報が関数呼び出しのコールスタックに暗黙に保持されているのに対して、こちらだと自前で管理する必要がある分だけ複雑になる。

ただツリーが深くなった場合、再帰呼び出しだとツリーの深さ分だけスタックを喰うから、実はコルーチン方式のイテレータはかなりメモリ食い。C++ の STL イテレータのように手軽にコピーはできない。

3.2 User-Level Multitasking

並行プログラミングにコルーチンを用いる方法について。コルーチンは本質的には独立したプログラムカウンタとレジスタをリソースとして持つプログラム実行状態なので、スレッドと同じように並行プログラミングに使える、しかも使い方簡単、という話。

ただ、ここは paper に書いてあることは額面どおりは受け取れないな。

Lua の仕様だと並列処理（同時に複数のコルーチンを実行する）は、たとえマルチプロセッサマシンでも無理。並列処理を実現するなら、今はひとつになっているコルーチンの再開と実行終了待ち (coroutine.resume) を分けることになるが、そうなると使い方はスレッドと同じぐらい面倒にならざるをえない。

また並行処理に関しては、オブジェクト指向でステートマシンとしても実装するのもシンプル＆効率的。

4. Coroutines in Programming Languages

コルーチンがあるプログラミング言語の話。

Simula: symmetric, asymmetric 両方あり。コルーチン間の階層構造は、プログラム実行時に動的に生成。同じ階層にあるコルーチンは symmetric で resume を使って切り替えられる。子階層のコルーチンは call でアクティブ化。非常に複雑。
BCPL: C言語の祖先。symmetric, asymmetric 両方ありだが、asymmetric coroutine のみを使用するのが一般的。
Modula-2: 並行処理実装のための基礎構造として symmetric coroutine を導入したが、あまり使われていない。
CLU: iterator という抽象概念を導入し、呼び出し間で状態を保つことから coroutine として説明。first class object ではなく使い方に厳しい制約あり。
Python: yield文を含む関数をgenerator functionと呼び、呼び出すとプログラム中の任意の場所で再開できる first class object を返す。ただし yield できるのは、その generator function の本体中のみで、そこからさらに関数を呼び出した先で yield するのは禁止。
Stackless Python: もともと継続 (continuation) を言語機能に取り入れるために作られて、その後 generator, coroutine, microthread をサポートする方向に主眼が移る。paper は 2000 年時点の話をしてるが、サイトを見るとどうやら今でも継続して開発中みたい。
Icon: ゴール指向評価 (goal-directed evaluation) で使う generator が制約された形の asymmetric coroutine。co-expression が事実上 asymmetric coroutine (参考：Co-expressions in Icon)。

個人的には stackless python のコードは読んでみようと思った。あと今時だと、C#, JavaScript の yield 文について追記かな。

ラベル: プログラミング

スクリプト D&I (18) タイムライン処理

今回のスクリプト言語は、C++ で書かれたプログラムから定期的に呼び出して使うことを想定しているが、特定の時間に処理を行いたいことが良くある。たとえば対戦格闘系のゲームを作っている場合、技の発動と同時にスクリプトを走らせて

0.5秒後から無敵状態に
0.7秒後に攻撃ヒット判定発生(1回目)
0.9秒後に攻撃ヒット判定発生(2回目)
1.0秒後に無敵状態解除

といった処理をさせたい。

開始時点からの経過時間を秒単位で取得するシステム関数 sysGetTimeSec() を用意すれば、この処理は次のように書ける。

void main()
{
　　while (sysGetTimeSec() < 0.5)
　　　　sysPass(1);
　　// ここで無敵状態に
　　while (sysGetTimeSec() < 0.7)
　　　　sysPass(1);
　　// ここでヒット判定1回目
　　while (sysGetTimeSec() < 0.9)
　　　　sysPass(1);
　　// ここでヒット判定2回目
　　while (sysGetTimeSec() < 1.0)
　　　　sysPass(1);
　　// ここで無敵状態解除
}

ただし、以下の点でバグが入り込む余地が大きい。

記述の順序を逆転させると動作がおかしくなる（細かいタイミング調整を行っていると、うっかり逆転させてしまうことがある）
やりたいことに対して余分な記述が多い

後者は C プリプロセッサマクロでも対応可能な範囲だが、エラー検出を容易にするためと、マルチスレッド対応を考えて、スクリプト言語にタイムラインを意識した記述を行うための文法を定義することに。サンプルコードは次のようになる。

timeline player_timeline()
{
　　when (0.5) {
　　　// ここで無敵状態に
　　}
　　when (0.7) {
　　　// ここでヒット判定1回目
　　}
　　when (0.9) {
　　　// ここでヒット判定2回目
　　}
　　when (1.0) {
　　　// ここで無敵状態解除
　　}
}

void main()
{
　　sysThreadBeginTimeline(player_timeline); // タイムライン処理の起動
　　sysThreadWaitAll(); // タイムライン処理が終わるまで待つ
}

タイムラインに沿った記述を行うためのデータ型 timeline を用意し、文法を定義。当初、字句解析ルーチンから timeline という文字列に対して型を表す TOK_CAST を返したところ、構文解析ルーチンが通常の関数とタイムライン記述を行う関数どちらか識別できないとエラーになったので、専用のトークン TOK_TIMELINE を用意して文法を見直すことに。意外と面倒だった。

そもそも変数をまとめて宣言する (int a, b; とか) ときのために node_cast に副作用設定しているのがイマイチなんだよな。

設計上の選択

タイムライン処理をメインスレッドで実行するのか、それとも別スレッドに分けるか？
タイムライン処理スレッドは、スクリプト実行時に自動的に走らせるか、それともスクリプトコード中で明示的に開始指定させるか？
タイムライン処理の実行終了をどう検知するか？
記述順序と時刻の逆転がある場合、コンパイル時エラーとするか、コンパイラが並び替えを行うか？

今回は言語・VMをマルチスレッド対応にしてあるので、タイムラインもそれに合わせてマルチスレッド化する。タイムラインの基準となる時刻についても「スクリプト開始時点から」ではなく「スレッド起動時点から」とする。

記述順序の問題は、エラー検出もコンパイル時並び替えもたいして手間は変わらないので、スクリプトコンパイラが並び替え処理を行う方向で。

個々の when() 句は、次のように書きなおして仮想機械のマシンコードに落とす。

when (2.3) {
　　do_something;
}

// ---------------------------------------- //
void __when()
{
　　int run = (int)(2.3 * CSCR_FRAMES_PER_SEC);

　　while (run >= sysThreadGetTime())
　　　　sysPass(1);

　　do_something;
}

// ---------------------------------------- //
void __when()
{
　　int run = (int)(2.3 * CSCR_FRAMES_PER_SEC);　　// (*1)

loop_begin:　　　　　　　　　　　　　　　　　　　　// (*2)　　[taddr1]
　　if (!(run >= sysThreadGetTime()))
　　　　goto loop_end;　　　　　　　　　　　　　　//　　　　[taddr2]
　　sysPass(1);
　　goto loop_begin;

loop_end:
　　do_something;　　　　　　　　　　　　　　　　// (*3)
}

タイムライン関数全体は、次のように考えて1 passで対応可能に。2 pass 以上にして、まじめに最適化を行えばジャンプ処理は減るが、もともと性能に重きを置いていない言語なので、お手軽に済ませる。


goto label;
label_when_1:
　　// 最初の when 句に対応するコード
　　return;
label_when_2:
　　// 2番目の when 句に対応するコード
　　return;
label_when_3:
　　// 3番目の when 句に対応するコード
　　return;
label:
　　// when 句を、時刻の小さい順に呼び出す（コンパイル時にソートする）
　　call label_when_1
　　call label_when_3
　　call label_when_2

call - return 処理はあるが enter - leave (スタックフレームの作成/解放) 処理は入れてない。おそらく大丈夫だと思うけど、スタック壊さないか一度よく考えてみよう。

ラベル: プログラミング

日曜日, 7月 01, 2007

スクリプト D&I (17) 割り込み処理

設計で悩み中。

割り込み処理の背景から。

今回のスクリプト言語は、C++ で書かれたプログラムから定期的に呼び出して使うことを想定している。基本的なシナリオは次の通り。

VirtualMachine のインスタンスをメンバ変数として持つ。
一定間隔ごとに VirtualMachine::run() メンバ変数を呼び出す。最初は main() 関数から、二回目からはスクリプトが前回実行を中断したところから処理が再開される。
スクリプト側に制御が移ったら、スクリプト側では必要な処理を行って sysPass() システム関数を呼び出し動作を中断。

ただ、処理の内容によってはこのプログラミングモデルよりも、必要に応じて C++ 側からスクリプトに「この処理をしてほしい」とリクエストする形にした方が記述しやすいことがある。実は現行のスクリプト言語の枠内でも、Win32 のメッセージ処理のように

// スクリプトのエントリポイント
void main()
{
　　int msg;
　　for (;;) {
　　　　// C++ 側から処理要求を取得
　　　　msg = getMessage();
　　　　switch (msg) {
　　　　case MSG_EMPTY: // 処理要求なし
　　　　　　sysPass(1);
　　　　case MSG_EXIT: // 終了
　　　　　　sysExit();
　　　　　　// 以下メッセージの種類に応じて、処理を分岐
　　　　case MSG_..
　　　　　　// ...
　　　　}
　　}
}

みたいなコードを書けば同じことは実現できるが、メッセージループみたいなゴツい代物をスクリプトで書くとなると、それなりのスキルがある人間しかスクリプトを書けなくなり、せっかく処理をスクリプトに逃がした意味が半減してしまう。MSG_EMPTY, MSG_EXIT の処理をミスると悲惨なことになるし。

そこで、スクリプト側の関数を C++ から直接呼び出せるようにする。方法はいくつか考えられるが、シンボルテーブルをコンパイル済みのスクリプトバイトコードに残さないことを前提とすると、C++ 側に公開したい関数に番号を付けておき、C++ 側からはその番号を使って呼び出すのが良さそう。

通常の VirtualMachine::run() とは非同期のタイミングで実行されるので、この処理の枠組みを割り込み (interrupt) と呼ぶことにして、スクリプトから C++ 側に公開する関数を割り込み関数、割り込み関数につける番号を割り込み番号としておく。割り込み処理を実行する C++ 側コードは次のようになる。

VirtualMachine vm;
// 初期化処理いろいろ省略
vm.interrupt(1);

問題はスクリプト側関数への番号づけと、それを VirtualMachine のインスタンスに反映させる方法をどうするか？　まず思いつくのが既存のシステム関数の枠組みを利用してスクリプト側から登録させる方法、それからスクリプトをコンパイルする時点で割り込み番号と割り込み関数を解析してファイルに書き出しておき、それを VirtualMachine に読み込む際にローダーが登録してしまう方法。

システム関数で登録

/*
* 割り込みテスト
*/
// 割り込み処理1
interrupt testIntr1()
{
　　sysPrintS("intr 1\n");
}

// 割り込み処理2
interrupt testIntr2()
{
　　sysPrintS("intr 2\n");
}

void main()
{
　　// 割り込み関数登録
　　sysIntrRegister(1, testIntr1);
　　sysIntrRegister(2, testIntr2);
　　sysPass(1);
}

コンパイラとローダが処理

/*
* 割り込みテスト
*/
__interrupt[1] testIntr1()
{
　　sysPrintS("intr 1\n");
}

__interrupt[2] testIntr2()
{
　　sysPrintS("intr 2\n");
}

void main()
{
}

実装の手間が少ないのは前者だけど、スクリプトの作成/保守効率を考えると後者の方が良いかな。あと前者のコードだと main() で登録するのは面倒なので、スクリプト読み込み時に自動的に実行される処理（コンストラクタというか Perl の BEGIN {} 関数というか) が欲しくなる。

またいずれのケースでも割り込み関数から呼び出せるシステム関数は制約しておかないとまずい。たとえば sysPass() を呼び出しても、再度そこから処理を再開することはないので意味がない。あとは割り込み関数のプロトタイプをどうするか（パラメタと戻り値は使えるようにするか？）も考えどころ。引数は、割り込み関数内から必要に応じてシステム関数呼び出して C++ 側に聞きに行けばいいから、無しでも良いか。

とりあえず、手元では両方実装してみた。分散 SCM だと、こういう時にいちいちブランチ切るとかせずに hg clone でサクサク作業始められて便利ですね。

2007/07/02 10:00追記

clone したリポジトリを Web 経由で見えるように。

ラベル: プログラミング

火曜日, 6月 26, 2007

LL魂

チケットget!

ラベル: プログラミング

月曜日, 6月 25, 2007

Seven Deadly Sins of Introductory Programming Language Design (PDF)

曰く「初心者向けプログラミング言語設計における七つの大罪」。Abstract によると

We discuss seven undesirable features common to many programming languages used to teach first-time programmers, and illustrate typical pedagogical difficulties which stem from them with examples drawn from the programming languages ABC, Ada, C, C++, Eiffel, Haskell, LISP, Modula 3, Pascal, Prolog, Scheme, and Turing. We propose seven language design (or selection) principles which may reduce the incidence of such undesirable features.

初心者向けのプログラミング言語で避けるべき7つの機能を取り上げ、逆にそれらの機能による影響を抑える 7 つの言語設計上の原則を提示する、とのこと。面白そうなので、ぱらっと目を通してみます。

ラベル: プログラミング

Bogo Sort

人から教えてもらったソートアルゴリズム。

平均演算量 O(n×n!) --- 頭悪すぎる。Bogo Sort つながりで Infinite monkey theorem とか RFC2795 The Infinite Monkey Protocol Suite (IMPS) とか読んで笑い転げてました。

ラベル: プログラミング

Google Developer Day Tokyo - 鵜飼文敏

先月末に開催された Google Developer Day Tokyo 最後のセッションを記録した映像。Google 内部での開発体制について。

レベルの高い開発者が数人規模でチームを組んで動くのは、technology oriented な開発をするには理想的な環境だよね。Google の社内インフラも一度見てみたい気がする。

ラベル: プログラミング

土曜日, 6月 23, 2007

Generics 本探索

amazon で適当な書籍がないか調査。

C++ Template Metaprogramming: Concepts, Tools, And Techniques From Boost And Beyond (C++ in Depth Series)

これ良さそうかな。amazon.co.jp には大した情報が載ってないけど、amazon.com に細かい内容＆レビューあり。

ラベル: プログラミング

金曜日, 6月 22, 2007

Generics Book

Nutshell Handbooks から、浸透しつつある新たなソフトウェア設計パラダイム「ジェネリックプログラミング」についての新刊「C++ and Haskell ``Generics''」が登場。

ジェネリックプログラミングは、手続き型やオブジェクト指向では難しいデータ型によらない汎用的なアルゴリズム記述を可能にするとともに、ソフトウェアの構成要素であるポリシーをコンパイル時に組み合わせることで、型安全性を保ちつつ実行時ペナルティなしでの部品再利用を促進する。

この本では、ジェネリックプログラミングの背後にある基礎概念の解説とともに、Haskell, C++ template を用いてジェネリックプログラミングを行う際に必要となる各種技法、またジェネリックプログラミングの実現例として ghc 標準ライブラリならびに C++ Boost Library に含まれるいくつかのライブラリのソースコードが詳解されている。また標準化が進められている次期 C++ 規格の動向についても簡単に触れてある。

……とかあったら、読みたいんだけどな。Modern C++ Design の Update 版でも良いけど。なお、画像は O'REILLY book cover ででっち上げたもので実在しませんので悪しからず。

ラベル: プログラミング

木曜日, 6月 21, 2007

スクリプト D&I (15) システム関数登録処理 - 2

スクリプト言語からC++側の関数 (システム関数) を呼び出す際のフローと、それをサポートする C++ コード自動生成ルーチンの設計/実装が一段落。

インタプリタ型のスクリプト言語から C++ 側のコードを呼び出す場合 (a) 呼び出されたシステム関数の種別によって処理を分岐し、 (b) 仮想マシン側のメモリから引数を取出し然るべき型に変換した上で、(c) 実際の処理を行い、(d) 結果を戻り値として仮想マシンに受け渡す必要がある。

実現に際しては、システム関数の識別子をどのように保持するか（文字列で関数名を持つのか、それとも整数値を振ってID管理にするのか）、また識別子から C++ 側の対応する処理を決定する（ディスパッチ処理）方法、スクリプト側のデータ型とC++側のデータ型の対応の取り方（スクリプトのコンパイル時に確定させるか仮想マシンの記憶域にデータ型情報を付加して動的に対処するか）など考慮すべきポイントが幾つかある。

今回は軽量型の組込型言語なので、次のような利用シーンを想定している。

システム関数の追加/変更は頻繁に発生しえる
システム関数の数は数十～多くても数千程度
実行時の柔軟性よりも、コスト（メモリ/CPUリソース消費量)を抑えたい

そこでスクリプト言語からのシステム関数呼び出しは、スクリプトコンパイラで中間コードに翻訳すると、仮想マシンのスタックに実引数を積むコードと、 syscall 命令 (オペランド部の整数値 - システム関数番号で呼び出す C+ 側関数を区別) の組み合わせとなるようにした。

またプログラマは本質的な処理 (c) に集中できるよう、(a), (b), (d) に関しては極力 C++ コードを自動生成し、またコンパイル時に型の不整合などが検出できるようにしてある。

大まかな処理の流れは、次の通り。

システム関数を定義したヘッダファイル (ファイル名 *.sch) を用意。
スクリプト言語でプログラミングする場合には *.sch を #include して、スクリプトコンパイラで解析/利用。
C++コード自動作成する場合には、*.sch のみを解析できるミニスクリプトコンパイラで解析/C++コード自動生成。なお自動生成されるコードには一切手を加えず、それを #include するなどして利用できる形にしてある。

図は仮想機械の内部動作に関わるシステム関数についてのコード生成フロー図。ユーザ定義のシステム関数に関しても文書化中。

p.s.

今回初めて Boost Multi-index containers library を使ったけど、これは便利。C++ プログラマなら使い方を学んでおくべき。

ラベル: プログラミング

月曜日, 6月 04, 2007

スクリプト D&I (14) システム関数登録処理

r443

スレッド関連のシステム関数設計と、対応する仮想機械の実装を進める。技術的には自由度高めることは簡単だけど、典型的な場合にバグが出にくくかつメンテナンスしやすいとなると、どう制約付けるかが難しい。

スレッドには親子関係がある
スレッド新規生成時に、現スレッドの子とするか、ルートスレッドの子スレッドにするかを指定可能。
親スレッドが終了すると、それに紐付く子スレッドも全て終了する。

このぐらいが落としどころかなぁ。kernelスレッドではなくuserスレッドとして実装してるので排他制御は不要。同期制御どうするかは検討中だけど、そこまで必要になったらスクリプトで書かない方が良いような気がする。

とりあえず最低限必要な同期制御（スレッド終了待ち）だけ入れておいて、後はサンプルスクリプトとして簡単なエフェクトでも作ってみて必要に応じて追加するか。

仮想機械の内部状態にアクセスする必要があるシステム関数（スクリプトではなく C++ 側で実装して、スクリプトに機能を提供する関数) の実装方法を見直し。仮想機械側でスタックに積んだ引数情報の取出しや (UNIX kernel だと fubyte() family 相当の処理)、システム関数番号とメンバ関数の対応を手作業で管理するのが嫌になったので、それ専用にパーサ書いて C++ コード自動生成する方向で実装中。ソースコードは sysdecl* あたり。

しかし言語処理系はまともに書こうとすると、どんどん自動生成されるコードの量と段数が増えてくる。

言語を解析するためのパーサを作成するツール (yacc, lex など) を用意
その入力ファイルも手書きだと重複が多くなってくるため、入力ファイルを自動生成するツール (CScriptだと GNU m4) を用意
仮想マシンの実装に際しては、スクリプト側のコードと C++ 側のコードのグルーとなるコードを自動生成するためのツール (今回作った sysdecl) を用意

比較的シンプルな手続き型言語でこの有様だから、ruby みたいな OOPL になると大変そうだ。どうやてるのかソース読んでみるかな。

CScript に関しても放置しておくと後ワケが分からなくなりそうなので、処理の流れと関連クラスを文書化しておこう。とりあえず覚書。

cscrypt/cscript.sch, cscript/system.sch
↓ cpp + sysdecl
debug.out/vm_sys_ctx.h (ICtxSyscall), debug.out/vm_sys_d.cc (VMSyscallDispatcher::Impl)

VirtualMachine::Impl

implements ICtxSyscall
delegates to VMSyscallDispatcher

仮想機械のスタック関連操作
システム関数番号から仮想関数へのマッピング

ラベル: プログラミング

木曜日, 5月 10, 2007

スクリプト D&I (13) マルチスレッド対応

設計時点での決定事項。

non-preemptive
親子関係を持つ
スレッド間のリッチな通信機能は用意しない。

システムプログラミングや複数CPUマシンで効率的に動かすプログラムを記述するのに使うわけじゃないので、これで十分。

実装に関して、まずはスレッド固有のリソース（資源）と共有されるリソースの区別から。

共有リソース

仮想機械の一部レジスタ

ステータスワード

実行対象のバイトコード
グローバル変数
文字列データ

固有リソース

仮想機械の一部レジスタ

実行中の命令を格納しておくレジスタ (pw)
プログラムカウンタ (pc)
スタックフレームポインタ (fp)
スタックポインタ (sp)

スタック領域

こんなところかな。

これまでグローバル変数をスタック下位領域に割り当てていたが、これだと固有/共有リソースがごっちゃになって都合が悪いため、別領域に割り当てるよう修正。コード生成ルーチン、仮想機械、あとはkンパイル済みのバイトコードのシリアライズ処理部分にちょろっと手を入れる。ここまでは簡単。

スレッド関連のAPIを決める必要があるが、まずスレッド生成はシンプルにスレッド開始のエントリポイントとなる関数を指定する方法で。Win32 の beginthread() や POSIX Thread の pthread_create () 方式。

下準備として型システムの拡張。これまで型は

float
handle
int
string
void

を実装済みで、関数ポインタ型は用意してない。また型の属性として「関数の型として使える」「引数の型として使える」というのを用意してある。void foo(void a) といった宣言をエラーにするため。

今回の API ではスレッド開始のエントリポイントを引数として渡す必要がある。C言語だと関数ポインタ型を使うところだけど、ポインタを実装する気はないので thread 型を用意。


// スレッドのエントリポイント
thread thread_main(void) {}

void main()
{
    // スレッド作成
    // ここで他にも引数を渡せるようにするかは要検討
    sysThreadCreate(thread_main);
}

thread 型は変数として使う必要はないが引数としては使いたいので、この二つの変数属性を分離 [354:405]。

これで文法的な処理は終わったので、本格的に API 設計と仮想機械の拡張に手をつけるか。

ラベル: プログラミング

木曜日, 4月 26, 2007

スクリプト D&I (12) グローバル変数初期化

ローカル変数の初期化処理は実装済みだが、グローバル変数はあのコードだとダメ。どうするかねぇ。

選択肢として、右辺値にどこまでの式を許すかがある。

定数のみ
変数や関数呼び出しも含める (parser.y でいうところの node_assignment_expression)

1だとコード生成ルーチンと文法はほとんど今のままで、プラスして次の処理を入れると実現可能。

グローバル変数に対する初期化の場合は、そのアドレスを覚えておくのと、最後に ret 命令を出力
仮想マシンでmain()関数呼び出し前に、上で覚えたアドレスに対して順次 call するコードを追加

2だとこうなる。

文法に手を入れて定数式を追加。グローバル変数初期化ではコードを生成しない。
代わりにグローバル変数の初期化情報(アドレスと値の対、あるいは全アドレス分のデータを出力してもOK)を、コンパイル後のバイトコードに出力。
仮想マシンでバイトコード読み込み時に、上で出力したデータを元に仮想マシンのメモリを初期化

簡単かつ記述性が高いのは前者だけど、実行効率とスクリプト記述時のヒューマンエラー防止を考えると、敢えて後者にしておくのも手だ。今回はC言語に合わせて後者にしておくか。


% od -Ax -tx1 sample/varinit.scb

000000 7f 73 63 62 00 00 00 00 01 00 00 00 00 00 00 00
000010 01 00 00 00 90 00 00 00 1a b8 c9 58 00 00 00 00
000020 20 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000030 02 00 00 34 0a 00 00 01 00 00 00 ff 00 00 00 20
000040 01 00 00 31 fd ff 00 51 00 00 00 21 00 00 00 02
000050 00 00 00 21 00 00 00 02 02 00 00 20 03 00 00 31
000060 00 00 00 51 01 00 00 33 08 00 00 31 01 00 00 51
000070 01 00 00 33 00 00 00 50 01 00 00 50 04 00 02 80
000080 1b 00 00 04 00 00 00 50 00 00 00 52 80 00 01 10
000090 00 00 00 31 82 00 01 10 11 00 00 03 83 00 00 10
0000a0 00 00 00 40 80 00 01 10 00 00 00 21 00 00 00 02
0000b0 02 00 00 00 20 00 00 00 8b 3e 1d a3 00 00 00 00
0000c0 02 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0000d0 00 00 00 00 0b 00 00 00 01 00 00 00 05 00 00 00
0000e0 05 00 00 00 10 00 00 00 e3 ae 1f b4 00 00 00 00
0000f0 20 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000100 06 00 00 00 20 00 00 00 30 7c bb 58 00 00 00 00
000110 01 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000120 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000130 07 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
000140

ラベル: プログラミング

木曜日, 4月 19, 2007

スクリプト D&I (11) 変数初期化

まとまった時間がとれないので、空いた時間にできることを少しずつ。バイトコードのディスアセンブルプログラムを作成し、変数定義時に初期化可能に。

変数定義部分の文法は、元々こうだった (parser.y #209)。

node_var: TOK_CAST node_var_list0 ';'
 { /* ここで node_var_list0 の変数を一気にシンボルテーブルに登録 */ }
node_var_list0: TOK_ID | node_var_list0 ',' TOK_ID

初期化を可能にするには、文法的には TOK_ID の後に '=' node_assignment_expression を追加すれば OK だけど、変数型と node_assignment_expression の型が合っているかチェックしたい。型チェック失敗時に、ソースコードの行番号付きのエラーメッセージを出すことを考えると

TOK_CAST を読んだ時点で型を覚えておく
node_var_list0 に還元された時点ではなく、その中の TOK_ID '=' node_assignment_expression に対応するアクションとして型検査を行う

としたいよね。ということで TOK_CAST の直後にアクションを置いたら、関数定義の文法と競合。

node_function:
 TOK_CAST TOK_ID '(' node_param_list ')'
 '{' node_block '}'

アクションがなければ TOK_CAST と次の TOK_ID を読んだ時点ではシフトしておき、後で '(' が出てきたら node_function に還元、そうでなければ node_var_list0 に還元すれば良いけど、途中にアクションがあるとその時点でアクションを実行するかどうかを決定する必要があるから、判別を先延ばしにできないんだ。

それなら両方とも同一のアクションが実行されるように

直接 TOK_ID と書くのを止めて、共通の非終端記号 node_cast を導入。node_cast は TOK_CAST に展開されるだけ、ただしアクションとして TOK_CAST に対応する型情報をスタックに積む。
変数定義・関数定義が終わった時点で、スタックから型情報を取り出す。

と書き直せばいいか (ChangeSet 380)。

あと、小手先の最適化を幾つか。

ラベル: プログラミング

月曜日, 4月 09, 2007

スクリプト D&I (10) バイトコード処理

スクリプトのソースコードをコンパイルしてできるバイトコードをファイルに落とす処理と、ファイルからバイトコードを読み込んで実行する処理を分離 (r370)。

後者に関係するコードは、ファイル名に vm というプリフィクスを追加。ここだけ、後で GameObj の本プログラムにマージする。

スクリプト D&I (9)以前

ラベル: プログラミング

月曜日, 10月 23, 2006

DirextX9 版 Ico for Win32 (1)

まずはトライアングル表示まで。最初にライティングなし/頂点カラー直接指定で表示を確認して、それからライティングしてみる(ChangeSet r183:185)。よしよし、まずは順調。

デバイス消失時に頂点バッファ作り直さんと。枠組み (ID3DRes インターフェース) は用意してあるから、モデル管理を別クラスに切り出したときに対応させる方向で。

ラベル: プログラミング

個人的な日記、サーキット走行記録、兼、プログラミング/ネットワーク運用系の技術的な覚書。

: 名前: issei; 場所: Japan

休日はワンボックスカーにバイク積んでサーキット走行に行ってましたが、鎖骨を折って半年かけてようやく完治。年取ると骨折は時間かかる X-(　仕事はゲームプログラマ (PS2, Xbox360) からコンサルを経て、再びエンジニアに。

詳細プロフィールを表示

あわせて読みたい

登録
投稿 [Atom]