天泣記

MurmurHash で大量の衝突を意図的に起こせるか考えてみる。

コードの冒頭の以下のコードで String をスキャンしてハッシュ値を求めている。(この後に 4バイトで割り切れない部分の処理やらなんやらがあるが、そこは繰り返しじゃないので興味がない)

h += 0xdeadbeef;

while(len >= 4) {
    h += *(unsigned int *)data;
    h *= m;
    h ^= h >> r;

    data += 4;
    len -= 4;
}

ここで、h の初期値は 0 なので、ループ開始時には 0xdeadbeef である。(m と r は定数で、それぞれ 0x7fd652ad, 16 である)

もし、ループが何回か回って、h が 0xdeadbeef に戻ってくるようなデータをひとつ見つけられれば、そのデータを持つ文字列は空文字列と等しいハッシュ値を持つ。そして、その文字列を任意回繰り返したものも等しいハッシュ値を持つ。つまり、ある長さ以下の文字列に限定すれば、その長さに比例する数のハッシュ値の等しい文字列をつくり出せる。

もし、0xdeadbeef に戻ってくるデータをふたつ見つけられれば、それらを組み合わせることができる。組合せにより、ある長さ以下の文字列に限定すれば、その長さの指数関数に比例する数のハッシュ値の等しい文字列をつくり出せる。

とりあえず一回の繰り返しでできるかと調べてみると、(2**32 は問題なく brute force で調べられるので) "\x9b\x2c\x93\x5d" という文字列がそうなるようだ。

% ruby -ve 'p "\x9b\x2c\x93\x5d".hash, "".hash'
ruby 1.9.0 (2008-03-12 revision 15755) [i686-linux]
212676728
212676728

ここで 212676728 が 0xdeadbeef じゃないのはハッシュ関数がループの後で値をいじっているからである。

ひとつしかないとすると、これだけだと長さに比例するくらいしか生成できない。もっとたくさん生成するには一回の繰り返しだけではだめなようである。

そうすると二回の繰り返しであるが、2**64 は brute force では歯が立たない。力ずくではなく、頭を使わないといけないようだ。

繰り返しの中のハッシュ値を更新するコードをもっとちゃんと調べてみよう。更新するんじゃなくて古い値 h1 から新しい値 h2 を計算するようにコードを変えたものを以下に示す。

t1 = h1 + d
t2 = t1 * m
h2 = t2 ^ (t2 >> r)

とりあえずやりたいのは、h1 と h2 から d を求めることである。まず、最初の式で移項して d について解く。

d = t1 - h1

というわけで、残りの式を t1 について解ければいい。

h2 と t2 の関係を考えると、32bit 符号なし整数の、上位 16bit はそのままにして、下位 16bit を上位 16 bit と xor するようになっている。上位 16bit はそのままなので、もう一回同じことをすれば元の値に戻る。とするとこうである。

t2 = h2 ^ (h2 >> r)

あとは、t2 から t1 を求められればいい。ここで m = 0x7fd652ad で、2**32 を法とした計算なので、これは一次合同方程式である。

t2 = t1 * 0x7fd652ad    (mod 2**32)

0x7fd652ad と 2**32 は互いに素なので、t2 をひとつ決めれば、t1 はひとつ決まる。

0x7fd652ad の (2**32 を法とした) 逆数は 0x8c4ce125 なので、両辺に 0x8c4ce125 をかけて t1 について解ける。(0x8c4ce125 は brute force で探したのだが、もっとましな方法があるのではないかという気がする)

t2 * 0x8c4ce125 = t1 * 0x7fd652ad * 0x8c4ce125          (mod 2**32)
t2 * 0x8c4ce125 = t1 * (0x7fd652ad * 0x8c4ce125)        (mod 2**32)
t2 * 0x8c4ce125 = t1 * 1                                (mod 2**32)
t2 * 0x8c4ce125 = t1                                    (mod 2**32)
t1 = t2 * 0x8c4ce125                                    (mod 2**32)

と、いうわけで

d = (h2 ^ (h2 >> r)) * 0x8c4ce125 - h1

である。

h1 == h2 == 0xdeadbeef とすると、

d = 0x7a09aff25d932c9b = 0x5d932c9b

であり、"\x9b\x2c\x93\x5d" を little endian として解釈したものに等しい。

h が一回で 0xdeadbeef -> 0xdeadbeef と変化するのはこのひとつしかないわけであるが、二回なら、たとえば 0xdeadbeef -> 0 -> 0xdeadbeef とか、0xdeadbeef -> 1 -> 0xdeadbeef とかが考えられる。まぁ、2**32個くらい。

具体的に 0xdeadbeef -> 0 -> 0xdeadbeef な文字列を求めてみると、

h1 = 0xdeadbeef, h2 = 0 として d = 0x21524111 となり、h1 = 0, h2 = 0xdeadbeef として d = 0x3c40eb8a となる、

これを little endian に並べて hash を求めるとちゃんと衝突する。

% ruby -e 'p "\x11\x41\x52\x21\x8a\xeb\x40\x3c".hash'
212676728

とすると、長さ 8バイト限定で、2**32 個のハッシュ値の等しい文字列が生成できる。

長さを 12 バイトにすれば 0xdeadbeef -> X -> Y -> 0xdeadbeef として、X, Y それぞれを 2**32 個選べるので、2**64 個生成できる。

あ、繰り返さないんであれば、0xdeadbeef に戻さなくてもいいかな。

さて、可視化はともかくとして、キャッシュである。

n*n の正方行列の積 a = b * c を単純に書けば、以下のようになる。a の各要素は 0 に初期化済ということにしよう。

n.times {|i|
  n.times {|j|
    n.times {|k|
      a[i,j] += b[i,k] * c[k,j]
    }
  }
}

最内ループの中では、b, c, a の要素を読んで、a の要素に書き戻す。キャッシュの観点からいえば、最後の a の要素の書き戻しでそれがキャッシュに載っている (キャッシュヒットする) のは明らかなので、以降では無視することにする。

そうすると、a, b, c の各行列の各要素のアクセス回数はそれぞれ n回である。1箇所に n回もアクセスするので、キャッシュが有効に働いていただけるとありがたい。

とりあえず各箇所におけるアクセス間隔だけを考えることにして、キャッシュライン等は気にしないことにしよう。

例えばキャッシュのサイズを、行列全体が入る程には大きくない (つまり n*n より小さい) という状況を考える。そうすると、とりあえず c の要素のアクセスは必ずキャッシュミスすることがわかる。c[k,j] の添字 k, j は内側の 2重ループなので、毎回変化し、同じ添字が出てくるのは n*n 回間隔である。そうすると、行列全体はキャッシュに入らないと想定したので、前回アクセスしたときのキャッシュは既に消えており、キャッシュミスとなる。

キャッシュのシミュレーションをしてみよう。無限に大きなキャッシュを考えて、Cell のリストとして実現する。ある場所 (Cell) にアクセスしたとき、キャッシュ内で Cell を並び替え、アクセスした Cell をリストの先頭 (一番最近アクセスされたことを意味する場所) に動かす。そのときに、動かす前にどのくらい古いところに位置していたかを記録する。あるキャッシュサイズを決めると、そのサイズよりも古いところへ移動してしまった Cell は LRU でキャッシュから破棄されたものとみなせる。つまり、動かす前の場所がキャッシュサイズよりも古いところだったときがキャッシュミスと判断できる。

ここで、あるキャッシュサイズを決めたときに、キャッシュヒットとキャッシュミスの割合がどうなるか知りたい。トータルでアクセスが 3*n**3 回なのはわかっているので、キャッシュサイズに対するキャッシュヒットの数がわかればいい。そのためには、あるキャッシュサイズに対して、そのキャッシュサイズ以下の古さのアクセスの数を数えればいい。

class Cell
  @list = Object.new
  class << @list
    attr_accessor :next
  end
  @list.next = nil

  def Cell.register(cell)
    cell.next = @list.next
    cell.prev = @list
    cell.prev.next = cell
    cell.next.prev = cell if cell.next
  end

  def Cell.access(cell)
    cell.prev.next = cell.next
    cell.next.prev = cell.prev if cell.next

    cell.next = @list.next
    cell.prev = @list
    cell.prev.next = cell
    cell.next.prev = cell if cell.next
  end

  def Cell.age(cell)
    n = 0
    until cell == @list
      cell = cell.prev
      n += 1
    end
    n
  end

  def Cell.stat_accumulation
    hist = []
    num_cells = 0
    num_access = 0
    cell = @list.next
    while cell
      num_cells += 1
      num_access += 1 + cell.history.length # "1" is first access (cache miss)
      cell.history.each {|t|
        hist[t] ||= 0
        hist[t] += 1
      }
      cell = cell.next
    end
    a = 0
    hist.each_with_index {|h, i|
      h ||= 0
      a += h
      yield i, a
    }
  end

  def initialize
    @history = []
  end
  attr_reader :history
  attr_accessor :prev, :next

  def inspect
    "<#{@history.inspect}>"
  end

  def access
    if !defined?(@prev)
      Cell.register(self)
    else
      @history << Cell.age(self)
      Cell.access(self)
    end
  end
end

class Mat
  def initialize(n)
    @ary = Array.new(n) { Array.new(n) { Cell.new } }
  end

  def access(y,x)
    @ary[y][x].access
  end
end

def matmul_naive(n, a, b, c)
  n.times {|i|
    n.times {|j|
      n.times {|k|
        b.access(i,k)
        c.access(k,j)
        a.access(i,j)
      }
    }
  }
end

matmul_naive(n, a, b, c)

n = 32
a = Mat.new(n)
b = Mat.new(n)
c = Mat.new(n)
matmul(n, a, b, c)
Cell.stat_accumulation {|i, n| puts "#{i} #{n}" }

ここでは n=32 として、32*32 な行列の積をシミュレーションしている。n=32 なので、3*n**3 = 98304 がトータルなアクセス回数である。各要素の最初の一回のアクセスどうやってもキャッシュミスするのでそれを減じると 3*n**3 - 3*n**2 = 95232 がキャッシュヒットの最大となる。

素朴な行列積のキャッシュヒット

グラフを見ると階段状になっていて、3, 65, 1120 あたりで急速にキャッシュヒットが増えている。

行列全体が入らなければ c が常にキャッシュミスすると予測したが、行列全体というのは 32*32=1024 で、1120 での変化はきっとこれであろう。

65 での変化は、最内のループがまわり終わったときに b のキャッシュが一行ぶん残っているかどうかの境界であろう。

3は最内のループのひとまわりで a のキャッシュが 1要素残っているかどうかの境界であろう。

まぁ、理解はできるが、行列全体がキャッシュに入らない限り、1/3 のアクセスはキャッシュミスする、というのは悲しいわけだ。

というわけでヒルベルト曲線を使ってみよう。

def matmul_hilbert(n, a, b, c)
  nn = n.to_s(2).length
  hilbert_each(nn, 3) {|i, j, k|
    next if n <= i || n <= j || n <= k
    b.access(i,k)
    c.access(k,j)
    a.access(i,j)
  }
end

n = 32
a = Mat.new(n)
b = Mat.new(n)
c = Mat.new(n)
matmul_hilbert(n, a, b, c)
Cell.stat_accumulation {|i, n| puts "#{i} #{n}" }

素朴なのとヒルベルト曲線順な行列積のキャッシュヒット

これを見ると、行列全体がキャッシュに入らなくてもキャッシュヒットがずいぶんと増えることがわかる。

また、階段状じゃないので、キャッシュサイズを増やすとそれなりに性能があがる、という挙動が予想できる。

ただ、素朴なやりかただと、行列ひとつが入るくらい (1200程度) でキャッシュミスが最低に達するのに対し、ヒルベルト曲線順だと、行列3つがぜんぶ入るくらい (3100程度) にならないとそうならないようだ。

ところで、ヒルベルト曲線でキャッシュヒットが増えるのは、n*n*n の立方体から 8分割を繰り返して局所的に作業するからであるとすると、ヒルベルト曲線みたいに難しいことをしなくてもいいかもしれない。

たとえば、2進整数を 3bit 毎に i,j,k に割り当てていけば、8分割の繰り返しという性質は実現できる。こういうやりかたは (2次元で) Peano/Morton Curve, Quad Codes, Locational Codes, Z-ordering などといろいろな名前で呼ばれているらしい。

試してみよう。

def matmul_z_ordering(n, a, b, c)
  0.upto(2 ** (n.to_s(2).length * 3)) {|x|
    i = j = k = 0
    bit = 1
    while 0 < x
      i |= bit if x & 1 == 1; x >>= 1
      j |= bit if x & 1 == 1; x >>= 1
      k |= bit if x & 1 == 1; x >>= 1
      bit <<= 1
    end
    next if n <= i || n <= j || n <= k
    b.access(i,k)
    c.access(k,j)
    a.access(i,j)
  }
end

n = 32
a = Mat.new(n)
b = Mat.new(n)
c = Mat.new(n)
matmul_z_ordering(n, a, b, c)
Cell.stat_accumulation {|i, n| puts "#{i} #{n}" }

素朴なのとヒルベルト曲線順なのと Z-ordering な行列積のキャッシュヒット

ヒルベルト曲線よりもちょっとキャッシュヒットは少なくなる。ただ、難しいことをしなくてもこれだけのキャッシュヒットが出せれば十分だ、という考えかたはあるかもしれない。

ところで、LRU なキャッシュを双方向リストで実装したわけだが、Cell を先頭に移動するのは O(1) で済むのだが、ある Cell の場所を調べるのに先頭まで線形探索をしているのが悲しい。

ここはなにか木を使うべきだろう。

とりあえず rbtree を調べて見たが、そういう操作は見当たらない気がする。

天泣記

2008-03-01 (Sat)

2008-03-03 (Mon)

2008-03-04 (Tue)

2008-03-05 (Wed)

2008-03-07 (Fri)

2008-03-09 (Sun)

2008-03-12 (Wed)

2008-03-13 (Thu)

2008-03-15 (Sat)

2008-03-16 (Sun)

2008-03-18 (Tue)

2008-03-19 (Wed)

2008-03-20 (Thu)

2008-03-21 (Fri)

2008-03-22 (Sat)

2008-03-27 (Thu)

2008-03-28 (Fri)

2008-03-29 (Sat)

2008-03-30 (Sun)

2008-03-31 (Mon)