キャッシュをバイパスをするとなぜ速くなるのか？

キャッシュミスを多発したときにキャッシュをバイパスするとなぜ速くなるのか？という疑問に答えるのはやさしくない。少なくとも性能を向上させるためにキャッシュを利用しないと言うのはどう考えても直感に反する。わたしもそう思う。
当初cache pollution aware patchを作ったときcache pollutionが発生しているならばキャッシュを使わないことによってcache pollutionの発生を抑えそれによって性能向上をはかるという風に理解していた。まあ、それは半分正しいのであるが全部ではない。
キャッシュミスにはreadのとき（すなわちメモリからレジスタへ読み込むとき）のキャッシュミスと、writeのとき（すなわちレジスタからメモリへ書き込むとき）のキャッシュミスがある。2つの種類のキャッシュミスがあるのだが、それぞれの動作は微妙にことなる。
読み込むときは、キャッシュミスをすると、キャッシュラインをアロケートして（確保して）、必要であれば犠牲になったキャッシュラインをメモリに書き出し、当該アドレス界隈のデータをキャッシュへ読み込む。メモリからの読み込みは最近のプロセッサでは２００〜３００クロック程度かかるのでプロセッサはそのメモリからデータを読み込むまで待つことがある。これをストールと呼ぶ。このストールのよる遅れを隠蔽するために２００ないし３００クロック前にあらかじめメモリを読み込んでおきキャッシュにおいておく。これをプリフェッチと呼ぶ。プリフェッチが有効に働けばメモリアクセス時のストールが見えなくなる（本当に必要なときにはすぐにアクセスできる）ので、レイテンシが下がり性能向上に繋がる。
従来はキャッシュミスにはプリフェッチがよく使われていた。効果があろうがなかろうが取り合えづ馬鹿の一つ覚えのようにプリフェッチだ。プリフェッチには当然悪い副作用がある。プリフェッチするタイミングが早すぎると利用される前に他のデータによってキャッシュから追い出されてしまうし（一度も利用される前にキャッシュから追い出される）、遅すぎるとデータアクセスするまでにキャッシュにデータが載らなくてレイテンシを隠蔽できない。すなわち待ち（ストール）が発生する。たちが悪いのはキャッシュを利用するために、すぐに利用される有効なキャッシュが犠牲になって追い出されることがある。これをcache pollutionというのだがプリフェッチにはそのよな副作用が付きまとう。
そのようなこともあってキャッシュミスのレイテンシ隠蔽工作のプリフェッチも特効薬とはならない。
書き込む時のキャッシュミスはさらに複雑だ。少なくとも私には複雑に見える。
キャッシュミスが発生すると、キャッシュラインをアロケートして（ここは読み込み時のキャッシュミスと一緒だ）、犠牲となるキャッシュラインを選び、必要であればメモリへ書き出す。ここも一緒。そしてRFO (Read for Ownership)のためにメモリからデータを読む。データを書くためにその界隈のデータを一旦キャッシュラインへ読み込むのである。これは自分の直感と微妙にズレル。少なくともわたしは、言われてみれば確かにそうなのだけど、日々そんなことを意識したことはなかったというような類の話である。ちょっと意外である。そんな感じである。
書くために読むと言うのが言ってみれば非常によけいな動作である。メモリから読むのはとってもコストがかかる。２００〜３００クロックもかかる。無駄である。
一方でキャッシュを利用しなければ、キャッシュラインのアロケートのコストも、犠牲となるキャッシュラインを書き出すコストも（多分数十クロックはかかるだろう）、RFOのためにメモリから呼び出すコスト（２００〜３００クロック）もかけなくてすむのである。すなわちキャッシュミスが発生しているときキャッシュを利用しないだけで３００クロック以上節約できるのである。ならばせっせと書き出すときのキャッシュミスを低減するべきである。
確かにキャッシュを利用することによって有効なキャッシュを追い出し、その犠牲になったキャッシュのpollutionによって無駄なキャッシュミスが発生していると言う事実もあるが、それは量的には実はwriteのキャッシュミスより随分少ない。
cache pollution aware patchによって減少しているのはcache pollutionによるキャッシュミスよりwrite時のキャッシュミスの方が比率としては多いのである。
というようなことはパッチを作っているときはよく分からなかったのであるが、Intelのマニュアルとかを熟読することによって徐々に理解が深まってきた。writeにおけるキャッシュミスは、readの時のキャッシュミスよりもコストが高くてどうもたちが悪そうである。ということで可能な限りwriteのキャッシュミスを効率的に発見する必要があるのであるが、IA-32のハードウェアイベントにはwrite cache missを検出する方法がないのでoprofileのようなツールでは簡単に発見できないのである。（残念だなあ）まあ、半歩前進なのでよしとする。