この話は前にも少し触れました。キャッシュという考え方の一般論です。具体的にプログラムのソースコードを書くことには、普通は関係しません。ただし、考え方としては、ネットワーク関係のアプリケーションなんかをベタで作ろうとすると、関係してきます。機械を直接操作するようなことをする際には、知っておいた方が良いようです。（長いです。すみません。）
発想
データ
このコーナーの初めの方でも述べたように、コンピュータは、非常に広い意味では、データの変換機であるという見方もできます。再述すれば、そのデータとは、大別して、処理対象として内容を成す狭義のデータと、そのデータを処理する手順をシンボリックに表現したデータであるコードからなります。この境界線は本性上確固不動というわけではなく、例えば、Mopsのようなネイティブコード型のForth環境では、文字データであるソースを取り込み、マシンコードにコンパイルして吐き出します。これは内容としての狭義のデータであるといえます。しかし、この吐き出されたデータであるマシンコードは、次の段階 — コンパイルの直後でもよい — では、別のデータを処理するための手順を示すコードとして利用されます。
記憶装置の特性
このような広い意味でのデータを、どこかに保管しておかなければなりません。これは何らかの記憶装置に格納されます。このデータを記憶をしておくやり方というか装置には種類があります。一般的に、記憶できるデータ許容量と、その記憶の中から必要なものを取り出す速さ、いってみれば、思い出すのにかかる時間とが、相反する傾向にあります。つまり、いっぱい覚えられるものは、なかなか思い出せない、ということです。これは二重の意味でいえます。第一には、異なる仕組みの記憶装置間でも、一般に大量に格納できる装置は読み書きに時間がかかります。第二には、同じ仕組みの装置でも、容量が大きくなればそれだけ読み書きに時間がかかるようになります。このような事情を克服して、コンピューターのデータ処理を迅速にし、かつ、大量のデータを扱えるようにしようという目的に応える考え方が、記憶階層という考え方です。記憶装置に段階を付ける、ってことですね。
階層化の発想
この階層の付け方を端的に言えば、頻繁に利用する少量のデータを近くに、時々参照するに止まる全体としては大量のデータを遠くに、という順序になります。近くとは速く思い出せる装置、遠くとは思い出すのに時間がかかるかもしれない装置、ということです。まあ、どうしてそうすると効率がいいのかはわかりますよね。
よくある喩えとしては、本の置き場所の工夫というのがあります。例えば、英語の文章を机上で読むときに、頻繁に引く英和辞典を机から離れたところにある書棚の中に置いて、わからない単語が出たらその都度、椅子から立って棚まで歩いて行き、書棚の中から辞書を探し出し、単語の意味を調べて、また書棚に辞書を戻し、机まで戻って来て、というのを繰り返していたら、ものすごく時間がかかってしまいます。というか自分なら書棚についた頃には何を調べるんだったか忘れてますね。まあ、それはともかく、そういう頻繁に参照するものは、机に持ってきて、手元においておく方がいいわけです。これがキャッシュという考え方です。キャッシュ（cache）は、貯蔵庫というような意味です。
実際の記憶装置
記憶装置というと、HDとかCDとかDVDとか、大量に格納できるけれども、読み出しはあまり速くないものがまず浮かびます。次が、少し許容量は減りますが、比較的速く読み出せるいわゆるメモリー、長く言うとランダムアクセスメモリー(RAM)が思い当たります。さらに、プログラミングをかじったことがある人でないと思いつかないかもしれない、レジスターというのがあります。スーパーのレジじゃないよ。レジスターは、コンピューター内部の演算装置の中にあって、データを手早く処理するための非常に小さな容量をもった記憶装置です。「何とかビット」コンピューターというときには、大抵の場合（いつもじゃない）、このレジスターに数値を格納する際の単位に対応しています。レジスター内のデータは直接計算処理されるので、レジスターは最も速い記憶装置ということになります。
で、実は最近のパソコンでは普通、レジスターとRAMの間に、もうひとつ、中間的な記憶装置があります。これがキャッシュメモリーと呼ばれるものです。最近ではこれもコンピューターの売り文句のひとつになっていたので、ご存知の方も多いかもしれません。このキャッシュメモリーもまた、何段階かに分かれていることがあります。二次キャッシュとか三次キャッシュとか。このキャッシュメモリーは、少なくとも第一次キャッシュは、演算装置に入っている、というか、それと同じVLSIの中に埋め込まれているもののようです。この、キャッシュメモリーの話をするのが、ここのひとつのテーマです。が、どう使うのが効率がいいかという話はしません。普通のパソコンでは、その使い方をプログラムから直接コントロールすることはできないと思います。多分、機械の仕組みとしてハードとして組み込まれているのでしょう。(アプリケーションプログラマーがキャッシュを操作できるための機械命令は定義されていますが。)どういう癖があるかわわかると、アセンブリーでプログラムする人や、コンパイラーを設計する人は、それを使って効率化することはできるでしょうね。高級言語でするのは、ちょっと聞いたことがありません。
VLSIですが、要はICですね。ICはインテグレーテッドサーキット(Integrated Circuit)で、集積回路と訳されます。電子部品が、特定の動作をするように組まれて、まるごと固めてある部品ですね。典型的には黒い四角い板に金属の足がいっぱい生えている、変な虫みたいなヤツです。で、LSIというのもあります。これはLarge Scale Integrationでしょう。大規模集積回路、と訳すはずです。Cがなくなっちゃいましたね。こでにVがついてVLSI。VはVeryですよ。非常に大きいと。超大規模集積回路とかいうんでしょうか。最後の訳はあやしいです。一枚にトランジスタが10万個とかなんか規準がある雰囲気です。確かに、技術水準としての違いというのはわかりますが、どっちかというと商業上の必要でつけた広告用みたいな気がします。だって、結局は集積回路ですから。この技術の基盤は印刷技術だって話を聞いたときは、むむむ、と思いましたよ。配線じゃなくて印刷するんですね、（半）導体をインクにして。なんともスゴイです。まあ、感光させるらしいので、写真製版って感じですか。活版とかバブルジェット印刷とかとは違います。ガラスのフィルムみたいなののサンプルを見たことがあります。まあ、昔のやつですが。
RAM内のデータの操作はレジスターと比べると非常に時間がかかります。数倍から十数倍くらいらしいです。そのため、RAMにデータを出し入れしている間、少なくともその値に依存する計算処理は滞ってしまいます。下手をすると、その間、何もしないで待っていなければなりません。このような状態はストールと呼ばれます。キャッシュメモリーはストール自体を解消できるわけではないようですが、少なくとも、CPUからみた仮想的なメモリーアクセスを速める効果を持っています。簡単にいうと、頻繁にアクセスしそうなデータを、予めキャッシュメモリーという速いメモリーに入れておいて、そこから使うわけです。よく使う辞書を机の上に置いておくのと同じです。
単にキャッシュというと、キャッシュメモリーのことを指していることもありますが、キャッシュというのは、頻繁に使うものを速くアクセスできるように近くにおいておく考え方、あるいは、その「近い」置き場所のことを言うのであって、いわゆるメモリー装置である必要はありません。例えば、Mopsでは、正式にはメモリー上にあってポインタで参照されていると考えられているスタック中の値の、上の方のいくつかを、メモリーではなく、レジスターに置いておくようになっています。スタックというデータ構造は、その上の方へのアクセスが通例なわけですから、ここをレジスターに置くことによってコードの実行速度がかなり改善されます。これも、キャッシュの方法です。レジスターキャッシュと呼んだりもしますが、これはレジスターでキャッシュするという意味ですね。スタックアイテムキャッシュという言い方もあると思いますが、これはスタックアイテムをキャッシュするという言い方でしょう。スタックCPUのような特殊なものを想定しているのでなければ、レジスターでキャッシュするのが前提でしょう。
外部への拡張（あまり本題と関係ない）
と、ここまでは記憶装置として内部装置だけを考えてきましたが、拡張機器として線でつないだ外部装置はもちろん、最近のコンピュータの多くはネットワークに接続されていることも考えないといけませんね。ネットの向こう側には、膨大な量のデータがあります。最近はAjaxとかいうんですか、JavaScriptとかで書いたソースコードを実行コードとみなすなら、ネット内には、単なる内容データにとどまらず、コードもまた格納され、読み出されているということになります。Javaでも同じことです。
ま、ネットワークの話はあまりできないんですが、こういう状況を考えた場合、離れた所、カタカナ英語でリモートとか言いますが、そこにあるものよりも、手元にあるものとか内部装置の方が、小さいが速い記憶装置、ということになります。なので、ここにもキャッシュという考え方が適用されます。ウェブブラウザーは、ネットからロードしたページを一旦ハードディスクに格納しています。これもキャッシュと呼ばれていますね。Windowsでの話ですが、昔、何の気なしにIEのキャッシュを消してみたら、HD空き容量が200MB増えて、おお、と思ったことがあります。意外に溜まってます。そして、キャッシュされた古いページを最新だと思って見続けている場合もあります。注意しましょう。
パソコンがクラスター接続とかされたりして、並列計算処理とかされると、外部のコンピュータに格納されたデータなんかにもアクセスしますよね。まあ、キャッシュとかは関係あるのかどうかわかりませんが、別のパソコンはやはり遠い所にある記憶装置なわけで、あまり通信を頻繁にしなくても良いようにすれば、より速い計算ができるんでしょうね。あまり関係ないか。
それと、最近では、HDがキャッシュを内蔵しているものもあるそうです。物理的な空間を検索する時間が省ける分だけ、読み書きは速くなるでしょう。いっそのこと10GBくらいつけて、たまにフラッシュ（ディスクに書き込むこと）すれば良いんじゃないかとか、思ったりします。なんでも、HDの代わりにフラッシュメモリをつかったMacBookの噂があるとか。むむむ。電気メモリーも安くなったものです。
キャッシュメモリーの概略
ハードウェアのバランス
キャッシュメモリーは最近では一般のRAM程ではないにしてもかなり大きくなって来ていますが、そこへのアクセスは、普通のRAMと比べてかなり速くなっています。なぜキャッシュメモリーなどという中途半端なものがでてきたのか。全部アクセスが速いメモリーにすれば良いんじゃないかと思うわけですが、速いメモリーは普通値段が高い。それに電気をたくさん喰うわけです。それに、いくらアクセスが速いメモリーといっても、大きくなればそれ相応に遅くなってきます。その費用と効果の関係が問題です。速いメモリーを大規模に投入しても、電力消費量が飛躍的に大きくて発熱したり、値段も高くなるというのに、動作は速くなると言ってもほんのちょっと、というのでは、バカバカしいわけです。それで、全部が速いメモリーということにはならず、適正な組み合わせを指向することになります。
バランスとしても、キャッシュメモリーを大きくすればそれで良いかと言うと、必ずしもそうではありません。というのは、例えば、高いパソコンでは三次キャッシュなんていうのもあって、これはつまり、三段階に少しずつ遅いキャッシュメモリーがついている感じなわけです。データが必要なときは、キャッシュメモリー内を順番に検索していきます。三つ目まで調べて、やっぱり無い、というときには、あらためて初めからRAM内にアクセスすることになります。これだと、キャッシュが何もなく最初からRAMにアクセスする場合よりも、キャッシュ内を検索する分だけ余分に時間がかかってしまうわけです。大きいキャッシュメモリーを持てば、確かにRAMにアクセスしなければならない機会は減りますが、その分、外れた場合の超過負担（オーバーヘッド）は大きくなります。CPUの設計とかRAMも含めたマザーボードでの組み合わせのバランスもありますから、それを考えて全体として一番よさそうな落としどころみたいなものがあるわけです。この辺にそれほど詳しいわけではありませんが、そういう理屈からいえば、キャッシュメモリーのサイズとかはCPU限りで決まってたりしますが、本当は、RAMとして使うメモリーの種類や大きさ、あるいはクロック周波数比とかのバランスを考えて決めた方が最適化できるはずなわけです。LSIをバラすことはできないので、せめて「このCPUにはこの種類のRAMをこれだけの大きさ」という最適組み合わせが考えられるはずなんですね。このバランスが崩れると、高い割にはあまり性能が良くないボードができるということもあるのではないかと想像できます。
読み出しの際の予想方法
さて、キャッシュは頻繁に使うデータを近くにおくのだといいました。頻繁に使うデータかどうかがどうやってわかるかが問題です。実際にあるデータを頻繁に使った後になら、それがそうだとわかりますが、その時点でもう省きたいと考えていた時間は経過してしまっているわけですし、その後もそのデータを使うかどうかわかりません。英語を読むなら英和辞典というパッケージになったものがあって容易に特定できるのでいいですが、アプリケーションの動作というのは場合によって異なりますし、動的に変化していきます。
予想方法には色々技巧があるようですが、基本的には、「メモリーの、ある特定の場所にあるデータにアクセスしたならば、次はその近くに置かれているデータにアクセスすることが多い」という法則に基づいています。つまり、ある処理プロセスで連続的に処理される一群のデータは、メモリー内で一カ所に集まっておかれていることが多い、ということです。例えば、構造体や配列データとかのためには、メモリー内に一塊の場所をとって利用しますが、同じ機会にそれらの複数のメンバー／アイテムにアクセスすることが多いだろうといえます。なので、メモリー内のある場所のデータにアクセスしたときには、その周辺のデータを、ある程度の広い範囲でガバッと持って来て、キャッシュに入れてしまうわけです。そうすると、次にアクセスしようとするデータは既にキャッシュ内にあって、素早く読み出すことができる場合が多くなるわけです。
書き出しに際してのキャッシュ
データをメモリーに書き込むのも、時間がかかります。ですが、書き込むだけというなら時間がかかっても、それはメモリーの方に任せておいて、CPUの方は次へと計算を進めていくことができます。ところが、いったんメモリーに格納したデータを、また使うということもあります。その格納と再利用の間隔が短いときには、メモリーに書き込んで、それから読み出して、とやっていると詰まってしまうこともありそうです。
そこで、書き出されるデータはキャッシュに残しておいて、次の読み出しはそこから取ると便利です。特に、ひとつの手続き内で頻繁に書き換えられるデータは、キャッシュ限りで書き換えておき、適当に間が空いた段階でメモリーに転送しておけばいいということになります。ただ、その場合、実際にメモリーに格納されている値と、処理プロセスのその時点で本来ならば格納されているべき値とが食い違ってしまうという事態が起こりえます。マルチタスクとか、ともかく、何らかの形で直接にメモリーにアクセスしたルーチンは、プログラマーが予想していたのとは異なる値をメモリー内に発見することになります。書き出しのキャッシュについては、この問題を回避し、かつ効率が落ちないようにキャッシュの内容をメモリーに転送するタイミング取りが課題となるということのようです。
もう少し細かく言うと、メモリーに値を書き出そうとしたとき、その変更前のデータがキャッシュ内にあれば(ヒットするといいます)、とりあえすキャッシュだけ変更してけばよいわけです。そして、メモリーの値をそれと合わせるタイミングが問題となります。これに対して該当部分のメモリーの値がキャッシュになければ、その周辺も早晩変更するだろうと考えてキャッシュに写しておくことになりますが、ヒットしたときにキャッシュのデータを変更すると同時にメモリーも変更しておくことにする場合は、外れても周辺をキャッシュにコピーしないのが普通らしいです。近隣の変更のときもどうせメモリーに書き込むのだから、キャッシュにいっぱい写してくる時間はムダになるからだとか。この考えだと、実質的には読み込みに関してのみキャッシュを使うという感じになりますね。
コードキャッシュ
上の話は、処理される内容としてのデータを前提としていましたが、コードの場合でも基本的には同じです。データの場合と区別して、コードキャッシュなどといいます。コードも、アプリケーションの起動と同時に実行可能ファイルからメモリーにコピーされます。そして、頭として指定されている部分から通常は番地が大きい方に向って順番に読みとられ、実行されていきます。PPCや68kだとひとつの機械命令が同じバイト長ですが、x86系ではバイト長が区々（まちまち）です。なので、x86系では、ますガボッとコードを読み込んだ上で、何処から何処までがひとつの命令かを分析し、分節化する手順が必要となります。ですから、コードキャッシュのようなことは本性上必要な感じですね。ただ、コードはいつもメモリーの下から上に順序よく進んでいくわけではありません。個々の関数（サブルーチン）のコードは、関数毎にメモリーのあちらこちらに置かれていますから、関数が別の関数を呼び出したりすると、コードの実行はメモリー内でジャンプします。ジャンプ先が遠いとキャッシュからはみ出してしまうので、またその時点で新しい関数の周辺 — この場合、ジャンプ先から上の隣接部分ですね — をキャッシュに読み込もうとすると、時間がかかってしまいます。なので、素朴なキャッシュを利用している場合、実行のジャンプにはかなりオーバーヘッドが生じてしまいます。
ですが、よく考えると命令はいつも先読みされているわけですから、実際に処理が移ってくる前にジャンプする命令を探知して、どこに行きそうかということを予測することが可能です。ジャンプが確実で、その先が確定的にわかるのなら、ジャンプ先のコードを実際にジャンプする前に予めキャッシュに取ってくるといいわけです。
ただ、ご承知のように、IF文とかCase構造とかで、実行コードの行く先が、その都度のランタイムの状況に応じて変わる変数に依存しているときには、まあ、確実にというわけにはいきませんね。実際に分岐する命令よりも充分前に条件の成否がわかっていれば、何とかなることもあるでしょう。ともかく、コンピューターのコードキャッシュは、あるアルゴリズムによる予測に基づいてコードを先取りするという方法を採用しているようです。いずれにしても、ハードウェアに組み込まれた仕組みです。これによって呼出しのオーバーヘッドはかなり減少するとはいえるでしょう。ですが、一般的に言って、あっちを呼んだりこっちを呼んだり、実行個所がジャンプばかり繰り返すようなコードは、実行速度が落ちてしまう傾向にあります。インライン化による高速化というのは、こういう所も影響して可能になっているわけです。インライン化とは、呼出しをする代わりに、呼び出したら実行されるコードをそのまま、そこに埋め込んでしまう方法です。呼出しの超過負担を避けられる反面、コードが複製されて埋め込まれるので、サイズが大きくなり、メモリー効率は悪くなります。まあ、呼出しには、キャッシュ云々よりも、いろいろ余分にしなければならないことがあるので、それが省けるというのがインライン化の主な効用なんですけれども。ちなみに、Pentiumの初期のバージョンは、ジャンプするときのキャッシュの扱いに難があって、呼出しのオーバーヘッドがものすごかったそうです（100ステップ分くらいとか）。今でもIA32(x86系のことですね)の最適化マニュアルには、あまり実行をジャンプさせるなと書いてあります。
コードキャッシュには、書き出しのキャッシュというのは考えられないといえますね。普通のコンパイラ系の言語では実行中にコードが追加されるなどというのは想定外の事態なので、機械が対応してくれているはずはないんですけどね。
コーディングとの関連
というわけで、キャッシュを有効に使うという観点から言うと、参照するものをあちらこちらにバラして置かずに、同時に使うものは一カ所にまとめておくとよい、ということになります。
コードという観点から言うと、あまり細かいサブルーチンに分解して呼び出すのは実行速度が遅くなるかもしれないわけです。すると、長～いひとつの関数で書いた方が、きちんとわけ書きするより、実行速度という点では有利ということになります。ですが、最近ではコードキャッシュも賢くなっているので、オーバーヘッドは大したことはありません。それよりも、長い関数は変更したりするのが大変だったり、バグがあるときその場所を特定するにも面倒だったりします。こっちのほうが大問題なわけです。Forthは伝統的に、ワード（サブルーチン）を非常に細かく区切ることが推奨されています。これはスタックというデータ構造を利用するということからくる圧力と言えます。Forthなりのオブジェクト指向ともいえますね。呼出しのオーバーヘッドという意味では、キャッシュ云々以外の部分は、Forthでは小さく抑えられるらしいので、その点でも細分にむいているわけです。まあ、最適化のためにはインラインしたりするんですけど。
データに関して言えば、どういう場合に参照先が散らばってしまうのか、普通のプログラミング言語では、表面からはわからないようになっています。ですが、前にも構造体とかアレイの話をしましたが、まとめて一度に扱うデータは、一個一個のアイテムを変数として定義するよりも、例えば型が同じならアレイにして一挙に扱う方が速いはずです。C言語の標準的なコンパイラだと、できるだけ局所変数を使うと速く、大域変数へのアクセスは遅いかもしれない、ということにつながります。というのは、C言語では、関数毎にスタックフレームと呼ばれる枠をメモリーの一続きの部分にとって、局所変数や引数はそこにコピーして使うからです。これに対して大域変数は全部別の所にまとめて枠を取ります。まあ、大域変数でもまとまってあるならいいわけですが。Forthではできるだけ大域変数ではなく
データスタックを使えということでしょうか。現実的には、変数にもそれぞれに機能があるのであって、アプリケーションコードで実行速度のために無理することはないわけですが、同時に扱うデータは意味上も関連しているはすなわけですから、それらは一カ所にまとめておこうというのは、わかりやすいコードという点でも意味があるかもしれませんね。
最終更新：2019年03月09日 16:17
