miura1729の日記

yarv2llvmでのduck typingの続き

22:53 |

クラスのアドレスから配列のインデックスを求めるメソッドを生成するプログラムを作ってみました。

こんな感じのメソッドを作ることができます。

def klass2idx(klass)
  add = ((klass.__id__ >> 1) << 2)
  add = add - 268622760
  functab = [:io, :array, :fixnum, :string]
  functab[(((add >> 14) - 1) >> 32) + 1 + (((add >> 15) - 1) >> 32) + 1 + ((add / 61360 - 1) >> 32) + 1]
end

これで、IO, Array, Fixnum, Stringを渡すと、それぞれ0, 1, 2, 3, 4をインデックスで求めて、funtabの内容:io, :array, :fixnum, :stringを返します。このメソッドはこのまま実行しても動きません。最後に示すプログラムで生成させなければダメです。

yarv2llvmではこんな感じのコードをllvmで生成させて、実行時のクラスのアドレスから呼び出すべき関数を求めようと考えています。

多分、inline method cacheを使っても動的なメソッド起動より速いと思いますが(追記: キャッシュがヒットしたらそんなわけ無い)、割り算の数によっては遅いかも知れないです。「ハッカーの楽しみ」に出ていた割り算を掛け算で実現するアルゴリズムが使えるかなと考えています。

もっと将来は、呼び出すべきメソッドのインデックスの決定を別コアで投機的に実行することが可能かなと思います。

テストをするとこんな感じでうまく行くようです。

[Fixnum, Array, String, IO].each do |c|
  print klass2idx(c)
  print "\n"
end

結果です。

fixnum
array
string
io

ソースコード全体です。テストも含んでいます。

def make_method_call(recvs)
  recv_addr = []
  addr2func = {}
  recvs.keys.each do |ele|
    addr = ((ele.__id__ >> 1) << 2)
    recv_addr.push addr
    addr2func[addr] = recvs[ele]
  end
  recv_addr.sort!
  functab = []
  recv_addr.each do |ele|
    functab.push addr2func[ele]
  end

  recv_addr_diff = recv_addr.map { |ele|
    ele - recv_addr[0]
  }

  expterms = []
  recv_addr_diff.each_cons(2) do |ele|
    n = 1
    i = 0
    while n <= ele[1] do
      n = n << 1
      i = i + 1
    end
    n = n >> 1
    i = i - 1
    if n > ele[0] then
      expterms.push "(((add >> #{i}) - 1) >> 32) + 1"
    else
      expterms.push "((add / #{ele[1]} - 1) >> 32) + 1"
    end
  end
  <<"EOS"
def klass2idx(klass)
  add = ((klass.__id__ >> 1) << 2)
  add = add - #{recv_addr[0]}
  functab = #{functab}
  functab[#{expterms.join(' + ')}]
end
EOS
end

met =  make_method_call({Fixnum => :fixnum, 
                          Array => :array, 
                          String => :string, 
                          IO => :io})
print "Generated method\n"
print met
eval met
print "\n-- test ---\n"
[Fixnum, Array, String, IO].each do |c|
  print klass2idx(c)
  print "\n"
end

追記

割り算の代わりに引き算でOKでした。http://github.com/miura1729/yarv2llvm/tree/dynamic_type/jikken/method_select.rb

においておきます。