天泣記

2016-11-02 (Wed)

#1 整数をkeyにしてみる

とりあえず無駄に利用しているメモリは削るか、ということで、今までは key を文字列にしていたのを、整数にしてみた。

% ./ruby -rPAPI -e '
events = %w[PAPI_L1_DCM PAPI_L2_DCM PAPI_L3_TCM]
evset = PAPI::EventSet.new
evset.add_named(events)
puts "n,l1,l2,l3"
rep1 = 100
rep2 = 100
nn = 1.0
ns = []
while nn < 2e4
  ns << nn.to_i
  nn = nn*1.001
end
ns = ns * rep1
ns.shuffle!
GC.disable
ns.each {|n|
  h = {}
  h[h.size] = true while h.size < n
  l1sum = l2sum = l3sum = 0
  GC.start
  rep2.times {|i|
    k = rand(n)
    evset.start; evset.stop
    evset.start
    h[k]
    evrec = evset.stop
    l1sum += evrec[0]
    l2sum += evrec[1]
    l3sum += evrec[2]
  }
  l1mean = l1sum.to_f / rep2
  l2mean = l2sum.to_f / rep2
  l3mean = l3sum.to_f / rep2
  puts "#{n},#{l1mean},#{l2mean},#{l3mean}"
}' > hash-lookup-cache-intkey.csv

L1 cache miss は以下のようになった。うぅむ、なんですかねこの折れ線は。

hash-lookup-cache-intkey-l1.R:

library(ggplot2)
library(plyr)
d <- read.csv("2016-11/hash-lookup-cache-intkey.csv.xz")
dl1 <- ddply(d, .(n), colwise(mean, .(l1)))
p <- ggplot(dl1, aes(n, l1)) +
  geom_point() +
  scale_x_log10(breaks = 5*2**(0:24)) +
  ylab("mean(L1 cache miss)")
print(p)

hash-lookup-cache-intkey-l1.png

L2 cache miss は以下のようになった。これも折れ線になっている。

hash-lookup-cache-intkey-l2.R:

library(ggplot2)
library(plyr)
d <- read.csv("2016-11/hash-lookup-cache-intkey.csv.xz")
dl2 <- ddply(d, .(n), colwise(mean, .(l2)))
p <- ggplot(dl2, aes(n, l2)) +
  geom_point() +
  scale_x_log10(breaks = 5*2**(0:24)) +
  ylab("mean(L2 cache miss)")
print(p)

hash-lookup-cache-intkey-l2.png

L3 cache miss は以下のようになった。これは曲線のままだな。

hash-lookup-cache-intkey-l3.R:

library(ggplot2)
library(plyr)
d <- read.csv("2016-11/hash-lookup-cache-intkey.csv.xz")
dl3 <- ddply(d, .(n), colwise(mean, .(l3)))
p <- ggplot(dl3, aes(n, l3)) +
  geom_point() +
  scale_x_log10(breaks = 5*2**(0:24)) +
  ylab("mean(L3 cache miss)")
print(p)

hash-lookup-cache-intkey-l3.png

L1/L2 cache miss の折れ線はなんだろうな。周期から考えて、rehash に関係しているとは思うのだが。(最初の rehash の n=80 を含め、rehash の直前で miss が急激に増えているのはどういう理屈なのだろうか。

なお、key を変えても、miss が目立ち始めるサイズはたいして変わらず、理屈と合わないという点に関しては変化は見られなかった。

2016-10-31 (Mon)

#3 cache size

ところで、cache のサイズはどうだったかというと、以下のとおりである。(line-size * number-of-ways * number-of-sets)

で、Ruby の st.h や st.c をみると、ハッシュ表の根元の構造体は st_table というもので、以下のように定義されている。この構造体自体はハッシュ表毎にひとつで、ハッシュ表の要素数 n には依存しない。

struct st_table {
    const struct st_hash_type *type;
    st_index_t num_bins;
    unsigned int entries_packed : 1;
    st_index_t num_entries : ST_INDEX_BITS - 1;
    union {
        struct {
            struct st_table_entry **bins;
            void *private_list_head[2];
        } big;
        struct {
            struct st_packed_entry *entries;
            st_index_t real_entries;
        } packed;
    } as;
};

今考えている連鎖法の部分は big のところ (packed のところではない) である。bins が st_table_entry へのポインタの配列で、この配列は bin 毎に 1 word 消費される。連鎖法のリストの長さは 2.5 から 5 までをいったりきたりするので、中央の (2.5+5)/2=3.75 をとると、bins は n / 3.75 word の長さになる。

連鎖法のリストの要素である st_table_entry は以下のように定義されている。

struct st_table_entry {
    st_index_t hash;
    st_data_t key;
    st_data_t record;
    st_table_entry *next;
    struct list_node olist;
};

list_node は ccan/list/list.h に定義されていて、2 word である。

struct list_node
{
        struct list_node *next, *prev;
};

というわけで、st_table_entry は 6 word である。

昔、がちゃぴん先生のmalloc動画を見た記憶によれば、glibc の malloc はヘッダに 1 word 使っていたような気がする。とすると、st_table_entry を malloc すると 7 word となる。つまり、全体としては 7n word となる。

つまり 1要素あたり (7 + 1/3.75)n = 7.27n word となり、64bit 環境では 1 word が 8 byte なので、58.1 byte である。

cache の line size は 64 byte なので、それよりは少し小さい。

と、考えていいのだろうか。多すぎる気がする。L3 cache miss の測定では 5120でキャッシュの拡張によるmissの減少が観測されており、そのあたりで L3 cache からあふれていると考えられるので、なにか計算をまちがえている気がする。

key に(短い)文字列を使っていて、ひとつの文字列は 5 word (Ruby の 1 object) 消費するというのを考えても 8192*1024/((7+1/3.75+5)*8)=85482で、まだまだ大きい。(それに、ほとんどはhash値の不一致になるから、文字列のkeyにはほとんどアクセスしないと思うし。)

#2 もうちょっと大きなところまで測ってみる

L3 cache miss についてはちょうどハッシュの拡張による影響が表れ始めたところで測定が終わっていて、繰り返しというのは苦しいので、もうちょっと大きなところまで測ってみた。

% ./ruby -rPAPI -e '
events = %w[PAPI_L1_DCM PAPI_L2_DCM PAPI_L3_TCM]
evset = PAPI::EventSet.new
evset.add_named(events)
def fmt(n) "%10d" % n end
puts "n,l1,l2,l3"
rep1 = 100
rep2 = 100
nn = 1.0
ns = []
while nn < 2e4
  ns << nn.to_i
  nn = nn*1.001
end
ns = ns * rep1
ns.shuffle!
GC.disable
ns.each {|n|
  h = {}
  h[fmt(h.size)] = true while h.size < n
  l1sum = l2sum = l3sum = 0
  GC.start
  rep2.times {|i|
    k = fmt(rand(n))
    evset.start; evset.stop
    evset.start
    h[k]
    evrec = evset.stop
    l1sum += evrec[0]
    l2sum += evrec[1]
    l3sum += evrec[2]
  }
  l1mean = l1sum.to_f / rep2
  l2mean = l2sum.to_f / rep2
  l3mean = l3sum.to_f / rep2
  puts "#{n},#{l1mean},#{l2mean},#{l3mean}"
}' > hash-lookup-cache-rand2.csv

L1 cache miss は以下のようになった。同じような結果だが、右端で増加が加速している感じなのが面白い。

hash-lookup-cache-rand2-l1.R:

library(ggplot2)
library(plyr)
d <- read.csv("2016-10/hash-lookup-cache-rand2.csv.xz")
dl1 <- ddply(d, .(n), colwise(mean, .(l1)))
p <- ggplot(dl1, aes(n, l1)) +
  geom_point() +
  scale_x_log10(breaks = 5*2**(0:24)) +
  ylab("mean(L1 cache miss)")
print(p)

hash-lookup-cache-rand2-l1.png

L2 cache miss は以下のようになった。前と同じような結果だと思う。

hash-lookup-cache-rand2-l2.R:

library(ggplot2)
library(plyr)
d <- read.csv("2016-10/hash-lookup-cache-rand2.csv.xz")
dl2 <- ddply(d, .(n), colwise(mean, .(l2)))
p <- ggplot(dl2, aes(n, l2)) +
  geom_point() +
  scale_x_log10(breaks = 5*2**(0:24)) +
  ylab("mean(L2 cache miss)")
print(p)

hash-lookup-cache-rand2-l2.png

L3 cache miss は以下のようになった。やはり、5120 の次に 10240 でも miss が減るので、ハッシュの拡張が見えているのだと思う。

hash-lookup-cache-rand2-l3.R:

library(ggplot2)
library(plyr)
d <- read.csv("2016-10/hash-lookup-cache-rand2.csv.xz")
dl3 <- ddply(d, .(n), colwise(mean, .(l3)))
p <- ggplot(dl3, aes(n, l3)) +
  geom_point() +
  scale_x_log10(breaks = 5*2**(0:24)) +
  ylab("mean(L3 cache miss)")
print(p)

hash-lookup-cache-rand2-l3.png

というわけで、L1, L2, L3 cache について、連鎖法ハッシュ表というアルゴリズムの性質が表れた cache miss のグラフを描くことが可能であることがわかった。

#1 アドレスを固定しない

アドレスの変化で性能がいろいろ変わるというのはわかったが、普通は (少なくとも Ruby を使う状況では) 狙ったアドレスのメモリを使えるわけではないので、アドレスを選べないことを前提にして平均的な性能に着目するほうが現実的だろう。

(というわけで /proc/sys/kernel/randomize_va_space は 2 に戻して、ruby もソースを変更していないものに戻した。)

そういう性能を測るにはどうすっかな、と考えて、ハッシュをなるべく作り直すことにした。

いままでは最初に空ハッシュを作って、そのハッシュに少しずつ要素を加えながら測定していたのだが、これだと最初のころに加えられた連鎖法のリストの要素のアドレスはずっと変化しない。ハッシュを作り直せばリストも新しく作られて各要素のアドレスも変わるだろう。そうやって変えていけば、異なるサイズのハッシュの測定で相互の影響を避けられるだろう。(ただし、この結果、大きなハッシュの測定はとても長い時間がかかるようになるので、あまり大きなハッシュは測定できなくなる。)

さらに、あるサイズのハッシュを10000回ループで測定していたのも 100回ループを100回と分解して、ハッシュを100回作り直すようにした。ループを分解した結果、測定結果は100倍出力されるので、これはR側で平均をとることにしよう。平均の平均になってしまうが、各平均が一定数 (100個) の平均だから全体の平均がちゃんと求められるはずである。これで、ひとつのサイズのハッシュの測定でも、いろんなアドレスの場合を平均できる。

さらに、ハッシュを作り直すということは、小さいほうから順に測定する必要もない。そこで、測定順もランダムにしてみた。

% ./ruby -rPAPI -e '
events = %w[PAPI_L1_DCM PAPI_L2_DCM PAPI_L3_TCM]
evset = PAPI::EventSet.new
evset.add_named(events)
def fmt(n) "%10d" % n end
puts "n,l1,l2,l3"
rep1 = 100
rep2 = 100
nn = 1.0
ns = []
while nn < 1e4
  n = nn.to_i
  ns << n
  nn = nn*1.001
end
ns = ns * rep1
ns.shuffle!
GC.disable
ns.each {|n|
  h = {}
  h[fmt(h.size)] = true while h.size < n
  l1sum = l2sum = l3sum = 0
  GC.start
  rep2.times {|i|
    k = fmt(rand(n))
    evset.start; evset.stop
    evset.start
    h[k]
    evrec = evset.stop
    l1sum += evrec[0]
    l2sum += evrec[1]
    l3sum += evrec[2]
  }
  l1mean = l1sum.to_f / rep2
  l2mean = l2sum.to_f / rep2
  l3mean = l3sum.to_f / rep2
  puts "#{n},#{l1mean},#{l2mean},#{l3mean}"
}' > hash-lookup-cache-rand.csv

L1 cache miss は以下のようになった。ハッシュの拡張毎 (80, 160, 320, ...) に miss がいっきに減っては次の拡張まで増加していくという形がよく表れている。

hash-lookup-cache-rand-l1.R:

library(ggplot2)
library(plyr)
d <- read.csv("2016-10/hash-lookup-cache-rand.csv.xz")
dl1 <- ddply(d, .(n), colwise(mean, .(l1)))
p <- ggplot(dl1, aes(n, l1)) +
  geom_point() +
  scale_x_log10(breaks = 5*2**(0:24)) +
  ylab("mean(L1 cache miss)")
print(p)

hash-lookup-cache-rand-l1.png

L2 cache miss は以下のようになった。これもハッシュの拡張毎 (80, 160, 320, ...) に miss が減っては次の拡張まで増加していくという形がよく表れている。

hash-lookup-cache-rand-l2.R:

library(ggplot2)
library(plyr)
d <- read.csv("2016-10/hash-lookup-cache-rand.csv.xz")
dl2 <- ddply(d, .(n), colwise(mean, .(l2)))
p <- ggplot(dl2, aes(n, l2)) +
  geom_point() +
  scale_x_log10(breaks = 5*2**(0:24)) +
  ylab("mean(L2 cache miss)")
print(p)

hash-lookup-cache-rand-l2.png

L3 cache miss は以下のようになった。5120でmissが減っているのはハッシュの拡張によるものかもしれないが、それより小さい部分でははっきりしない。あと、1280と2560直後でmissがいったん減ってから増加する傾向なのは奇妙である。

hash-lookup-cache-rand-l3.R:

library(ggplot2)
library(plyr)
d <- read.csv("2016-10/hash-lookup-cache-rand.csv.xz")
dl3 <- ddply(d, .(n), colwise(mean, .(l3)))
p <- ggplot(dl3, aes(n, l3)) +
  geom_point() +
  scale_x_log10(breaks = 5*2**(0:24)) +
  ylab("mean(L3 cache miss)")
print(p)

hash-lookup-cache-rand-l3.png

あと、6要素までとそれ以降で傾向が異なるのも L1, L2, L3 すべてのグラフでみてとれる。6要素までは線形探索なのでまた違うのだろう。その部分で、なんで L1, L3 が増加傾向で、L2 が減少傾向なのかはわからないが。

まぁ、いろいろ工夫して測定すれば、L1, L2 cache についても 連鎖法ハッシュ表というアルゴリズムの性質が表れたグラフを描くことが可能であることがわかった。

2016-10-30 (Sun)

#1 アドレスをなるべく固定してみる

同じプログラムを動かしても毎回グラフが変わるというのは、毎回変化する要素がどこかにあるということである。

そういう要素はなんとか制御して固定するか、あるいは、制御できないものとして無視して測定したい。

キャッシュの話なので、さまざまなメモリのアドレスが問題ではないかという気がする。具体的には、ふたつの要因が考えられる。ASLR (address space layout randomization) と、Ruby のハッシュ関数である。

どちらも起動毎に異なる動作をする。

Linux で ASLR は以下のようにして設定で抑制できる。(0 に変える前は 2 だった。)

# echo 0 > /proc/sys/kernel/randomize_va_space

追記: がちゃぴん先生が教えてくれたのですが、以下のようにして ASLR をプロセス単位に抑制できるそうです。こっちのほうが限定的に抑制できていいですね。 <URL:https://twitter.com/kosaki55tea/status/792943771948154880>

setarch --addr-no-randomize a.out

(現在使っている) Ruby のハッシュ関数は SipHash だが、これには種を与えることができて、種はプロセスが起動するときにランダムに決定する。これを固定するにはソースを変更する必要がある。まぁ、fill_random_seed から種をゼロクリアした以降のコードを取り除くだけである。

% svn diff --diff-cmd diff -x '-u -p'
Index: random.c
===================================================================
--- random.c	(revision 56525)
+++ random.c	(working copy)
@@ -552,6 +552,7 @@ fill_random_seed(uint32_t *seed, size_t

     memset(seed, 0, len);

+/*
     fill_random_bytes(seed, len, TRUE);

     gettimeofday(&tv, 0);
@@ -565,6 +566,7 @@ fill_random_seed(uint32_t *seed, size_t
 #if SIZEOF_VOIDP > SIZEOF_INT
     seed[2] ^= (uint32_t)((VALUE)&seed >> SIZEOF_INT * CHAR_BIT);
 #endif
+*/
 }

 static VALUE

そうやってなるべく固定的に動作するようにすると、以下のように String#hash, Object#object_id, rand が毎回同じ値になるようになった。

% ./ruby -e 'p "".hash'
1543336582023656316
% ./ruby -e 'p "".hash'
1543336582023656316
% ./ruby -e 'p "".hash'
1543336582023656316
% ./ruby -e 'p Object.new.object_id'
46912500431520
% ./ruby -e 'p Object.new.object_id'
46912500431520
% ./ruby -e 'p Object.new.object_id'
46912500431520
% ./ruby -e 'p rand'
0.42843998755088286
% ./ruby -e 'p rand'
0.42843998755088286
% ./ruby -e 'p rand'
0.42843998755088286

測定プログラムは前回と同じなので省略する。前回同様、3回測定を行った。

L1 cache miss の測定結果が以下の3つである。それなりに似ているが、違うところもけっこうある感じである。

hash-lookup-cache-fixed1-l1.png

hash-lookup-cache-fixed2-l1.png

hash-lookup-cache-fixed3-l1.png

L2 cache miss の測定結果が以下の3つである。かなり似ている。少なくともアドレスを固定しなかったときに比べればはるかに似ている。でも、違う感じなところもある。

hash-lookup-cache-fixed1-l2.png

hash-lookup-cache-fixed2-l2.png

hash-lookup-cache-fixed3-l2.png

L3 cache miss の測定結果が以下の3つである。かなり似ている。ずれも一致しているところが多い。

hash-lookup-cache-fixed1-l3.png

hash-lookup-cache-fixed2-l3.png

hash-lookup-cache-fixed3-l3.png

測定結果が毎回異なる理由は、アドレスの変化がかなり大きな部分を占めている感じがする。

2016-10-29 (Sat)

#1 cache miss を測る

TLB miss の挙動については納得できた気がするので、cache miss を測ってみよう。

% ./ruby -rPAPI -e '
events = %w[PAPI_L1_DCM PAPI_L2_DCM PAPI_L3_TCM]
evset = PAPI::EventSet.new
evset.add_named(events)
def fmt(n) "%10d" % n end
puts "n,l1,l2,l3"
nn = 1.0
rep = 10000
GC.disable
h = {}
while nn < 1e4
  n = nn.to_i
  h[fmt(h.size)] = true while h.size < n
  l1sum = l2sum = l3sum = 0
  GC.start
  rep.times {|i|
    k = fmt(rand(n))
    evset.start; evset.stop
    evset.start
    h[k]
    evrec = evset.stop
    l1sum += evrec[0]
    l2sum += evrec[1]
    l3sum += evrec[2]
  }
  l1mean = l1sum.to_f / rep
  l2mean = l2sum.to_f / rep
  l3mean = l3sum.to_f / rep
  puts "#{n},#{l1mean},#{l2mean},#{l3mean}"
  nn = nn*1.001
end'

L1, L2, L3 の miss を数えている。ハッシュの要素数 n を 1 から 1e4 まで増やしながら、それぞれの n について cache miss の数を数えるのを10000回繰り返して平均を出力している。

グラフにすると、どうも不安定なので、3回測ってみた。(上記のプログラムを 3回動かしてみた。)

L1 cache miss の測定結果が以下の3つである。まず、全体に値がばらけている。(平均をとっているにもかかわらず、である。) 80〜160あたりまでは増加傾向で、その後はあまり変わらないもしくは小さな増加傾向という感じかな。ハッシュの拡張 (80, 160, 320, ...) でのずれもあるが、そうでないところでずれることがある。

hash-lookup-cache-1-l1.png

hash-lookup-cache-2-l1.png

hash-lookup-cache-3-l1.png

L2 cache miss の測定結果が以下の3つである。100〜400あたりまでは素直に増加している。その後も大きく見れば増加傾向がさらに増しているが、ふたつの線のあいだをいったりきたりしているように見える。いったりきたりしているところは、3つの測定で異なることが多い。ハッシュの拡張 (80, 160, 320, ...) でのずれもあるが、そうでないところでずれることがある。

hash-lookup-cache-1-l2.png

hash-lookup-cache-2-l2.png

hash-lookup-cache-3-l2.png

L3 cache miss の測定結果が以下の3つである。おおざっぱな形はどれも同じで、右端で急激に増加している。ただ、ここでもふたつの線の間をいったりきたりしているような感じである。いったりきたりしているところは、3つの測定で異なることが多い。

hash-lookup-cache-1-l3.png

hash-lookup-cache-2-l3.png

hash-lookup-cache-3-l3.png

2016-10-28 (Fri)

#3 load命令数

命令数全体がほぼ一定であることは前に測定してわかっているので、loadの命令数もほぼ一定であることは容易に想像できる。

しかし、この「ほぼ一定」な中での微妙な違いが miss の違いを発生させているようなので、細かく測ってみよう。PAPI では、PAPI_LD_INS で測れるようだ。

% ./ruby -rPAPI -e '
events = %w[PAPI_LD_INS]
evset = PAPI::EventSet.new
evset.add_named(events)
def fmt(n) "%10d" % n end
puts "n,mean,var"
n = 1
ntimes = 100000
h = {}
GC.disable
while n < 1e8
  h[fmt(h.size)] = true while h.size < n
  sum = sqsum = 0
  GC.start
  ntimes.times {|i|
    k = fmt(rand(n))
    evset.start; evset.stop
    evset.start
    h[k]
    evrec = evset.stop
    nev = evrec.first
    sum += nev
    sqsum += nev**2
  }
  mean = sum.to_f / ntimes
  var = sqsum.to_f / ntimes - mean ** 2
  puts "#{n},#{mean},#{var}"
  n = (n*1.01).to_i + 1
end' > hash-lookup-load.csv

平均をグラフにすると以下のようになる。

hash-lookup-load-m.R:

library(ggplot2)
d <- read.csv("2016-10/hash-lookup-load.csv")
p <- ggplot(d, aes(n, mean)) +
  geom_point() +
  scale_x_log10(breaks = 5*4**(0:12)) +
  ylab("mean(load)")
print(p)

hash-lookup-load-m.png

平均を見ると、なんか上下に分かれているのが奇妙だが、だいたいが1060から1070に収まっているし、下だけみれば1060から1063くらいに収まっていて、一定の範囲に収まっていることが確認できる。値としては 1%以下の範囲なので、ほぼ一定といって差し支えないだろう。

その一定の範囲の中で、loadの増加の繰り返しが見える。この周期はTLB missが起きるようになるよりもずっと小さなハッシュから発生している。まぁ、それほど大きくなくてもハッシュの拡張は起きているからな。

平均の周期的挙動は、だいたい3命令弱くらい増加しては元に戻るという形に見える。

Ruby の st.c には ST_DEFAULT_MAX_DENSITY が 5 と定義してあって、リストの(平均)長さが5を越えると rehash する。なので rehash する直前にはリストの(平均)長さはだいたい 5 で、rehash した直後での(平均)長さはだいたい 2.5 になるはずである。

検索でリストをたどるときはハッシュ値と次の要素へのポインタの 2つは load しないといけなくて、平均的にはリストの半分の長さをたどるので、rehash前後で load は 2 * (5/2 - 2.5/2) = 2.5命令くらいの差があるはず、ということでだいたい理屈どおりの実験結果といえるかな。

あと、要素数が40より小さいところでは、load数が1060を下回っている。おそらくこれはリストが短いのだろう。6要素を越えると bin が 16個のハッシュテーブルが構成されるので、リストの平均長は 7/16=0.43個くらいから始まり、次の拡張は 80要素(平均長80/16=5) となる。40要素(平均長40/16=2.5) まではそれ以降よりも平均長が短いので、そのぶんload命令が少ないと理解できる。

分散をグラフにすると以下のようになる。分散は大きくなることもあったので、両対数にしてみた。

hash-lookup-load-v.R:

library(ggplot2)
d <- read.csv("2016-10/hash-lookup-load.csv")
p <- ggplot(d, aes(n, var)) +
  geom_point() +
  scale_x_log10(breaks = 5*4**(0:12)) +
  scale_y_log10() +
  ylab("var(load)")
print(p)

hash-lookup-load-v.png

分散は、両対数なのでちょっと形が違うように見えるが、平均と同じような感じで、平均が大きくなれば分散も大きくなっているように見える。右端とかですごく分散が大きくなることがある理由はよくわからない。

#2 ハッシュの拡張

Ruby の Hash の実装の st.c を眺めると、要素数6個までは埋め込んで、それを越えると bin の数が 16, 32, 64, ... となるように拡張していく。ST_DEFAULT_MAX_DENSITY が 5 と定義してあって、rehash 直前には各 bin には (平均) 長さ5のリストがつながっており、rehash直後には半分の長さ 2.5 に落ちる。

要素数で考えると、16*5=80, 32*5=160, 64*5=320, ... というところで挙動が変化するはずである。グラフの目盛をそのように変えてみよう

hash-lookup-tlb-freq3-m2.R:

library(ggplot2)
d <- read.csv("2016-10/hash-lookup-tlb-freq3.csv")
p <- ggplot(d, aes(n, mean)) +
  geom_point() +
  scale_x_log10(breaks = 5*4**(0:12)) +
  ylab("mean(miss)")
print(p)

hash-lookup-tlb-freq3-m2.png

やはりちょうど目盛のところで変化している。

#1 もっと細かく

細かく測定することに味をしめたので、もっと細かくしてみた。

細かく測定するとデータが大きくなってしまうのが面倒なので、今回は測定段階で平均と分散を計算してしまい、生データは記録しないことにした。あと、せっかくなので小さいサイズから測定しよう。

% ./ruby -rPAPI -e '
events = %w[DTLB_LOAD_MISSES:MISS_CAUSES_A_WALK]
evset = PAPI::EventSet.new
evset.add_named(events)
def fmt(n) "%10d" % n end
puts "n,mean,var"
n = 1
ntimes = 1000000
h = {}
GC.disable
while n < 1e8
  h[fmt(h.size)] = true while h.size < n
  sum = 0
  sqsum = 0
  GC.start
  ntimes.times {|i|
    k = fmt(rand(n))
    evset.start; evset.stop
    evset.start
    h[k]
    evrec = evset.stop
    nev = evrec.first
    sum += nev
    sqsum += nev**2
  }
  mean = sum.to_f / ntimes
  var = sqsum.to_f / ntimes - mean ** 2
  puts "#{n},#{mean},#{var}"
  n = (n*1.01).to_i + 1
end' > hash-lookup-tlb-freq3.csv

ハッシュの要素数に対する TLB miss の平均は以下のようになる。

hash-lookup-tlb-freq3-m.R:

library(ggplot2)
d <- read.csv("2016-10/hash-lookup-tlb-freq3.csv")
p <- ggplot(d, aes(n, mean)) +
  geom_point() +
  scale_x_log10() +
  ylab("mean(miss)")
print(p)

hash-lookup-tlb-freq3-m.png

ハッシュの要素数に対する TLB miss の分散は以下のようになる。

hash-lookup-tlb-freq3-v.R:

library(ggplot2)
d <- read.csv("2016-10/hash-lookup-tlb-freq3.csv")
p <- ggplot(d, aes(n, var)) +
  geom_point() +
  scale_x_log10() +
  ylim(0,10) + ylab("var(miss)")
print(p)

hash-lookup-tlb-freq3-v.png

とくに平均はきれいに測定できた。右側に注目すると、ハッシュの拡張(rehash)による周期的構造がよく現れている。

Ruby におけるハッシュの拡張は、要素が増えていったときに密度が一定以上になったときに起こる。拡張時にはテーブルのサイズを倍にするので、密度は半分に下がる。また、Ruby のハッシュは連鎖法のハッシュテーブルであり、密度に比例した長さのリストが作られる。

検索時にはそのリストをたどる(平均して半分の長さをたどる)ので、密度に比例して load 命令が増える。load が増えれば (リストなので連続したアドレスでもないし) miss が増える。拡張が起きると密度が半分になるので miss がいっきに減る。これが、要素数が倍になる毎の周期性が現れる原因と推測できる。

ただ、周期的挙動よりも大きな範囲での傾向として、平均は右肩上がりの増加傾向が見える。分散にはこの増加傾向は見えない。テーブルのサイズが大きくなるとテーブルへのアクセスで miss が増えるからかなぁ。miss の平均は load 数だけでなく個々の load の miss 率もそれなりに影響するが、miss の分散は load 数のほうが支配的ということだろうか。

2016-10-26 (Wed)

#1 TLB miss の分布 (再)

もっと細かく測定すればなにかわかるかな、ということでやってみた。

% ./ruby -rPAPI -e '
events = %w[DTLB_LOAD_MISSES:MISS_CAUSES_A_WALK]
evset = PAPI::EventSet.new
evset.add_named(events)
def fmt(n) "%10d" % n end
puts "n,i,t[s],#{events.join(",")}"
n = 10000
h = {}
GC.disable
while n < 1e8
  h[fmt(h.size)] = true while h.size < n
  GC.start
  10000.times {|i|
    k = fmt(rand(n))
    Process.clock_gettime(Process::CLOCK_THREAD_CPUTIME_ID)
    evset.start; evset.stop
    t1 = Process.clock_gettime(Process::CLOCK_THREAD_CPUTIME_ID)
    evset.start
    h[k]
    evrec = evset.stop
    t2 = Process.clock_gettime(Process::CLOCK_THREAD_CPUTIME_ID)
    t = t2-t1
    puts [n,i,t,evrec].join(",")
    STDOUT.flush
  }
  n = (n*1.03).to_i + 1
end' > hash-lookup-tlb-freq2.csv

グラフにすると、明確な規則性が読み取れる。

(ところで、read.csv は .csv.gz, .csv.bz2, .csv.xz を直接読めることを始めて知りました。xz の場合に lzma decoding result 10 という警告が出るのがなんですが。)

まず試行数については、最初の予想の一定というのは外れたのだが、ぐいっと上がっている曲線が一定間隔で繰り返されているように見える。(x軸は対数軸なので、一定間隔というのは、一定の倍数を意味する。)

hash-lookup-tlb-freq2-n.R:

library(ggplot2)
library(plyr)
d <- read.csv("2016-10/hash-lookup-tlb-freq2.csv.xz")
d$i <- as.factor(d$i)
d$miss <- d$DTLB_LOAD_MISSES.MISS_CAUSES_A_WALK
d$DTLB_LOAD_MISSES.MISS_CAUSES_A_WALK <- NULL
binom_p <- function(x) { 1 - var(x) / mean(x) }
binom_n <- function(x) { mean(x) / binom_p(x) }
dn <- ddply(d[d$i!=0,], .(n), colwise(binom_n, .(miss)))
p <- ggplot(dn, aes(n, miss)) +
  geom_point() +
  scale_x_log10() +
  coord_cartesian(NULL, c(-10,200)) +
  ylab("estimated number of experiments")
print(p)

hash-lookup-tlb-freq2-n.png

そして、確率についてはやはり同様の周期で、下降する直線が繰り返されているように見える。ただ、この直線は hash のサイズの増加につれて miss率がある程度まで増加して飽和しているように見える。

hash-lookup-tlb-freq2-p.R:

library(ggplot2)
library(plyr)
d <- read.csv("2016-10/hash-lookup-tlb-freq2.csv.xz")
d$i <- as.factor(d$i)
d$miss <- d$DTLB_LOAD_MISSES.MISS_CAUSES_A_WALK
d$DTLB_LOAD_MISSES.MISS_CAUSES_A_WALK <- NULL
binom_p <- function(x) { 1 - var(x) / mean(x) }
binom_n <- function(x) { mean(x) / binom_p(x) }
dp <- ddply(d[d$i!=0,], .(n), colwise(binom_p, .(miss)))
p <- ggplot(dp, aes(n, miss)) +
  geom_point() +
  scale_x_log10() +
  ylab("estimated probability")
print(p)

hash-lookup-tlb-freq2-p.png

あと、そもそも二項分布という想定がおかしいかもしれないので、平均と分散を直接プロットしてみよう。

hash-lookup-tlb-freq2-m.R:

library(ggplot2)
library(plyr)
d <- read.csv("2016-10/hash-lookup-tlb-freq2.csv.xz")
d$i <- as.factor(d$i)
d$miss <- d$DTLB_LOAD_MISSES.MISS_CAUSES_A_WALK
d$DTLB_LOAD_MISSES.MISS_CAUSES_A_WALK <- NULL
dm <- ddply(d[d$i!=0,], .(n), colwise(mean, .(miss)))
p <- ggplot(dm, aes(n, miss)) +
  geom_point() +
  scale_x_log10() +
  ylab("mean of misses")
print(p)

hash-lookup-tlb-freq2-m.png

hash-lookup-tlb-freq2-v.R:

library(ggplot2)
library(plyr)
d <- read.csv("2016-10/hash-lookup-tlb-freq2.csv.xz")
d$i <- as.factor(d$i)
d$miss <- d$DTLB_LOAD_MISSES.MISS_CAUSES_A_WALK
d$DTLB_LOAD_MISSES.MISS_CAUSES_A_WALK <- NULL
dv <- ddply(d[d$i!=0,], .(n), colwise(var, .(miss)))
p <- ggplot(dv, aes(n, miss)) +
  geom_point() +
  scale_x_log10() +
  ylab("variance of misses")
print(p)

hash-lookup-tlb-freq2-v.png

ふむ、二項分布という仮定は悪くはないのかもしれない。細かい周期的な挙動を無視して全体的な傾向だけをみると、平均と分散は両方とも右上がりな傾向なのが、二項分布のパラメータに直すと、右上がりな傾向は確率だけになり、試行数は一定になる感じなので、性質をうまく分離できている気がする。

それはそれとして、この周期的挙動はなんだろうか、と想像すると、もしかすると、hash table の拡張 (と rehash) あたりだろうか?

Ruby の hash table の拡張は倍々にしていく。実験では要素数を 1e4 から 1e8 まで増やしていくので、log2(1e8/1e4)=13.3 ということで、だいたい 13回くらい拡張が起きているはずである。周期的な挙動は12回弱くらいだから、それなりに近い。

でもそのあたりの hash table の中身の状態は測定するのが面倒くさいな。Ruby の上からは調べられないし。

2016-10-25 (Tue)

#1 TLB miss の分布

この分布は二項分布な気がする。

何回か load を行って、それぞれで hit/miss して、miss の回数を数えるわけで、もし hit/miss の確率が一定で独立なら、二項分布だろう。

確率が確かに一定で独立かというと、そうでないのはわかっている。load 時に cache/TLB miss が起きれば、cache/TLB の中身が変化して、その変化はその後の load に影響を与えるので、明らかに独立でない。でも、一定で独立と近似できたりしないかなぁ、というわけである。

まぁ、試してみよう。

まず、実行時間じゃなくて回数が必要なので、TLB miss の回数を測る。ここでは、PAPI の DTLB_LOAD_MISSES:MISS_CAUSES_A_WALK をつかう。(PAPI_TLB_DM は DTLB_LOAD_MISSES:MISS_CAUSES_A_WALK と DTLB_STORE_MISSES:MISS_CAUSES_A_WALK の和であり、今回は store は基本的にしないので、PAPI_TLB_DM と DTLB_LOAD_MISSES:MISS_CAUSES_A_WALK は基本的には同じはずである。)

% ./ruby -rPAPI -e '
events = %w[DTLB_LOAD_MISSES:MISS_CAUSES_A_WALK]
evset = PAPI::EventSet.new
evset.add_named(events)
def fmt(n) "%10d" % n end
puts "n,i,t[s],#{events.join(",")}"
n = 10000
h = {}
GC.disable
while n < 1e8
  h[fmt(h.size)] = true while h.size < n
  GC.start
  1000.times {|i|
    k = fmt(rand(n))
    Process.clock_gettime(Process::CLOCK_THREAD_CPUTIME_ID)
    evset.start; evset.stop
    t1 = Process.clock_gettime(Process::CLOCK_THREAD_CPUTIME_ID)
    evset.start
    h[k]
    evrec = evset.stop
    t2 = Process.clock_gettime(Process::CLOCK_THREAD_CPUTIME_ID)
    t = t2-t1
    puts [n,i,t,evrec].join(",")
    STDOUT.flush
  }
  n *= 2
end' > hash-lookup-tlb-freq.csv

グラフにすると、hash のサイズが小さいときには左端に鋭い山があったのが、サイズを増やしていくと山がなまりつつ右にずれていくことがわかる。そして、ある程度以上大きくしてもあまり変わらないようにも思える。(もちろん page fault が起き始めれば変わるだろうが)

hash-lookup-tlb-freq.R:

library(ggplot2)
d <- read.csv("2016-10/hash-lookup-tlb-freq.csv")
d$n <- as.factor(d$n)
d$i <- as.factor(d$i)
d$miss <- d$DTLB_LOAD_MISSES.MISS_CAUSES_A_WALK
d$DTLB_LOAD_MISSES.MISS_CAUSES_A_WALK <- NULL
p <- ggplot(d[d$i!=0,], aes(miss, color=n)) +
  geom_freqpoly(binwidth=1) +
  coord_cartesian(c(0,20))
print(p)

hash-lookup-tlb-freq.png

確率pの事象をn回試行する二項分布では、期待値 E[X]=np, 分散Var(X)=np(1-p) になるそうなので、実験結果の平均と分散から試行数n と確率pを求めてみよう。たぶん p=1-Var(X)/E[X], n = E[X]/p で求められるよな。(平均や分散を求める関数が組み込まれているのは便利。)

> library(plyr)
> d <- read.csv("2016-10/hash-lookup-tlb-freq.csv")
> d$n <- as.factor(d$n)
> d$i <- as.factor(d$i)
> d$miss <- d$DTLB_LOAD_MISSES.MISS_CAUSES_A_WALK
> d$DTLB_LOAD_MISSES.MISS_CAUSES_A_WALK <- NULL
> head(d)
      n i      t.s. miss
1 10000 0 3.776e-06    7
2 10000 1 2.858e-06    8
3 10000 2 2.369e-06    5
4 10000 3 2.262e-06    3
5 10000 4 2.380e-06    6
6 10000 5 2.296e-06    2
> binom_p <- function(x) { 1 - var(x) / mean(x) }
> binom_n <- function(x) { mean(x) / binom_p(x) }
> ddply(d[d$i!=0,], .(n), colwise(binom_p, .(miss)))
          n         miss
1     10000 -39.61511252
2     20000   0.10107692
3     40000  -0.02825651
4     80000   0.03137766
5    160000  -0.06389309
6    320000   0.00239858
7    640000   0.10880288
8   1280000   0.08411615
9   2560000   0.05003379
10  5120000   0.06694540
11 10240000   0.03340431
12 20480000   0.08971798
13 40960000   0.08732990
14 81920000   0.06629310
> ddply(d[d$i!=0,], .(n), colwise(binom_n, .(miss)))
          n          miss
1     10000   -0.05152178
2     20000   26.49148463
3     40000 -124.34349243
4     80000  136.15651050
5    160000  -77.56638875
6    320000 2174.71054171
7    640000   50.11312521
8   1280000   66.71265778
9   2560000  114.09707497
10  5120000   87.81602294
11 10240000  177.40004722
12 20480000   63.97535777
13 40960000   66.89394621
14 81920000   90.86954149

plyr は便利だね、とか周回遅れの感想は置いておくと、各 hash size n に対して、確率と試行数を求めているが、あまり安定していない。

やってみる前は、hash size にかかわらず試行数 (load 回数) が一定になり、また、hash size が大きくなるにつれて確率 (miss の率) が大きくなっていくと期待したのだが、そうとは言い難い。

しばらく考えると、二項分布は確率が 0や1に近いときには山が鋭くなるので、今回のように山がなまっていくだけなのは、二項分布として考えると miss の確率が 1 に収束しないことを示している感じがする。しかし、hash table のサイズが大きければ、hash table の内容にランダムなキーでアクセスするのはほぼ確実に miss するようになるというのは間違いではないと感じられる。

ふむ。hash table の根元の構造体からの load とか、ベンチマークの中での load とか、Ruby の実行自体で起こる load とか、hit すると期待される load を無視しているのがいかんのかな。ほぼ確実に hit する部分が hash table のアクセスによって cache/TLB から追い出されることがあるというストーリーはどうだろうか。これであれば hit が消えないし、アクセスするアドレスによって追い出されたり追い出されなかったりして miss の回数がばらけることを説明できる気がする。



田中哲