2003-05-01
テストプログラム用のフレームワークとして CppUnit を利用する場合に，最も問題となるのが，メモリ関連のチェック機能が不足していることではないかと思う。これは CppUnit のオリジナルである JUnit が Java での実装であったことに関連しているかもしれない。ともかく，ここでは C++ を用いているのだから，テストと同時にメモリリークの検出ぐらいは行っておきたいものだ。
ここではひとまず，外部ツールの助けを借りて，メモリ周りのチェックを行うことにしようと思う。
メモリの不正利用を検出するためのツールは，意外と多く存在する。
http://www.home.linuxjournal.com/modules.php?op=modload&name...
UNIX 方面で人気があるのは "GNU Check" や "mpatrol", "ElectricFence" といったツールのようだ。これらのツールは，メモリ保護機能を応用して不正な領域へのアクセスを検出し，デバッグ情報と共に表示するというものだ。また同時に，メモリリークの検出も行えるようになっている。
http://www.gnu.org/software/checker/checker.html
http://www.cbmamiga.demon.co.uk/mpatrol/
http://perens.com/FreeSoftware/
http://cs.ecs.baylor.edu/~donahoo/tools/efence/
この他に，ガベッジコレクタの実装を転用してリークデテクタとする方法もあるようだ。 "Boehm-GC" として有名な "The Boehm-Demers-Weiser conservative garbage collector" は，本来ガベッジコレクタの実装であるものの，「おまけ」としてメモリリークを検出する機能も付けられている。元がガベッジコレクタであるため，参照されなくなったメモリ領域だけを正確に検出することができるようになっている。
http://www.hpl.hp.com/personal/Hans_Boehm/gc/
……と，このように，ツールは色々と存在するものの，ここでは「手軽にリークの検出ができること」と，「できるだけシンプルな実装であること」の２つに条件を絞って選択してみようと思う。
そこで最も良さそうだったのが， Erwin Andreasen 氏の "LeakTracer" だ。
http://www.andreasen.org/LeakTracer/
ん，何だか知らないけどサイトが落ちてしまっているな……。この "LeakTracer" は Debian の標準パッケージに含まれているので，そちらからソースを拾ってくることも可能だ。
http://ftp.debian.org/debian/pool/main/l/leaktracer/leaktrac...
パッケージには以下のようなサンプルプログラムが含まれている。
もう，見るからに不正なプログラムだ……。これを LeakTracer でチェックするには，まず， "LeakCheck" コマンドと共にプログラムを走らせる。これによって，リークポイントの検出結果が "leak.out" ファイルに出力される。
ただし， cygwin 上でこれを行うと，共有ライブラリの結合でコケてしまうようだ。これについては， LeakCheck コマンドを用いる代わりに，オブジェクトファイル (LeakTracer.o) を静的にリンクすることによって対処が可能だ。
こうして得られた leak.out ファイルには，リークポイントのアドレス情報が羅列されている。デバッグ情報付きでビルドされたプログラム（いわゆる「"-g" オプション付き」）ならば， "leak-analyze" コマンドを用いることで，ソースとの対応を取ることができる。
結構見やすい表示だ。他のツールと比較した場合，機能的には限定されているのだけれど，それがかえって使いやすさに繋がっているような気がする。
LeakTracer の行っていることは，基本的に "operator new" と "operator delete" のオーバーライドだけだ。そこから「delete 忘れ」等の検出を行い，得られた情報を leak.out へ出力する。 "leak-analyze" コマンドの実体は perl スクリプトであり，内部から gdb を呼び出すことによって，アドレス情報とソース内容の対応を可能としている。
このように，内部的にはアドホックな実装なのだけれど，やっていることがシンプルなだけに，ゲーム機環境への組み込みも楽に実現できそうだ。これについては，いずれ機会を見て検討してみようと思っている。
2003-05-02
今日は久しぶりの有休日。せっかくの好天を満喫しようと思い，玉川河川敷へと散歩に出かけた。
休日は常に人で溢れ返っている河川敷も，まだ今日は人もまばらだった。川端のコンクリブロックに腰を据えて，しばらくの間，何をするでもなく，ただ本を読んでいた。
しばらくして日が傾いてくると，急に風が冷たくなってきた。日光浴なら，もっと昼間に来なきゃだめだな……。
５時ぐらいで早々に退散。ファミレスのラザニアとコーヒー２杯で，家に戻ってきた。
散歩のついでに読んでいた本がある。 "Ruminations on C++" の和訳版，「Ｃ＋＋再考」だ。
http://www.pearsoned.co.jp/washo/prog/wa_pro62-j.html
http://www.amazon.co.jp/exec/obidos/ASIN/489471776X
先日，いつもの本屋へ立ち寄った際に，何気なく手に取った本なのだけれど，一目見て良い内容だと感じたので，その場で購入を決めたものだ。
この本は，著者の Andrew Koenig 氏が JOOP (Journal of Object-Oriented Programming) 等に連載していたコラムを集め，一冊の本として再編集したものであるらしい。そのためか，一つ一つの章の内容が比較的独立しており，どこからでも読み始めることができるような内容となっている。
ただ一つ気を付けなければならないのが，この本は C++ 入門者に向けた内容ではないということだ。むしろ， C++ や STL を一通り修めた中級者へ向けた内容となっている。文字通り「再考」するための本だということだ。
この本の中で，個人的に最も興味深かったのが第三部の内容だ。
第三部「テンプレート」では， C++ のテンプレートの各種応用法について解説を行いつつ， STL のコアとなる概念「ジェネリシティ」の導入を行う内容となっている。どのようにして「ジェネリックなイテレータ」という概念が導き出されたのか？ 関数オブジェクトの本来の目的とは？ 関数アダプタは我々に何をもたらすのか？ 等々……。 STL の考案者が辿ったであろう思考の道筋を，読者自身の視点から辿り直すことで，その存在意義と応用法についてより正確なイメージを掴むことが可能となっている。
これまでにも，オブジェクト指向に関して解説を行った書籍は巷に山ほどあれど，ジェネリックプログラミングを扱った書籍の数は極めて限られているように思える。一般的な STL の解説書は，ライブラリ自体の解説に終始してしまっているきらいがあるし， "Modern C++ Design" のような凝った本は，内容が専門的過ぎるために導入書としては適さないのではないかと思う。
この本のコンセプトは実に曖昧なものだ。前述の通り C++ の入門書では無いし，いわゆる「ノウハウ本」とも違う。特定の技術について解説した本でも無ければ，実のところ，一定のテーマすらも与えられていないような雰囲気がある。しかし，この本に詰め込まれた数々の考察は，いわゆる「C++ 中級プログラマ」に対して幅広い俯瞰を与え，これまでバラバラに学んできたことを体系的な概念としてまとめる手助けとなってくれるのではないかと思う。
同じ著者によって書かれた本に "Accelerated C++" というものがある。
http://www.pearsoned.co.jp/washo/prog/wa_pro51-j.html
ううむ……目次だけじゃ判らないけれど，興味の惹かれる内容ではある。機会があれば読んでみようと思う。
2003-05-03
唐突に秋葉原へ出かけてみた。
学生の頃は毎週のように通っていたものだけれど（あの街全体が学校の購買部のようなものだった），最近では行く機会が極端に少なくなってしまった。年に１回，行くか行かないか，ぐらいのものだと思う。
今日も特に目的があったわけでも無くて，ただなんとなく，どの程度雰囲気が変わったものかなと，確認をしに行ったようなものだった。
様々な伝聞から，もう相当にヤバい萌え都市と化してしまった様子を想像していたのだけれど，久しぶりの秋葉原は，案外に大した変化も無くて，少し拍子抜けするようなものだった。それでも，相当に特殊な都市であることには違い無いのだけれど……。
目的も無く，末広町方面の裏路地を，ただぶらぶらと歩いていると，頻繁にジャンクショップの類を目にすることに気が付いた。お馴染みの「ガレージショップ」を始め，「じゃんぱら」やら「掘出屋権兵衛」やら，結構な数のジャンクショップを目にする。休日ということで露天も多かったし，何故か国籍不明の人達の姿もよく見かける。
そういったジャンクショップで扱っている商品と言えば，中古 PC や中古ワークステーション（Sun や DEC や SGI のマシンもゴロゴロ），放送用機材や謎の計測機具，型番落ちのマイクロソフト製品を始めとするゴミのようなソフトの山，等々……。他なら産業廃棄物も同然であろう代物に，堂々と値札を貼って売りさばいている。客の方も，物珍しさに惹かれて来ている人が多いようだ。あまり売れているような気配は感じられない。
放送機材のテレビモニタが 5,000 円だった。あれは確か PAL も映るヤツだから，何かの役には立つかもな……。買わないけど。
適当なレコード屋に入って，キューブリックの「フルメタルジャケット」の DVD を購入。ここまで来て何も買わないのは少し寂しかったので，紛らわしに買ってみたまでだ。
それと，某ゲーム店で PS 版「プリルラ」を発見したので，即購入。これは思わぬ収穫だった。
http://happygamers.fc2web.com/review/prurira.htm
これを証拠物件として提出し，某氏を尋問するのだ。うひひ……。
今回，秋葉原まで遠征したもう一つの理由は， GBA 用の特殊な機材を調達することにあったのだけれど，これは実現することができなかった。どこも店頭では取り扱っていないからだ。まあ，使い方によっちゃあ，非常によろしくないことも出来てしまうツールだから，無理もないのだけれど……。
http://optimize.ath.cx/bootcable/
よく知られているように， GBA のソフトには，１つのカートリッジで複数人の対戦プレイに対応しているものがある。この場合，子機におけるプログラムやデータの類は，対戦ケーブルを介して親機側からダウンロードされ，本体内蔵の 256kB RAM に格納されることになる。これと同様のことを，親機を PC として行えば，任意のプログラムをダウンロードして起動することが可能となるのではないか……というのが「ブートケーブル」の原理だ。
今では，この「ブートケーブル」を利用して， GBA 本体を SRAM 書き込みデバイスとして利用する方法が一般的となっているようだ。 "Flash2advance" 等の市販製品も，基本的には同様のテクニックを利用したものであるらしい。
しかも驚いたことに，この仕組みを小型ドングルによって実現するテクニックまで開発されているようだ。
http://optimize.ath.cx/bootcable/bootchip.html
これを使えば，例えば上のページでも挙げられているように，ゲームセーブ用の SRAM に任意のプログラムとデータを格納し，それをドングルから起動する，というようなテクニックが実現可能となる。もはや何をしたいのか分からなくなってきている感はあるけれど……相当に楽しそうなハックであることは伝わってくる。
2003-05-04
普通の休日。散歩中に立ち寄った本屋で，クーロン黒沢氏の新刊「マイコン少年さわやか漂流記」を購入した。
http://bookweb.kinokuniya.co.jp/guest/cgi-bin/wshosea.cgi?W-...
アンダーグラウンドの伝道師として有名な氏の，暗澹たる少年時代の記憶を綴った本だ。氏のサイトのプロフィールでは数行にまとめられてしまっていることを，じっくりと一冊の本をもって語り尽くす……というような内容になっている。
http://www.hehehe.net/users/kowloon/profile/
国産ＰＣの創世記に少年時代を迎えた氏の生い立ちは，他のＰＣフリーク（例えばスパタ斎藤氏など）と重ねて見れる部分も多い。しかし，そこでほんの少し違った過程を歩んでしまったがために，最終的にはまったく異なった種類の人生を歩む結果となってしまった。その，氏の方向性を決定付ける要因となった青春時代の出来事の数々が，実に生々しいドキュメントとして描かれている。
本の中で描かれる氏の少年時代の像は，決してフリークや地下世界の住人としての存在では無く，ごく普通の気弱な少年でしかない。ただそれが，周囲の特異な環境や，持ち前の無謀さ，個性的な知人の存在などによって，徐々に薄暗い世界へと吸い込まれていくことになる。
氏が後書きで述べている「十年前の日本にはチャンスがそこらに転がっていた」という言葉が不思議と胸に残る。８０年代後半から９０年代初期にかけてのＰＣ創世記は，何にでも，何処にでも，あらゆる可能性が存在していた。カンブリア紀の生物が進化の多様性に挑戦したように，国内のＰＣ産業とそれを取り巻く環境は，己の存在を試すべく，あらゆる可能性へと挑戦をかけていった。氏が体験したような暗部の存在も，その時代に生まれるべくして生まれ，消えるべくして消えた流れの一端なのだろうと思う。
氏は PC88 の同人ソフト界でも特異な活動を行っていたということで，その辺りの話にはかなり親近感を覚える。
http://www.google.co.jp/search?q=%83J%83%7D%83_%83%7E%83A%83...
自主制作の暗部についても生々しい体験談が綴られている。どのような事情によって，あのような謎のラインナップが生み出されることになったのか，その真相が初めてここで明かされることになる。青臭いだけならまだしも，読んでてここまで気まずい思いをするのも珍しいな……。
今となっては過ぎ去った日々の出来事なのだけれど，その裏舞台を知ることができるのは楽しいことだ。あの時，自分が田舎でのうのうと暮らしていた時に，確かにその世界が存在したという確証を得たわけだ。……きっと何処かに存在すると信じていた，刺激溢るる紫色の桃源郷を……
やはり，生まれた環境の影響は重要な問題であると認識せざるを得ない。氏の体験も，周囲の環境や知人による影響が強く表れているようだし，少年期にどのような体験をしたかでその後の人生が決まってしまうというのも，あながち適当な話でもないのだろうなと強く感じた。
2003-05-05
突然だけど， Pete Isensee 氏のページが面白い。
http://www.tantalon.com/pete.htm
氏は数週間前に Gamasutra で "Developing Online Console Games" という記事を書いていた人物だ。マイクロソフト内部で Xbox のソフトウェアエンジニアという役割を担いつつも，わりと中立的な視点で記事を書いている所に興味を惹かれた。氏の個人サイトの方には，氏が過去の GDC で行った講演の資料などが置かれている。特に， Xbox ローンチ時の内情を明かした講演 "Xbox Launch: Lessons Learned" などは，プログラマ以外の人でも興味を持てるものなのではないかと思う。
http://www.tantalon.com/pete/xboxlessonslearned_files/frame....
氏は，以前から C++ の応用に関して強く興味を持っているようだ。過去の Game Programming Gems にも C++ 関連の記事を数個寄稿しているほか， GDC でも C++ 関連の話題を中心に講演を行っている。例えば， 1998 年の GDC 講演 "C++ Optimization Strategies and Techniques" では，氏がゲーム開発のために組み上げた C++ 設計方針とその効果について詳しい解説を行っている。
http://www.tantalon.com/pete/cppopt/main.htm
ただし，若干冗長で羅列的な内容となっているため，既にこの辺りのノウハウを蓄積している人にとっては，あまり得るところの無い内容となっているかもしれない。それでも，実測での速度比較を眺めるのは面白いと思うし（意外と効果の小さな項目が多いことに注目したい），中には新たな発見があるかもしれないと思う。
例えば，仮想関数を持つクラス（仮想クラス）においては，コンストラクション／デストラクションに対して追加の負荷が要求されるという話は，ここで初めて聞いたような気がする。
http://www.tantalon.com/pete/cppopt/final.htm#AvoidVirtualFu...
これは，コンストラクタが継承ツリーを順に辿っていく段階において，タイプ情報を段階的に変更しなければならない，という仕様に起因するものだ。
例えば，次のようなコードを用意する。
ClassA は BaseClass の派生であり， ClassB は ClassA の派生だ。それぞれのコンストラクタでは外部関数 test_func を呼んでおり，その中では仮想メンバ関数 display の呼び出しと，タイプ情報の取得を行っている。
ここで， ClassB の生成を行うと，次のような出力が得られる。
この出力から分かるのは，例え ClassB の生成であっても， ClassA のコンストラクタの時点では，インスタンスには ClassA のタイプ情報と仮想関数テーブル (vtable) が設定されているということだ。そして，これらのタイプ情報と vtable は， ClassB のコンストラクタが呼び出される直前に， ClassB のものへと入れ換えが行われる。これらの処理はコンパイラによって自動的に生成されるものだ。もちろん，継承ツリーが長くなればなるほど，この処理も長く複雑なものへと成長することになる。
この辺りの処理の詳細については， C++ の規格を当たるよりも，各処理系の ABI (Application Binary Interface) を参照した方が良い場合もある。 ABI は，各言語処理系におけるバイナリ化の規約を集めたものであり，例えば，関数 Foo::bar() のシンボル名はどう変換されるだとか，引数の ** 番目までが ** レジスタに割り当てられるだとか，そういったものが延々と定義されている。 C++ の場合は，タイプ情報の格納方法や，仮想関数の実装方法なども，すべてここに含まれることになる。
どうやら GCC では 3.0 系より CodeSourcery 社の定義する "Itanium C++ ABI" を採用しているようなので，これを参照することにする。
http://www.codesourcery.com/cxx-abi
ドラフトの 2.6 章 "Virtual tables During Object Construction" が今回の件に相当する個所のようだ。
http://www.codesourcery.com/cxx-abi/abi.html#vtable-ctor
しかし，いかにも仕様書って感じの記述で読みづらい。ていうか，読んでも全然分からないや……。ええと，とりあえず，仮想クラスのコンストラクション処理が，予想以上に小難しいってのは，なんとなく分かったよ……。
2003-05-06
Pete Isensee 氏は，ゲーム制作現場における C++ の啓蒙活動を行うと共に， STL に関しても積極的な啓発を行っている。 GDC 1999 の講演 "Embracing the C++ STL" は，ゲーム開発において STL を活用する際に，特に重要となるであろう項目について触れたものだ。
http://www.tantalon.com/pete/roadtrip99_files/frame.htm
http://www.tantalon.com/pete/files/embracingstl.zip
内容的には，やや基礎的な部類に入るものであり，これから STL を導入しようという人達へ向けたものであることが感じられる。僕がこれを読んで初めて知ったのは， std::deque が "deck" と発音するらしいということだ。ずっと「ディキュー」だと思ってたよ……。
もう一つの資料 "STL Optimization Techniques" は， GDC 2001 で開かれた同名のラウンドテーブル・ディスカッションの内容をまとめたものだ。
http://www.tantalon.com/pete/gdc2001roundtablereport.htm
ディスカッションに参加した約 80 名のデベロッパが，自身のグループにおいて採用しているポリシーや，テクニック，体験談などについて色々と語っている。こちらの資料は，実際の制作現場において STL がどのような扱いをされているのか，という点を知るために参考になるのではないかと思う。なかなか，他所様の雰囲気を知る機会ってのは少ないものだからね……。
ただ，これは GDC 2001 におけるディスカッションとのことだから，多少の内容の古さは考慮しておいた方が良いかもしれない。 2001 年と言うと，ちょうど現世代機への移行が完了した頃であり， C から C++ への移行も過渡期であっただろうと考えられるからだ。現世代機での反復期に入った今となっては，また新たなノウハウを蓄積し始めている所も多いのではないかと思う。
レポートに軽く目を通してみた感じでは，やはり限定的な利用に留めている所が多いな，という印象がある。「コードの増加を防ぐために void* のコンテナを利用している」なんていう意見は，ひどく野暮ったく感じる人もいるだろうと思う。果たして，そこまでストイックにならなければ駄目なのだろうか？
これは C++ の話になるのだけれど， RTTI や仮想関数，例外処理などについても，全面的に禁止するというポリシーが常識的に適用されているようだ。しかし，これらの問題については，もう少し慎重に吟味してみたいと考えている。「結局同じようなものを自前で実装するケース」が何処かで発生するのは必然であり，それならば何のために利用を禁止するのだろうかという疑問が常に付きまとうからだ。盲目的に禁じるのではなく，具体的に「駄目な理由」を挙げることが出来ればと考えている。
少し話は逸れるのだけれど，件のページから， STL の作者である Alex Stepanov 氏のインタビュー記事へのリンクが張られている。ポータブルな STL 実装として知られる "STLport" のサイト内にある記事のようだ。
http://www.stlport.org/resources/StepanovUSA.html
氏は旧ソ連生まれの計算機科学の専門家であり，ソビエトではパワープラントのシステム設計等を行いつつ，渡米以降は主に研究者として様々な舞台で活躍しているようだ。このインタビューの中で，氏は， STL と「ジェネリックプログラミング」の発祥の背景について様々な逸話を披露している。
その中でも特に興味深かったのが， STL の起源について触れている個所だ。
氏は，自身のことを「数学者になりきれなかった人間」というように評している。しかし， STL の優れた設計方針は，氏の持つ技術者としての経験と，数学者としての直感が組み合わさることによって生まれた，まさに必然の産物なのだろうと思う。
2003-05-07
Pete Isensee 氏のページから張られているリンクの中に，もう一つ興味を惹かれるものがあった。 "Guru of the Week" − 通称 "GotW" のページだ。
"Guru of the Week" は， C++ コラムニスト兼コンサルタントとして有名な Herb Sutter 氏のサイト内にある人気コンテンツだ。氏がニュースグループ (comp.lang.c++.moderated) に投稿していたクイズ形式のコラムをコンテンツとしてまとめたものであるらしい。
この "GotW" は，書籍としても出版されている。 "Exceptinal C++" だ。
http://www.gotw.ca/publications/xc++.htm
http://www.pearsoned.co.jp/washo/prog/wa_pro34-j.html
GotW 内の Q&A のうち，最初の 30 問を "Exceptional C++" に収録し，続く 30 問を "More Exceptional C++" に収録しているとのことだ。 "Exceptional" の方は和訳版が出されているのだけれど， "More Exceptional" の方は未訳であるらしい。
"Exceptional C++" の存在は，それとなく知っていたのだけれど，この手のノウハウ本は基礎を固めてからでないと楽しめないだろうと思い，今まで購入を控えていた。しかし……そろそろ手を出してみてもいいかなあ。
http://www.amazon.co.jp/exec/obidos/ASIN/4894712709
結局のところ， C++ という言語は十分に複雑な世界であるため，知らないと損をする罠がそこいらに転がっている。そういった罠を避けるためのノウハウを蓄積することが，駆け出しの時期には重要なタスクとなるのだろうと思う。もちろん，そういう下手な工夫を必要とされない言語こそが理想であるのだろうけども，どんな言語であれ少なからず覚えなくてはならないことが存在するのだから，むしろ優れた資料が豊富に存在することを利点と考えるのが良いのではないかと思う。
Isensee 氏のページでも挙げられているものなのだけれど， GotW #54 の "Using Vector and Deque" などは，ゲーム開発にも深く関わってくるところかもしれない。
http://www.gotw.ca/gotw/054.htm
ここで挙げられているのは， std::vector のメモリ開放手順についてだ。まず前提として， vector は基本的にメモリの開放を行わないものと仮定することができる。これは，メモリの再確保（再配置）の発生頻度を出来るだけ減らすためだ。例として SGI の実装を参照してみると，「バッファのオーバーフローが発生する度に容量を２倍にする」というような記述は見られるものの，開放についてはまったく触れられていないことが分かる。
http://www.sgi.com/tech/stl/Vector.html
reserve はメモリを拡張する方向にしか働かないし， clear を発行したとしても，ほとんどの実装ではメモリを開放しないようだ。
ここで GotW は，メモリの完全な開放を行うには，以下のような「慣用句」を用いれば良いと指摘している。
同様に，メモリ容量 (capacity) を現在の実サイズ (size) まで減退させるには，以下の慣用句を用いる。
ううむ，ちょっとトリッキーな表記だ。こういうのはあまり好きじゃないんだけどな……。ともかく，覚えておいて損は無いだろうと思う。
もう一つ挙げられているのが，「vector よりも deque を使え」という指摘だ。
ごく一般的な C++/STL の教科書では， vector を標準的なコンテナとして扱っている。これは C++ 規格の中でもそのような定義がなされているようだ。しかし， GotW の指摘によれば，メモリ効率の良さや挿入処理の早さ，オペレーションの多彩さなどを考慮した場合， deque の方が総合的に優れた結果を導き出すことができるとしている。つまり， vector よりも deque を標準的なコンテナとして用いよう，ということだ。
実際には，挿入・追加処理を除けば vector の方が高速であるため，「何にでも deque を使えば良い」という具合にはならないだろうと思う。ただ， list の代わりに deque を利用した方が良いケースが存在することは確かだ。
ここでちょっと面白かったのが，以下の記述だ。
へへ，なるほど。それで「デック」ってわけか……。
2003-05-08
なんだか知らないけれど，朝から喉が痛い。風邪をひいてしまったみたいだ。
明日は健康診断なんだけどなあ……，不健康な状態で健康診断とか受けて大丈夫なんだろうか。
余計なものが出ると困るので，風邪薬は飲まないことにする。
そんなわけで，いつもより早めに帰宅して，とっとと寝ることにした。
2003-05-09
朝になっても体調は悪いままだった。身体が重い。通勤で電車に乗ることを思うと気が滅入る。何も無かったら休んでいたと思うのだけれど，健康診断があるので出社することにした。再検査とかなると，また面倒なことになるし……。
健康診断を終えて風邪薬を飲むと，だいぶ気が楽になってきた。相変わらず頭はクラクラするけれど，もう何となく治りかけている感じだ。
GDC 2003 における Pete Isensee 氏の講演は "Custom STL Allocators" という題目だった。用途に合わせてアロケータを使い分けよう，という内容のものであり， Game Programming Gems 3 にも同名の記事を寄稿している。
http://www.tantalon.com/pete/customallocators_files/frame.ht...
http://www.tantalon.com/pete/files/customallocators.zip
この講演の中で氏は， STL のアロケータの仕様について簡単な解説を行っている。自前で実装を行うためのノウハウについても述べており，メモリを厳密に管理しようと考えている人にとっては，参考になるものがあるだろうと思う。
GPG 3 の記事では，実際に数個のアロケータを実装し，その内容を公開している。 Win32API の HeapCreate / HeapAlloc 関数を用いてメモリ確保を行う "HeapAlloc" や，スタック上に確保した配列をアロケータ化する "StackAlloc" などがその一例だ。特に StackAlloc は利用価値が高いのではないかと思う。テンポラリとして STL コンテナを利用する場合などに効果を上げられそうだ。
http://www.tantalon.com/pete/files/gems3update.zip
また，これと同時に，STL アロケータ用のテストスイートも公開されている。自作したアロケータの動作を検証する際に，これを役立てることができるかもしれない。
http://www.tantalon.com/pete/files/stlallocatortestbed.zip
このように， Isensee 氏は自作アロケータの必要性について説いているのだけれど，実際には，アロケータを自作しなければならないシチュエーションは非常に限られているように思える。大抵の場合，デフォルトアロケータ (std::allocator) が適度に最適化された実装を提供してくれるからだ。
例えば， GCC の C++ 標準ライブラリ (libstdc++) におけるデフォルトアロケータは，内部でメモリのプーリングを行うようになっている。メモリの確保は適度な量をもって一括に行われ，開放要求が来ても保持を続けることで再確保のオーバーヘッドを削減している。また，この内部プールは異なるコンテナ間でも共有されるため，非常に効率良く再利用が行われるようになっている。実際に動作を観察してみると，システムコール (new/delete) の呼ばれる回数は極力少なくなっていることが分かる。この処理は，ほとんどのケースにおいて適切な効果を上げているようだ。
http://gcc.gnu.org/onlinedocs/libstdc++/ext/howto.html#3
しかし，逆に言えば，メモリをタイトに切り詰めたい場合には，自前のアロケータが必要となるかもしれない。デフォルトアロケータでは，実際には利用されていない領域まで余計に保持しているかもしれないからだ。また，この手のプーリング処理はメモリの残存量を見え難くする性質があるため，組み込み環境などのようにメモリ容量が制限された状況においては，あまり好ましくない挙動を見せる可能性がある。
メモリをタイトに管理したい場合に役立つのが， Doug Lea 氏の malloc ルーチンだ。
http://gee.cs.oswego.edu/dl/html/malloc.html
この malloc ルーチン（通称 "dlmalloc"）は，ごく一般的な用途を想定して最適化されたものだ。これと言って特徴のあるものでも無いのだけれど，非常に素直な挙動を見せるルーチンであるため，クセのあるシステムコールを囲い込んでしまいたい場合などに役立てることができる。コンシューマゲーム機においては，メモリの管理が非常にクリティカルな問題となるため，このような「囲い込み」は意味のある行為となる。
前述のようなデフォルトアロケータの挙動も，問題になるようであれば dlmalloc で囲い込んでしまった方が良いかもしれない。ただ，速度面に多少不安な要素が残るため，後に比較検証を行いつつ方針を決定したいと考えている。
2003-05-10
メモリ管理と言えば，最近になって目を付け始めているのが， boost の Pool ライブラリだ。
http://boost.org/libs/pool/doc/index.html
この Pool ライブラリは，まとまった容量のメモリ領域を一括に確保し，それを固定長のブロックに切り分けて再分配を行うという機能を提供するものだ。細かなメモリブロックの一元管理を可能にするというメリットのほか，再分配処理が非常に高速であるという特徴がある。この辺りの仕組みについては，同ライブラリのドキュメント内の "Pool Concepts" の項に詳しく解説されている。
http://boost.org/libs/pool/doc/concepts.html
唯一の制限は，再分配の際のサイズが固定されてしまっているということだ。例えば requested_size = 128 で初期化した Pool は， 128 バイト単位でしか malloc を行うことができない。
従って， Pool ライブラリの利用は，ある決まったサイズのオブジェクトを大量に生成するようなシチュエーションに限られるだろうと思う。しかし，その特性と用途が正しく合致していれば，非常に優れたソリューションを提供してくれるはずだ。
Pool ライブラリには多種のインタフェースが用意されている。 STL 用のアロケータである "pool_allocator" などは，その一例だ。
http://boost.org/libs/pool/doc/interfaces/pool_alloc.html
この "pool_allocator" を利用すれば，任意の STL コンテナに対して Pool ライブラリのメカニズムを適用することができる。常に固定されたサイズの領域を確保する list や deque とは相性が良いだろうと思う。逆に，コンテナが増える度に領域の拡張を行う vector などでは，まったく効果を上げられないどころか，非常に効率の悪い挙動となってしまう恐れがある。
pool_allocator は，テンプレート引数に指定された型のサイズを元に singleton_pool を導出し，そこからメモリの確保を行うという仕様になっている。しかし，この仕組みには少し裏があって，例えば，
このようなコードを組んでも，実際には RequestedSize = sizeof(int) の singleton_pool が生成されることは無い。上のコードでは型として int を指定した "my_alloc" を std::list のコンストラクタへ渡しているものの，これはコンストラクタ内部で別の形式へと rebind が行われ，実際には異なったサイズの singleton_pool が生成されることになる（この場合，恐らく RequestedSize = 12 となるだろう）。
これは， STL コンテナのサイズを正しく特定するために必要な手続きではあるものの，場合によっては，勝手に任意のサイズの singleton_pool を作成されては困る場合もあるかもしれない。少し注意が必要だ。
"Pool Concepts" のページには以下のような記述が見られる。
いかにストイックなプログラマでも， C++ / STL を本格的に使い始めれば，細かなメモリブロックの乱造は避け難いものとなってしまう。また，ゲームプログラミングの場合は，これと同時に，慢性的なメモリ不足とも戦い続けなければならないという宿命がある。従って，それぞれの道具の特性を正しく把握し，要所においてそれらを使い分けることが重要な作業となるのだろうと思う。
2003-05-11
散歩中に立ち寄った駅前の本屋で， UNIX USER 誌を購入した。
http://www.unixuser.jp/magazine/2003/200306.html
なんとなく面白そうな記事が多かったのと，西田亙氏の短期連載企画「Linux から目覚めるぼくらのゲームボーイ」に興味を惹かれたからだ。
http://www.skyfree.org/jpn/unixuser/gba.html
GBA をターゲットとして， GCC を利用したクロス開発を体験してみよう，という趣旨の連載だ。第一回目の記事では， GBA 本体のアーキテクチャと「ブートケーブル」に関する簡単な説明のほか， arm-gba-elf をターゲットとしたクロス環境の構築などについて触れている。
西田氏は他に， UNIX User 誌上で「GCC プログラミング工房」という連載記事を執筆している。
http://www.skyfree.org/jpn/unixuser/index.html
「GCC プログラミング」と題されているものの，実際には Linux kernel や x86 CPU, PC-AT アーキテクチャなど，話題は多岐に渡っている。ソフトウェアの基盤を構成するこれらの要素は，今や大半のソフトウェア技術者にとってはブラックボックス的な存在となってしまっている。それらの要素に対する理解を深め，ソフトウェアの動く「メカニズム」を把握しようというのが，この連載の趣旨であるようだ。 GCC はそのために選ばれた一つのテーマでしかなく，いざとなれば何でも解説してやろうという気概が，この連載からは伝わってくる。現に， GCC 以外について解説しているページの方が圧倒的に多いし……。
普通に PC プラットフォーム上でソフトウェアを開発する分には知らなくて済む知識も，クロスプラットフォームでの組み込み環境向けの開発ともなれば，必須となってしまうことも少なくない。それらの知識を探し求める際に，このような記事の存在は，解答までの道程のショートカットとして大いに役に立つことだろうと思う。
UNIX USER 誌は毎月購入しているわけではないので，単行本化などされると嬉しいのだけれど……。どうだろう。
2003-05-12
とある perl モジュールのソースを眺めていて気が付いたことなのだけれど， perl のコードは，時折，妙な具合に文芸的な表現を含んでいるように感じられることがある。例えば， perl には次のような有名な慣用句がある。
この "or die" 記法は， perl の基礎的な文法として教科書にも登場してくるようなものだ。まだ perl を真面目に勉強している頃ならば，ただありのままにこれを受け入れることができるのだけれど，改めて見返してみると，ひどく間抜けな表記のようにも思える。「ファイルを開け − さもなくば死だ」
"die" コマンドは perl のエラー処理の一種で，引数として渡されたリストを標準エラー出力へ通しながら exit をコールする，というものだ。
http://www.perldoc.com/perl5.6/pod/func/die.html
"or" は単なる論理式の "or" であり，文全体としては，「式の値が決定されると，それ以降の要素は評価されない」という規則を利用したトリックとなっている。つまり， open が false 値を返さない限り die が呼ばれることは無い。
perl は文法に対して非常に大らかなポリシーを持っていることで有名だ。これは，同じ機能を実現するための構文が幾通りも存在することを意味している。しかし，このような「いい加減さ」が perl の嫌われる要因であることは間違い無い。プログラマ毎に異なった「クセ」を付ける隙を与えてしまっていることは，一般に非難されるべきことだと考えられているようだ。
その一方で，構文が多彩であるがゆえに，状況に合わせた自由な文の組み立てが可能であるという利点もある。もっとも，本当の実益主義者にとっては，これは利点とはなり得ないのかもしれないけれど……。
このようなことから， perl という言語は，実務主義的な側面と，文芸的な側面という，プログラミング言語としては特異な要素を兼ね備えた，実にユニークな存在であると言えるのではないかと思う。
http://munitions.vipul.net/documents/rsafin.html
もう一つ，僕の短い perl 歴の中でも印象深かった経験が，後置型の条件文の存在だ。
英文では if 以降の文節を文の後方へ配置するケースが多いことから，このような構文は「しっくりくる」ものがあるのだろうと思う。実際， if 以降に記述する条件が限定的なものである場合，これを後ろに配置することは見た目の上での利点があるように思える。条件式があくまでも副次的なものであり，関数のコールが主目的であることを強調できるからだ。
これらの構文は C / C++ でも，いくらか真似をすることができる。例えば，関数 foobar の返値が 0 であることを確認する assert 文を書くとしよう。
このコードには大小の問題が含まれている。まず大きな問題は，リリースバージョンにおいて assert を空マクロとして定義すると，関数 foobar が呼ばれなくなってしまうという問題だ。そしてもう一方の小さな問題は，文全体を "assert()" が支配しているために，この文が関数 foobar を呼ぶものであるという意味合いが，若干薄れてしまっているように感じられることだ。
例えば，これを次のように書いてみるのはどうだろうか。
これならば foobar を呼んでいることは明確になるし， die() を "0" と置き換えても問題無く評価されるようになるし……いや，これ以上頑張っても，逆に変態扱いされるだけだからやめておこう……。
2003-05-13
今日は E3 隊の出発日だった。会場は東海岸のロサンゼルスコンベンションセンター。移動に飛行機で９時間も掛かるという話だ。移動するだけでも大変なこったなあ……。
主要メンバーがごっそりと E3 へ行ってしまったので，仕事の勝手がいつもと違う感じになっている。しかし，そんな間にも片付けておくべき宿題がいくつか残されている。順次手を付けていかなければ。
昼過ぎにもなると， E3 関連の情報が徐々に入り始めてきた。昨日，マイクロソフトのカンファレンスが行われたようで， Xbox 関連のニュースが怒涛の如く舞い込んでくる。
その中でも，やはり最大の目玉は "Halo 2" だ。
http://www2u.biglobe.ne.jp/~nanko/e32003/03-halo2.html
相変わらず恰好いいデモをぶつけてくるなあ……。敵味方入り乱れる戦場へと突入するマスターチーフ。圧倒的に不利な状況にも恐れずに立ち向かう姿は，単純な構図だけれど至極恰好いい。彼の寡黙なキャラクタと，顔を常に覆い隠しているヘルメットは，プレイヤーの感情移入を高めるための演出であるらしいのだけれど，その一方で，背後に確立された自己の存在を感じ取ることができる。渋くてストイックな軍人的ヒーロー像だ。
アメリカの制作集団は，徐々に戦争ゲームを作り出すことに小慣れてきているような印象がある。 "Medal of Honor", "Battlefield 1942", "Operation Flashpoint" 等々……，単なるガンシューターの存在を超えて，戦争を一つのテーマとして捉えたゲーム作りが始められている。今回の "Halo 2" のデモは，そんなトレンドの匂いを強く感じる。
そう言えば，カーネギーメロン大学にて行われた Halo 2 プレゼンの内容が "unlimited lives" というサイトで公開されている。
http://www.unlimitedlives.com/special_reports/ul_spec_halo2-...
これは，同大学内にある "MSImpact" と呼ばれるマイクロソフト関連組織（詳細はよく分からない）の主催で行われたもののようだ。
このプレゼンテーションでは， Bungie Studios の Adrian Perez 氏が，初代 Halo における失敗の回顧と， Halo 2 に向けての挑戦の解説を行っている。その， Halo 2 における挑戦の中でも比較的大きな比重を占めているのが，法線マッピングを利用した局所照明エフェクトと，フォトンマッピングを利用した大域照明エフェクトの技術だ。
これらの要素のうち，法線マッピングについては，画面写真を見ればすぐに伝わってくる要素なのだけれど，フォトンマッピングについては，その効果が非常に分かり難いところがある。 Halo のように，極端な屋外や，薄暗い屋内などが舞台である場合，大域照明の効果はなかなか出難いように思える。しかも，全般的にギラギラとグロスの強いビジュアルイメージで統一されているものだから，大域照明の生み出す柔らかな照り返しなどは，まったくかき消されてしまうのではないかと思う。
例えば "ICO" のように，淡色系の壁面と複雑な建造物，それに強烈な太陽光などが加わると，間接照明の影響が強くなるために，大域照明の効果が非常に現れやすいシチュエーションとなる。逆の例では， Id Software が過去に大域照明を採用しながらも，それを敢えて捨てたという話がある。同社は Quake II においてラジオシティ法を採用したものの，結局，ぼんやりとした効果と長い計算時間しか得られなかったために， Quake III では単純なシャドウ処理に戻したという顛末だ。
いずれにしろ，あの Halo のギラギラしたイメージと大域照明の効果はミスマッチであるように思えてならない。個人的に大域照明を推していながらも，応用に対しては楽観できない理由が，この辺りに存在している。
2003-05-14
STL の創始者こと Alex Stepanov 氏のインタビュー記事をもう一度読み返してみた。
http://www.antiquark.com/escape/public_html/stepanovusa.html
それにしても，この人，よく読んでみると，かなり過激な発言をしていることが分かる。
氏のインタビューを読んでいて強く感じるのは，氏の持つ数学的なバックグラウンドが， STL の設計思想に対して絶大な影響を与えているという印象だ。
氏は件のインタビューの中で，ジェネリックプログラミングのアナロジーとして数学の概念を引き合いに出している。数学の世界では，様々な種類の定理 (theory) が，同じ公理 (axiom) を出発点として導き出されている。
数学とその応用の世界に存在する様々なモデルは，その多くが，ある部分で公理を共有している。これは，異なったモデルであっても同じような概念が適用できることを意味している。例えば，情報代数の導入によってデータ群を線形代数のように扱うことが可能となることや，関数解析によって関数を空間的に扱うことが可能となること，ラプラス変換を使えば微分方程式を代数演算によって解くことが可能となること，伝達関数から線形システム回路の解析と設計が可能となること……等々。 Stepanov 氏は，これこそが「抽象化」の概念であると主張している。
氏の挙げた例で言えば，「結合則が公理として成立すれば（つまり半群であれば）並列化が可能となる」という関係が存在する。これは，結合則によって以下のような入れ換えが可能であることを意味している。
この「アルゴリズム」に必要な条件は，ニ項演算 f が結合則を持つという事実だけだ。これと同じように，現実世界の様々なアルゴリズムには，共通して適用することのできる原則が存在するはずだと氏は指摘する。それを上手く見つけ出し，抽象概念として定義することができれば，非常に応用範囲の広いモジュールを設計することが可能となる。
STL では，例えばイテレータの存在が，この「公理」の部分に相当する。
http://www.sgi.com/tech/stl/Iterators.html
STL において，イテレータとは，ポインタの一般化された概念として表すことができる。イテレータには，単なる参照を意味する "Trivial Iterator" や，前進 (operator ++) を持つ "Forward Iterator"，後退 (operator --) を併せ持つ "Bidirectional Iterator"， 任意な移動が可能である "Random Access Iterator" 等が定義されている。これらの定義は，ジェネリックな領域における要求仕様として「コンセプト」と呼ばれている。この「コンセプト」こそが，数学での「公理」に相当する概念として存在するわけだ。
STL において二分探索を行うアルゴリズム "binary_search" は，コンセプトとして Forward Iterator と Strict Weak Ordering を要求する。 "Strict Weak Ordering" は「厳密弱順序」に基づいた比較演算を意味しており，これも STL のコンセプトの一種として定義されている。アルゴリズム "binary_search" は，これらのコンセプトに基づいて設計が行われており，コンセプトさえ正しく備えられていれば，その実態について何も問われることは無い。それが単なる int* であろうが，線形リストノードへの参照であろうが，一向に問題無く実装が導出されるということだ。
2003-05-15
では，我々はどのようにして，ジェネリックプログラミングの概念を役立てることが出来るのだろうか。僕が個人的に，ゲームプログラマにとって最も分かりやすい例ではないかと考えているのが， A* アルゴリズムの実装についての話だ。
http://www.policyalmanac.org/games/aStarTutorial.htm
http://www.gamasutra.com/features/20010314/pinter_01.htm
A* アルゴリズムは，ゲームプログラミングにおいて，一般に経路探索 (pathfinding) の手法として知られている。敵キャラクタが障害物を避けてプレイヤーへ近寄るには，どのような経路を選択したら良いのだろうか，とか，戦略ゲームのユニットが指定地点まで最短コストで移動するには……とか，そのようなものを決定する手法である。
しかし， A* は本来，経路探索だけのために存在するアルゴリズムではない。 A* は一般に，探索木（ゲーム木）に対する探索処理の最適化されたアルゴリズムとして用いることができる。
http://www.na.cse.nagoya-u.ac.jp/~reiji/lect/alg99/sec9-4.ht...
単純なバックトラック法に対し優先度評価 (heuristic estimation) を与えることによって，探索の最適化を行うというものだ。
従って， A* の応用範囲は単なる経路探索にとどまらない。チェスの思考ルーチンに適用することもできるし，戦略ゲームの CPU アルゴリズムとして利用することもできる。パズル問題の解法としても使えるし，もしかしたらデータ構造の最適化に応用することも可能かもしれない。
http://www.gamasutra.com/features/20000626/brockington_01.ht...
A* の実装に必要となる要素は，問題の「状態」を表すデータ構造と，状態の「評価」を行う手段の存在だ。状態の評価を行う方法は２種類必要で，１つは，現状の評価を行う関数 G ，もう１つは，現状から到達し得る最良の評価値を求める関数 H だ。
ここで，「状態」を表すデータ構造 State は，現状から移行し得るすべての状態を列挙するメソッド enum_trans と，同一演算子 "==" を持つものとする。ファンクタ GFunc と HFunc はそれぞれ関数 G, H に相当し， State::Value 型の値を返すものとする。
以上をコンセプトとして置いた場合，関数 a_star は，次のように書き出すことができるかもしれない。
この関数のユーザは，前述のコンセプトを満たすデータ構造として State と GFunc, HFunc をそれぞれ用意してやれば，その実態については何も問われずに，関数 a_star の適用を行うことができる。例えそれが，経路選択を行うためのセットであっても，戦略思考を行うためのセットであっても，何でも良いということだ。
これをオブジェクト指向的に解決するとなると，ライブラリ側に用意された抽象クラス AbstractState を継承して State を定義しなくてはならなかったり，各種評価関数や enum_trans を仮想関数として実装しなければならなかったり……という風に，様々な制約が付加されることになるだろうと思う。
ここで重要なのは，ジェネリックプログラミングによる実装が，データ構造をアルゴリズムから完全に引き剥がすことに成功しているということだ。これは，アルゴリズムのインタフェースが，真に抽象的な領域において定義されていることを意味している。オブジェクト指向では，その「オブジェクト指向性」ゆえに，アルゴリズムとデータ構造が同一の領域に混在してしまっていた。それ故に，抽象化を行うには仮想関数や多重継承の概念を導入する必要があったのだけれど，それも実のところ，付け焼き刃的な進化でしか無かったと言うことが出来るのかもしれない。
2003-05-16
Stepanov 氏のインタビューを読み直して，改めて感じるのは， C++ ジェネリックプログラミングと関数型プログラミングとの間に存在するスタイルの類似だ。 C++ 方式のジェネリクスでは，関数のファンクタ化とテンプレートを用いることによって，「関数をファーストクラスとして扱うことが出来ない」という C++ の弱点を補い，関数型プログラミング的なセマンティクスの導入を可能としている。また， STL や Boost に含まれる関数アダプタの機構は，関数型プログラミングにおける「高階関数」（あるいは「超関数」……つまり，関数を操作する関数のことを指す）の概念を連想させるものだ。
http://www.sato.kuis.kyoto-u.ac.jp/~igarashi/class/isle4/mlt...
事実， Stepanov 氏は過去に，関数型プログラミング言語を含む複数の言語において，ジェネリックなライブラリを作成した経歴があるようだ。 SGI の STL ページにある次のインタビュー記事には， C++ STL が設計されるに至るまでの長い道程が，実に詳細な形で語られている。
http://www.sgi.com/tech/stl/drdobbs-interview.html
結局，関数型プログラミングに偏重したスタイルは失敗に終わったものの，そこでの経験が後の設計方針に影響を及ぼしているという事実は興味深い。それに，僕は今まで関数型プログラミングに接した経験がほとんど無い。もし，関数型プログラミングの手法が「コンポーネント空間」を構成する１つの軸だと考えるならば，これを欠かしていることは，表現の幅を大きく失っていることに他ならない。
ちなみに，「コンポーネント空間」とは，氏が STL の設計概念について述べる際に，よく用いられる表現の１つだ。
http://www.byte.com/art/9510/sec12/art3.htm
everything2.com の解説によれば，「関数型プログラミング」とは，「コマンドの実行」よりも「関数の評価」に重きを置くスタイルのことである，と定義されている。
http://everything2.com/index.pl?node=Functional%20programmin...
単に関数がファーストクラスだからと言って，その言語が関数型か，と判断してはならないようだ。実際に関数型言語の例を見てみると，これが実に数学的な思考のもとに作られたものであることがわかる。関数の再帰的な定義によってロジックが組み上げられていく様は，まるで数学の教科書を覗いているかのような雰囲気であり，手続き型言語には決して見られない論理的な堅さが感じられる。
http://a414s1.it.nanzan-u.ac.jp/smlbook/smlwww/index.html
http://a414s1.it.nanzan-u.ac.jp/smlbook/smlbook.pdf
もう少し具体的な定義を行うならば，関数型プログラミングとは，ラムダ計算 (lambda calculus) をベースとして構築された言語として見ることができるかもしれない。
http://members.tripod.co.jp/nbz/ref/lambda.html
ここから先は，もうちょっと数学的な知識が無いと踏み込めなさそうだ……。ともかく，今までまったく注意を払っていなかった関数型プログラミングというものに対して，もう少し興味を持ってみようと思っている。
2003-05-17
これらの Stepanov 氏の言説によって明らかにされているのは， STL 及びジェネリックプログラミングの手法が，これまでのプログラミング体系を複数内包した，いわゆる「マルチパラダイム」的な存在であるということだ。これは， Stroustrup 氏の行った C++ の設計思想から影響を受けたものであり，またこれとは逆に， STL 自身が C++ の設計に対して影響を与えた部分（例えば部分特殊化 - "partial specialization" の機能など）も存在することが，文献の中で述べられている。
C++ / STL におけるマルチパラダイムとは，一体どのようにして導き出された結論なのだろうか。一見して，マルチパラダイムは安直で危険な思想のように思える。複数の体系を内包することによって，その基礎原理を曖昧なものとしてしまうように感じられるからだ。しかし，氏の持つ優れた学術的見識と，多くのプログラミング言語から得られた豊富なバックグラウンドは，その困難な仕事の実現を可能としたようだ。
単一的に凝り固まった解を安易に提示するのではなく，様々な見地から最適と呼べるソリューションを導き出す手腕は，氏のように豊富な経験を持つ人物でなければ持ち得なかったであろうと思う。そしてそれこそが，それまでの議論に欠けていた要素なのだろうと思う。
なんだか引用ばかりになってしまったけれど，つまり， Stepanov 氏の言説の中に，それだけ重要な要素が含まれているということだ。 STL や C++ を一通り修めた後にこれらの文献に目を通せば，その奥に潜む深い思想を垣間見ることができるだろうと思う。そして，今までよりもほんの少し C++ が許せるようになっているはずだ。
最後に， STL を構成する重要な概念である「複雑性」 (complexity) と「コンセプト」 (concept) について触れた言葉を引用して締めくくりたいと思う。
おまけ……
2003-05-18
普通の休日。散歩してみたり，本屋で立ち読みしてみたり。
ここ数日に渡って，関数型プログラミングについて調べる機会が何度かあった。これも何かの縁だから，ひとつ関数型言語でも触ってみようかと思い，試しに Haskell を遊んでみることにした。
数ある関数型言語の中から Haskell を選んだのは，これが現状で最も「ピュア」な関数型言語であるとの指摘が各所でなされていたからだ。どうせ本気で利用する気は無いんだし，試すだけなら極端なものを試してみるのが良いだろうと思う。
処理系は "Hugs" を使うことにした。 Haskell 処理系の中では最も有名なもののようだ。
ソースのアーカイブを入手し，インストラクションに従ってビルドを行う。 Linux や Cygwin なら問題無くビルドできるはずだ。
haskell.org のリンクから適当なチュートリアルを入手して，一から手習いを始めてみている。しかし，こりゃあすごいもんだなあ……。ちっとも要領が得られないのだ。
http://www.di.uminho.pt/afp98/PAPERS/Tutorial.ps
ftp://ftp.geoinfo.tuwien.ac.at/navratil/HaskellTutorial.pdf
僕は今まで，何らかのプログラミング言語を一通り習得した人であれば，二つ目以降の言語は比較的速やかに習得できるものと考えていた。しかし，その法則は今回の経験によって完全に覆されることになりそうだ。自分のプログラミングに対する思考パターンと設計能力が，いわゆる手続き型言語のそれへと完全に限定されてしまっていたことを認識するに至った。
散歩中に立ち寄った本屋で，思わず衝動買いをしてしまった。 John Barrow の「天空のパイ」だ。
http://www.msz.co.jp/titles/7018.html
とても恥ずかしいことなのだけれど， Stepanov 氏の記事を読んでいる間に，自分の数学的見識の無さに対して愛想が尽きてしまった。何か数学関連の本を読んで，少しでも知識を補いたい……。そんなことを考えながら書店を徘徊していると，いつの間にかこの本を手に取っていた。数学の本を探していたはずなのに，何故か縦書きの本を買ってしまっている所が，まったくもって駄目だと思う。専門書を買うつもりでブルーバックスを買ってしまっているような勘違い具合だ。
そして，なぜかそのまま勢いに乗ってしまい，ついでに "Exceptional C++" も買う羽目になってしまった。ああ，もう何がなんだか……。
http://www.pearsoned.co.jp/washo/prog/wa_pro34-j.html
こんな一度に本を購入して読み切れるはずがない。また積読が増えてしまう……。そう言えば，まだ「コモンズ」も読み終わってないんだよね。うう，駄目かも……。
2003-05-19
E3 の遠征隊が帰国した。お仕事ご苦労様。お土産たくさん，嬉しいな……。
とりあえず真っ先に手を付けてみたのが "Jak II" の体験版だった。
http://www.gamespot.com/ps2/action/jak2/index.html
US リージョン用なので普通の PS2 では動かない。職場の開発機を使って動かしてみることにした。
前作は徒手空拳が主体のジャンプアクションであったのに対して，近作は銃火器系を備えた撃ちまくりアクションへと変質を遂げているようだ。銃を撃ちまくる行為には単純な面白さがある。 "Jak" も結局はそこに落ち着いてしまうのか，という，少し残念な気持ちはあるものの，滑らかな操作性のジャンプアクションとシューティングという組み合わせは，意外と相性の良いもののように感じられた。
少し気になったのは，昔の全方位スクロールシューティングにおけるジレンマというか，「敵に狙いを定めるには，敵に対して突っ込まなくてはならない」ということから「一度距離を詰められてしまうと反撃が不可能となる」という死にパターンが発生してしまっているように感じられたことだ。前作よりもステージの一方向性が希薄になっていることが，敵に背後を取られる危険性を高め，死にパターンを発生させる状況を増長してしまっているように思える。もっとも，そういう場合は近接攻撃を使えばいいんだろうけど，一旦トリガーに指をかけてしまうと，こう，なかなか……ね。
ボスコニアンばりにケツから弾吐くってわけにも行かないだろうしなあ……。今のままでも，アクションゲームとしての面白さは十分に伝わってくる状態ではあるのだけれども，果たして最終的にはどのような形へまとめてくるんだろうかと，やや不安を抱えながら楽しみにしている状況だ。
Halo2 や MGS3 など，色々と見所の豊富な E3 だったのだけれど，最後に登場した "Half-Life 2" のムービーには，正直なところ，度肝を抜かされてしまった。これは凄い……。
http://38.118.133.70/gt_vault/t_halflife2_e3_2k3_gameplay.wm...
プライベートカンファレンスだか何だかの映像が流出したもののようだ。前半部分に見られる，いかにも技術デモ的な部分は敢えて無視するとして（ここのシステムだけとって見ても，かなり強力なものではあるんだけれど），中盤以降……特に後半の，実際のゲームプレイを映し出したと思われる部分に深い感銘を受けた。これは恐らく開発中の映像であろうから，少し勘違いをしている可能性もあるんだけれど，そこは敢えて受け取ったままの印象を元にしてみようと思う。
このゲームにおいて驚くべきことは，カットシーンとしての演出がまったく存在しないことだ。すべての演出がゲーム内の出来事として完結している。ダイナミックな環境の扱いを可能とする Half-Life 2 エンジンの強力な機能性は，デザイナの望むすべての事象を，ゲーム内の空間において実現することを可能としている。 NPC 達は優れた AI 処理によって自然な行動様式を持ち（ここは Half-Life シリーズの伝統だ），ゲーム空間を構成するもう１人のアバターとしてそこに存在する。彼等（とプレイヤー）は自由にゲーム内の環境に触れ，それを動かし，利用し，破壊する。従来はカットシーン……つまり，ゲーム進行における「特異点」として演出しなければならなかったものを，すべて実際のゲームプレイとして体験することが可能となっている。
戦火に荒らされた東ヨーロッパを連想させる街並みの奥の方から，突如として轟音が聞こえてくる。「スパイダーだ！」 叫びながら逃げてくる数人の男と，巻き上がる砂埃。そして，その奥から現れる巨大モンスターの影。必死に応戦する人間達と，それを支援するプレイヤー。圧倒的な火力を誇る化け物の攻撃に街は蹂躙され，人々は一撃のもとに串刺しにされていく。一人称視点から見上げるスパイダーの存在は強い威圧感を感じさせるものであり，本物の恐怖を連想させる。 Half-Life 2 では，これらをすべてゲームプレイの一部として体験することが可能なのだ。
外見せ用のムービーということで，少し「出来過ぎている」感は否めない。しかし，ここは敢えて，このゲームを信用してみようと思っている。本当にこのゲームを楽しむことができたとしたら，この臨場感を味わうことができたとしたら，それはとても素晴らしいものであるはずだ。
2003-05-20
普通にお仕事の一日。ううむ，そろそろコンパイラの新しいバージョンが欲しいなあ……。
以前，メモリ管理関連の話題で Boost Pool Library に注目したことがある。
http://boost.org/libs/pool/doc/
これが，実際に利用してみると，色々と細かな問題を抱えているライブラリであることが分かってきた。
まず問題となるのが，実に些細なバグが残された状態で放置されているということだ。
http://lists.boost.org/MailArchives/boost/msg37427.php
もしかしたら既に修正されているかもしれないと思い，リポジトリ内の最新バージョンを参照してみたのだけれど，そのような気配はまるで感じられなかった。多くのファイルが半年以上放置されている状態だ。ううむ，自前で修正するのは簡単なことだけれど，訳の分からぬまま手を加えてしまうのも何だか腑に落ちない。このバグは現在どういう扱いになっていて，将来的にどう処理される予定なのだろうか。その辺りの事情が分かっていれば，迷うことも無いのだろうけど……。
詳しく調査を進めていくと，他にも色々とクセを抱えたライブラリであることが分かってきた。アイデア自体は決して悪くないのだけれど，細かい所をつつきだすと，さすがにボロが出てしまうようだ。特に singleton_pool を使ってしまうと，メモリの明示的な開放がほぼ不可能となってしまう点が，歯痒く感じられる。 pool_allocator も内部で singleton を呼んでいるので，迂闊に利用することができない。ううむ……。
結論を言えば，このライブラリをそのまま利用するのではなく，修正や多少のカスタマイズを適用した上で利用するのが良さそうだ。 pool クラス自体は前述のバグを修正するだけでほぼ問題無く利用できるようになるから，あとは細かい不満点をちくちくと修正するだけだ。少し面倒に感じられるかもしれないけれど，すべてを自作するのと比べれば，随分楽な作業量で済ますことができるだろうと思う。
正味な話， Boost は全般的に，細かい所で気になる点が多い。提供される機能に対して払うコストが明らかに見合っていないモジュールや，今回のケースのように，中途半端な状態で枯れてしまっているモジュールなど，少なからず存在する。それにも関わらずモジュールは増える一方であり，かなり混沌とした雰囲気を呈してしまっている。
構文パーサの "Spirit" や，線形代数ライブラリの "uBlas" など，元は独立したライブラリとして開発されていたものだと記憶しているのだけれど，これが一体どのような経緯で Boost に統合されることになったのか，僕にはまったく見当も付かない。
http://boost.org/libs/spirit/index.html
http://boost.org/libs/numeric/ublas/doc/index.htm
ともかく， Boost を STL 並に「枯れたライブラリ」だと受け取ってしまうのは危険な考えだ。各モジュールの複雑度や安定性を見極めた上で，利用するか否かの取捨選択を行うのが良いだろうと思う。
2003-05-21
雑用サーバの HDD がクラッシュしたので，換装作業を行うことにした。ううむ，なんだか知らないけれど，このビルに来てからというもの，マシンのクラッシュ率が高くなっているような気がするんだよな……。
インストール作業の間，自分のマシンが手すきになるので，その間に 4gamer.net に掲載されていた Half-Life 2 の高画質版ムービーをダウンロードしておくことにした。
http://www.4gamer.net:880/HALF-LIFE2.lzh
さすがに 260MB も食っているだけあって，こちらの方が画質が数段良いようだ。
うむむ……，これ，「ストライダー！」って言ってるよね。スパイダーじゃねえっつうの……。
http://www.gamers.com/game/273625
ええと，まあ，こんな調子なんで，字幕の無い洋ゲーは非常に辛い。字幕が付いていれば，少なくとも要点ぐらい掴むことができるのだけれど，字幕無しでミッション内容とか告げられた日にゃ，どうにも途方に暮れてしまう。うう……。
以前， shinichiro さんが gcc-pch 関連の話題を挙げた際に， ccache というツールの存在について軽く触れていた。これがなかなか面白そうなツールなので，少し試してみることにした。
ccahce は Samba プロジェクトの副産物として生み出されたツールだ。同プロジェクトのビルドファームにおいて定期的に実行されているリビルド処理を効率化するために編み出されたものであるらしい。
ccache は，その名前が表しているように， C ソースのコンパイル処理に対してキャッシュを設けるというものだ。このツールは gcc のフロントエンドとして機能し，入力に用いられたソースファイルと，そこから出力されたオブジェクトファイルの対応を記録し，キャッシュへ格納するようになっている。そして，過去にコンパイルしたことのあるソースが入力されると，実際にはコンパイルを行わずに，キャッシュ内に格納されたオブジェクトファイルを取り出してくる。こうすることにより，コンパイル時間の大幅な削減が実現できるというわけだ。
「過去にコンパイルしたことのあるソース」という判定を正確に行うために，少しトリッキーな手順が用いられている。単純にソースのみで判定を行ってしまうと，インクルードファイルの依存関係の解決が難しくなってしまうため，実際にはプリプロセス済みファイル (.i) が判定対象として用いられる。また，コンパイルオプションによっても生成結果は変化するため，これも判定基準として加味しなければならない。それらをすべて含めた上で， MD4 アルゴリズムを用いたハッシュインデクスを取得し，それをキーとしてキャッシュ処理を行う……という手順になっているようだ。
結局のところ，ソースが変化してしまえば再コンパイルとなってしまうのは同じことなので，個人環境においてはなかなか効果が得られ難いかもしれない。しかし，複数のユーザが共同で作業を行う場合においては，かなりの効果を上げられる可能性がある。キャッシュを他人と共有すれば，他人がコンパイルした結果をそのまま流用することが可能となるからだ。
例えば，リポジトリから取り出してきた最新状態のソーススイートなどは，それをコミットしたユーザが既にコンパイルを済ませているという見込みがある（というか，そうあって然るべきだ）。そのような場合に ccache を利用していると，二人目以降のユーザは一度もコンパイルを行うことなくビルドを完了させることができる。通常ならば数分間も待たされるはずのフルビルド作業が，瞬く間に終わってしまうのは非常に爽快だ。マシンリソースを有効活用するという点から見ても大きなメリットがあるだろうと思う。
Samba には，もう１つ注目すべき副産物がある。分散コンパイル支援ツール "distcc" だ。
distcc は ccache によく似たアイデアを持つツールだ。このツールは，親マシンにおいてプリプロセス処理までを行い，その結果として得られた中間生成ファイルを子マシンに分配する。実際のコンパイル処理は子マシンにおいて行われ，その結果として得られたオブジェクトファイルは親マシンへと戻される。このように，かなり簡単な原理で動いているツールなのだけれど，それが結構ソツ無く作られており，手軽に強力な分散コンパイル環境を構築することが可能となっている。
distcc の良さは，プリプロセス処理までを親マシンで行うことにある。プリプロセスの段階でインクルードファイルの処理は完了しているため，子マシン側にソースやライブラリの類を入れておく必要はまったく無い。ただコンパイラのみが辛うじて動けばそれで良いという，非常に緩い条件のもとで分散コンパイルを実現することができるわけだ。
実際に分散コンパイル環境を構築したことのある人なら分かると思うのだけれど，この条件の緩さは大変に有り難いものだ。リモートシェル等を使ってアドホックな分散環境を構築する場合，子マシン側にも完全な開発環境を用意しておく必要があった。コンパイラや各種ライブラリをインストールして，アカウントをメンバー分作成して，作業ディレクトリをネットワーク共有して，リモート制御に必要な設定を行って……等々，とにかく管理面での煩わしさが最大の難点であったと思う。
distcc を使えば，これらの問題に頭を悩ますこと無く，即興に分散コンパイル環境を構築することが可能となる。これは飛躍的な進化だ。少なくとも僕にはそう感じられる。
注意深くクロス環境を用意すれば， Linux ホストと Windows ホストを連携させることも可能であるはずだ。どこかに余ったマシンが放置されているならば，電気代と相談しつつ，再利用を試みるのも面白いかもしれない。
2003-05-22
最近， PC 上でベクトルの演算を行うコードを書く際に SSE を利用する試みを始めている。
http://homepage1.nifty.com/herumi/adv/adv50.html
一応， GCC は SSE をいくつかの形式でサポートしている。最も単純なのはインラインアセンブラを使って記述する方法であり，他にはビルトイン関数を利用する方法や，内蔵関数 (intrinsic function) を利用する方法などが用意されている。
http://gcc.gnu.org/onlinedocs/gcc/X86-Built-in-Functions.htm...
最もコンパイラとの親和性が高いのは内蔵関数を利用する方法だ。内蔵関数は xmmintrin.h 内に定義されており，これをインクルードすることでソース内での利用が可能となる。
http://savannah.gnu.org/cgi-bin/viewcvs/gcc/gcc/gcc/config/i...
具体的な利用例は以下のようになる。
"__m128" は 128 bit 長の変数型であり，これが SSE の xmm レジスタに対応するものとイメージすれば良いと思う。あとは，まあ，見た目通りの機能を持つ関数群だ。
本来ならばこれで第一歩目を踏み出すことができるはずなのだけれど，残念ながらこのサンプルコードは正常に動いてくれない。恐らく未定義命令を発行して停止してしまうことだろうと思う。もしまぐれで動いたとしても，もっと複雑な応用を繰り返すうちに同じ現象へと突き当たってしまうはずだ。
とりあえず，これを次のように書き換えてから，最適化を有効にしてコンパイルし直すと，辛うじて動かすことが可能となる。
前者の例がコケてしまった理由は， SSE の各命令が 16 byte 境界整合を要求することと関連している。 SSE 命令は，非整合アクセス命令である loadups と storeups を除き，すべての命令がメモリ参照のターゲットアドレスとして 16 の倍数を要求する。 RISC プロセッサのようなものだと考えればいいかもしれない。
GCC において変数の境界整合をとるには "aligned" 属性を用いるのがセオリーだ。しかし， GCC における aligned 属性の指定は，確実にそれが適用されるという保証が無く，最終的な結果はターゲットにおけるコンパイラとリンカの仕様に依存するものと定義されている。
http://gcc.gnu.org/onlinedocs/gcc/Variable-Attributes.html
つまり，実際にはコンパイラに与える「ヒント」程度の意味合いしか含まれていないわけだ。現に i386 ターゲットの GCC においては，データ領域については要求通りの整合配置が行われるものの，スタックに関しては 4 byte までの整合しかとられないという仕様になってしまっているらしい。
http://gcc.gnu.org/bugzilla/show_bug.cgi?id=3299
また，この仕様に加えて，メイン関数のスタックが確実に非整合となる現象も報告されている。
http://gcc.gnu.org/ml/gcc/2002-07/msg00453.html
以上の関連する事実から，前者のコードでは，各変数の境界整合がとられていないことがクラッシュの原因となっていることが推測できる。これに対して後者のコードでは，各変数をデータ領域へと格納し， SSE 操作をメインとは別の関数で行うようにしたため，諸問題の解決が可能となっている。ただこのコードも，最適化を無効にすると落ちてしまう。内蔵関数がインライン展開されない限り，引数渡しの部分でスタックが用いられてしまうためだ。
……と，ここまで見れば明らかなように，内蔵関数を用いる方法が上手くいく見込みはまったく無い。また，この問題は長らく放置されている状態であり，近い将来に修正される見込みもほとんど無いように感じられる。 xmmintrin.h なんていう大層なヘッダファイルが用意されているわりには，それがほとんど無価値なものとなってしまっているのは，一体どういう状況なんだろうかと不思議に思う。
ビルトイン命令を用いる方法も，やはり同様に上手くいかない。ビルトイン命令は値渡しのインタフェースとして __mm128 相当のものを利用するから，結局同じ問題でつまづいてしまうわけだ。
では， GCC において SSE を利用することができないのかというと，必ずしもそうとは言い切れない。まだラストリゾートとしてのインラインアセンブラが残されているからだ。それも相当に注意深く用いなければならないのだけれど，やってやれないことは無いレベルのものだ。
今後はその辺りの問題について，もう少し探ってみたいと思う。
2003-05-23
残念ながら現状では， GCC に備わっている各種の SSE 拡張機能が，ほとんど当てにならないものであることが分っている。残された手段は，インラインアセンブラを用いてこれを直に実装する方法だけだ。
ところで， GCC のインラインアセンブラは，他のコンパイラの持つそれと比較すると，幾分複雑な構造であるように見える。
http://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html
おそらく移植性を高める上でこのような工夫が必要となったのだろうと思う。基本的に GCC はインラインアセンブリ文の内容を解釈することができないので，値の受け渡しや各操作における副作用等を，ユーザが明示的に指定してやる必要があるということだ。
まず，値を格納するためのクラスを適当に設計する。 x86 GCC における境界整合が信用ならないことは既に分かっているので，もはや小細工を用意する必要は無い。安直に "float[4]" を使ってしまって構わないだろうと思う。
例として，このクラスに対応する加算操作 (operator +) を実装してみる。引数は非整合 (unaligned) の状態で渡されることが予想されるから， movups 命令で確実にロードを行ってから加算を行い，再び movups 命令で結果を格納する必要がある。
ここでは，できるだけ GCC の作法に忠実な記述を行ってみた。例えば，レジスタ名を直接に用いるのではなく，プレースホルダとしての変数を介して参照している。また，処理を一連のアセンブリ文として書くのではなく，１命令毎に分割して記述するようにしている。このような記述を行うことによってコンパイラとの親和性を高め，最適化の可能性を広げることが可能となる。特にインライン展開されることを前提とした関数では，このような配慮が一定の効果を上げることがある。
上のコードは，以前に述べたような理由から x と y が境界整合されないと分かっているにも関わらず，一応正常に動かすことができる。変数 x, y はレジスタの形でしか参照していないため，コンパイラが余計なコードを差し挟まない限り，非整合アクセスでクラッシュすることも無いはずだ。
ただし，最適化の設定を無効にすると，コンパイラはこれを律儀にスタックに格納しようとするため，不正な非整合アクセスが発生してしまう。そもそも，境界整合が保証されないことが分かっているなら movups を使うようにすればいいと思うのだけれど，何故か GCC は movaps を使いたがるんだよな。むむむ……。
また，たとえ最適化がかけられているとしても，何らかの要因によって xmm レジスタのスタック退避が行われる可能性は十分に存在する。やはり，現段階で本当に安全なコードを実現するには，一連のアセンブリ文として記述してしまうしか方法は無いようだ。
ここまで直截的な記述を行えば，コンパイラの余計な介入を差し挟むこと無く処理を行うことが可能となる。正直なところ，本来ならば movaps と addps の２ステップで済ますことのできるはずの処理が，ここまで回りくどい記述になってしまうとは思いもよらなかった。非常に歯痒いことだけれど，この辺りが現時点における GCC の限界だと把握しておくのが妥当だろうと思う。
2003-05-24
こうして行った SSE 化が，どの程度パフォーマンスにインパクトを与えるものなのか，検証してみることにした。
まずは単純なショートループで計測を行ってみる。
長い配列に対して加算を繰り返すだけのサンプルだ。これを条件を変えてコンパイルし，得られた結果を比較してみる。
ここで， "FPU math" は通常の手順で生成されたバージョンを指し， "SSE math" はコンパイルオプションに "-mfpmath=sse" を指定して生成されたバージョンを指している。 "fpmath" オプションは浮動小数点演算に使用するプロセッサを指定するオプションであり，これを "sse" に設定すると，通常なら FPU 命令が利用される処理に対して SSE 命令が適用されるようになる。
http://gcc.gnu.org/onlinedocs/gcc/i386-and-x86-64-Options.ht...
最後の "SSE" は，今回作成した SSE によるベクトル演算を行うバージョンを指している。
ちなみに，今回のテストは Pentium III 866 MHz を搭載した Windows 2000 マシン上で行った。コンパイル時の最適化オプションは "-O2 -mcpu=pentium3" だ。 Pentium 4 等で同様のテストを行った場合，これとは異なった結果が得られる可能性は十分にあるだろうと思う。
得られた結果を比較してみると， SSE バージョンはオリジナルと比較して２倍近くのパフォーマンスが得られていることが分かる。非整合アクセスによってかなりのペナルティが課せられるものと予想していたのだけれど，実際にはそれほどの影響も無かったようだ。全力で SSE 化を行って２・３倍程度のパフォーマンス改善が目安とのことだから，これはかなり妥当な結果だろうと思う。
http://www.gamasutra.com/features/20000131/barad_pfv.htm
少し意外に感じられたのが， SSE math バージョンが健闘していることだ。条件によって効果が得られたり得られなかったりする不思議なオプションなのだけれど，少なくとも微視的なレベルでは効果が得られるはず，ということなのだろうと思う。
確認のために，生成コードの比較を行っておこうと思う。まずは FPU math バージョンのディスアセンブリだ。
これが SSE math では以下のようになる。
これだけでも，結構すっきりするもんなんだなあ……。ただ， FPU バージョンと比較すると若干精度が低下しているはずなので（FPU 内では 80 bit float 形式で演算が行われるため），厳密な精度の互換性を保つには注意が必要だ。
これが SSE バージョンだと，以下のようになる。
本当は，
こうなって欲しいんだけどね……。
2003-05-25
実験レベルでの効果は分かったので，実際の応用ではどの程度の効果が得られるものなのか，検証してみようと思う。
テスト対象としては，毎度お馴染みの pathtracer を使用することにした。元は tvmet を使って書いていたものなのだけれど，今回の検証のために多少の書き直しを行った。浮動小数点形式が倍精度 (double) であることを前提として書いている部分があるから，それらを丁寧に float 化してやらないと，厳密な比較を行うことができないのだ……。
結果は以下のようになった。
前の実験と比較すると，随分と面白くない結果になってしまったものだと思う。 SSE math に負けてしまっているなあ……。
ここで予想以上に tvmet が健闘しているのは，ベクトル型として３次元ベクトル (Vector<float,3>) を利用していることが大きいと思われる。光線追跡処理は３次元ベクトルでもほぼ問題無く処理を行うことができるため，何気なくそうしていたのだけれど，これは予想以上に重要なファクターとなっていたようだ。単純に考えて 1.3 倍程度の高速化，およびメモリアクセスの軽減となるのだから，その効果は無視できないものになるだろうと思う。
その他の要因としては，比較的複雑な操作（例えば内積演算）における SSE の非効率性や，複合的な操作における tvmet の効率の良さ（Expression Template のおかげで並列性の高いコードが生成される）等が候補として挙げられる。アプリケーションの性質上，特に前者の影響は大きそうだ。
GCC でも，アドレス非整合の問題や，ベクトル型（クワッドワード型）の扱いに関する不具合等が改善されれば，少なくとも tvmet に劣るようなことは無くなるのではないかと考えている。本来ならば，ベクトル型が xmm レジスタに直接格納されるようになり，関数のインタフェース部分における無駄なロード・ストア処理が一切削除されるはずなのだ。今回の実装ではこの部分がかなりのオーバーヘッドとなっているはずだから，これが改善されれば状況は異なってくるだろうと思う。
とりあえず現段階においては， tvmet + SSE math で十分なパフォーマンスを出すことができる，という結論にしておきたい。ゲーム的なグラフィック処理のように，それこそストリームの如くデータが流れてくるようなシチュエーションにおいては SSE の効果が十分に上げられるかもしれないけれど，今回の例に代表されるような通常のベクトル操作においては，努力したところで得られるものは少ないだろう，ということだ。
SSE における各種オペレーションを実装するにあたって， Intel の提供するサンプルコードを参考にした（実際には Gamasutra の記事へ転載されているものを利用した）。
http://www.gamasutra.com/features/20000131/barad_pfv.htm
命令セットの詳細な仕様については， Intel サイト内の以下のページからリファレンスマニュアル等をダウンロードすることができる。
http://developer.intel.com/design/PentiumIII/manuals/
SSE は非常にシンプルな命令セットだ。ロード・ストア，加算・乗算など，一通りの基本操作が用意されているほかは，ほとんど何の付加機能も用意されていない。 3D 処理につきもののブロードキャスト演算や swizzle 操作等は何も用意されておらず，成分の入れ換えに関してはシャッフル命令やパック・アンパック命令を辛うじて使うことができる程度であり，さすがに心許ないものを感じてしまう。あくまでも MMX の延長線上にあるものなのだと捉えておくのが良いだろうと思う。
また， RISC 系のアセンブリ記述に慣れた人にとっては，２オペラント主体の命令体系に若干戸惑いを覚えることになるだろうと思う。ソースを破壊せずに演算を行いたいシチュエーションってのが，意外と多くあるんだよね……。なにげにレジスタが８個しかないのも中途半端に感じるところだ。
これらの制限の中でも，ブロードキャスト演算が用意されていないことは，最も不満の募る点になるかもしれない。これが無いために，行列の乗算などはちょっと冗長なことになってしまう。結局のところ，十分に速い CPU と広大なキャッシュ領域があるのだから，無理して SSE 命令を使うよりも，通常命令との住み分けを上手く行い，適切なバランスを保っていくのが良いのではないかと思う。
例えば，内積演算を SSE のみで実装すると，以下のようなコードになる。
これを SSE math 的にコーディングすると，以下のようなコードになる。
単純なライン数では後者の方が多いけれど，前者のコードはすべてのラインにおいて前ラインとの依存関係が生じてしまっている。ペアリングによって並列化が行われる分まで考えると，その優劣は非常に微妙な問題となるだろうと思う。
2003-05-26
仕事中に突然の地震があった。ゆったりとした振幅の大きい揺れに，思わず酔ってしまいそうになる。さすがにビルの２０階ともなると揺れ幅が大きい。地上付近で感じるような細かい振動とは違って，まるで船に乗っているかのような「うねり」を感じる。一瞬，眩暈がしたのかと勘違いしてしまうんだよね……。
一応，ビルに制震機構が備えられているおかげで，揺れ幅はある程度抑えられているはずなのだけれど，それでも揺れるものは揺れるんだな。気持ち悪い……。
http://contest.thinkquest.gr.jp/tqj2000/30295/structure/styl...
先日，どこかの掲示板への書き込みから，こんな記事へのリンクを見つけた。 PS2 ソフトウェアの海賊行為について触れた記事だ。
http://edu.peopleweb.com/chrisp/gin.html
この記事で取り上げられているのは "Splinter Cell" の「公式チートディスク」なる製品だ。販売元 (Ubi Soft) からの認可も受けているとのことで，一見まともなライセンス製品のように思われるのだけど，実は非公然的な海賊ソフトウェアの一種であることがここで暴かれている。
通常の場合， PS2 には種々のプロテクト機構が備えられており，正規のルートで生産された製品以外は動かすことができないようになっている。これを回避するための手法として有名なのが，いわゆる「mod チップ」等の本体改造テクニックだ。しかしここで用いられている手法は，未改造の本体でも非正規のソフトウェアを動かしてしまうという種類のものであり，しかもその内容が実に豪快なのだ。
この手のメディアプロテクトは，主に CD / DVD のリード領域を利用するものであるらしい。
http://bit-drive.e-words.ne.jp/w/E383AAE383BCE38389E382A4E38...
http://www.geocities.co.jp/HeartLand-Tachibana/9059/tomatoma...
そこで，まず，適当な正規のソフトウェア（ここではセガの "Crazy Taxi" が用いられている）の物理コピーを用意する。そして，そのリード領域に相当する部分を「物理的に」くり抜き，別途にプレスした本体の CD と「物理的に」接合してしまう。これで "Crazy Taxi" のプロテクション情報を持つ海賊ソフトウェアが出来上がってしまうというわけだ。なんと単純なメカニズムであることか……。
こうして作成されたメディアは，元となったソフトウェアの TOC 情報とリード領域を持っていながらも，データ本体は目的のソフトウェアの内容であるという，規格的にはあべこべな状態になってしまっている。しかし PS2 本体は TOC 情報を利用しないため（どうもそうであるらしい……詳しいことは僕にも分からない），問題無く動作させることが可能とのことだ。
それにしても，こんな「ニコイチ」手法でプロテクトが回避できてしまうとは知らなかった。その昔，セガサターンのハックに「CD-R の外周に『サターンリング』シールを貼り付ける」なんていうキワいテクニックがあったと思うのだけれど，それを工場規模で実行してしまっているような構図だ。
http://www.google.co.jp/search?q=%83T%83%5E%81%5B%83%93%83%8...
他社ソフトの海賊版を製造するならともかく，自らの製品に対してまでこのような手口を働く理由があるのだろうか？その目的がライセンス料のキャンセルであろうことは容易に想像がつく。生産をメーカーに委託するのではなく，生産から出荷までを自前で管理することによって，各種ライセンス料の支払いをごまかすことができるし，製造原価も最低レベルまで引き下げることができるはずだ。
たとえ改造の手間が新たなコストとして加えられるとしても，コストの最も安い地域において生産が可能であることを考慮すれば，それも十分に相殺することが可能なのではないかと思う。むしろここまで来ると，そもそも販売ライセンス自体，本当に取得しているのかどうか怪しくなってくるのだけど……。
件の記事によれば，このような「ニコイチ」手法は，アジア地域における海賊手法の一種として広く用いられているものであると指摘されている。また伝聞によれば，アジアの特定の地域では，改造済みの PS2 が店頭で堂々と売られているというような話もある。
そのようなアジア地域における海賊行為自体は珍しくないとしても，今回の話はある種の事件性を有している。それは，欧米において何の疑いも無く流通されていた商品が，実は海賊ソフトウェアの一種であったという事実だ。 Ubi Soft のような著名なパブリッシャをも騙くらかし，何の罪の意図も無い流通や販売店にも海賊行為の片棒を担がせたというところで，その大胆にして恐れ知らずな行為には，まったくもって敬服を……っていうか敬服しちゃだめだな。
その，なんて言うか，まあ訴えられても当然かな，と……。
2003-05-27
通勤電車の中で John Barrow の「天空のパイ」を読み終えた。
http://www.msz.co.jp/titles/7018.html
http://www.edge.org/3rd_culture/bios/barrow.html
珍しくまともに最後まで本を読んだような気がする。はっきり言って，この本が述べている内容のほとんどを理解することができなかったのだけれど，それでも強く興味を惹く何かをこの本は持っていた。だからこそ，苦労しながらも最後まで読み通すことができたのだろうと思う。
この本は，数学という学問の根底に存在する「哲学」について触れた本だ（「数学哲学」って言葉で合ってるのかな）。
今日，数学という学問は，すべての科学分野における基礎をなす下部構造となり，それらの理論を支える術となっている。数学という抽象概念は，実在にまとわる曖昧さをすべて取り除いた記号的な存在であり，そこから導き出される理論は，当然の如く確固たる根拠を有しているように考えられている。しかし，人々は何故，それほどまでに数学を信頼することができるのだろうか。そもそも，数学とは一体何なのだろうか。
遥か紀元前に数学の起源となる学問が生まれて以来，数学は絶対的な理論の拠り所として考えられていた。しかしそれも，２０世紀に入り論理学が進歩を遂げると，それまでは絶対と考えられていた論理体系に矛盾の生じる余地のあることが明らかになってくる。こうした数学の本質に対する揺さぶりに対して，２０世紀初頭の代表的な形式数学主義者であるヒルベルトは，ある公理から形式化された演繹の展開によって，純粋数学を論理的に完全な存在へと仕立て上げることができるという信念を持ち，それを実行に移していた。
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Hilb...
このヒルベルトの大業に対して，同時期に活躍した論理学者ゲーデルは，その代表的な業績とされる不完全性定理によって，ヒルベルトの試みが成功することはあり得ないことを提示した。その内容とは，ある体系が論理的に矛盾を含まないことを証明すること自体が不可能である，という証明だった。
http://www-gap.dcs.st-and.ac.uk/~history/Mathematicians/Gode...
http://www.nadeshiko.sakura.ne.jp/~kaigakai/godel/
http://matsuda.c.u-tokyo.ac.jp/~ctakasi/first/t5/talk.html
ゲーデルの導き出した定理は，それまでの純粋数学の在り方に対して衝撃を与えるものだった。純粋数学の完全な姿を作り出そうとしたヒルベルトの試みは敗れ去り，知り得るもののすべてが正しいと証明できるに違いないという確信は，人々の心の中から失われることになる。
では，数学の本当の姿とは何なのだろうか。決して到達することのできない数学の本質とは，一体何なのだろうか。それは人間の手によって生み出された「発明」なのだろうか。それとも，いずこかに実在する真理を発見するプロセスの一種なのだろうか。数学者ベルナイスはこの考えをプラトンのイデア論にちなんで「数学的プラトン主義」と呼んでいる。そこでは，我々の主体と切り離された所に実在する数学的本質を想像し，それによって数学の普遍性を保とうとしている。その解釈に拠るならば，「円周率」とは人間の手の内に存在するものではなく，まさしく天空に存在するものと考えられる。
この本の前半部分は，原始社会と初期の文明における数学の起源を追うことによって，人間の心理構造と数学概念の関連性を明らかにしようと試みている。この部分は単純に読み物としても面白い。
本の中盤に入ると，今度は２０世紀まで一気に時代が飛ぶ。そこでは論理学の発展と純粋数学の分化を追い，哲学化しつつある数学の探求について触れている。様々な近代数学史上の偉人が登場し，それらの人々の織り成す対立のドラマが描き出される。この時代の純粋数学は，科学分野への応用という数学本来の目的から既にかけ離れており，哲学的な理念を持って数学の探求が行われていたのだということが伝わってくる。
そして，本の後半にある「締め括り」の部分に入ってくると，とたんに話が難しくなってくる。この本の主題，つまり，数学の本質の哲学的探求という，非常に捉えることの難しい問題が浮上してくるからだ。哲学のテの字も分からないような僕にとっては，とてもついて行くことのできないような話になってしまっている。そもそも，応用を目的としない「純粋数学」って概念自体が，非常に近寄り難いものであるのだから，なおさらだ。
この本を読んで明らかに分かることが１つあるとすれば，それは，純粋数学という分野が何ゆえ存在するのかという問いに対しての解答だろうと思う。素粒子科学者が，原子力発電のためにではなく，宇宙の起源を解き明かしたいという思いから超巨大加速器を作り出したように，純粋数学者は，明日の株価を予想するためにではなく，数学の本質を見極めたいという思いから研究を行う。それは科学分野における哲学者の姿であり，絶対に解き明かされることの無いであろう真理を追い求める探求者の姿でもあるのだろうと思う。
2003-05-28
最近，どうにもボンクラな暮らしを送っているためか，自分の中のタスクリストが雑多な項目の山で埋め尽くされてしまっている。その中でも特に重要な項目であるはずの， Tim Rowley 氏の SIGGRAPH 論文コレクションのチェックも，まだほとんど手が付けられていない。もう既に，かなりの数の論文が出揃っているというのに……。
http://www.cs.brown.edu/people/tor/sig2003.html
あと spin のニュースも真面目にチェックしておく必要がある。最近，まともに追いかけられてないんだ……。
普通に追随して行くだけでも，全力で走っていなきゃならないのに，ましてやそれを追い越そうとするならば，一体どれだけの努力を払わねばならないのだろうかと考えることがある。
http://www.genpaku.org/alice02/alice02j.html
Tim Rowley 氏の論文コレクションをさらっと見回して，まず目に付いたのが， Xavier Decoret 氏の "Billboard Clouds for Extreme Model Simplification" だった。
http://www-imagis.imag.fr/Publications/2003/DDSD03/index.fr....
http://www-imagis.imag.fr/Publications/2002/DSDD02/index.fr....
要するに，任意のポリゴンモデルからビルボード集合への変換を行うというものだ。例えば，上にあるヘリコプターの画像ならば，元は 5,000 枚以上のポリゴンで構成されていたモデル（左）が，自動変換によって，たった 32 枚のビルボード（右）にまで落とし込まれている。画面上での占める面積が少なければ，これでも十分に代替することが可能だろうと思う。それにしても，案外少ない枚数でごまかせるものなんだねえ……。
ここで必然的に湧き上がる疑問がある。任意のモデルに対して「最適な」近似となり得るビルボードの構成とは，一体どのようなものなのだろうか。この問題に対して Decoret 氏は「ハフ変換」 (Hough Transform) と呼ばれる画像処理の手法を持ち出してきている。
http://mikilab.doshisha.ac.jp/dia/research/person/shuto/rese...
http://www.whaleeaters.org/~3ki3ro/diary/cgnotes/97/04/97043...
ハフ変換は，画像処理の分野において，主に直線成分の抽出のために用いられる手法のようだ。ハフ変換は，解析対象となる座標空間から，線分パラメータによって構成される「パラメータ空間」への変換を行う。座標空間上のある点をパラメータ空間へ変換すると，それは「その点を通る線分」のパラメータの集合を構成することになる。逆にパラメータ空間上の点は，座標空間上において１本の直線を構成する。
そこでまず，任意の画像に対してフィルタリングを行い，重要な意味を持つ点の集合を抽出し，それらをパラメータ空間へと変換する。その結果として得られた画像は，元の画像に潜む直線成分の組み合わせを足し合わせた (accumulate) ものとなっているはずだ。すなわち，ここから重要な意味を持つ点を任意の数だけ抽出し，それを元の座標空間へと逆変換すれば，結果として「重要な意味を持つ」直線の集合が得られるというわけだ。
ハフ変換の特徴として挙げられるものに，ノイズへの強い耐性がある。断続的な途切れを持つ形状に対しても正しい効果が得られることなど，特に面白い特性なのではないかと思う。
http://www.dai.ed.ac.uk/HIPR2/hough.htm
Decoret 氏の手法では，前出のハフ変換の例と同様に，曲座標による平面のパラメータ化を扱っている。
まず，座標空間上のあらゆる平面の候補のうち，条件に適合しそうなものだけを選別し，それらを平面パラメータ空間 (plane space) へと変換する。このとき，それぞれの平面に対して「点数」 （ここでは「密度」 - "density" と呼ばれている）を評価しておき，その点数をパラメータ空間上のボリュームデータ構造へと格納する。
そうして得られたパラメータ空間上のボリュームデータから，高い「密度」を持つ点を任意の数だけ抽出する。それらを座標空間上へと逆変換すれば，結果として「最適な」ビルボードの組み合わせを得ることができる，という仕掛けだ。
ここで用いられる「密度」の評価は，モデル全体に対しての適応度 (coverage) や，その面を選択したことによって失われる要素の量 (penalty) 等から決定される。この評価方法が最終的な品質に大きな影響を及ぼすであろうことは想像に難くない。
2003-05-29
"Billboard Clouds" の応用として少し面白かったのが，法線マッピングを用いることでビルボードに対して光源計算を行うというテクニックだ。ビルボードを作成する際に，テクスチャと共に法線情報を取り込んでおくようにすれば，ビルボードに対して動的に光源を適用することが可能となるというわけだ。ううむ，確かに可能だわな……。
その他に，ビルボードから他の物体に対して影を落とすというテクニックも紹介している。この手法によって生成されるビルボードは，一般的に用いられている「書き割り型」のビルボードとは違って，どの方向から見た場合にも欠けの少ない形状をしているから，それをソースとして投影を行ったとしても，ビルボードそのものと同じ程度には問題無くシルエットが描き出されるはず，ということだ。
"Billboard Clouds" の手法は，高品質な低ディテールモデルの生成を自動化するという意味では非常に興味深いものなのだけれど，実際にこれを利用するにはいくつかの弱点を解決するか，あるいは回避しなければならないだろうと思う。そのうちの最大の弱点は，静止物しか扱うことができないという制限だ。
もとより，画面上に占める面積の少ないモデルは，形状に関してかなり荒っぽく扱うことが可能であると思う。しかし，アニメーションに関しては別問題だ。実際にゲームの画面などを眺めてみると，たとえ遠くにあって形状が定かでない物体であっても，「なんとなく動いている感じがする」という知覚は働いていることが分かる。だから，むしろ形状の変化に対しては比較的鈍感であっても，「動いていたものが動かなくなってしまう」という変化に対しては敏感に反応してしまうのではないかと思う。もしそうだとしたら，ビルボード化によってアニメーションが止まってしまうことは大いに不具合となり得る。
主要なパーツ群への分解を行って，その個々のパーツ毎にビルボード化を行って，云々……というような工夫も考えられないことは無いけれど，そこまでしてこの手法を用いる利点はあるだろうかと考えると，実に微妙なところだ。シンプルな手法であるからこそビルボードを使おうというモチベーションがあったはずなのに，システムが複雑化してしまっては意味が無い。そもそも自動化が難しくなってしまうのではないかと思う。それならば，もう少し単純なリダクション手法を探した方が良いだろう。
そんなわけで，結局のところ，この技術があらゆる用途に対して利用可能であるわけではないんだけれど，幾つかの興味深い示唆を与えていることは確かだ。ハフ変換を用いて最適なビルボードの構成を求めるという手法はそれ自体面白いものだし，比較的少ない枚数のビルボードで見た目の区別が付かないほどの品質を得ることができるという事実は，かなり参考になるものだと思う。
ていうか，どこかで誰かが製品化すれば，何に使うかはともかくとして，明らかに買い手は付くだろうね……。
2003-05-30
これは以前から度々主張していることなのだけれど， SourceForge のフォーラムは非常に使い難い。
http://sourceforge.net/mailarchive/forum.php?forum=gdalgorit...
使い難いだけならともかく，最近の SourceForge はやたらと反応が重いものだから，ログの閲覧などとてもじゃないけどやってられない。それで，例えば GDAlgorithms-list のように SourceForge でログを管理しているメーリングリストがあると，非常に残念な気持ちになってしまう……。
せめて GDAlgorithms-list のログぐらいは自前で管理してみようかと思い，メールログを HTML 化するツールの導入を検討することにした。
この手の "Mail to HTML" コンバータとして有名なのが "MHonArc" と "HyperMail" だ。
これらのツールは，メーリングリストのログを管理する用途などで広く用いられている。
http://lists.boost.org/MailArchives/boost/
http://www.bitmechanic.com/mail-archives/mysql/
とりあえず両方とも試してみたのだけれど，機能的にはそれほど差が見られなかった。ただ， MHonArc の実体は perl スクリプトであるのに対して， HyperMail の方は普通に C で書かれている。そのため，動作速度は断然に HyperMail の方が速い。他に選択を左右する要素が見られないのであれば HyperMail を選んだ方が良いだろうと思う。
どちらのツールも入力ファイルとして UUCP mailbox 形式を要求するため， Windows では少々使い難いものがあるかもしれない。かく言う僕も，自宅では Windows 用の "AL-Mail" を利用しているため，これのログをそのまま入力ファイルとして用いることはできない。
ただ， mailbox 形式とは言っても，特殊なヘッダの加えられたメール群を単純に連結しただけの内容だから，やろうと思えばいくらでもでっちあげることが可能だ。特に AL-Mail のログファイルはメール本体をダンプしただけの内容なので，非常に加工が行いやすい。例えば，下のようなシェルスクリプトで適当に生成したファイルでも，一応問題無く入力することができるようだ。
ここで問題となったのが，これらのツールに付いているスレッド表示機能の仕様だ。
これらのツールでは RFC 822 に規定されている "In-Reply-To" フィールドを利用して返信の判別を行い，そこからスレッドを構築しているようなのだけれど，一部のメールソフトではこのフィールドがまともに処理されていないことがあるようだ。
http://www.faqs.org/rfcs/rfc822.html
例えば Gmane 等に転載されている GDAlgorithms-list のログを見てみれば，スレッド表示がまともに機能していないことが分かるだろうと思う。
http://news.gmane.org/thread.php?group=gmane.games.devel.alg...
In-Reply-To フィールドが抜けているだけならともかくとして，場合によっては，まったく内容と関係の無い参照先へ In-Reply-To フィールドが設定されてしまっていることもあるようだ。これは恐らく，どこかの物臭な人が，まったく関連の無いポストへの返信として新規の書き込みを作成する（題名さえ書き換えてしまえば，新規ポストに見えないこともない……）ことが原因なのだろうと思う。もし，そういうことが本当にあるのだとすれば，作法の通じない場所においては In-Reply-To フィールドを当てにしてはいけないという教訓が導き出される。
これは余談なんだけれど， GDAlgorithms-list は，他の開発系メーリングリストと比較しても，書式に無頓着なポストが多く見られるように思える。まったく意味を失ってしまった引用の羅列や，メーラーの自動改行によってめちゃくちゃな改行になってしまっているポスト，等々……。むむむ。
散々悩んだ挙句， MHonArc に備えられている「題名から返信を判別する機能」を利用することにした。 In-Reply-To フィールドはフィルタリングによって削ってしまい，題名からの判別のみを当てにしてスレッドの構築を行うというわけだ。
この方法は比較的上手く行った。スレッドの途中で題名が変更されてしまう場合などもあるから（メールソフトの文字数制限に引っかかって切り詰められてしまう場合もある……），一概に上手くいくとは言えないのだけれど，それでも以前よりはまともな結果になっただろうと思う。
http://www.radiumsoftware.com/gdalgorithms/threads.html
これでやっと，メーリングリストの参照が，職場からもまともに行えるようになった。望むべくは，過去のログをすべて保管できると良いのだけれど，サーバの容量がどうにも……。
2003-05-31
このところ，ウェーブレットについて簡単に調べてみている。
JPEG 2000 にウェーブレット圧縮が採用された頃から興味は持っていたのだけれど，従来のサブバンド圧縮を上回る技術って言うんだから相当に難しい理論なのだろうな……という憶測から，あえて無視を決め込んでいた。
それが最近になって，リアルタイムレンダリングやモーションデータ処理などの分野において，ウェーブレットを取り入れた技術が増え始めているように思える。 SIGGRAPH 2003 における Ren Ng 氏および Ravi Ramamoorthi 氏の論文 "All-Frequency Shadows Using Non-linear Wavelet Lighting Approximation" などが，その一例だ。
http://graphics.stanford.edu/papers/allfreq/
また付け焼き刃に終わってしまうかもしれないけれど，せめて概論を把握する程度には手を染めてみようと思っている。
まず，手始めに読んでみたのが， Beyond Discovery の記事 "Wavelets: Seeing the Forest - and the Trees" だ。
http://www.beyonddiscovery.org/content/view.article.asp?a=19...
一般的な読者を対象として書かれている記事なので，非常に読みやすい内容となっている。前知識を備えるにはいい資料かもしれない。印刷用に組版された PDF も置いてあるので，通勤読書にもばっちりだ。
余談なのだけれど，この "Beyond Discovery" は米国科学アカデミーが主催するサイトであり，本来は科学関連の記事を集めた刊行物であるらしい。日本では日経サイエンスなどに記事を提供しているようだ。他にも面白い科学記事が置いてあるので，一度目を通してみると面白いかもしれない。
http://www.beyonddiscovery.org/
http://www.nikkei-bookdirect.com/science/beyond-discovery/in...
Beyond Discovery の記事を読んでいくつか分かったことがある。どのようにしてウェーブレットが生み出されたのか，また，どうしてウェーブレットが必要とされているのか……などという疑問に対する答えだ。
どうやら，ウェーブレット解析を用いる最大の動機は，ウェーブレットが時間と周波数の両方の領域に対して優れた特性を持っていることにあるようだ。このことが，フーリエ変換などの従来の技法と比較した場合に，最も異なっている要素であるらしい。
そもそも，ハイゼンベルクの不確定性原理によれば，時間的な精度と周波数的な精度を同時に得ることは，理論的に不可能であるらしい。周波数に対して高い精度を得ようとするならば，時間的に長い区間が必要となってしまうし，それとは逆に，時間的に短い区間に対する解析を行おうとするならば，今度は周波数の方の精度を下げなければならない。ここでなぜ不確定性原理が出てくるのかさっぱり分からないんだけれど，とにかくそういうことになっている。
http://sepwww.stanford.edu/sep/prof/waves/rnd/paper_html/nod...
ここで通常のフーリエ変換を見てみると，これが無限の時間に対して積分を行い，無限の精度の周波数分布を得るものであることが分かる。時間領域から周波数領域への完全な変換を行うものであり，変換後の関数には時間の要素がどこにも存在しない。
それでは応用に適さないから，適当な窓関数などを使って区間を制限してやるのだけれど，場合によってはこの処理が不都合を起こすことがある。先ほども出たように，周波数領域と時間領域における精度は相対的に変化するものであるから，変換前の関数に対して単純に畳み込みを行ったところで，理想的な結果が得られないであろうことはなんとなく予想することができる。
例えば（これはあまり良くない例だけれど）， JPEG におけるブロックノイズなどは，画像を無理やり 8x8 の区域に分割して DCT を適用することから生まれるものだと考えれば，その副作用を直感的に理解することができるかもしれない。