日々の流転

λ. “Three Partition Refinement Algorithms” by Robert Paige and Robert Tarjan

20041122#p02 で「Paige-Tarjan の手続きってのはstabilizationのための効率的なアルゴリズムのことなのかな? (ぉぃ」とか書いたが、ようやく*1原典の論文読んで、アルゴリズムを理解した。載っている3つのアルゴリズムのうちの relational coarsest partition problem のためのアルゴリズムが「Paige-Tarjan の手続き」と書かれていたもの。

(後で書く)

確かにこれはムダが無くて速そうだ……

試しに Ruby で書いてみた。 paige-tarjan.rb

λ. 最近のRuby処理系の話

第341回PTTでやっていた、笹田さんの「最近のRuby処理系の話」を聞いてきた。 並列版の話など、とても面白かった。 以下は印象的だった話。

自動的なアフィニティの設定

スレッド間でのロックの取り合い(?)を防ぐために、監視スレッドがいて、閾値を超えたら自動的にアフィニティを設定して同一CPUに割り当てるとか。かっこいい!

インラインキャッシュの話

インラインキャッシュの話への首藤さんのツッコミは、最初は納得してしまったけど、よくよく考えたらそう簡単ではないような。例えば、以下のコードを考える。

class Foo
  def foo
    ...
  end
end

class Bar < Foo
end

x = Bar.new
2.times {
  x.foo
}

このとき、私の理解では以下のようになる。

• x.fooが一回目に実行されたとき、<Bar, Foo#foo> というキャッシュエントリが作られて、それへの参照がインラインキャッシュとして格納される。
• 次にx.fooが実行されたとき、x.classとBarとを比較して、それが一致するのでFoo#fooを直接呼び出す。

首藤さんのアイディアは私の理解では「エントリへの参照ではなくFoo#fooへの参照を直接インラインキャッシュに格納してしまう」というものだと思う。ただ、Foo#foo は Foo への参照は持っていても、Barへの参照は持っていないだろうから、x.classとの直接の比較が出来ないのではないだろうか?

ダミーのBar#fooを用意しておけば良いだけかも知れないけど。

64bit環境での浮動小数点数の即値化

結局、Rubyでは指数と仮数のどちらを削るのかは忘れてしまったが、「数値計算屋は0〜1付近に正規化するので、指数部を削っても結構大丈夫。指数部が沢山必要なのを書くのは馬鹿」というコメントが興味深かった。

関連リンクなど

• 最近の Ruby 処理系の話 - まめめも

λ. お菓子買いだめ

20080122#p01はやっぱり買いすぎだった。 まだ残っているので、今回は少なめに。