前回はコンテキスト——頭の窓に何が載っているか、という話をした。窓は有限で、入りきらないものは外に出すしかない、というところで終わった。今回はその続きにあたる。外に出したものを、どこに置くか。よく使うものを、手の届くところに置く。それだけの話に、コンピュータは一つ名前を付けている。キャッシュという。
断っておくと、今日は「近さ」と「速さ」の話に絞る。手元に置けば速い、遠くにあれば遅い。それだけ。「たくさん置けるか」という量の話は別にあって、混ざりやすいので、出てきたらその都度はっきり分ける。第2回のテーマはキャッシュ。台所のコンロの脇と、玄関のフックで考える。
シマダ コンピュータの中には、記憶を置く場所が何段階かあります。速いけれど小さい記憶を、計算するところのすぐ近くに置く。遅いけれど大きい記憶を、遠くに置く。近いほど速くて狭い、遠いほど遅くて広い。この段々をキャッシュ階層と呼びます。一番手元の、小さくて速い記憶——あれがキャッシュです。
シマダ 家に翻訳すると、調味料の置き場がそのまま階層になっています。コンロの脇に、塩・こしょう・油・醤油。手を伸ばせば届く一軍です。少し離れた戸棚に、たまに使うスパイスや乾物の二軍。そして床下や別室のパントリーに、箱買いの三軍。一軍は狭くて速い。三軍は広くて遅い。どれを一軍にするかで、料理の速さが変わる。
マキノ カートが、まさにそれですね。私の場合、三段になってます。腰のポーチ、これが一番速い。手を下ろせば届く。次がカートの上段、ひと振り向いて十秒。一番遠いのがリネン室で、片道で歩いて三分。
シマダ ポーチには何が入っているんですか。
マキノ 六点です。ゴム手袋、クロス二枚、小型のスプレー、髪の毛を取るゴムベラ、ペン、ルームキー。これだけ。多くも少なくもない、六点。何を入れるかは、もう22年で決まってます。考えてないです、手が覚えてる。
シマダ その六点が、マキノさんの一番速い記憶です。コンロの脇の四本と、役割は同じです。
シマダ なぜ手元に置くと速いのか。当たり前に聞こえますが、効く理由がちゃんと二つあります。一つめは、さっき使ったものは、また使う。今夜のおかずで醤油を使ったなら、明日も使う見込みが高い。だからコンロの脇に出しっぱなしにしておく価値がある。これを時間的局所性といいます。時間の近さ、です。
シマダ 二つめは、一緒に使うものは、一緒にある。砂糖を出すとき、たいてい塩も近くにある。シャンプーの隣にはリンスがある。だから並べて置く。これが空間的局所性。場所の近さです。「使う場所のそばに置く」というのは、要するにこの二つめを手で実装していることになります。
マキノ 浴室の洗剤とクロスは、必ずセットで持ちます。片方だけ持っていくと、もう片方を取りに戻る。一往復が一番もったいないので。
シマダ それが空間的局所性です。一緒に使うから、一緒に持つ。
マキノ 言葉は知りませんけど、そうしないと終わらないだけですよ。砂糖と塩を別々の棚に置く家、たまに見ますけど、あれは料理する人が決めた配置じゃないですね。しまう人が決めた配置です。
シマダ ……それは鋭い。しまう都合で並べると、使う都合と合わなくなる。配置は、使う側の動線で決まっているときに一番速い。
シマダ ここで量の話が一度だけ出ます。キャッシュは小さい。だから新しいものを入れたければ、何かを出すしかない。コンロの脇は四本ぶんしか置けないとして、五本目を置きたいなら、一本は戸棚に下げる。どれを下げるか。よく使われている規則がLRU——一番長く触っていないものから追い出す、というものです。
シマダ 新しく買った調味料をコンロの脇に置きたければ、一番触っていない瓶が戸棚に下がる。半年あけていないナンプラーがあれば、それが二軍に落ちる。最近の手の動きが、置き場を決める。
マキノ ポーチの中身も、季節で入れ替えます。結露の季節になると、鏡や窓を拭くクロスが一枚で足りなくなる。だから二枚目を足す。そうすると六点のままにするには、何か一つ下げないといけない。
シマダ 何を下げるんですか。
マキノ その時期に一番使ってないものです。冬はゴムベラの出番が減る。髪が乾いてると、そんなに排水口に絡まないので。だから冬はゴムベラをカートの上段に上げて、クロスをポーチに下ろす。夏はその逆。
シマダ まさにLRUです。一番使っていないものが、手元から一段遠くへ下がる。
マキノ 全部ポーチに入れたら速いだろう、って新人は思うんですよ。でも全部入れると、探す時間で結局遅くなる。六点だから、見ないで取れる。
シマダ ……それ、原則として効きます。全部一軍は、一軍なしと同じ。手元が混めば、手元である意味が消える。狭いことが速さの条件なんです。
シマダ 手元にあれば、数秒で済む。これをヒットといいます。手元になくて、戸棚まで、あるいは床下のパントリーまで取りに行く——これがミス。ミスすると、ヒットの何倍も時間がかかる。階段を降りてパントリーまで往復すれば、数秒のはずが一分になる。
シマダ だから、ミスしたときの値段が高いものほど、近くに置く価値がある。よく使うものを近くに置くのは当然として、それに「外したときどれだけ痛いか」を掛け算する。頻度と、ミスの値段。この二つの掛け算で、置き場が決まります。
マキノ ペンですね、私の場合。一日に何回も使うわけじゃない。チェックリストに印を付けるときだけ。でもポーチに入れてます。
シマダ 頻度は高くないのに、手元なんですか。
マキノ 無いと、その場で記録できない。後でまとめて書こうとすると、どの部屋で何を補充したか分からなくなる。一回外すと、その後ぜんぶ狂う。だから頻度は低くても、手元から外せない。
シマダ それがミスの値段の高さです。頻度では二軍でも、外したときの痛みで一軍に残る。極端な例が、火を使う台所の消火器です。一年に一度も使わない——使わないに越したことはない。でも玄関の物置じゃなくて、火元の近くに置く。
マキノ 使う頻度なら、玄関の傘立てのほうがよっぽど高いですよね。
シマダ ええ。普通の掛け算なら、頻度ゼロに近いものは遠くへ行く。でも消火器だけは、ミスの値段が——間に合わなければ家が燃える——掛け算が壊れるくらい大きい。だから例外として手元に残る。安全にかかわるものは、頻度の計算の外にある、ということです。
シマダ キャッシュには、もう一つ先回りの技があります。使う前に、取り寄せておく。これをプリフェッチといいます。まだ要求されていないけれど、どうせ次に要るだろうと見越して、先に手元へ運んでおく。
シマダ トイレットペーパーの買い置きが、ちょうどこれです。今は足りている。でも切れると困るし、切れてから買いに行くのはミスの値段が高い。だから切れる前に取り寄せておく。先読みです。
マキノ 次の部屋の分は、いまの部屋にいるうちにカートへ積みます。廊下を一回戻るのが、一番高いので。だから先に積む。
シマダ 使う前に運んでおく、まさにプリフェッチです。ただ——ここでまた量の話を一度だけ断りますが——先読みしすぎると、置く場所を食います。トイレットペーパーを二十四ロール箱買いすると、確かに当分ミスしない。でも、その箱が洗面所の床を占領する。手元の棚に置けるのは、せいぜい数ロール。先読みは速さを生むけれど、やりすぎると場所を圧迫する。速さと量の、別々の話がここで一回ぶつかります。
マキノ カートも同じです。次の部屋の分まで積むのはいい。でも三部屋先まで積むと、カートが重くて取り回しが悪くなる。一部屋先まで、と決めてます。
シマダ ちょうどいい先読みの幅がある、ということですね。一部屋先までは速さに効いて、三部屋先からは重さに変わる。
シマダ ここからが、今日の本題かもしれません。この分野に、よく引かれる言葉があります。「計算機科学には難しい問題が二つしかない。キャッシュの無効化と、名前付けだ」。フィル・カールトンという人の言葉とされています。手元に置いた控えが、いつの間にか古くなっている——本物が変わったのに、手元の控えだけ昔のまま。これを取り替えるのが、なぜか異様に難しい。
シマダ 家でいちばん分かりやすいのは、冷蔵庫の奥です。手前のものはよく取り替わる。でも奥は手が届かない場所、つまり遠いキャッシュで、賞味期限の切れた古い情報が居座る。本人は「ある」と思っている。実際には使えない。古くなった控えのことを、CSではstale——腐ったデータ、と呼びます。
マキノ 体のほうにも残りますよ。引っ越して半年経つのに、夜中に水を飲もうとして、前の家のコップの場所に手が伸びる。頭では分かってるのに、手が前の配置を覚えてる。
シマダ それも無効化の失敗です。家の中身は変わったのに、体に焼き付いたキャッシュだけが取り替わらない。頭で「変わった」と知っていても、手のほうの控えは、すぐには更新されない。
マキノ 一番厄介なのは、家族で配置を変えたときですね。誰かが良かれと思ってハサミの定位置を変える。本人は新しい場所を覚えてる。でも、ほかの全員が前の場所を探す。一人が更新して、残りが古いまま。
シマダ ……それは、前回の話につながります。一人が場所を変えたとき、それを全員の頭に書き込まないと、ほかの人のキャッシュは古いまま残る。配置の変更は、変えた本人にとっては一瞬でも、ほかの人の控えを全部書き換えないと、家全体としては整合が取れない。無効化が難しいのは、自分の控えは更新できても、他人の控えまでは手が届かないからです。
マキノ だから現場では、配置は勝手に変えないのが鉄則です。変えるなら、全員に言ってから。言わずに変えた人が、たいてい一番効率がいいつもりでいる。
シマダ 最後に、玄関の鍵の話をさせてください。これだけは、家の中で唯一、ヒット率100%であるべきエントリだと思うんです。出かけるたびに必ず使う。見つからなければ、外出そのものが止まる。だから定位置を一つ決めて、必ずそこに戻す。理屈の上では、これ以上ないキャッシュの優等生です。
シマダ ところが現実には、玄関に「とりあえず置き場」が増殖する。郵便物、レシート、買ったまま開けていない荷物。最初は鍵専用だったはずの場所が、だんだん何でも置く場所になる。定位置が、ただの置き場に変わっていく。そうなると、鍵はその山に紛れて、ヒット率が落ちる。
マキノ うちは、鍵が三回消えました。三回目で、玄関の壁にフックを付けたんです。帰ったら掛ける、出るとき外す。それだけ。それで消えなくなった。
シマダ フックは、置き場を一点に固定する仕掛けですね。
マキノ 仕掛けっていうほどのものじゃないです。要は、置く場所を一個に減らしただけ。私、二十二年カートを積んで、ポーチの六点も季節で入れ替えて、人の家のゆうべを毎日まっさらにしてます。それでも、自分の家の鍵は三回なくしてる。手元に置けば速い、っていうのは知ってるんですよ。知ってても、自分の家ではフックを付けるまでできなかった。家ってのは、そういうところです。
第3回はキューを取り上げる。洗濯物、シンクの食器、片づかないタスク——どれも「待っているものの行列」だ。先に入れたものから出すのか（FIFO）、最後に積んだものから出すのか（LIFO）、それとも急ぎから割り込ませるのか（優先度つきキュー）。並んで待っているものを、どの順で片づけるかの話をする。
#3 洗濯かごは先入れ先出しか——キュー（近日公開）
「家事のコンピュータサイエンス」は、シマダ（AI使用法研究者）とマキノトモエ（ホテル客室清掃員22年）の対談シリーズです。コンピュータサイエンスの基本概念を一つずつ取り上げ、掃除・洗濯・炊事・買い物・名もなき家事に当ててみる。効率だけでなく、快適さ・分担・諦めも等価に扱います。生成エッセイの現在地に戻る。