NAT Traversal

2003-04-01

Gamasutra の，今週の特集記事 "Designing Online Console Games" を読んでみた。

http://www.gamasutra.com/features/20030328/isensee_01.shtml

PS2, GC, Xbox の各プラットフォームにおけるオンライン環境の現状について解説した記事だ。それぞれのプラットフォームにおけるインフラの状況や，メーカー側の提示するポリシー等について，比較などを交えつつ詳細な解説を行っている。

ここで，本題からはちょっとズレるのだけど，なにげなく興味を誘われたのが， Xbox では API レベルで NAT Traversal への対応が行われているという記述だ。

実は， NAT Traversal という用語を聞くのも初めてのことだったので，軽く google で検索にかけてみたところ，次のようなページを引き当てることができた。

http://www.microsoft.com/japan/WINDOWSXP/pro/techinfo/planni...

NAT Traversal とは，どうやら， NAT の割り当て情報を動的に変更する機能のことを指しているようだ。従来はデバイス毎に用意されたインタフェースを通して，管理者が明示的に設定を行う方法しか無かったものを， UPnP (Universal Plug and Play) を利用することで，アプリケーション側から一様に操作することが可能となった，ということだ。

現在，ブロードバンド環境における，いわゆる ADSL ルータの普及率は意外と高いように思える。ただ，全体を見渡せば，依然 ADSL モデムの方が割合は高いだろうと思う。しかし，ゲーム機をネットワークに繋いで遊ぶような人は，やはりある種の「濃さ」を持った人たちであることが予想できるから， PC とゲーム機を同時にネットワークへ繋ぐ目的でルータを導入している可能性は，比較的高いと言えるのではないかと思う。

ともかく， IPv4 が在り続ける限り， NAT が消えることは無いだろうし，今後もその重要性を増していくはずだ。

しかし，多くのネットワーク・アプリケーションがそうであるように，オンラインゲームにとって NAT の存在はややこしい問題となり得る。ピア同士での接続を困難とするからだ。 MMORPG のように完全な中央集権方式を利用するならともかくとしても，それ以外の条件では Peer-to-Peer 方式や代表サーバ方式が主な接続方式となっていることから，この問題はどうしても避けることのできないものとなっている。

もし，ユーザがルータを利用しており，ターゲットとなるゲーム機が NAT の影響下に存在している場合，その中で「中央集権方式でない」ネットワークゲームを動かすには，ユーザに対して NAT の静的割り当てを要求する必要がある。この手順は製品によってかなり異なるはずだし，設定内容自体も若干複雑なものだから，カジュアルユーザにとってはやっかいな障害となり得るのではないかと思う。

http://sega.jp/bba/psonat.html

このような問題に対して， NAT Traversal は理想的な解決方法を提供することになるかもしれない。少なくとも，その可能性を秘めていることは間違い無いはずだ。

NAT Traversal の実態については，もう少し詳しく調べてみる必要があると思う。実際の応用例についてもっと調べてみるべきだと思うし，そもそも対応機器がどの程度普及しているものなのか，僕にはまったく把握できていない。ただ，こういった技術が既に存在し，そのことがある種のリスクに対して回避策となる可能性を秘めていることは，それだけで大きな意味を持っているように思えたわけだ。

permalink

Online Console Games

2003-04-02

引き続き "Developing Online Console Games" を読んでみている。

http://www.gamasutra.com/features/20030328/isensee_01.shtml

記事を読み進める際に，まず目に付くのが，国内と北米における PS2 のオンライン戦略に大幅な違いが見られることだ。

国内では "PlayStation BB Unit" としてネットワークアダプタと内蔵ハードディスクユニットの販売が行われている（本当は，こう一言で表すことのできないほど複雑な背景が存在するのだけれど，それはひとまず置いといて……）。これに対し，北米ではネットワークアダプタ単体での販売が行われている。

これは恐らく，ハードディスクユニット付きでは値段が釣り合わないことからの判断だろうと思う（アダプタのみで $40 の低価格販売を実現している）。 "SOCOM" や "Madden NFL" 等の初期タイトルは無料でオンラインサービスを提供しているため，基本的にはアダプタとソフトを入手するだけで即オンラインプレイを楽しむことができるようになっている。その辺りの手軽さが評価を受けていることから， SCEA の「読み」は，それなりに的を得ていたのだろうと思う。

対する Microsoft (Xbox) は， "Xbox Live" と呼ばれる統一ネットワークサービスを中心に据えたオンライン戦略を展開している。その強力なバックグラウンドと統一されたポリシーは，ユーザと開発者の双方に安定感を与えるものとなっているはずだ。 SCE(A) のような，各社バラバラで足並みの揃っていない状態と比較すると，実に対照的だ。

しかし一方で，その「堅い」ポリシーの強制が開発側にとって負担となるケースも存在するようだ。例えば， Xbox Live ではブロードバンド環境のみがサービスの対象となっており，いわゆる「ダイアルアップ環境」はサポート対象外となっている。現状ではブロードバンド環境の普及が完全でない以上，この限定条件はユーザ層を不用意に狭めてしまう危険性があると指摘されている。また， Xbox Live ではボイスチャット機能の搭載が義務付けられているのだけれど，これは開発側にとって頭を悩ます存在となっているはずだ。

他にも，パッチ配布の制限や（セキュリティ改善が目的の場合のみ許可されている），他機種との相互接続の禁止など，細かい制限事項がいくつか存在する。どれもそれなりに理由があることは納得できるのだけれど，多角的なオンライン戦略を目論んでいる企業にとっては，あまりありがたくない制限となってしまうのではないかと思う。

何かにつけてソフトウェア面でのインフラ不備が目立つ PS2 だけれど，これはネットワーク周辺についても大いに当てはまるような気がする。 SCEA では，このソフトウェア面での不備をカバーするために，米 RTIME 社を買収するという大胆な作戦に出た。そして，同社のオンラインゲーム開発環境を "SCE-RT" と改名し，ライセンシ各社へ無料配布を行っているとのことだ。

http://www.sce-rt.scea.com/

このように，通信機器自体のリリースは早かったにも関わらず本質的に何も進んでいない国内の状況とは対照的に，北米ではそれなりの戦略が進められているようだ。

http://www.us.playstation.com/onlinegaming/

とは言っても， "SOCOM" と EA のスポーツゲームだけでいつまでも引っ張れるものでもなく，早急に対応コンテンツを充実させることが求められているのだろうと思う。率直に言って，現状での見通しは決して良くない。 "EverQuest Online Adventures" がキラータイトルのつもりだったのかもしれないけれど，外部記憶装置の無い環境で MMORPG が成功するとは誰も考えていないだろうし，それが現に証明されるのも，そう遠い未来の話ではないかもしれない。

permalink

泊まり

2003-04-03

何となく調子が良かったので，久しぶりに職場に泊まってみた。

コード書きのためにまとまった時間を確保できたのは，久しぶりのことのような気がする。キーボードに向かってコードを打ち込んだり，紙に向かって設計を検討してみたり……。

そんな仕事の合間に，この前買った本を軽く読んでみた。 Jack Crenshaw の "Math Toolkit for Real-Time Programming" だ。まだ全然手を付けてなかったんだよね。

そもそもの購入の動機となっていた "bitlog" 関数については，かなりのページ数を割いて解説が行われている。とは言っても，その内容は書籍の本題から外れたものとなっており，むしろ，ちょっとしたこぼれ話というような位置付けで記述されている。

もし，コメントの十分でない Z80 アセンブラコードを渡されて，関数名のみからその機能を特定しろと言われたら，どのようなことが起こるだろうか。しかも，その書き手が相当のテクニシャンだったとしたら……なんて感じの話だ。

この本は，著者自身がかなり長い経歴を持つ人物だけに，所々に昔話が織り交ぜられている。何しろ，まだ FORTRAN さえも普及していなかったような時代からコードを書き連ねていたというのだから，驚くほど長い経歴だ。

http://www.renewamerica.us/columns/crenshaw.htm

結局のところ，あの bitlog の式の根拠は， 8 bit CPU でいかに精度良く log を扱うか，という所にある。だから，近代的な CPU において同等の処理を組む必要に迫られた場合は，もう少し異なったアプローチを用いた方が良いだろうと思う。

FPU も無い環境で， log が必要になるシチュエーションなんてのも，そう滅多にあるもんじゃないとは思うけど……例えば SIMD でデシベル変換とか，やりたいこともあるんでないかなあ。

permalink

Collaborative Filtering

2003-04-04

今日は横浜に遠征の日。色々と仕事を済ませた後，駅周辺の飲み屋で遅い夕食をとることになった。

金曜の夜なんで，周囲はすっかり飲み気分なんだけれど，最近持病になりつつある頭痛のことを考えて，アルコールは控えておくことにした。酒飲むと必ず頭が痛くなるんだ……。

結局，家に着いたのは夜中のことだった。なにげに終電だったらしい。

今まで，「購入予定本リスト」なるものを Wiki の方に作っていたんだけれど，これを amazon の「ウィッシュリスト」へ移してみることにした。

amazon の「ウィッシュリスト」とは，本来，自分の欲しい商品を他人に公開するためのシステムだ。

http://www.amazon.co.jp/exec/obidos/tg/browse/-/720602

これを使えば，ある人がその時点で最も欲しがっている商品を，確実にプレゼントすることができる（しかも，本人にはそのことを内緒にできる）という仕組みだ。いいシステムだ……。

本来の機能については，ここではひとまず置いておくことにして……実は，単に自分の欲しい本をメモしておくだけの機能としても有用なものだ。 amazon のカタログには大抵目立つところに「ウィッシュリスト」ボタンが付いているから，それをポチポチと押していくだけで購入予定本リストを作成することができる。それで，たまに本でも買ってみようかという気分になったら，ウィッシュリストにある「購入」ボタンを押すだけで買い物を済ますことができる，というわけだ。

他にも amazon には色々と凝ったサービスが存在する。中でも，大規模オンライン書店としての利点を感じるのが「おすすめ商品」機能だ。

http://www.amazon.co.jp/exec/obidos/tg/browse/-/779360

amazon では，その膨大な販売履歴情報を利用して，「このような本を買う人は，他にどのような本を買っているか」という，個人嗜好の相関情報を取り出している。これを利用すれば，その人の嗜好に的確にマッチした本の推薦を行うことができるというわけだ。

情報マネジメントの分野では，このような手法のことを "Collaborative Filtering" （協調フィルタリング）と呼ぶらしい。いわゆる「データ・マイニング」手法の一つだ。

http://www.sims.berkeley.edu/resources/collab/

http://www.ai.univie.ac.at/~juffi/Web-Mining/usage_mining.pd...

さらに，「おすすめ商品の絞り込み」ページを使えば，自分の嗜好についてより詳しい情報を与えることができる。例えば，たまたま興味の無い商品を買ってしまった場合などには，「絞り込み」ページからその商品を「削除」してしまえば，余計なノイズを混ぜることなく，より錬度の高いフィルタリングを行うことができるようになる，というわけだ。

それで，その機能によれば……今の僕への「おすすめ商品」は， Alan H. Watt の "Advanced Animation and Rendering Techniques: Theory and Practice" らしい。

http://www.amazon.co.jp/exec/obidos/ASIN/0201544121

ふうん……。

そう言えば， Gino Van Den Bergen 氏のコリジョン本に続き， Christer Ericson 氏もコリジョン本 "Real-Time Collision Detection" を出す予定とのことだ。 Real-Time Redering のページにちょこっと情報が載っている。

http://www.realtimerendering.com/

ていうか，ここの "Recent Books" のリストが凄いことになっているなあ……。なにげに要チェックだ。

permalink

Proebsting's Law

2003-04-05

宅配便のベルで目を覚まし，髪を刈りに床屋へ出かけ，いつものルートで本屋に寄ってから，大戸屋で夕飯を食べた。幸運な事に，今日は焼魚サバ定食にありつくことができた。何故か品切れの多い，僕のお気に入りメニューだ。

そんなわけで，今日もやはり，大戸屋はサバ定食が旨いという結論に至る。

帰りがけに雨が降ってきた。わりあい大きな降りだったので，コンビニでビニール傘を買う。ああ，また要らない傘が一本増えてしまった。一年に一本の割合で増えていくような気がする。

僕の家にある本当に要らないものの一つが，この古傘どもだと思う。いつか，どうにかしてやりたい。

最近は，たまに暇があると GDC 2003 の資料を覗いてみている。 SIGGRAPH の paper などにも言えることなんだけれど，重いネタは後にとっておいて，まずは軽いネタからさらっと読み流してしまうのが良い方法だと思う。そういう意味では， Christer Ericson 氏の "Memory Optimization" など，最初に手を付けるネタとして適したものかもしれない。

http://www.gdconf.com/archives/2003/Ericson_Christer.ppt

一般的なプログラミングにおけるメモリアクセスの「作法」について触れたレクチャーだ。わりと基礎的な話なので，その辺りの勝手知ったる人々に対しては不向きな内容かもしれない。ただ，あまりそういう世界に馴染みの無い人達にとっては，良い導入となり得るのではないかと思う。新米プログラマなどに一読を勧めるのが，正しい使い方かもしれない。

プレゼンテーションの中で，ちょっと面白かったのが，次の "Proebsting's Law" についての記述だ。

Proebsting's Law:
Compiler Advances Double Computing Power Every 18 Years

http://research.microsoft.com/~toddpro/papers/law.htm

Todd Proebsting 氏は Microsoft Research に所属するプログラミング言語研究の専門家だ。氏は，かの有名なムーアの法則（「計算機の能力は１８ヶ月毎に倍増する」）へのアナロジーとして（あるいはアイロニーとして），この法則を打ち出している。その心は，コード最適化とは予想以上に実りの少ない研究分野であり，それよりも生産性の向上に努めることの方が重要である，という主張だ。それと同時に，コンパイラへの過信を諌める言葉とも受け取ることができる。

かの "Black Book" の中で Micheal Abrash はこう述べている……「真のオプティマイザは君の両耳の間に在る」。重要なのは，常に最適化可能な設計を行うセンスと，ボトルネックを見極める洞察力，そして，実際に最適化を行う技術力，の３つに集約されるのだろうと思う。

permalink

花見

2003-04-06

今日はドジ研花見の日。いつもの出勤と同じような時間帯に起床して，一路上野公園へと向かう。

桜満開の上野公園などという，花見には最高のロケーションを確保できたのも，ひとえにミキタさんをはじめとする場所取り隊の方々の尽力があってのことだ。いやあ，有り難いことです。そのおかげで，ガラにも無く長閑な行楽気分を味わうことができた。こんなのは久しぶりだ。

呑みの場の話題は様々。やはり，げーはなさんが登場すると会話が加速する。ちょっと堅い話から，全然堅くない話まで，そりゃもう色々出たものだ。ちょっと業界話が多過ぎたかもしれない。その分，かわちさんやミキタさんのカタギっぽいキャラが強調されていい感じだった。僕もゆりかもめで通勤したい（あるいは自転車で）。

その後，呑みの場が焼き鳥屋に移されると，まったりした感じの二次会が開始された。しばらくしてすずなさんも登場。狩野さん忙しそうだねえ，とか，そんな話題で盛り上がったっけ……。あと，なにげにこうのさんの危険トークが危険な香りで良かった。呑みの場は油断できんぜ。

さすがに真昼間から飲んでいたとあって，今日は２次会までで打ち切り。酔いを覚ましながら，ガラガラの銀座線に乗り，悠々と家路についた。

久しぶりに有意義な休日だったと思う。最近は，休日と言えば寝てばかりの日々だから，こういう機会があると大変嬉しい。

でもたぶん，来週の土日は寝っ放しだろうな，と思う。

permalink

Dynamics For Designers

2003-04-07

ミーティング漬けの月曜。最近はそんな日が多い。

Will Wright 氏の GDC 講演のビデオ映像が Gamasutra で公開されている。

http://www.gamasutra.com/features/20030403/wright_01.shtml

とりあえず覗いてみたものの……だめだ，全然聴き取れやしない。読むのも精一杯なのに，聴くことなんてできるはずもないんだ。

せめて英文テキストになっていれば，あとはどうにでもなるのだけれど……それもちょっと無理な望みであるようだ。

ヒアリングとかって，練習すれば会得できるものなんだろうか。小林克也氏は米軍ラジオを聴いて英語を覚えたという話だけれど，果たして本当にそんなことが可能なのだろうかと，不思議に思うことがある。

permalink

strict aliasing rule

2003-04-08

先日読んだ "Memory Optimization" の中で，少し気にかかっている個所がある。エイリアシングに関する記述だ。どうやら C の標準規格の中にも，エイリアシングに関する制限事項が存在するらしい。僕は今まで，ポインタ経由でのメモリアクセスは無制限に行えるものだと思い込んでいた。もし，氏の指摘が本当だとすると（嘘なわけは無いんだけれど），かなり危うい思い込みの上でコーディングを行っていたことになってしまうかもしれない。

思い返してみれば，これまで C の規格書などというものを一度も読んだことがない。大抵のことは VC++ に付属のランゲージ・リファレンスで済ませていたからだ。そんな体たらくだから，いきなり規格書を読めなどと言われても，一体どこを当たったら良いものやら見当もつかない。

漠然と「C の規格書」ってのも，ちょっと難しそうな探し物だ。しかし意外なことに，適当なワードを google に突っ込んでみると，一発で引き当てることができた。そうそう，たしかこれでいいはず……。

http://std.dkuug.dk/JTC1/SC22/WG14/

ISO/IEC JTC1/SC22/WG14 は，いわゆる「ISO C 委員会」と呼ばれているもので， C 言語標準規格の策定を進めている国際的な組織だ。

最新の C 言語標準規格である ISO/IEC 9899:1999 （いわゆる "C99"）の規格書 SC22/N2794 (WG14/N843) は，以下のページからダウンロードすることができる。

http://std.dkuug.dk/jtc1/sc22/open/n2794/

前述の N2794 内，節 6.5.16.1 (p.81) の "Simple assignment" が該当個所のようだ。以下にその一節を引用する。

> If the value being stored in an object is accessed from another object
> that overlaps in any way the storage of the first object, then the overlap
> shall be exact and the two objects shall have qualified or unqualified
> versions of a compatible type; otherwise, the behavior is undefined.

なんかこう，冗長な表現で分かりにくいのだけれど……簡潔にまとめると，同一のメモリ領域に対して２種類の型でアクセスすることを禁じているようだ。ただし，２つの型の間に互換性がある場合（例えば int と unsigned int など）は許されるらしい。

ISO C の規格書には，本編とは別に rationale （設計理論書）が用意されており，設計の各所についてその根拠を知ることができるようになっている。つまり，規格書の方はただ厳密な定義を与えるのみに集中しており，その「正味の話」については rationale の方で伝えようという意図であるようだ。だから，場合によっては raionale を参照した方が手っ取り早い場合もあると思う。

http://std.dkuug.dk/JTC1/SC22/WG14/www/docs/n897.pdf

こちらも該当個所の一部を抜粋し引用する。

> The types of lvalues that may be used to access an object have been
> restricted so that an optimizer is not required to make worst-case
> aliasing assumptions.
...
> In principle, then, aliasing only need be allowed for when the lvalues
> all have the same type.

オプティマイザの動作を厳密に定義するには，このルールの存在が欠かせなかったようだ。まあ，確かに……。

このルールを厳密に適用する場合，以下のコードの動作は不定となる。

unsigned int floatbin(const float *x)
{
return *(int*)x;
}

これ，意外と心当たりがあるんだよなあ……。高級言語よりも先にアセンブラを習っていると，ポインタの仕組みの理解が速い一方で，こういった危険な応用に対しても奔放になってしまう傾向があるように思える。

gcc では， "-fstrict-aliasing" オプションを指定した場合に，この「厳密なルール」の適用を前提とした最適化処理を行うようになっている。ちなみに， "-O2" オプションはこのスイッチを暗黙に適用している。つまり，普段から -O2 を使っているような場合は，それと同時に「厳密なルール」を適用していたことになるわけだ……。

例えば次のようなコードがあるとする。

int foo(int *a, float *b)
{
  *a = 0xff;
  *b = 3.141592f;
  return *a;
}

これを，オプションに "-O2 -fomit-frame-pointer" を指定してコンパイルすると，以下のようなコードが生成される。

   0:   8b 44 24 04             mov    0x4(%esp,1),%eax
   4:   c7 00 ff 00 00 00       movl   $0xff,(%eax)
   a:   8b 44 24 08             mov    0x8(%esp,1),%eax
   e:   c7 00 d8 0f 49 40       movl   $0x40490fd8,(%eax)
  14:   b8 ff 00 00 00          mov    $0xff,%eax
  19:   c3                      ret

a と b が互換性の無いポインタであることから，両者の間にエイリアシングは無いものと見て，最適化を行っていることが分かる。つまり， "return *a" の時点で "*a == 0xff" が成立するため， a からのロードは行わずに，定数 0xff を直接に返すことができるわけだ。

ここで，オプションに "-fno-strict-aliasing" を追加してみると，以下のようなコードに変化する。

   0:   8b 44 24 04             mov    0x4(%esp,1),%eax
   4:   c7 00 ff 00 00 00       movl   $0xff,(%eax)
   a:   8b 54 24 08             mov    0x8(%esp,1),%edx
   e:   c7 02 d8 0f 49 40       movl   $0x40490fd8,(%edx)
  14:   8b 00                   mov    (%eax),%eax
  16:   c3                      ret

ルールの適用を緩くしたがために， a と b の間にエイリアシングが発生することを考慮しなければならなくなってしまった。こうなると前述の仮定は成立しなくなってしまい（エイリアシングが存在すれば *b への代入によって *a が書き換わる可能性がある），律儀に a をロードし直す必要ができてしまったわけだ。

permalink

omit frame pointer

2003-04-09

今日もミーティング漬け。むこう数週間，こんな調子が続く予定だ。

良し悪しは別として，日本人が会議好きであるのは，確かに言えることだろうと思う。

先日の "strict aliasing rule" の一件から，コンパイラのオプション指定について気になり始めている。普段から慣れ親しんでいながらも，一度も真面目に取り組んだことの無い要素であるだけに，まだ見過ごしている点があるのではないかと思う。復習の意味も込めて，軽く調べてみることにした。

ところで， gcc のコマンドライン・オプションには，ドキュメントに記載されていないものが意外と多く含まれているように思える。自分の使用している gcc について，指定可能なコマンドライン・オプションを調べるには， "-v --help" をコマンドラインに渡して gcc を起動すればいい。組み込まれているすべてのオプションを列挙することができる。

調べていて少し気にかかったのが， "-fomit-frame-pointer" フラグの効用についてだ。このフラグは，スタック参照の際にフレームポインタを利用するかどうかを制御する。このフラグを有効にすると，フレームポインタの初期化処理などが省略される分，コードが短くなるという効果が得られる。少なくとも僕はそう信じていたので，わりと日常的にこのフラグを利用していた。

ところが，よくよく調べてみると， x86 系の CPU では，かえって逆効果となってしまう場合もあるようだ。うう，油断できないなあ……。

例として，次のようなコードを用意する。

extern void bar(int*);

int foo(void)
{
    int a[16] = {0};

    a[0] += bar(a); a[0] += bar(a); a[0] += bar(a); a[0] += bar(a);
    a[0] += bar(a); a[0] += bar(a); a[0] += bar(a); a[0] += bar(a);
    a[0] += bar(a); a[0] += bar(a); a[0] += bar(a); a[0] += bar(a);
    a[0] += bar(a); a[0] += bar(a); a[0] += bar(a); a[0] += bar(a);

    return a[0];
}

これをデフォルト状態でコンパイルし，ディスアセンブリをとってみる。

次に， "-fomit-frame-pointer" を指定した場合のディスアセンブリをとってみる。

   0:   57                      push   %edi
   1:   31 c0                   xor    %eax,%eax
   3:   b9 10 00 00 00          mov    $0x10,%ecx
   8:   53                      push   %ebx
   9:   83 ec 54                sub    $0x54,%esp
   c:   8d 5c 24 10             lea    0x10(%esp,1),%ebx
  10:   fc                      cld
  11:   8d 7c 24 10             lea    0x10(%esp,1),%edi
  15:   f3 ab                   repz stos %eax,%es:(%edi)
  17:   89 1c 24                mov    %ebx,(%esp,1)
  1a:   e8 00 00 00 00          call   1f <_foo+0x1f>
  1f:   01 44 24 10             add    %eax,0x10(%esp,1)
  23:   89 1c 24                mov    %ebx,(%esp,1)
  26:   e8 00 00 00 00          call   2b <_foo+0x2b>
  2b:   01 44 24 10             add    %eax,0x10(%esp,1)
...
  ce:   e8 00 00 00 00          call   d3 <_foo+0xd3>
  d3:   8b 54 24 10             mov    0x10(%esp,1),%edx
  d7:   83 c4 54                add    $0x54,%esp
  da:   5b                      pop    %ebx
  db:   01 d0                   add    %edx,%eax
  dd:   5f                      pop    %edi
  de:   c3                      ret

導入と終了の各処理については，後者の方が短くなっている様子がうかがえると思う。しかし，バイナリでのサイズを比較してみると，前者の方が僅かに小さい。前者が 0xd0 = 208 バイトに対して，後者は 0xde = 222 バイトだ。

なぜ，このような逆転現象が起こるのか……それは， x86 のアドレス指定方式の妙に起因している。

http://www.intel.com/design/intarch/techinfo/Pentium/opcode....

http://www.intel.com/design/intarch/techinfo/Pentium/instfor...

インストラクション・フォーマットの説明を読んでみると分かるけれど， x86 のアドレス指定方式において，スタックポインタ (esp) の存在はかなり冷遇されている。元来，スタックポインタは push/pop 命令によって利用されることが前提とされているためだ。それでも無理やりアドレッシングに esp を利用しようとすると，どうしても SIB 指定モードのような冗長な形式が多くなってしまう。そのため，インデクスレジスタ等を利用する場合と比較して，僅かながら膨らんでしまう傾向にあるようだ。

これに対し，フレームポインタ (ebp) は，もともと間接参照のために用意されているレジスタなのだから問題無い。 x86 の多彩なアドレッシングモードの恩恵にあずかることができる。

このような逆転現象は， MIPS や ARM のような RISC 系 CPU では発生しない。 RISC では一般にインストラクションが固定長だし，なにより，特殊な「スタックポインタ」というようなものが存在しない。ただ，汎用レジスタのうちの１個をスタックポインタとして利用するという「作法」が存在しているだけだ。

そのため， RISC 系 CPU では，フレームポインタの利用を止めることによってコードサイズの節約が可能となっている。現に MIPS 用 gcc では "-O2" オプション指定によって "-fomit-frame-pointer" フラグが自動的に有効とされるような設定となっているようだ。

この件が示唆していることは， "-O2" オプションによる曖昧な指定が，案外良い効果を持っているということだ。闇雲に細々とフラグの指定を行うよりも，各プラットフォームの事情に合わせて調整の行われている "-O2" オプションを信用するのが無難だろうと思う。その上で， "-ffast-math" のように，アプリケーションの特性に依存する調整を加えていけば，十分に良好な状態へと持っていくことができるのではないかと思う。

permalink

686 optimization

2003-04-10

今日は本当に会議漬けの日。一行たりともコードを書いていない。

コンパイラのオプションについて，もう一つ気になることがあった。 x86 アーキテクチャに依存する設定項目についてだ。

http://gcc.gnu.org/onlinedocs/gcc-3.2.2/gcc/i386-and-x86-64-...

どうやら，僕が普段使っている Red Hat Linux 8.0 の gcc は， i386 をデフォルトの cpu-type として適用するようになっているらしい。コマンドラインオプションに "-march=i686" を追加しただけで数％の速度改善が得られた。こいつはおいしいな……。

$ time ./pathtracer_default

real    0m14.752s
user    0m14.721s
sys     0m0.030s

$ time ./pathtracer_i686

real    0m13.713s
user    0m13.689s
sys     0m0.020s

i386 と i686 (pentiumpro) では，命令セットなどほとんど変わりないわけだから， i686 向けの特殊な最適化といっても，スケジューリングが微妙に変化する程度のことだろうと思う。それでも，全体としては確実に効果をあげることができているようだ。やることと言えばオプションをちょっと追加するだけであり，あとはタダも同然で手に入れることのできる機能なのだから，是非とも利用していきたいところだ。

ちなみに，手元の cygwin に入っていた gcc は，ターゲットの設定が i686-pc-cygwin となっており， cpu-type には i686 がデフォルトで適用されるようだった。 Linux の方も，コンパイラを自前でビルドすればいいのかな……。

もう一つ， x86 関連で面白いオプションがある。 "-mfpmath" オプションだ。

> -mfpmath=unit
> generate floating point arithmetics for selected unit unit.

...

> sse
>  Use scalar floating point instructions present in the SSE instruction set.

...

>  The earlier version of SSE instruction set supports only single precision
>  arithmetics, thus the double and extended precision arithmetics is still
>  done using 387. Later version, present only in Pentium4 and the future AMD
>  x86-64 chips supports double precision arithmetics too.

...

>  The resulting code should be considerably faster in majority of cases and
>  avoid the numerical instability problems of 387 code, but may break some
>  existing code that expects temporaries to be 80bit.

どうやら，浮動小数点演算を SSE 命令セットでコーディングするという機能らしい。僕は SSE をよく知らないので，これによってどの程度の効果が得られるものなのか見当も付かないのだけれど……しかしあの FPU (387) の使いづらさと比較したら，大抵のものはマシに見えてしまうのではないかと思う。

早速，オプションに "-march=i686 -msse -mfpmath=sse" を追加して計測を行ってみた。

$ time ./pathtracer_sse

real    0m11.779s
user    0m11.756s
sys     0m0.020s

確実に速くなっているようだ。これはおいしい……。

FPU ベースでの実装と比較した場合に挙げられるデメリットとしては，演算の内部精度が若干低くなることがあるらしい。通常， 387 では内部的に 80 bit 浮動小数点を利用しているようだから，その精度を期待しているユーザにとっては，多少問題を含む要素となってしまうかもしれない。しかし，ゲームや CG のように，ある程度の誤差が許容される用途であれば，このトレードオフにまったく問題は無いはずだ。

また， CPU が SSE2 をサポートしているアーキテクチャならば， "-msse2" を追加することによって double の扱いをも SSE 化することが可能なようだ（僕のマシンは Pentium III なので試すことができなかった）。

余談だけれど，コンパイルオプションに -mmmx や -msse を指定しておくと，専用のビルトイン関数を介して SIMD 命令セットを利用することが可能となるようだ。

http://gcc.gnu.org/onlinedocs/gcc-3.2.2/gcc/X86-Built-in-Fun...

これらの関数群は，同名のインストラクションとほぼ一致する内容となっている。ここまでアセンブリ感覚が露骨だと，ともあればインラインアセンブラを用いてしまった方が手っ取り早いと感じるかもしれない。しかし実際には，レジスタの割り当てなどを自動的に解決することのできるビルトイン関数の方が，最終的に得られるメリットが大きいように思える。

これを利用してベクトル・マトリクス系の演算ライブラリを組んだら，かなり処理能力が向上するかもしれない。ただ， SSE はその手の演算をあまり意識して設計されていないように見える。ベクトル同士の加減算はともかくとして，単に内積や外積をやらすにも，ちょっと苦労してしまいそうな雰囲気だ。誰かライブラリを作ってくれれば良いのだけれど……。

permalink

Boundary Alignment

2003-04-11

今日もミーティング多し。

もうしばらくはこんな調子だから，少ない時間でこなせる作業を中心に消化していこうと思っている。

昨日，自宅では調べることのできなかった SSE2 最適化について，職場のマシンを使って検証してみることにした。職場には Pentium4 マシンや Xeon マシンが置いてあるからだ。休み時間にパンを食いながらジョブを走らせてみる。普段はコンパイラのジョブにパワーを占有されているから，まともにパフォーマンスの計測を行うことができないのだ。

そんな感じで，しばらくの間，コードをいじくり回してみたんだけれど……思ったように効果が現れてくれない。浮動小数点形式を double にしてから "-msse2 -fpmath=sse" を指定すると， FPU コードが SSE2 に置換されるところまでは確認できた。しかし，処理速度については，むしろ FPU よりも遅くなっているように見える。

なんとも微妙な空気を感じる……迂闊に結論を出すことはできなさそうだ。とにかく，単純に SSE 化したところで，必ずしも効果が得られるとは限らない，ということだけは分かった。

それにしても， i686 向けの最適化は，常に一定の効果を得られているように見える。具体的には，どのような変化が起きているのだろうか。ちょっと気になるところだ。

例として，次のようなコードを用意してみた。

int test_func(const int* p)
{
    int sum = 0;

    for (int i = 0; i < 32; i++)
    {
        sum += (p[i] > 0) ? p[i] : 0xff00;
    }

    return sum;
}

このコード自体に意味はない……ちょっと意味ありげな要素を並べてみただけだ。これを "-march=i386" でコンパイルすると，以下のようなコードが得られた。

00000000 <__Z9test_funcPKi>:
   0:   53                      push   %ebx
   1:   8b 5c 24 08             mov    0x8(%esp,1),%ebx
   5:   31 c0                   xor    %eax,%eax
   7:   31 c9                   xor    %ecx,%ecx
   9:   8d 76 00                lea    0x0(%esi),%esi
   c:   8b 14 8b                mov    (%ebx,%ecx,4),%edx
   f:   85 d2                   test   %edx,%edx
  11:   7e 0d                   jle    20 <__Z9test_funcPKi+0x20>
  13:   01 d0                   add    %edx,%eax
  15:   41                      inc    %ecx
  16:   83 f9 1f                cmp    $0x1f,%ecx
  19:   7e f1                   jle    c <__Z9test_funcPKi+0xc>
  1b:   5b                      pop    %ebx
  1c:   c3                      ret
  1d:   8d 76 00                lea    0x0(%esi),%esi
  20:   05 00 ff 00 00          add    $0xff00,%eax
  25:   eb ee                   jmp    15 <__Z9test_funcPKi+0x15>

ごく普通の x86 コードだ。次に "-march=i686" でコンパイルしてみる。

00000000 <__Z9test_funcPKi>:
   0:   56                      push   %esi
   1:   31 d2                   xor    %edx,%edx
   3:   53                      push   %ebx
   4:   31 db                   xor    %ebx,%ebx
   6:   8b 74 24 0c             mov    0xc(%esp,1),%esi
   a:   8d b6 00 00 00 00       lea    0x0(%esi),%esi            ; << nop
  10:   8b 04 9e                mov    (%esi,%ebx,4),%eax        ; << jump to
  13:   8d 0c 10                lea    (%eax,%edx,1),%ecx
  16:   81 c2 00 ff 00 00       add    $0xff00,%edx
  1c:   85 c0                   test   %eax,%eax
  1e:   0f 4f d1                cmovg  %ecx,%edx
  21:   43                      inc    %ebx
  22:   83 fb 1f                cmp    $0x1f,%ebx
  25:   7e e9                   jle    10 <__Z9test_funcPKi+0x10>
  27:   5b                      pop    %ebx
  28:   89 d0                   mov    %edx,%eax
  2a:   5e                      pop    %esi
  2b:   c3                      ret

かなり雰囲気の異なるコードが得られた。最も目立つ違いは，条件判定が cmov 命令に置換されていることと，ジャンプ先アドレスについて境界整合が行われていることではないかと思う。

特に，境界整合の部分が印象的だ。詳しい事情は分からないのだけれど， i686 ではジャンプ先アドレスを 16 の倍数に整合させることによってパフォーマンスの改善が得られるらしい。ループ処理のジャンプ先を整合させるために， 6 バイトも無駄なコードを埋め込んでいる。しかも，その間隙を nop 命令で埋めるのではなく， "lea 0(esi), esi" というように，単一の「無効な命令」によって埋めているところが面白い。まさに CISC 的と言える妙技だ。処々の複雑な理由によって，このような方法が最も効率良いことになっているのだろうと思う。

もう一つの最適化要素である条件付きインストラクション (cmov) は， i686 以降において新たに追加されたフィーチャーだ。個人的には，条件付きインストラクションと言うと，どうしても MIPS の movz 命令を連想してしまうのだけれど，これはゼロフラグの判定とレジスタ間の複写のみをサポートしたものであり，機能的にはかなり貧弱であると言わざるを得ない。それに対して， i686 に備わっている条件付きインストラクションは，多彩な処理を行うことのできる命令群となっている。

http://www.intel.com/design/intarch/techinfo/pentium/instsum...

FPU 側のロード処理にも条件判定を付けることができるんだなあ……これはまったく知らなかった。近頃の CPU ではブランチ処理のペナルティが更に高まっていることだろうし，このような機能はそれなりに価値のあるものとなっているのだろうと思う。

ちなみに，ターゲットとして i686 を指定された gcc は，デフォルトで種々の i686 最適化を行うものの，条件付きインストラクションのような拡張命令を暗黙に利用することは無いようだ。アーキテクチャの指定を明示的に行わない限りは， 386 上で動かないコードは生成しない，という基本方針であるらしい。

permalink

ARM7TDMI

2003-04-12

条件付きインストラクションと言えば， ARM (ARM7TDMI) が面白い。

http://www.arm.com/armtech/ARM7TDMI

ARM7 のインストラクション・フォーマットでは，上位４ビットが "cond(ition)" フィールドとして割り当てられている。これは，あらゆる命令に対して条件判定を付加できるということを意味している。この機能を利用すれば，条件付きロードだけでなく，例えば「条件付き乗算」や「条件付き割り込み」などのような，一風変わった命令を作り出すことも可能だ。

例として，昨日のサンプルプログラムを ARM7TDMI 用クロスコンパイラでコンパイルしてみたところ，以下のようなコードが得られた。

00000000 <_Z9test_funcPKi>:
   0:   e3a01000        mov     r1, #0  ; 0x0
   4:   e1a02001        mov     r2, r1
   8:   e7903102        ldr     r3, [r0, r2, lsl #2]
   c:   e2822001        add     r2, r2, #1      ; 0x1
  10:   e3530000        cmp     r3, #0  ; 0x0
  14:   c0811003        addgt   r1, r1, r3
  18:   d2811cff        addle   r1, r1, #65280  ; 0xff00
  1c:   e352001f        cmp     r2, #31 ; 0x1f
  20:   da000000        ble     8 <_Z9test_funcPKi+0x8>
  24:   e1a00001        mov     r0, r1
  28:   e1a0f00e        mov     pc, lr

昨日の x86 コードと比較すると，非常に簡潔で読みやすい。加算処理の部分で "addgt" と "addle" が用いられている。また，「条件無し」を意味する cond フィールド値が "e" であるため，４バイト毎に規則正しく "e" が現れるところが ARM7 コードの特徴だ。

余談だけど，関数からのリターンが "mov pc, lr" であるところも面白い。 "ret" でも "j $31" でもなく，プログラムカウンタに直接ロードでジャンプだ。どうやら， ARM7TDMI にはレジスタ指定によるジャンプ命令というものが存在しないらしい。まさにミニマニズムの極みだ。

ARM プログラミングのノウハウについては， GDC 2002 における Gopi Kolli 氏の講演 "3D Graphics Optimizations for ARM* Architecture" が参考になる。

http://www.gdconf.com/archives/2002/gopi_kolli.ppt

ところで， Gopi Kolli 氏は ARM ではなく Intel のエンジニアだ。 XScale 関連の記事などで氏の名前を見受けられることから，その近辺の担当者なのだろうと予想される。ううむ， Intel も本物の RISC を作る時代になったんだなあ……。

ARM と言うと，個人的に GBA や PocketStation などを連想してしまうため，どうしても地味な印象が拭い切れない。しかし，近頃になって， ARM アーキテクチャは非常に「色気」を帯びてきた。昔のような「縁の下の力持ち」的存在ではなく，堂々と時代の主役へ踊り出ようとしている。その推進役を担っているのが Intel の XScale テクノロジだ。

http://www.intel.com/design/intelxscale/

PCA プロセッサの登場以来， 400MHz で駆動するハンドヘルドマシンの存在も決して珍しくないものとなっている。そのような環境であれば，ここで扱っているような「浮動小数点エミュレーションでソフトウェアレンダリング」なんてのも，非実用的な話として片付けることはできないはずだ。

ARM について調べる度に登場する話題なのだけれど，とにかく， ARM プロセッサにおいてまず問題となるのは除算命令の欠如であるようだ。除算が遅いのはどのアーキテクチャにも共通して言えることだけれど，それが著しいペナルティを伴うものだとすれば，プログラマに圧し掛かるプレッシャーの重さは，また違うものになってくるだろうと思う。

GBA の場合は，さらに ROM へのアクセスの遅さも問題となるらしい。とにかく ROM へのバスが細いのだ。

http://www.work.de/nocash/gbatek.htm

それ故に，縮小命令セットである "Thumb instruction set" を用いる必要性が出てくるということだ。むむ……。

http://wombat.doc.ic.ac.uk/foldoc/foldoc.cgi?Thumb

http://www.gbadev.org/files/armthumb-romram.txt

この辺りについて，近頃の携帯マシンなどでは，また事情が異なってくるのだろうと思う。高速な RAM が一定量確保できていれば， Thumb 命令を使う必要性はかなり低下するはずだ。純粋にバイナリのサイズを減らす目的で Thumb を用いるモチベーションが発生するとは考え難いものがある。それとも，まだ他の理由が存在するのかな……。

permalink

Grounds for Termination

2003-04-13

最近，時間的余裕が減ってきていることを理由に， GDAlgorithms のチェックを怠りがちになってしまっている。できるだけ，こういった地味な情報源を大切にしていきたいと思っているのだけれど，なかなか習慣として身に付かないというのが正味な感想だ。この際，ログ閲覧のためだけに PDA でも買ってみようかと目論んでいるぐらいだ。

ここ数日の GDAlgorithms で特に面白かった流れが "Animation Interpolation" スレッドだ。

http://www.radiumsoftware.com/excerpts/animation_interpolati...

ことの始まりは， Jamie Fowlston 氏の何気ない質問に発している。その質問とは，こんな感じの内容だ……キャラクタアニメーションに感情表現を付加する目的で Charles Rose (Microsoft Research) の "Verbs and Adverbs" 法を用いようと思っているが，同技術が特許として申請されているのが気がかりだ……。さて，どうしたものだろうか。

http://sourceforge.net/mailarchive/message.php?msg_id=430372...

http://www.vuse.vanderbilt.edu/~bobbyb/pubs/VandAdv98.pdf

http://patft.uspto.gov/netacgi/nph-Parser?Sect1=PTO1&Sect2=H...

以降，話の流れはソフトウェア特許に関する討論へと移っていった。中でも興味深いのが， Christer Ericson 氏の便乗質問から発せられた流れだ。

http://sourceforge.net/mailarchive/message.php?msg_id=432761...

氏の話によると， Electronic Arts 社では，特許関連の訴訟に対する予備防護策として，従業員が特許情報へアクセスすることを禁じているそうだ。このような奇妙とも思える方針を打ち出している理由については，後に Tom Forsyth 氏が詳しく解説している。

http://sourceforge.net/mailarchive/message.php?msg_id=432762...

http://sourceforge.net/mailarchive/message.php?msg_id=433090...

つまり，特許情報へアクセスする手段を持ちながらも特許技術を無断で利用してしまった場合，それは「特許に対する故意の侵害」とみなされ，被る打撃を倍増してしまう危険性があるということだ。そのことから，暗黙のうちに特許情報を参照することのできる機構を用意しないこと……つまり，「従業員は皆無知である」ことを保証すること……が防護策になるという，実に皮肉な結論が導き出されてしまっている。

現に，このポリシーを採用している組織は決して珍しくないようだ。この件に関する法律家のコメントが，以下の Gregory Aharonian 氏のレポートにまとめられている。

http://www.derwent.com/piugl2000/0071.html

特に気を配らなければならないのが，各種カンファレンスにおいても特許の罠が潜んでいるという事実だ。 ACM （SIGGRAPH 等の母体となる団体）も，以前は特定の特許やコピーライトに依存する内容の論文を発表することを禁じていたものの，最近になってこの制限を外してしまったそうだ（そうしなければ埒のあかない事情があったのだろうと思う）。

最も身近な例を挙げれば，先日開催された GDC 2003 における Jos Stam 氏の "Real-Time Fluid Dynamics for Games" の内容が，同氏の持つ特許（Stable Fluids 法）に完全に依存した内容となっている。このことは，ただでさえ応用の難しい流体関連の技術に対して更なるマイナスイメージを付加する状況を作り出してしまっているように見える。

http://www.dgp.toronto.edu/people/stam/reality/Research/pdf/...

このような特許法上の矛盾を抱え込み，それに苦悩しているのは，技術系の企業ならばどこでも同じ事情のようだ。しかし，そもそも「特許というシステムがなぜ存在するのか」「なぜ今のような形態になっているのか」という点を明らかしておかない限り，この種の議論を続けることは難しい。さもなくば，単なる個人的スタンスの提示に終わってしまうからだ。

Lawrence Lessig 氏の「サイバー法律家」としての活動は，そのような古来のシステムが抱える矛盾点を明らかにして提示し，法律の専門家でさえも難しいとされる同種の議論を，一般人に理解可能なレベルにまで落とし込むものとなっている。その上で，我々がどのような危険意識を持たねばならないのかという点を示唆し，実際に我々自身が変容の原動力となることを求めている。

http://cyberlaw.stanford.edu/lessig/

そんな訳で，僕も「コモンズ」に手を出してみているものの，まだ半分ぐらいしか読み終えていない。一体何ヶ月かかっているんだ……。絶対に読まなきゃならんと思っているわりには，歩みが遅すぎるように見える。ううむ……。

同スレッドにおいて，オフトピック的な話題として "The Spanish Prisoner" という映画が取りあげられていた。

http://www.sankei.co.jp/mov/review/99/spanish_p/

http://www.sonyclassics.com/spanishprisoner/

http://www.amazon.co.jp/exec/obidos/ASIN/B00005HSDT

インディペンデント系映画の傑作として知られる作品らしい。巨万の富を得られる可能性を秘めた「プロセス」を発明した男が，詐欺師たちの巧妙な罠にはめられていく様を描いた作品とのことだ。

たまには，こういうのを観てみるのもいいかな，ということで，とりあえず「ウィッシュリスト」に入れておくことにした。

permalink

Hyper-Threading

2003-04-14

気分の良い月曜日。休日を終始寝て過ごしたおかげか，終電近くの時刻になっても，やけに気力が残っている。ただ，天候があまりよろしくないようなので，泊まりは無し。そそくさと家路についた。

だいぶ春っぽい気候になってきたものの，いまだ気温の上下が激しくて油断できない。天気予報と睨めっこしながら，日々の勤務計画を立てている。

近頃よく名前を耳にする Intel の Hyper-Threading について，軽く調べてみることにした。職場に念願の Xeon マシンが導入されたからだ。

http://www.intel.com/technology/hyperthread/

まず， Hyper-Threading を活用するための最も簡単な方法は，これを単純にデュアルプロセッサとして扱うことだろうと思う。例えば， Linux の SMP カーネルにおいて，同システムは一定の効果を上げられることが知られている。

http://www-106.ibm.com/developerworks/linux/library/l-htl/

上記にある developerWorks の記事では，単純なシングルプロセスでのベンチマークと，マルチプロセスにおけるベンチマークの，２系統のテストについて検証を行っている。シングルプロセスでのパフォーマンスに変化が見られないのは当然のこととして，後半のマルチプロセスにおける負荷テストでは，大方において 20% 以上の性能向上を確認することができる。

また，それに加えて， Linux Kernel 2.5.x では，ロードバランサが仮想マルチプロセッサ向けに改善されたことにより，更なる性能の向上が望めるとのことだ。

これは，僕個人の漠然とした感想なのだけれど，マルチプロセッサにおけるロードバランス処理は，シングルプロセッサにおけるそれよりも，上手く機能する傾向があるように思える。僕は OS のカーネルの挙動について詳しくないので，その仕組みについて理解することは出来ない。ただ，この数年間，デュアルプロセッサマシンをヘビーに使い続けてきた結果として，そのような結論を持つに至っている。

例えば，デュアルプロセッサ環境においては，３つまでの高負荷プロセスを効率良く動作させることができるという経験則がある。単純に考えれば，デュアルプロセッサで２つのプロセスが効率良く並行動作するってのは理解できる。ただ，それが３つまで大丈夫というのが，いまいち解せない。果たして３つ目のプロセスを動かす余力はどこから湧き出てくるのだろうかと，今でも不思議に思うことがある。

このようなロードバランス性能の違いは，ユーザインタフェースの反応速度にも影響を及ぼすため，ユーザにとって非常に分かりやすい現象となって現れることがある。

例えば，シングルプロセッサの場合には，バックグラウンドで gcc を１ジョブ走らせただけでも，システム全体がモタついてしまう。エディタはまともに反応しなくなるし， WinAmp も音がブツ切れ始め，ウェブサーフィンなどは望むべくも無くなってしまう（まあ，これは数年前の話）。ところが，デュアルプロセッサを積んだ SMP カーネルの Linux マシンでは，例えば gcc を同時に８ジョブ走らせるような，明らかにオーバーロードな状態においても，比較的軽快にユーザインタフェースが反応してくれる。

僕は普段，コンパイル用サーバのターミナル上に vi を立ち上げて作業している。そのマシンには，チーム内のプログラマが全員ログオンして，好き勝手に gcc を走らせているのだけれど，普段はコンパイルがいつ発行されているのか体感することができないぐらい，非常に安定した状態となっている。

しかも，そのマシン上で vnc-server が複数立ち上がってるってんだから……改めて考えると，もの凄い高負荷を保ち続けているマシンだと思う。専用のサーバハードウェアならともかく，単なる安物のデスクトップマシンに過ぎないという事実を敢えて忘れて使い倒している状態だ。

permalink

OpenMP

2003-04-15

OSNews の特集記事 "Exploring the Use of HyperThreading Technology for Multimedia Apps" は， Intel C++ Compiler と OpenMP を利用した Hyper-Threading の活用法について解説している。

http://www.osnews.com/story.php?news_id=3023

また， Intel Technology Journal の次の記事は，同じく OpenMP を用いた Hyper-Threading 的高速化技法について，より一般的な解説を行っている。

http://www.intel.co.jp/jp/developer/technology/itj/2002/volu...

両者の記事に共通しているのが， OpenMP と呼ばれるシステムを利用して処理の並列化を実現していることだ。

http://www.openmp.org/

OpenMP は，共有メモリ方式のマルチプロセッサシステム向けにデザインされた並列プログラミングモデルの一種だ。詳細については， OpenMP の代表的な処理系である "Omni OpenMP Compiler" のページにチュートリアルがあるので，これを参照すると良いだろうと思う。

http://phase.etl.go.jp/Omni/home.ja.html

http://phase.etl.go.jp/Omni/openmp-tutorial.pdf

OpenMP の特徴は，各言語に備わっている補助的なディレクティブ（指示子）を利用して，ソース内に並列化の「ヒント」を埋め込んでいくという形式をとっていることにある。例えば， OpenMP のチュートリアルには以下のような例が登場する。

#pragma omp parallel shared(A,B) private(i)
{
    #pragma omp sections nowait
    {
        #pragma omp section
        for(i = 0; i < n; i++) A[i]= A[i] * A[i] - 4;

        #pragma omp section
        for(i = 0; i < n; i++) B[i]= B[i] * B[i] + 9;
    }
}

このように， C 言語ならばプラグマ指示子を利用して並列化情報を埋め込んでいくことになる。

上記の例における一連のプラグマは，２つの for ループがそれぞれ並列化可能であることを表し，かつ，配列 A, B については常に実体を共有，変数 i については各個の処理においてプライベートに利用されている（相関性が無い）ことを表している。 OpenMP コンパイラは，このような補助情報を元に処理単位の特定を行うことが可能となる。

Intel C++ Compiler では，このようにして特定された処理単位をサブ関数 (T-region) 化し，それをスレッドルーチンとしてコールするようなコードを生成する。この辺りの詳しい実装方法については，処理系によって差があるものの，「各処理単位を別個の関数として分離し，スレッド化する」という流れは大体同じであるようだ。

ここで追加された OpenMP 指示子は，通常の（OpenMP 非対応の）コンパイラに対しては何ら意味を持たない情報となる。このことは，非 OpenMP 環境との互換性を保つのに役立っている。同じソースでも，食わすコンパイラが違うだけで並列処理／逐次処理が切り替えられ，しかも両者の動作は完全に互換であるという，非常に都合の良い状態が実現されているわけだ。

ここで登場した Intel の "Intel C++ Compiler" は， OpenMP を利用した並列化プログラミングに対応している。前述のようなマルチスレッディングによる並列化だけでなく，ストリーミング SIMD (SSE) を利用した並列化にも対応しているようだ。

http://www.intel.com/software/products/compilers/

この "Intel C++ Compiler" は，元は "KAI C++ Compiler" と呼ばれていた製品に相当する。 KAI Software Lab (Kuck and Association, Inc) が供給する並列化プログラミングの処理系として有名な存在であったものの，同社が Intel に買収されたことにより，改めて "Intel C++ Compiler" の名が付けられることになったようだ。

http://developer.intel.com/software/products/trans/kai/

同社はマルチプロセッサ向けソフトウェアのベンダとして非常に有名な企業であったようだ。 Intel が同社を買収したのが 2000 年のことだというから，ちょうど Intel が並列プロセッシングへのアプローチを強めていたころと重なるのではないかと思う。 Intel にとってみれば， KAI の持つ並列化ソフトウェアの開発力こそが，まさに自らの求めていたソリューションとして映ったのかもしれない。

Intel C++ Compiler の Linux 版は「非商用，サポート無し」を条件に無料で入手することができる。並列処理に興味があるのならば，これを試してみるのも面白いだろうと思う。

http://www.intel.com/software/products/compilers/clin/noncom...

このコンパイラの存在（および，無料で入手できるという事実）は以前から知っていたのだけれど，導入する強い動機が特に見当たらなかったため，今まで手を出さずに過ごしてきた。しかし，これを機に触ってみるのも面白いかもしれないと思っている。ただ，商用での利用は禁止されているから，仕事の上では利用しないように気をつけなければならない……。

permalink

SOCOM and Some Glitches

2003-04-16

朝，眠い目を擦りながら，日課のウェブ巡回をこなしていると， Gaming Age Forum の，次のようなスレッドに目が留まった。

http://forums.gaming-age.com/showthread.php?threadid=30072

あの "SOCOM" が滅茶苦茶に荒らされてしまっているという話だ。事の顛末については， GameSpot の Jeff Gerstmann 氏の記事に詳しく解説されている。

http://www.gamespot.com/gamespot/features/all/gamespotting/0...

ここで取り上げられている "SOCOM: U.S. Navy SEALs" (SCEA/Zipper Interactive) は，北米 PS2 市場におけるオンライン戦略の要となっている売れ筋ソフトだ。内容的にはありふれた軍事モノのシューターゲームであるものの，マルチプレイヤーゲームとしてのバランスの良さや，同梱のヘッドセットを使ったボイスチャットシステムの目新しさ，それから，良質な対戦型シューターゲームが不足しているという PS2 の現状にうまく適合したことなど，様々な要因から堅調な売り上げを記録している。

ところが，このゲームの売りの部分であるオンライン対戦プレイに関して，非常に深刻な問題が発生している。チートの横行だ。

http://boardsus.playstation.com/playstation/board/message?bo...

Gerstmann 氏の記事や，掲示板への投稿情報によれば， "ActionReplay" や "GameShark" と言った改造ツールを利用してチートを行う方法が，一部ユーザの間で流布している模様だ。しかも，そのチートの内容たるや散々なものとなっている。「壁抜け」チートを始めとして，弾薬無限チート，体力無限チート，等々……どう転んでも致命的なチートばかりだ。

しかも，不正プレイ防止のために仕掛けられている「投票制追放機能」に関しても，「名前消し」チートを利用してメンバーリストから姿を消してしまえば，その機能を無効化することが可能であるとのことだ。結局のところ，ひとたびチーターが登場したならば，全員でそのゲームを自主放棄することぐらいしか対抗する術が無いという，惨たる状況となってしまっている。

ここで最も問題となるのが， "SOCOM" が一般的な DVD-ROM 供給のソフトウェアであり，外部記憶装置を利用したパッチ当てに対応していないという事実だ。そのため，非常に制限された範囲内でしかチート対策を行うことができず，まさにどん詰まりの状況へと追い込まれてしまっている。

先日の Gamasutra の特集記事 "Developing Online Console Games" によれば， PS2 はメモリーカードを利用したパッチ当てに対応しているとのことだったのだけれど，ここまで事態が深刻化していることから鑑みるに， "SOCOM" ではこの種の対応を行っていなかったことが推測される。

同様の障害を引き起こしてしまったケースとしては， GameCube 版 "Phantasy Star Online" における初期不具合の件が記憶に新しい。

http://www.sonicteam.com/psogc/pc/news1.html

http://www.sonicteam.com/psogc/pc/news.html

これらの例からも導き出されるように，固定的な（更新不可能な）システムを前提としたオンラインマルチプレイサービスの供給は，非常に難しい側面を伴っているように思われる。ユーザがこれらのゲームを購入するとき，そのユーザは，決して ROM メディアやその中身に対して対価を払っているわけではなく，「遊び場」としてのオンラインサービスを期待してお金を払っているはずだ。その点において，オフラインゲームとオンラインマルチプレイヤーゲームは，基本的な性質を異としている。そのため，継続的なシステムの保守やコンテンツの拡充を行えない仕組みでは，本当に充実したサービスの実現は難しくなってしまうはずだ。

それにしても，今回の "SOCOM" の件に関しては，残念ながらも，非常にお粗末な結果であったと言うしか無い。 ActionReplay のようなツールを利用すれば，バイナリレベルでの改造が可能であることは明らかであったはずだ。それにも関わらず，前述のような現象から察するに，制作側は何の対処も行っていなかったかのように思える。しかも，無限ライフや「壁抜け」等のチートは，システム上の矛盾を検出する機構を用意すれば，比較的確実に対処することが可能であったはずだ。結局のところ，不正行為に関して何も対策が講じられていなかったであろうことが推測される。

このような家庭用オンラインゲームの惨たる状況を目の当たりにする度に，逆に輝きを増して見えるのが，国内における FF XI の成功事例だ。近日，同ゲームは拡張パックである「ジラートの幻影」をリリースすることで，既存ユーザの更なる囲い込みを実現しようとしている。

http://www.playonline.com/ff11/ex1/g_index.html

FF XI は，家庭用ゲームにおいて，現時点で唯一，動的なコンテンツの更新に対応している製品ではないかと思う。バグ修正を含む継続的なサービスの改善，新規コンテンツの拡充，ゲームシステムの強化・調整，定期的なイベントの開催など，「一旦掴んだユーザを絶対に放さない」ための数々の戦略が展開されている。このような「持続的コンテンツ供給」の流れは，今までの家庭用ゲームには存在し得なかった新たなサービスの形を作り出すとともに，「ビジネスモデルとしての MMORPG 像」を確固たるものとして確立しようとしているように思える。

permalink

Reference to Reference

2003-04-17

久しぶりの継続勤務。季節の合間の時期は，空調の切られたオフィスでも比較的快適に過ごすことができる。泊まるなら今のうちだ。

実のところ，職場に泊まったところで，得られる活動時間は高々５時間程度のものだ。しかし，その５時間がとても貴重なものと思えることがある。

本当は，こんなダラけたやり方はいけないのだと思う……しかし，どうしても，日中の成果に納得できないこともあるんだ。

近々，職場が赤坂へ戻るとの話がある。赤坂ならば３０分強での通勤が可能だ。そうしたら，もう，こんな締りの無い生活はやめにしようと考えている。

職場に泊まることはできるのに，９時に出社して１２時に帰宅するぐらいのローテーションを実践できないのは何故だろうと，たまに考えることがある。それは，単に気合が足りていないのと，泊まった方がダラけるのに都合が良いからなのだろうと思う。

通勤時間が短くなれば，「通勤時間の分を惜しんでいる」という，自分に対しての最後の言い訳も効かなくなる。そうしたら，「最も効率良く生活するための方法とは，どのようなものか」という問題と，少し真面目に対面してみようと思っている。

何気なくコードを書いていて，初めて binder アダプタの「参照の参照」問題に突き当たった。問題となったのは，次のようなシチュエーションだ。

struct Node
{
ostream& printOn(ostream& os) const;
};

void printNodeList(const vector<Node*>& nodes)
{
for_each(nodes.begin(), nodes.end(), bind2nd(mem_fun(&Node::printOn), cout));
}

これをコンパイラに与えると，以下のようなエラーメッセージが返ってくる。

/usr/include/c++/3.2/bits/stl_function.h:393:
forming reference to reference type `std::ostream&'

STL の binder アダプタは，バインドする引数が参照型である場合，テンプレート内部で「参照の参照」問題を引き起こしてしまう。僕はまったく知らなかったんだけれど，この不具合はかなり有名なものであるらしい。アダプタ類とか真面目に使ったことが無いからなあ……。エラーと遭遇してしばらくの間，何が起こったのかさっぱり理解することができなかった。

この問題については Stroustrup が次の論文で詳細な解説を行っている。

http://anubis.dkuug.dk/jtc1/sc22/wg21/docs/papers/2000/n1245...

この問題に対する最も簡単な回避策は， STL の "std::bind2nd" の代わりに Boost の "boost::bind2nd" を利用することだ。

http://boost.org/libs/functional/binders.html

これは驚くほど簡単に問題を解決することができる。もう， STL の binder を使うのは止めて，常に Boost の方を利用するものと決めてしまうのも，良い案かもしれない。

ちなみに， Boost には STL の binder を一般化した "bind.hpp" ライブラリが存在する。しかし，これの利用はあまり勧められない。実装が複雑過ぎて移植度が低くなってしまうし（コンパイラのバージョンによっても不具合が生じるかもしれない），生成されるコードも相当に複雑なものとなってしまうからだ。

Boost には鬼門がいくつか存在する。 bind や lambda はその一種だと考えた方が良いだろうと思う。

permalink

mem fun

2003-04-18

朝，目覚めてから最初に取った行動は， flipCode への巡回だった。ニューストピックによれば， Lua 5.0 の正式版がリリースされたらしい。ほう……。

http://www.lua.org/news.html

さっそくダウンロードし，ほんの少しカスタマイズを加えたのちに，プライベート CVS リポジトリへコミットした。試しに diff を取ってみると，変更点が浮き彫りになってくる。そのほとんどが些細な変更であり，機能的な追加と呼べるものはほとんど無いようだ。

また，正式リリースよりライセンスが MIT スタイルへと移行したようだ。

http://www.lua.org/copyright.html#5

この影響により，今後，製品への組み込みの際には，コピーライトの表示が必須となる。

これは，以前のライセンスが若干曖昧な内容を含んでいたため，逆にコピーライト表示を義務付けることによって条件をシンプルにしようという意図が働いているようだ。

昨日の binder の一件と関連して，同時に利用していたメンバ関数アダプタ (mem_fun) についても，少し気になるところがある。

メンバ関数アダプタ mem_fun は，任意のクラスメンバ関数を，関数オブジェクト（ファンクタ）化するものだ。

http://www.sgi.com/tech/stl/mem_fun_t.html

ラムダ式などに慣れている人にとっては，こういったアダプタ類の存在は，ひどくナンセンスなものに見えるだろうと思う。ていうか，むしろ，テンプレート自体が訳分からないだろうな……。ともかく， C++ 上でのジェネリックプログラミングにおいて，各種関数アダプタの存在は重要なものだ。意外と使いでがあるもので，油断すると mem_fun やら binder やらでガチガチに接続してしまっていることがある。

そこで浮かんでくるのが，そんなに気軽に使って良いものなのだろうか，という疑問だ。 STL や Boost では，機能的には簡単なものであっても，極めて複雑な実装が行われていることがある。何らかのフィーチャーを使ってみようと考えたならば，それによってどの程度の負荷が発生するものなのかを見極めておくことが肝心だと思う。

最近こればっかだけれど，とりあえずディスアセンブリを取って確認してみようと思う。さっそく次のようなコードを用意した。

struct Foo
{
    int x;
    Foo(int x) : x(x) { }
    int get() const { return x; }
};

int test_func_1(const Foo& r)
{
    return std::mem_fun_ref(&Foo::get)(r);
}

int test_func_2(const Foo& r)
{
    return r.get();
}

test_func_1 は mem_fun_ref を経由したメンバ関数呼び出しであり， test_func_2 は比較のために用意した同等の実装だ。これをコンパイルした後にディスアセンブリを取ると，以下のような結果が得られた。

00000000 <_Z11test_func_1RK3Foo>:
   0:    53                       push   %ebx
   1:    83 ec 14                 sub    $0x14,%esp
   4:    b8 00 00 00 00           mov    $0x0,%eax
   9:    89 44 24 0c              mov    %eax,0xc(%esp,1)
   d:    8b 4c 24 0c              mov    0xc(%esp,1),%ecx
  11:    89 c8                    mov    %ecx,%eax
  13:    83 e0 01                 and    $0x1,%eax
  16:    31 d2                    xor    %edx,%edx
  18:    84 c0                    test   %al,%al
  1a:    8b 5c 24 1c              mov    0x1c(%esp,1),%ebx
  1e:    89 54 24 10              mov    %edx,0x10(%esp,1)
  22:    74 18                    je     3c <_Z11test_func_1RK3Foo+0x3c>
  24:    8b 54 24 10              mov    0x10(%esp,1),%edx
  28:    c1 e9 02                 shr    $0x2,%ecx
  2b:    8b 04 1a                 mov    (%edx,%ebx,1),%eax
  2e:    8b 0c 88                 mov    (%eax,%ecx,4),%ecx
  31:    8d 04 1a                 lea    (%edx,%ebx,1),%eax
  34:    50                       push   %eax
  35:    ff d1                    call   *%ecx
  37:    83 c4 18                 add    $0x18,%esp
  3a:    5b                       pop    %ebx
  3b:    c3                       ret
  3c:    8b 54 24 10              mov    0x10(%esp,1),%edx
  40:    eb ef                    jmp    31 <_Z11test_func_1RK3Foo+0x31>
  42:    89 f6                    mov    %esi,%esi

00000044 <_Z11test_func_2RK3Foo>:
  44:    8b 44 24 04              mov    0x4(%esp,1),%eax
  48:    8b 00                    mov    (%eax),%eax
  4a:    c3                       ret

ある程度見当は付いていたのだけれど……見事に間延びしてしまっている。そんなに都合良く最適化はしてくれないようだ。

結論として，「明らかにメリットの得られるケース以外では使わない方が良い」と言えるのではないかと思う。例えば，昨日のシチュエーションならば，以下のようにシンプルな記述を行うのが無難だ。

for (vector<Node*>::const_iterator i = nodes.begin(); i != nodes.end() ; i++)
{
(*i)->printOn(cout);
}

アルゴリズムテンプレートを利用する場合においても，アダプタでガチガチに固めるのは避けて，専用のファンクタを場面毎に用意することが望まれる。また，アダプタ類を複雑に組み合わせたコードは「どう考えても読みにくい」という欠点がある。そこも考慮に入れるならば，なおさら避けるべきだと思う。

もし，その処理が全体のパフォーマンスに対して影響を与えないという確信があり，かつ，アダプタを利用した方がシンプルに記述することができるという結論に至ったならば，使うべきかもしれない。いずれにせよ言えることは，単なるトリッキーな遊びのためにアダプタを利用してはいけないということだ。

permalink

Jak and Daxter

2003-04-19

今日は普通の休日。飯ついでに寄った本屋兼電器屋で「ジャック＆ダクスター」が 1,780 円で売られているのを偶然見かけてしまった。新品なのにこの価格……なんとも凄い投売りをされているものだと思う（定価は 5,800 円）。このゲームに関して色々と胃の痛む話を聞いたことがあるのだけれど，恐らく本当の話なんだろうなと，納得せざるを得ない状況だった。

そう言えばこのゲーム，以前から一度プレイしてみようと思っていたのだけれど，いまだ手を出せずにいる。いい機会だ。買ってしまえ……。

http://www.naughtydog.com/jak_N_dax/

ゲームを開始してから数十分が経過し，海外のゲームに特有の３Ｄ酔い症状にも慣れてくると，このゲームを純粋に楽しむことができるようになってきた。滑らかな操作感覚に，美しい背景，個性的なキャラクターの動きなどが印象的だ。そう言えば，このゲームの売り文句は「冒険アクションゲーム」であったと思う。実際にプレイしてみて，その言葉が簡潔に表現しようとしていたものを，やっと理解することができたような気がする。

このゲームの環境（ステージ背景）の表現は，僕がこれまで持っていた漠然としたイメージよりも遥かに美しく，活き活きとしたものだった。特に，導入部の舞台となる海岸沿いの村や遺跡の造形が美しい。緑と水の豊富な自然地形と，そこへ照りつける強烈な日差しの感覚は，どこか南の楽園を彷彿させる。それらの環境は時間の推移と共に外観をダイナミックに変化させ，豊かな表情をプレイヤーに与えてくれる。夜になると攻撃性植物が動かなくなってたりするのも，なんだか面白いね……。

そうやって「ジャック＆ダクスター」の世界を駆け回っていると，自分がまだ小さかった頃の，自然の中で遊び回るような感覚が呼び覚まされる。ちょっと裏山まで遊びに行くような感覚で，谷間の「オーブ」を集めに行くと，次第に日が変化していき，集め終わるころには夕焼け空となってしまう。日に赤く照らされた草原を見つめていると，なんとなく切ない気分になってしまう。そんな，ある種のリアルな感覚が，このゲームでは表現されている。

そういった意味で，このゲームは「冒険アクション」であると共に，「探検アクション」でもあるのではないかと思う。ちょうど "ICO" が巨大な遺跡内の探検をテーマとしていたように，この「ジャック＆ダクスター」は，大自然の中を相棒と共に駆け回るという「探検」をテーマとしているのではないかということだ。

ほとんどの人にとって「冒険」とは物語の中だけの概念であるはずだ。でも，「探検」ならば，誰もが体験したことのある感覚だろうと思う。逆に，物語は「冒険」を作り出すことはできても，「探検」を与えることはできない。それを具現化できるのはインタラクティブなメディアだけであり，そこでビデオゲームこそが最も適切な存在となり得るのではないかと思っている。

permalink

ワイヤード松屋

2003-04-20

明日は天気が良さそうだから，昼間にちゃんと起きてみるかと，目覚ましを９時間後にセットして眠りに就くと，起きた頃には中途半端な曇り空となっており，今にも雨が降り出すのではないかというような空模様だった。

期待に反した結果に，僕は一気にやる気を失ってしまった。また布団の中へと滑り込むと，心地よい惰眠を貪り続ける。それから数時間後，次に気が付いた頃には，辺りはいつも通り暗くなっていた。だめだ，また不毛な休日の始まりだ。

適当に松屋で夕飯を済ますと，おもむろに「ジャック＆ダクスター」の DVD-ROM を取り出し，昨日の続きを始めることにした。もう，今週は「ジャック＆ダクスター」でおしまい。それでいいさ……。

最近，松屋の店内を注意深く見回してみると，水色のケーブルが店内に張り巡らされているのが見える。あの太さと特徴的なカラーリングから言って， 100Base-T のイーサケーブルではないかと思われる。一体，あんなもの何のために張っているんだろう……。

他にも，券売機が新しいモデルに入れ替えられたり，調理場に液晶端末が据え付けられたりと，意味深長な動きが店内の一部に見られている。どうやら，松屋は最近，相当に高度な電子化を推し進めているようだ。

ちょっと興味があったので，松屋のウェブサイトを覗いてみると，それらの動きと関連する情報が少し載っていた。

http://www.matsuyafoods.co.jp/7features/joho/index.html

どうやら，券売機に入力があった瞬間から調理場の端末に注文が表示され，着席以前から調理を始めるような体制が整えられているようだ。注文内容は同時に社内の POS システムへと転送され，食材の発注管理やマーケティングへと反映される。このように，松屋の店内ではいつの間にか，非常に機能的な情報管理システムが構築されようとしているようだ。いまだに口頭での注文と食後清算を続けている吉野家とは対照的な雰囲気となっている。

松屋のように極度に特化されたファーストフード店において，このような情報化を進めるメリットは少ないかのように見える。しかし，高度な食材管理によって余剰発注のリスクが引き下げられれば，より多くの食材を用意しメニューを増やすことが可能になるかもしれない。また，来店客数の推移が時間帯毎に割り出せるようになれば，人員数を細かに調整して人件費対効果を理想的な値へと近づけることが可能となるかもしれない。

こういった電子化の流れは，ファーストフード店だからこそ許されるという風潮もある（普通の飲食店が電子端末だらけになったら，大抵の客は嫌がるだろうと思う）。その点を極端に突き詰めることによって，今までに無かったレベルのコスト削減を狙おうというのが松屋の目指すところではないかと思う。「吉野家より松屋」派の僕にとって，この流れは非常に興味深い意味を含んでいる。これからの進展に期待しようと思う。

「ジャック＆ダクスター」をプレイしている間，このゲームは何故国内で受けなかったのだろうか，という疑問を何度となく思い浮かべることになった。鶴見六百氏の GDC 講演の内容は，キャラクターやビジュアル戦略の観点から，ローカライズ展開の難しさを解説したものだったけれど，このゲームの場合，その難しさはもっとゲームとして根源的な要素に依存しているように思える。例えば，同氏がコラムの中で述べていた「３Ｄ探検に対する国内外の興味の差」などだ。

http://www.mrspider.net/0600design/uso19.html

"MYST" や "ICO", "GTA", それからこの「ジャック＆ダクスター」のようなゲームをプレイしていると，「仮想世界の中を探検する楽しさ」というものが確かに存在することを感じ取ることができる。しかし，そのような「楽しさ」の要素は，これまでのゲームのメインストリームとは性質を異にする部分であり，そのためひどく捉え難い概念となっている。その概念を口にしてみたところで，それを人に伝えることは難しいし，共感を得ることは不可能なのではないかと感じることさえある。

その点において，僕の興味は，「このゲームが国内で受けなかった理由」よりも，「このゲームが国外で受けた理由」に推移する。欧米のユーザは，本当に探検が好きでこのゲームを買ったのか，それともキャラクタやアートデザインに惹かれて買ったのか，それとも……。

それが判明したところで，僕自身や，僕の周囲で作られているものが何一つ変化するものではないと思う。しかし，あの「感覚」を，世界の何処かにいる人達が共有していたという事実を掴めればと，空しい足掻きを続けているだけのことだ。

permalink

Latency Compensation

2003-04-21

少し前に GDAlgorithm で盛り上がっていたスレッド "Network console game/distributed object strategies" に目を通してみている。

http://www.radiumsoftware.com/excerpts/network_console_game....

なにしろ長いスレッドなもので，なかなか読み終えることができずに苦労している。

話の発端は， Sammy Studios の Charles Nicholson 氏が，ネットワークゲームのアーキテクチャに関する一連の考察を投稿したことに始まっている。避けようのないラグ（通信遅延による操作の不安定性）が発生するシチュエーションにおいて，いかに「納得のいく」インタフェースを提供するべきか，という話題だ。それと同時に，分散型のネットワークモデルにおいて発生しやすいハッキングの問題に関しても触れている。

件の投稿の中で氏は， Tim Sweeney 氏の執筆した Unreal アーキテクチャに関する解説記事を参考資料として挙げている。

http://unreal.epicgames.com/Network.htm

この記事は，既成技術の解説としてそれなりに興味深いものだ。しかし，これよりももっと興味を惹かれる資料が，話の途中に挙げられていた。 Valve Software は Yahn Bernier 氏による GDC 2001 講演 "Latency Compensating Methods in Client/Server In-game Protocol Design and Optimization" の資料だ。

http://www.gdconf.com/archives/2001/bernier.doc

この講演は，氏が過去に制作に関わった "Half-Life" や "Counter-Strike" において利用されている技術 "Latency Compensation" （遅延相殺）について解説したものだ。

http://valvesoftware.com/projects.htm

この技術は，サーバ側の処理に対して柔軟性を与えることによって，よりユーザが納得することのできる結果を求めようというものだ。従来の方法論が「一貫性を重視する」「矛盾を発生させない」という部分に焦点を当てていたのと比較すると，実に対照的な考え方だと思う。

僕が Quake にハマっていたころ，最もプレイの妨げになると感じたのが，武器トリガに対する通信遅延の影響だった。

Quake のネットワークアーキテクチャには，通信路の遅延に対する様々な防護策が盛り込まれている。プレイヤーの操作に関して遅延を感じることはほとんど無かったし，対戦相手の動きに関してもまずまず納得のいくものだった。しかし，武器トリガに関してはまったく別問題だ。ゲームとしてクリティカルな要素であるゆえか，厳密な一貫性を保護するために，通信路の影響を完全に被る仕様となっていた。

そのため，例えば通信路において 150ms の遅延が発生しているとしたら，ユーザはその倍である 300ms もの「先読み」を行わなければならなかった。ただでさえ外挿法によるガタついた挙動が見られるのに，その上 0.3 秒も先読みをしなければならないなんて！当然，そんな状況下でまともに狙いなど定められるはずも無いわけで，範囲攻撃系の武器でチビチビ攻撃しつつ，ハイエンドユーザ（彼らの遅延は 50ms 以下だ）のレールガンの的にされるのがオチだった。

このような一貫性重視のアーキテクチャに対して， Bernier 氏の述べている「遅延相殺」の技術は，サーバ・クライアント間に存在する通信遅延を考慮し，その分だけサーバ側の時間を巻き戻して処理を行うことによって，ユーザに遅延を感じさせないインタフェースを提供しようというものだ。

これには，まず，サーバ側に過去数秒間のヒストリを蓄積し，任意の時点まで処理を巻き戻すことを可能とする機構が必要となる。その上で，ユーザからの要求パケット（例えば「ｘ時にライフルを発射した」など）が到着したならば，その要求がクライアントに�