2007-10-30 [長年日記]
λ. “Faster laziness using dynamic pointer tagging” by Simon Marlow, Alexey Rodriguez Yakushev, Simon Peyton Jones
を読んだ。
これは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%程度のメリットがあったが、現在では正味ではマイナスだとか。 実行環境も変わってきているんだねぇ。
