メモリアクセスは遅い
多くのプログラマにとってメモリアクセスの速度を気しなければならない状況というのはめったに無いが、OS、ライブラリ、コンパイラ、RDBMSなどの実装をする時には意識をしなければならない場合がある。
IA-32 Intel Architecture Optimization Reference Manual (order number 248966) をひもとくと6章にOptimizing Cache Usageというのがある。
マイクロベンマークの定番 lmbench http://www.bitmover.com/lmbench/ では、一次キャッシュ(L1)や二次キャッシュ(L2)を測定してくれる。例えば、わたしが利用しているノートだと、L1が1.776nsでL2が5.3490ns、メインメモリアクセスが139.4nsである。
Memory latencies in nanoseconds - smaller is better
(WARNING - may not be correct, check graphs)
---------------------------------------------------
Host OS Mhz L1 $ L2 $ Main mem Guesses
--------- ------------- ---- ----- ------ -------- -------
asianux2. Linux 2.6.9-3 1700 1.776 5.3490 139.4
クロック数でいうと、L1が3クロック、L2が9クロック、メインメモリが237クロックくらいになる。
L1とメインメモリでは2桁のアクセス速度の差がある。CPUのクロックはムーアの法則によって18ヶ月で倍になると言われていたが、その間のメモリ速度の向上は数%で、年々そのギャップは広がる傾向にある。
近年、性能向上のためのクロック数の向上は消費電力の上昇をまねいたため、性能向上のためにはクロック向上ではなくコア数の増加という傾向になりつつある。それにしても、CPUの速度向上にくらべてメモリ速度の向上ペースは低いので、そのギャップの拡大はおわっていない。
昔はCPUのクロックと同じ速度でメモリにアクセスできたが、現状では100倍程度遅いことを覚悟しないといけない。
性能を極限まで追及する時には、そのキャッシュの振舞いを理解する必要がある。リストをたぐるような操作はアドレスが連続していないので最悪毎回キャッシュミスをひきおこし、メインメモリにアクセスする必要が生じる。従って速度が2桁遅くなる。一方配列を順アクセスする場合は最初の一回はキャッシュミスをおこすがその後はキャッシュにデータがあるのでメインメモリにアクセスしなくてすむので高速な実行が可能になる。
リストやハッシュはキャッシュに厳しいが配列はキャッシュに優しい。
リスト処理の場合は次にアクセスするところ(nextポインタの指しているところ)が分るので、あらかじめプリフェッチをしておけばlatencyを隠蔽できる。
Rubyの RejectKaiji2007で発表したRubyのキャッシュミスを削減した話はキャッシュミスをプリフェッチで削減するというアイデアを実装したものである。
RejectKaigi2007
http://blog.miraclelinux.com/yume/2007/06/rejectkaigi2007.html
一方プリフェッチというのは今あるデータを追い出して新しいデータをキャッシュに置くという事であるから、追い出されたデータがすぐに必要になるとキャッシュミスを発生させる場合がある。これをcache pollution(キャシュ汚染)という。ページのスラッシングみたいなものである。なんでもかんでもプリフェッチをしてキャッシュにのせればいいというものでもない。
そのアイデアを元に作ったのがcache pollution aware patchである。
Linux Kernel 2.6.18とCache Pollution Aware Patch
http://blog.miraclelinux.com/yume/2006/09/linux_kernel_26_2c2c.html
CPUのクロック数の上昇は消費電力の増加をまねくのでマルチコア化が進展しているという事は先に記した。マルチコア化が進展するとプロセッサ間の同期をどうとるかがますます重要になってくる。その実装としてスピンロックがある。スピンロックはメインメモリにフラグを用意して、そのフラグをセットできたものがロックを取得でき、セットできなかったものはセットできるまでループで待つという単純な同期方式である。
あるフラグがセットされているかを毎回メインメモリに見にいくという処理は、バスをロックして、アトミックにそのフラグをセットできるかを確認することだから非常にコストがかかる。バスをロックするので他のCPUは別の場所にアクセスしようとしてもアクセクを待たされるのでスケーラビリティもでない。(100nsから200ns位メインメモリアクセスにはコストがかかることを思い出してほしい）
マルチコアになってキャッシュに優しいロック方式あるいはロックなしの同期方法が求められている所以である。
メモリアクセスにまつわるバイナリハックの場所はまだまだいっぱいある。
コメント