日々の流転

λ. 今日も慶早戦で学校は休み。

λ. 失業率5.3%っすよ。ウケケケケケッΨ(｀▽´)Ψ

λ. PrologのBoxモデルについてお勉強。

λ. ゆっけが日記をはじめた。

λ. 『私の救世主さま』 水無月すう

を読んだ。

λ. 言語の意味論の課題

苦戦中。

カテゴリ文法って結構扱いにくいなぁ。文脈自由文法と等価のはずなのに……

うぅむ、やっぱ単純化のために内包/外延と様相も外してしまおっかなぁ……

λ. 天才柳沢教授の生活

ドラマをやっているそうなので見た。

λ. 明符「東方の夜明け」

ZUN氏のトークショウ「東方の夜明け」を見るために明治大学の和泉キャンパスまで行ってきた。

λ. The Village of Headless Knight

人狼BBSと同様のゲームで、システムは若干異なるものの、画面構成と雰囲気は人狼BBSに非常に近い。現在βテスト中だそうです。最近、人狼BBSの方のサーバーがだいぶ重くなってしまってますし、次はこっちに参加するかも。

The Village of Headless Knightとは

欧米のパーティゲーム「汝は人狼なりや？」をベースとした 人狼BBS を参考に制作されたゲームです。

ここはある辺境の村。かつて戦争の最中に殺戮に狂った騎士達の首をはねて殺した過去をもつこの村では、首なし騎士の亡霊が自分の首を探して蘇るという言い伝えがある。そして今、その言い伝えが現実に・・・

あなたが村人なら魔物[首なし騎士]を見つけ出し退治しましょう。もしあなたが首なし騎士であったら、、村人を騙し村を滅ぼしてしまいましょう！

ここは村人達と首なし騎士のかけひきを楽しめるBBS（掲示板）です。人狼BBSさんを元にしていますのでノリがブラックなのはご了承ください。

λ. Rubyの配列を渡せる呼び出し

rb_apply()を使えばよいと思います。

rb_apply(rb_mKernel, rb_intern("printf"), args)

λ. “Faster laziness using dynamic pointer tagging” by Simon Marlow, Alexey Rodriguez Yakushev, Simon Peyton Jones

• <URL:http://research.microsoft.com/~simonpj/papers/ptr-tag/index.htm>

を読んだ。

これはGHCのcase式の新しい最適化に関する論文。 面白かったので、少し紹介。

例えば、以下のような関数があるとする。

map :: (a -> b) -> [a] -> [b]
map f xs = case xs of
             [] -> []
             (x:xs') -> f x : map f xs'

この関数が呼び出されたときには、大雑把には以下のように実行される。

• この関数はxsを呼び出して、
• xsは自身がwhnfになるまで実行したらリターンして、
• この関数はxsがどのコンストラクタの形かを調べて、対応する分岐を実行する

問題はxsが最初からwhnfの場合。この場合にはxsは即座にリターンするが、この呼び出し・リターンという間接ジャンプは分岐予測が効かず非常にコストが大きい。

それに対処するため、xsを呼び出す前にxsのinfo_tableを参照し、評価済みかどうかと、評価済みならどのコンストラクタかを調べ、もし評価済みであることが分かれば直接分岐先にジャンプするようにすることが考えられる。これがsemi-taggingで、OpteronとXeonで7.2%と9.4%の性能向上。

semi-taggingにも効率の悪い点があって、それは必要な情報を得るために遠くにあるinfo_tableを一度だけ参照し、キャッシュ汚染を引き起こす点。 これを改善するためにxsを指すポインタの下位ビットにそれらの情報をエンコードするのがpointer-tagging。 評価前のサンクが評価結果に書き換わったときには、そのサンクを指すポインターのタグを書き換えないと意味がないのだけど、これはガベージコレクションのタイミングでガベージコレクタが行う。 というのも、copying GC なのでどうせアドレスの書き換えは必要なので。 pointer-taggingを適用した結果、OpteronとXeonで13.7%と12.8%の性能向上。

あと、個人的に驚いたのは、vectored returns が最早有効ではないという話。 数年前のベンチマークでは正味5%程度のメリットがあったが、現在では正味ではマイナスだとか。 実行環境も変わってきているんだねぇ。