Radium Software Development

HOME - ARCHIVE - ABOUT - RSS

Not Just Solving Puzzles

2006-03-01

Guido van Rossum. Language Design Is Not Just Solving Puzzles.

― ある人々は,言語の設計をパズルを解くようなものだと考えているようだ。彼らは要求条件が与えられると,解空間をシステマティックに探索する。そして解を見つけると,完璧な言語フィーチャーを得ることができたと主張する。その様はまるで数独のパズルを解いたかのごとくである。

スクリプト言語 Python にはラムダ記法が用意されている [Olli] 。どちらかと言えば手続き型の言語の一派に属する Python にとって,ラムダ記法のような関数型の言語フィーチャーは少し異質な存在だが,リストに対して即席の処理を適用する場合などに便利であり,度々重宝する。

ただし Python のラムダ記法は,内部にステートメント(文)を含むことができない。そのため,例えばラムダ関数の中で代入を行ったり print を行ったりすることはできない。前者は代入ステートメントを含む必要があり,後者は print ステートメントを含む必要がある。

Python ではステートメントの区切りを改行によって表現する。また,ステートメントのグループ化にはインデントが用いられる。これらの文法はラムダ記法のマルチ・ステートメント対応を非常に難しくしているように思われるが,コミュニティの一部では,非常に特殊な文法を取り入れることによって,この問題を解決することが可能であると主張されている [Python-Dev] 。

Python の作者であり,今も代表的な開発者の一人である Guido van Rossum 氏は,この提案を「Python 的でない」として撥ねつけている。確かによほど特殊な文法を導入すれば,互換性を保ちながらラムダ記法をマルチ・ステートメント対応させることが可能かもしれない。しかし,それはただ単にこの問題を迂回することができたというだけに過ぎない。言語として発展性のある拡張であるとは,あまり思えない。

もとよりこの手の処理は,スコープ・ローカル関数(ネストした関数定義)を用いれば容易に実現することができる。そもそも誰が何のためにマルチ・ステートメントに対応したラムダ記法を必要としていたのだろうか? それが単なるパズル・ゲームでしかないということを Guido 氏は分かりやすく(かつ少し皮肉っぽく)説明している。

[via Lambda the Ultimate]

Double-Blind Test

2006-03-02

ある事象についての評価を行う際に,先入観や自己欺瞞から生じるバイアスを取り除くには,二重盲検法(ダブル・ブラインド・テスト)が役に立つ。二重盲検法は医学分野での治療法の検証や,オーディオ機器の品質評価などに用いられている。その概要については [SkepDic] や [オーディオの科学] が参考になる。簡単に言えば,通常の盲検法では評価対象を被験者から隠すのに対して,二重盲検法では試験を実施する側も対象に関する情報を持たない状態にする。つまり,試験に関わる誰もが対象についての情報を持たない状態で,無作為に試験を繰り返す。それで統計的に有意な結果が得られないようであれば,その事象には十分に疑いの余地があるということになる。

オーディオ機器の音質比較のための盲検法・無作為化法としては ABX テストや ABC/HR 比較などがよく用いられる [匿川] 。これらの検証法を実践するためのツールがフリーで配布されており [ff123] ,誰でも手軽に盲検法を応用した検証を行うことができるようになっている。同様のツールを用いた実践例としては,ブラジルはパラナ連邦大学の Roberto Amorim 氏が行った音声圧縮コーデックの音質比較の公開検証などが挙げられる [RJAmorim1] 。この検証の結果は,低ビットレートにおける Vorbis コーデックの優位性を裏付けるものとして引用されることがある [RJAmorim2] 。

A Scanner Darkly

2006-03-04

060304_0.jpg

フィリップ・K・ディックの邦訳本は後期の3部作を除いてほとんど読んでいる。中でも「暗闇のスキャナー」は最も好きな作品だった。覆面麻薬捜査官フレッドことボブ・アークターは,「物質D」の製造・販売経路を調査すべく,自らも「物質D」を服用し薬物中毒者のグループに混ざり込むが,やがて「物質D」は彼自身の精神をも蝕み始める。薬物によって自我の崩壊していく様子が,ディック得意の存在論的アプローチによって描き出される。薬物を賞賛する物語でもなければ,薬物中毒者を批判する物語でもない。ただ,薬物によって急速に燃え尽きていく生命の哀しさと,それを食い物にする人々の罪深さが,淡々と描かれている。

フィリップ・ディックの小説は数々のハリウッド映画の原作となっていることで有名だが,「暗闇のスキャナー」は今まで映画化されることが無かった。それが,監督リチャード・リンクレイター,主演キアヌ・リーブスによって映画化されると発表されたのは 2004 年の春のことだった。当初は 2005 年秋に公開される予定だったが,制作は遅延に遅延を重ね,現時点では 2006 年の夏に公開予定となっている [Warner] 。

映画版「暗闇のスキャナー」は,ロトスコープ (rotoscope) と呼ばれる手法によって制作されている。ロトスコープは,実写映像をトレースすることによってアニメーションを制作する手法であり,CG導入以前のディズニー映画などにおいて部分的に用いられていた [Wikipedia] 。映画版「スキャナー」では,このロトスコープを用いることによって,有名俳優達の生きた演技とアーティスト達の美術性を融合させた,非常に斬新な表現を生み出している。その様子は先月公開された最新のトレイラーにおいて確認することができる [Apple] 。

制作遅延の理由については Wired 最新号の記事に詳しい [Wired1] 。「スキャナー」のアニメーションパートは,リンクレイター監督のロトスコープ作品 "Waking Life" [WakingLife] から引き続きボブ・サビストン [FlatBlackFilms] が担当していたが,チームの統率などに問題が生じたために,途中で交代を余儀なくされたことなどが明かされている。小規模・低予算制作の "Waking Life" とは違って,「スキャナー」では『キアヌ・リーブス主演のハリウッド映画』としての体裁を整える必要がある。そのためには,カット毎に絵柄が変化してしまうようでは困るし,進捗も厳しく管理されなければならない。

ロトスコープは非常に手間のかかる手法だが,美術性以外の利点が無いわけでもない。ロトスコープの元となる実写映像では,俳優の動きや表情のみが重要な要素となるため,背景セットの構築や俳優のメーキャップなどに手間をかける必要が無い。実際に「スキャナー」では,これらの工程を大幅に簡略化し,全撮影をたったの6週間で終えることができたとされている(裏を返せば,それだけアニメーションパートが時間を費やしているということになるのだが……)。

余談だが,ボブ・サビストン氏は MIT Media Lab の出身であり, "Waking Life" および「スキャナー」では "RotoShop" と呼ばれるロトスコープ支援ソフトの提供も行っている。ロトスコープにおける実写のトレースは,基本的にはアニメーターの手作業によって行われるが,フレーム間の内挿はソフトウェアによって行われる [Wired2] 。いわゆる「原画」の部分を人が担当し,「動画」を自動生成していると考えることもできる。このように重要な技術面を担当したサビストン氏をも更迭した辺りに,プロデューサーとの間の確執の深さをうかがうことができる。

[via Bradley Newman]

P4Merge

2006-03-06

Windows 上でバージョン管理システム Subversion を使用する場合には, TortoiseSVN と呼ばれるクライアントが用いられることが多いかと思う。 TortoiseSVN はエクスプローラのシェル拡張を用いており, Windows ユーザにとって非常に馴染みやすいインタフェースを提供している。もはやこのクライアントの存在自体が Subversion の魅力の一部になっていると感じられる。

TortoiseSVN は非常に安定したソフトウェアだが,敢えて不満点を挙げるとすれば,差分ビューア (TortoiseMerge) の多言語対応が不完全であることが挙げられる。 SVN クライアント自体の Unicode 対応は安定しているものの,差分ビューアの表示にはどうにも怪しいところがある。 UTF-8 で書かれたソースの差分を取ると,容易に表示が化けてしまう。

TotoiseSVN では外部差分ビューアを用いることができるようになっているので,日本語表示に対応した適当な差分ビューアを用いると,この問題を解決することができる。該当するビューアは数種存在するが,個人的には Perforce Visual Merge Tool (P4Merge) が気に入っている。

060306_0.png

Perforce 自体は商用のバージョン管理システムだが, Visual Merge Tool は無料で配布されている。ダウンロードページから "Core Perforce Windows Installer" を実行し, "Administrator - Custom" から "Visual Merge Tool" 以外のチェックを外せば, Visual Merge Tool のみをインストールすることができる。

インストール中に Server Port を聞かれる箇所があるが,これは Perforce 本体側の設定なので, Visual Merge Tool のみを用いる場合は,適当に "localhost:1666" とでもしておけば(恐らく)問題無い。

Programming Fonts

2006-03-07

プログラミングに適したフォントにはいくつかの条件があると考えられる。小さいポイント数でも視認性が良いこと,文字の密度が高いこと,混同しやすい文字の組み合わせ("0" と "O" など)が無いこと,大文字と小文字のバランスが適切であること,等々……。

個人的には, Windows 標準のフォント "Verdana" をプログラミング用のフォントとして愛用している。プロポーショナルフォントであるためにインデントがおかしくなることがあるものの,低ポイントでの優れた視認性や,標準フォントの中でも屈指の密度の高さなどが気に入っていて,ここ数年使い続けている。

060307_0.png

等幅フォントでは "Courier New" が広く用いられているのではないかと思う。すっきりしたデザインが目に心地良い。ただ,密度が少々低めなのが気にかかる。画面全体に広がると,少し疎らな印象を受ける。

060307_1.png

Windows 標準フォントの中では "Lucida Console" などもよく用いられている。こちらは Courier とは対照的に太くどっしりとした印象を受ける。視認性は良いものの,少し丸みを帯び過ぎているように感じられる点と,大文字と小文字のバランスが不釣合いに感じられる点が気になる。

060307_2.png

Mark Simonson Studio のフォント "Anonymous" は,これらの等幅フォントを代替するものとして使えるかもしれない。視認性の良さ,誤認識の少なさに加え,デザインの良さ,適切な文字の密度など,優れた点を多く挙げることができる。また,「小文字の読みやすさ」と「大文字の目立ちやすさ」のバランスが絶妙である点も良い。

060307_3.png

最後に,統合環境のエラー出力ビューなどのように,画面の片隅に極力小さい表示をさせたい場合には, Tobias Jung 氏の "ProFont" が薦められる。非常に低いポイント数でも,ある程度の視認性を保つことができる。

060307_4.png

なお,これらのフォントは,ソフトウェアによっては日本語の表示に不具合を生じる場合がある。そのような場合は FontLink 機能を使って調整を行うと,多くの場合は状況が改善される。

Mind Hacks

2006-03-09

Tom Stafford, Matt Webb 著,夏目大訳, Mind Hacks ― 実験で知る脳と心のシステム.

人間の知覚は,脳が処理することのできる量よりも遥かに多くの情報を常に受け取っている。また同時に,人間の知覚には様々な部分に欠落があり,受け取った情報そのままでは十分な認知を構成することができない。そこで脳は,ある部分では大幅な情報の切り捨てを行ったり,またある部分では実際には知覚していない情報を補ったりと,様々な「ハック」をやってのけることによって,周囲の環境に問題無く対応することができるようになっている。これらの脳の働きは閾下で行われているため,普段意識することはまったく無い。しかし,これらの働きを逆手にとった状況を人為的に作り出してみると,脳の中で行われていることの片鱗が僅かながらも見えてくるようになる。 Tom Stafford および Matt Webb の著書 "Mind Hacks" では,そのような脳の隠された働きの数々と,それを知るためのトリックの数々が紹介されている。

この本の構成は大きく二つに分けられる。前半部では視覚や聴覚などの知覚の働きについて触れており,後半部では記憶や推論のような高次の働きについて触れている。前半部の内容は,その働きをしっかりと認識できるものが多く,比較的理解しやすい。後半部は高次の働きについて触れていることから,やや概念的な説明に偏ってしまいがちなきらいが見られる。

個人的には,やはり前半部の知覚について触れている部分が最も興味深く感じられた。視覚や聴覚や触覚は,それぞれまったく異なる感覚のように思えて,実際には相互に情報を補い合うことによって知覚を構成している。また,それぞれの感覚には異なる特性が存在し,一方では知覚の不可能なことも,他方では敏感に知覚することが可能であったりする。例えば,1秒間に24回切り替わる画像(映画など)は,人間の目には連続したひとつの映像として感じられるが,1秒間に24回鳴るクリック音が連続したひとつの音として感じられることは無い。これは,これら二つの感覚が時間に関して異なる特性を備えていることを意味する。

この本のコンセプトは,様々な「マインドハック」を通じて己の脳の働きに触れることにより,その働きの複雑さを感じ取ることにある。その内容は何かの応用に役立てることができるというほど深くはないが,少なくとも,人が普段考えているよりも多くの「仕掛け」が脳には隠されているということを認識させるのに十分な内容ではある。

PMF

2006-03-13

C++ におけるメンバ関数へのポインタ (pointer to member function; PMF) は,単純な関数ポインタと比較して複雑な構造を持っている。仮想関数や多重継承への対応を暗黙に行う必要があるため,どうしても複雑にならざるをえない [msdn] [OldNewThing] 。

GCC には,独自の拡張機能として,オブジェクトと関連付けられたメンバ関数ポインタを,単純な関数ポインタに変換するという機能が用意されている [gcc] 。例えば次のようにして用いる。

class Base
{
public:
  void operation() { ... }
};
 
Base base_obj;
 
// 変換後の関数ポインタ型
// 第一引数がオブジェクトへのポインタになる
typedef void (*pmf_t)(Base*);
 
// メンバ関数ポインタの呼び出しを無理矢理キャストするような感じ
pmf_t pmf = (pmf_t)(base_obj.*(&Base::operation));
 
// 普通の関数ポインタとして使うことができる
pmf(&base_obj);

決まったオブジェクトに対してメンバ関数ポインタを頻繁に適用するような場合は,この機能を用いることによって幾分かの高速化を期待することができる。

また,この機能は仮想関数のオーバーライドの確認に用いることもできる。例えば次のコードのように,基底クラスにおいて空の仮想関数が定義されており,一部の派生クラスにおいてその実装がなされているとする。

class Base
{
public:
  virtual void operation()
  {
    // 基底クラスでは何もしない
  }
};
 
class DerivedA : public Base
{
  void operation()
  {
    // 何か特殊な処理
    ...
  }
};
 
class DerivedB : public Base
{
  // オーバーライドされない場合もある
};

このような設計はテンプレート・メソッド・パターン [rice] の一種としてよく見られるが,この関数がオーバーライドされていない場合は,空の関数を呼び出すだけの無駄な処理となってしまう。関数の呼び出しを行う際には,引数の積み上げやスタックの退避などが行われるため,たとえ空の関数でも呼び出しには一定のコストを伴う。また,プロセッサの微視的な挙動にも注目するならば,間接分岐 (indirect branch) の実行によるスループットの低下や,分岐先予測ミスに伴うパイプライン・ストールの発生なども考えられる。

このような事情から,オーバーライドされていない場合には,関数の呼び出し自体をスキップするようにしてしまいたい。オーバーライドされているかどうかの判定は,前出の関数ポインタへのキャストを用いれば,関数ポインタの比較として実装することが可能になる。

void call_operation(Base* pobj)
{
  pmf_t pmf_base = (pmf_t)(&Base::operation);
  pmf_t pmf_pobj = (pmf_t)(pobj->*(&Base::operation));
 
  if (pmf_pobj != pmf_base) pmf_pobj(pobj);
}

この手法による高速化は,オーバーライドの頻度が低いほど効果が高い。逆に,オーバーライドされることの方が多い場合は,かえって処理を増やしてしまう可能性があるため,用いない方がよいと考えられる。

もし,オーバーライドされる頻度が非常に低いと判明しているならば,次のような分岐予測ヒントを挿入することにより,高速化の効果を高めることができる。

if (__builtin_expect(pmf_pobj != pmf_base, false)) pmf_pobj(pobj);

この高速化の効果は,対象となる実行環境における仮想関数呼び出しコストの大きさによっても異なる。昨今のアーキテクチャでは間接分岐のコストが相対的に高まる傾向にあるため,新しいプロセッサほど高い効果を期待することができるかもしれない。手元にある Intel 系のプロセッサで試してみた限りでは,比較的良好な結果を得ることができた。

Spore

2006-03-14

Will Wright 氏が GDC 2005 において開発中のタイトル "Spore" のプレゼンテーションを行ってから1年が経とうとしている。その時の映像は GDCTV のページ [GDCTV] からダウンロードすることができる。あるいは Google Video 上でも閲覧することができる [Google] (ただし,この転載が許可を得たものであるかどうかは分からない)。

Spore のゲーム内容は恐ろしいほどの広がりを持っている。最初は原始生物の生存競争をテーマとした内容から始まって,次は文明の発展をテーマとした内容へと変化し,最終的には銀河を舞台とした広大な「箱庭」へと辿り着く。その途方も無いスケール感は,イームズの "Powers of Ten" [PowersOf10] を彷彿とさせるものがある。

その中で描かれる世界は手続き的に生成されており,「可能性の空間」が許す限り無限の展開を提供すると言う。この映像を観ていると,そのうちのどこまでが「仕込み」なのだろうかと不思議に思う。エディターを使って生物のデザインを自在に変化させる辺りなどは,驚くほどの可能性の広がりを見せてくれるが,果たしてその広がりはどの程度まで許容されており,どの程度までゲーム内容にフィードバックされるものなのだろう。

その仕様はどうなっているのか,あるいは,もし自分ならばどうするか,想像しながら観てみると面白い。

Code Review

2006-03-16

Hacknot. "In Praise of Code Reviews".

多くのタイプの職業には,制作物を世へ送り出す前に,制作した本人以外がチェックを行うという工程が存在する。例えば,文筆家の書いたものは編集者がチェックを行い,エンジニアが設計したものは検査官がチェックを行う。ソフトウェア開発の場合は,いわゆる「コードレビュー」がこの工程に相当すると考えられる。

レビューはコードに含まれる欠陥を発見するのに効果的な手法であるとされる。単純なウォークスルーを行うだけでも多くの欠陥を発見することができるほか,インスペクション [BCM] のような形式化された手法を導入すれば,非常に高い効率で欠陥を発見することができる。その効率の高さは,テストコードを用いた場合の効率を越えるともされる [IPA1] [IPA2] 。

このようにレビューは効率の高い欠陥発見の手法であるにも係わらず,その普及率は依然低いままであると Ed 氏は指摘する。なぜソフトウェア開発者はレビューに対して積極的になることができないのだろうか? それには心理的な働きがあると考えられる。

例えば,既に完成して動作確認も取れたコードを,今まさにコミットしようとしているとする。ここで敢えてコミットを踏みとどまりレビューへと回すのと,あるいはさっさとコミットして次の仕事に着手するのとでは,どちらが魅力的な選択のように思われるだろうか? このコードは,少なくともコーディングを行った本人にとっては,間も無く完成を迎えるものとして認識されている。これを踏みとどまり,他人の厳しい批評眼の前に晒し,そのフィードバックから修正の義務を負い,完成からまた一歩遠ざけるというのは,なかなか気持ちの良いことのようには思えない。プログラマにとって一つのコードをコミットするという行為には儀式的な意味合いがあり,そこから得られる達成感には抵抗し難き魅力がある。その達成感を得たいという欲求を抑制するには,ある種の理性が必要とされる。

しかし,ここでレビューを避けて欠陥を埋もれさせてしまえば,その欠陥はいずれ大きな問題となって己の身に返ってくる可能性がある。長期的な視点に立てば,この時点でレビューを行うことに利点があるのは明らかであり,最終的なプロダクトのスケジュールを守るためにも必要とされる行為であると考えられる。しかし,そのような長期的な視点を持たずに,目先の事象にばかり囚われてしまうと,レビューを行うことの利点も見えなくなってきてしまう。

ところで,レビューを行う場には,チームの管理者は出席しない方が良いとする指摘がある。これは,レビューの内容が人事的な評価に用いられるのを避ける(あるいは「評価に用いられるのではないか」という疑念を避ける)という意図がある。また,レビュー対象となるコードを書いた本人も出席しない方が良いとする指摘もある。これは,レビューが「コードに対するレビュー」から「コードを書いた本人に対するレビュー」に変化してしまうことを避けるためであるとされる。これらの指摘は,コードから制作者の人格を切り離すという点において共通しており,その切り離しがレビューを成功させる上で重要な前提となることが分かる。

Having Friends Who Disagree

2006-03-20

One Man Hacking. "The Importance of Having Friends Who Disagree".

エッセイストの Paul Graham 氏は,事業を興すならば一人でやるよりも複数人の方が良いと勧める [PaulGraham] 。なぜ一人ではいけないのだろう? 曰く,アインシュタインのような天才でさえ,自分のアイデアを投げかける対象を必要としていた。アイデアとは,それを人に説明する過程において洗練されるものである。また,それには適度な「手ごたえ」が必要とされる。彫刻家が木を彫るには,木に適度な「手ごたえ」が無くてはいけない。それに似ていると言う。

では,その「アイデアを投げかける対象」として相応しい人物とは,どのような人だろう。例えば ― 自分の信念を持っている人,自分の考えを述べる能力を持っている人,相手の話に耳を傾ける気構えがある人,自我で信念を束縛することの無い人,然るべきときには信念を変える余地を持っている人,等々……。

自分と同じ考えを持つ人とだけ働くのは楽なことかもしれない。自分と同じ信念を持つ人とだけ話し合うことは楽しいかもしれない。あるいは,人の力を借りずに自分の頭の中だけで何かを片付けることができれば,それが最も手っ取り早いと感じるかもしれない。しかし,そういった一方的な視点は,世界の見え方を歪ませてしまう。本来見えるはずの過ちをも見えなくしてしまう。その歪みを正すには,常に自分と異なる視点を受け入れるよう努力しなければならない。

もし,常に自分の意見に反対する人が周囲にいるならば,その存在を疎んではいけない。もしその人が,単なる好き嫌いや自我やイデオロギーからではなく,筋の通った己の考えから反対しているのならば,その存在を大切にした方がいい。自分の考えは,その人に説明をする過程で洗練されていく。そしてもし,最終的に両者が納得のいく結論に辿り着くことができたならば,それはこの上なく素晴らしいものになっているに違いない。

C++ Templates are Turing Complete

2006-03-23

C++ のテンプレートは,単に型の総称性 (genericity) を与えるだけでなく,様々な式の評価をコンパイル時に行うことを可能にする。部分的な特殊化 (partial specialization) や再帰的な構文を駆使すれば,条件分岐やループを組むことさえも可能になる。これらのテクニックは「テンプレート・メタプログラミング」 (template metaprogramming) として知られる [Veldhuizen1] 。テンプレートによるメタプログラミングは,例えば Boost のようなテンプレートライブラリにおいても各所で用いられており,汎用性と実行時性能の両立に寄与している [MPL] 。

このように, C++ のテンプレートはそれ自体をひとつのプログラミングの手段として見ることができる。それでは,プログラミングの手段としての C++ のテンプレートはチューリング完全 [Wikipedia] であると言えるだろうか? Todd Veldhuizen によれば,テンプレートをインスタンス化 (instantiation) する際の意味体系 (semantics) が形式的に定義されていない以上,厳密な証明は困難であるとされている [Veldhuizen2] 。ただし,インスタンス化の回数に制限が無いとすれば,これをチューリング完全であるとみなすことはできる。論文中には簡単なチューリングマシンの実装例が示されており,どのようなチューリングマシンも基本的にはその手法の拡張によって実装可能であることが分かる。

仮に C++ のテンプレートがチューリング完全であるとすると,チューリングマシンの停止問題 [Wikipedia] より,テンプレートのインスタンス化が有限実行時間内に完了するかどうかを判定することはできない。つまり,どのような C++ コンパイラも,与えられたプログラムがコンパイル可能であるかどうかを自動的に判定することは原理的に不可能であるという事実を示している。

帰結1. インスタンス化に制限が無い場合,与えられたプログラムをコンパイルする際に, C++ コンパイラが停止するかどうかを決定することはできない。

C++ の標準規格ではこの種の問題を軽減するために,テンプレートの再帰的なインスタンス化を最低で 17 回までサポートすればよいことになっている。ただし, 17 回の再帰でもコンパイラに十分な負担を与えることは可能ではある。例えば,論文にある以下のコードでは,定数 z の右辺を評価するために 517 回(約 7600 億回)のインスタンス化が発生するため,現状のコンパイラでは処理することが事実上不可能となっている。

template<int Depth, int A, typename B>
struct K17 {
  static const int x =
    K17<Depth+1, 0, K17<Depth,A,B> >::x
  + K17<Depth+1, 1, K17<Depth,A,B> >::x
  + K17<Depth+1, 2, K17<Depth,A,B> >::x
  + K17<Depth+1, 3, K17<Depth,A,B> >::x
  + K17<Depth+1, 4, K17<Depth,A,B> >::x;
};
template<int A, typename B>
struct K17<16,A,B> {
  static const int x = 1;
};
static const int z = K17<0,0,int>::x;

[via C++ Truths]

UltraSPARC T1

2006-03-27

Poonacha Kongetira, Kathirgamar Aingaran, Kunle Olukotun. Niagara: A 32-Way Multithreaded Sparc Processor. IEEE Micro, Vol. 25, No. 2, pp.21-29.

Sun Microsystems の UltraSPARC T1 プロセッサ(コードネーム "Niagara") [Sun] は,高い並列性と省電力性を特徴としている。コア毎に 4 本のハードウェアスレッドをサポートしており,そのコアを 8 個搭載することによって,計 32 本のハードウェア・マルチスレッディングを実現する。それでいて消費電力は約 72W と,サーバー向け製品群の中では比較的低いレベルに抑えられている(例えば UltraSPARC IV の消費電力は 108W に達する)。

また,興味深いことに UltraSPARC T1 の設計は "OpenSPARC" プロジェクトとして GPL の下に配布されることになった [ZDNet] 。ソースの配布は今月 21 日から開始されており, SunSource.net から Verilog コード [Wikipedia] やテスト環境をダウンロードすることができるようになっている。

デュアルコアが主流の世の中にあって, 8 コア 32 スレッドというのはかなり大胆な発想のように思える。この設計は,命令レベルの並列性 (ILP; Instruction Level Parallelism) よりもスレッドレベルの並列性 (TLP; Thread Level Parallelism) を重視した末の結論であることが記事より読み取れる。

TLP を重視する根拠としては,サーバーアプリケーションの特性が挙げられる。サーバーアプリケーションの分野では非常に大きなデータセットを扱うために,メモリ参照の局所性が低下する傾向にある。メモリ参照の局所性が低下すると,キャッシュミスの確率が高まり,結果としてメモリ参照による遅延がスループットを低下させることになる。また,データに依存した分岐が多いこともパフォーマンス低下の要因として挙げられる。データに依存した分岐は予測が難しく,予測ミス時に発生する遅延がスループットを低下させることになる。

ハードウェア・マルチスレッディング (fine-grained multithreading) は,これらの遅延によるスループットの低下を相殺する目的で用いられる。命令毎に実行するスレッドを入れ換えるため,単一スレッドに注目した場合の実行速度は低下する恐れがあるが,スレッド側から見た「見かけ上の遅延の量」は大きく減少する。昨今のプロセッサでは常に高い割合で遅延が発生しているため,多くの場合においてはスループットの向上が期待される。

幸いなことに多くのサーバーアプリケーションはスレッドによる並列性をサポートしているため,ソフトウェア面での支援も受けやすい条件にある。このような事情から,無理に ILP を高めるために回路の複雑化・大規模化を招いてしまったり,クロック速度を高めるために消費電力・発熱量の増大を招いてしまうよりも, TLP を推し進めることによってコア面積あたりの性能や消費電力あたりの性能を高めた方が有利な選択となりうることが分かる。

懸念点としては,コア毎の L1 データキャッシュが 8KB と比較的低めに設定されていることが挙げられる。これは,例えば UltraSPARC IV には 64KB の L1 データキャッシュが搭載されていることなどと比較すると,かなり低い水準であることが分かる。メモリ参照の遅延は並列性によって相殺されるという思想からすれば, L1キャッシュが減らされるのはもっともな選択かもしれないが,果たしてその遅延を隠蔽するのにコアあたり 4 スレッドが十分であるかどうかという点については量りかねる部分がある。

ハードウェア・マルチスレッディングは,特定の条件化においてはスループットの向上が期待できるものの,逆の条件化においてはスレッド間の資源の食い合いからスループットが低下する恐れもある。個人的な経験では,メモリアクセス頻度の高いスレッドが同時に動作する場合は,キャッシュの汚し合い(スラッシング)からスループットの低下が引き起こされることが多いように思われる。逆に,命令間の依存性や分岐予測ミスからスループットが低下している場合においては,ハードウェア・マルチスレッディングによる遅延の隠蔽が効果を発揮するように思われる。ただし,これらの経験はコアあたり 2 スレッドの場合に基づくものであるため,これが 4 スレッドの場合にどのような効果を導き出すかという点については,やはり経験からは量りかねる。

Trusting Trust

2006-03-29

Ken Thompson. Reflections on Trusting Trust.

UNIX の生みの親である Ken Thompson 氏は,その功績により 1987 年の ACM チューリング賞を受賞した。その受賞の際に, "Reflections on Trusting Trust" (「信用を信じることに関する考察」)と題された有名な講演を行っている。この講演において氏は,ソースコードの入手性がセキュリティの保証とは必ずしも結びつかないことを説明している。

講演によると,氏は UNIX の C コンパイラに,ある「仕掛け」を組み込んでいる。その仕掛けとは, "login" プログラムに相当するソースコードが入力された場合に,出力するバイナリコードの中に「バグ」を組み込むというものであった。その「バグ」とは,ある特定のパスワードが入力された場合に,本物のパスワードと同じようにログインを許してしまうというものであった。「バグ」というよりも,ありていに言えば「バッグドア」である。

このような単純なバックドアは,ソースコードを注意深く読み解けば見つけることができる。そこで氏は,第三者の発見から逃れるために,もうひとつの「仕掛け」を C コンパイラに組み込んでいる。その仕組みとは, C コンパイラ自身のソースコードが入力された場合に,出力するバイナリコードの中にこれらの「仕掛け」を組み込むというものであった。こうして作られたコンパイラは,ソースコードの中に「仕掛け」が無くても,「仕掛け」を含んだバイナリコードを出力するようになる。あとは,「仕掛け付き」のバイナリコードと「仕掛け無し」のソースコードを組にして配布すれば良い。

更に入念なことに,氏はディスアセンブラについても同じような「仕掛け」を組み込んでいる [Wikipedia] 。そのため,誰か非常に疑り深い人がディスアセンブリからの解析を行ったとしても,「仕掛け」が見えてくることは無い。ここまで来ると,バックドアの存在を第三者が知る可能性は限りなく少なくなり,誰もがその信頼性を疑うこと無く利用を続けることになってしまう。

このバックドアを含んだ UNIX は,テストケースとしてベル研究所内部で使用されたものの,外部に広められることは無かったとされている [Wikipedia] 。外部でこのバックドアが発見されたとの噂話もある [JargonFile] が,信憑性はあまり無い。当時のコミュニティの狭さを考えれば,内部用のパッケージが外部に流出したという事態も考えられないわけではないが……。

David Wheeler 氏によれば,「信頼することのできるコンパイラ」がひとつ存在すれば,そのコンパイラを利用した二重チェックを行うことによって,「仕掛け」の存在を見抜くことが可能であるとされている [Wheeler] 。ただし,このチェック方法を用いるには,チェック対象となるコンパイラのソースコードが「信頼できるコンパイラ」によってコンパイル可能であることが前提となる。ソースコード内で処理系に依存する記述などが用いられている場合には,この前提が破綻する。そして何よりもまず,「信頼できるコンパイラ」を入手するという難題をクリアしなければならない。そもそもそれが出来れば苦労しないという感もある。

SomethingManager

2006-03-30

Cardboard.nu. Naming Java Classes Without a 'Manager'.

Coding Horror. I shall call it.. SomethingManager.

ふとコードベースを見回してみると,「なんとか Manager クラス」がそこら中に溢れていることに気付く。例えば ScreenManager, AnimationManager, EntityManager, TextureManager, 等々……。 "Manager" という接尾語は,「何かを管理する」という機能を表しているものと考えられるが,この「管理する」という表現は非常に曖昧な意味を持つもののように感じられる。「管理」とは,具体的には一体どのような処理を行うことを指しているのだろう?

例えばこれが "Builder" であれば,何かを生成することが目的であることが分かる。 "Pool" であれば,何かを蓄積することが目的であることが分かる。 "Registry" であれば,何かを登録することが目的であることが分かる。それでは,これら全てをまかなうクラスだとしたら? それこそ "Manager" という名前が相応しいかもしれないが,それはひとつのクラスに機能を集約し過ぎている。「ひとつのクラスが扱う問題の領域はひとつに限定する」という基本的なクラス設計の約束事を守るべきではないだろうか。

このように,クラス名に "Manager" という接尾語を用いていることは,そのクラスの設計に不備があることを暗に告げていると考えることができる。このような,クラス名から伝わってくる「兆候」 ― いわゆる "code smell" [Wikipedia] は,他にも幾つか見つけることができる。例えば "Object", "Handler", "Data" などがこれに含まれる [C2Wiki] 。これらの接尾語をクラス名に見つけたならば,そのクラスの設計を見直すことを考えた方が良いかもしれない。