Cuckoo hashingによる多相インラインキャッシュの実験

追記 2008/12/31

http://lambda-the-ultimate.org/node/2259

PICについて面白そうな議論がありました。IOはメソッドルックアップにCuckoo hashingを使っているが、継承木を辿るため継承木のオブジェクト数に対して線形時間かかるようです。yarv2llvmでは継承を辿る作業も静的に行うつもりなので、定数時間で済むと考えているのですが、ちょっと心配になってきました。

追記終わり

Cuckoo hashingで多相インラインキャッシュ(PIC)を実現する場合、本当に大丈夫かなって思ったので実験してみました。

こんな感じの入力を与えると

{Array => :array_foo,
 String => :string_foo,
 Float => :float_foo,
 Hash => :hash_foo,
 Range => :range_foo,
 Object => :object_foo}

こんな感じの関数が出てきます。実際にはこのコードをllvmに変換してインライン展開することになります。

def select_method(klass)
  av = [:range_foo,:array_foo,nil,:object_foo,:hash_foo]
  bv = [nil,:string_foo,:float_foo,nil,nil]
  ak = [268633500,268654320,nil,268706160,268648480]
  bk = [nil,268691560,268668060,nil,nil]
  klassadd = ((klass.__id__ >> 1) << 2)
  ha = (klassadd / 20 + klassadd) % 5
  if ak[ha] == klassadd then
    return av[ha]
  end
  hb = ((klassadd / 21) + klassadd * 31) % 5
  if bk[hb] == klassadd then
    return bv[hb]
  end
  return nil
end

思ったより中身がつまっていて結構よさそうです。実行環境によって結果は変わってくると思いますが。
20と21で割る処理がネックになりそうですが、20は4*5に分解して、5で割るところを掛け算にすればよいし、21も3*7で２つの掛け算に分解できるかなと思います(アルゴリズムは「ハッカーの楽しみ」のものを使用)。
思ったより効果があるという印象です。fujita-yさんすばらしいアドバイスありがとうございます。

実験で作ったプログラムのリストです。

class CuckooHash
  PRIMES =  [ 
             3,
             5,
             7,
             8 + 3,
             17,
             16 + 3,
             32 + 5,
             64 + 3,
             128 + 3,
             256 + 27,
             512 + 9,
             1024 + 9,
             2048 + 5,
             4096 + 3,
             8192 + 27,
             16384 + 43,
             32768 + 3,
             65536 + 45,
             131072 + 29,
             262144 + 3,
             524288 + 21,
             1048576 + 7,
             2097152 + 17,
             4194304 + 15,
             8388608 + 9,
             16777216 + 43,
             33554432 + 35,
             67108864 + 15,
             134217728 + 29,
             268435456 + 3,
             536870912 + 11,
             1073741824 + 85,
             0
            ]
  
  def initialize(elements)
    es = elements.size
    @plimepos = 0
    PRIMES.each_with_index do |n, i|
      if es / 2 < n then
        @tabsize = n
        @primepos = i
        break
      end
    end
    
    @value = [Array.new(@tabsize), Array.new(@tabsize)]
    @key = [Array.new(@tabsize), Array.new(@tabsize)]
    @hfunc = [gen_hash_function_a(@tabsize), gen_hash_function_b(@tabsize)]
    fill(elements)
  end

  def emit_code
    <<-EOS
def select_method(klass)
  av = [#{(@value[0].map {|n| n.inspect}).join(',')}]
  bv = [#{(@value[1].map {|n| n.inspect}).join(',')}]
  ak = [#{(@key[0].map {|n| n.inspect}).join(',')}]
  bk = [#{(@key[1].map {|n| n.inspect}).join(',')}]
  klassadd = ((klass.__id__ >> 1) << 2)
  ha = (klassadd / 20 + klassadd) % #{@tabsize}
  if ak[ha] == klassadd then
    return av[ha]
  end
  hb = ((klassadd / 21) + klassadd * 31) % #{@tabsize}
  if bk[hb] == klassadd then
    return bv[hb]
  end
  return nil
end
EOS
  end
  
  def fill(elements)
    elements.each do |key, value|
      keyadd = ((key.__id__ >> 1) << 2)
      insert(keyadd, value)
    end
  end
  
  def insert(keyadd, value)
    while true
      @tabsize.times do 
        hv = @hfunc[0].call(keyadd)
        
        vala = @value[0][hv]
        keyadda = @key[0][hv]
        @value[0][hv] = value
        @key[0][hv] = keyadd
        if vala == nil then
          return true
        end
        keyadd = keyadda
        
        hv = @hfunc[1].call(keyadd)
        valb = @value[1][hv]
        keyaddb = @key[1][hv]
        @value[1][hv] = vala
        @key[1][hv] = keyadd
        if valb == nil then
          return true
        end
        keyadd = keyaddb
        value = valb
      end
      
      rehash
    end
  end
  
  def rehash
    ovalue = @value
    okey = @key
    @primepos += 1
    @tabsize = PRIMES[@primepos]
    @value = [Array.new(@tabsize), Array.new(@tabsize)]
    @key = [Array.new(@tabsize), Array.new(@tabsize)]
    @hfunc = [gen_hash_function_a(@tabsize), gen_hash_function_b(@tabsize)]
    [0, 1].each do |n|
      okey[n].each_with_index do |ele, i|
        if ele then
          insert(ele, ovalue[n][i])
        end
      end
    end
  end
    
  def gen_hash_function_a(size)
    lambda {|v|
      (v / 20 + v) % size
    }
  end
    
  def gen_hash_function_b(size)
    lambda {|v|
      ((v / 21) + v * 31) % size
    }
  end
end

c = CuckooHash.new({Array => :array_foo,
                    String => :string_foo,
                    Float => :float_foo,
                    Hash => :hash_foo,
                     Range => :range_foo,
                     Object => :object_foo})

code =  c.emit_code
print code
print "\n  --- OUTPUT --- \n"
eval code
[Array, String, Float, Hash, Range, Object].each do |klass|
  print "#{klass} -> #{select_method(klass)} \n"
end