実例！キャッシュの仕組み

CPUのキャッシュ（cache）

　もう1つのキャッシュの話をしましょう。先ほどディスクとメモリの間に置かれるキャッシュを紹介しましたが、キャッシュはメモリとCPUの間にもあります。一般に、キャッシュはスピード差があるものの間に置かれます（図3-1）。

　CPUの仕様には「二次キャッシュ」（L2 cache）というものがあります。メモリとCPUの間では、データや命令の転送を行いますが、メモリからCPUへ転送する際に、1バイトずつ転送するのでは効率が良くないので、まとめてメモリイメージをCPU側に持って来ておくための「置き場」のことです。

　ディスクのためのバッファキャッシュと同じように、ここではメモリブロックの番号に対応してキャッシュの場所を決めます。この場所決めの際、計算に時間がかかってはせっかくのキャッシュの性能が出ませんから、計算は素早く行える必要があります。そこで、多くのCPUではセットアソシアティブ（set-associative）と呼ばれる方式が使われています。個々のメモリブロックごとに管理するのではなく、セット（set）、つまり「集合」として管理する方式です。

　このセットアソシアティブも考え方の基本はハッシングです。ブロックの集合をいくつかのグループに分ける際に、どのような分け方をするかを一意に決めるためのものです。ある数値で割った余りの数値に対応したキャッシュのブロックが使われるのが一般的です。ただし、バッファキャッシュのようにリスト構造になってはいません。セットごとにブロックの領域はひとつしかありませんから、その場所の内容を置き換えて使います。

　「連想」（アソシアティブ：associative）という言葉が出たついでにこのことについても少し話しましょう。

　C言語などでは配列の要素はその数値の添え字（index）で参照するのが普通です。これに対して、PerlやPHPでは添え字として文字列が使えます。これが連想配列（associative array）です。

　筆者が知る限りでは、連想配列はUNIXのawk（「オーク」と読みます）で導入されたのが最初だと思います。その後Perlが現れました。Perlはawkの機能を完全に含んでいるため、今ではawkを使うことは多くはありません。

Perl、PHP、B-Tree

　Perl 4では連想配列（associative array）と呼んでいたものが、Perl 5ではハッシュ（hash）と呼ばれるようになりました。個人的には、この呼び方の変更は理解できません。連想配列とは名前をインデックスとして使うことができる抽象度の高いデータ構造です。これに対してハッシュはそれを実現するための実装方法の1つでしかありませんから。

　ともかく、Perlではこのメカニズムのおかげで文字列処理が格段に楽になりました。動的なWebサイトを実現するための方式であるCGIで、多くPerlが使われたのもこの文字列処理の便利さに負うところが多かったと思います。

　PHPの配列がすべてハッシュであることは今さら言わなくてもご存じでしょう。ですので、リンクトリストやハッシュをPHPで書くこと自体は無意味です。この点はこのシリーズの最初にも書きましたが、データ構造とアルゴリズムの中身を見るのが今回のシリーズの目的です。PHPの仕事でこのようなプログラミングをすることはないはずですが、あえて、基本的なデータ構造＋アルゴリズムを勉強しました。

　ハッシュやリストの例を示しましたが、「第2回：図解！二分探索のプログラミング（http://www.thinkit.co.jp/article/159/2/）」で扱ったツリー構造はどんなところで使われているでしょう。

　第2回で紹介したのは二分木ですが、1つのノードに複数の要素を持たせるB-Treeがより一般的かもしれません（図3-2）。

　このような構造は文字通り「索引」として使われます。索引が活躍するのはデータベースです。DBMSがデータを素早く検索するためにこのような構造を索引として利用します。また、ハードディスク上でファイルの場所を示すためのインデックスにもB-Treeが使われます。

　さて、いかがでしたでしょうか？

　基本的なデータ構造とアルゴリズムを理解することはとても重要なことです。これらは、PHPに限らず特定のプログラミング言語で書くことではなく、その考え方の基本を理解し身につけることが重要なのです。PHPは、今回の例でも紹介しましたように、すぐに例を試すことができます。その便利さがあるのでPHPを使ってみたにすぎません。

　言葉不足のところもあったと思いますが、これをきっかけにコンピュータ科学の面白さに気づいていただければ望外の喜びです。

　今回の執筆にあたっては、以下のものを参考にしました。

M.J.Bach『The Design of the UNIX Operating System』Prentice-Hall（発行年：1986）

J.L.Hennessy『D.A.Patterson, Computer Architecture: A Quantitative Approach, 4th
ed.』Morgan Kaufmann Pub.（発行年：2007）