For Gauche 0.9.12Search (procedure/syntax/module):

Next: , Previous: , Up: ライブラリモジュール - ユーティリティ   [Contents][Index]

12.12 data.cache - キャッシュ

Module: data.cache

キャッシュは、キーと値を結びつけるという点では辞書と似たように動作しますが、 キャッシュアルゴリズムの方針によってエントリが消去されることがあります。 このモジュールは、キャッシュについて共通のプロトコルを定義し、 またいくつかの典型的なキャッシュの実装を提供します。

まず簡単な例によって、どんな具合かを示しましょう。

指定されたファイルを読み込むルーチンに、 頻繁に読むファイルをキャッシュする機能をつけたいとします。 次のコードはfile->stringにキャッシュ機能を持たせたものです。

(use data.cache)
(use file.util)

(define file->string/cached
  (let1 file-cache (make-lru-cache 10 :comparator string-comparator)
    (^[path] (cache-through! file-cache path file->string))))

この手続きはfile-cache変数をクロージャの中に綴じ込んでいます。 その値は文字列のパス名とファイルの中身を結びつけるLRU(least recently used)キャッシュです。 キャッシュの動作はcache-through!で実現されています。 この手続きは、 まずpathをキーとして持つエントリがfile-cacheにあるかどうか調べます。 そのキーを持つエントリがキャッシュ中にあればその値(ファイルの中身)が返されます。 キャッシュ中に無ければ、file->stringpathを引数として呼ばれ、 それが返したファイルの中身がキャッシュに登録され、返されます。 キャッシュの容量はmake-lru-cacheの第1引数で指定され、ここでは10になっています。 つまり、11個目のファイルが読まれた時に、一番長く使われていない (least recently used)ファイルがキャッシュから消去されます。

上の例そのままではキャッシュの効果が見え辛いです。 次の例の通り、printスタブをいれて、いろいろなファイルを file->string/cachedで読んでみて下さい。 いつキャッシュが実際にファイルの中身を取りにゆくかわかるでしょう。

(define file->string/cached
  (let1 file-cache (make-lru-cache 10 :comparator string-comparator)
    (^[path]
      (print #"file->string/cached called on ~path")
      (cache-through! file-cache path
                      (^[path]
                        (print #"cache miss.  fetching ~path")
                        (file->string path))))))

注意: キャッシュ自身はスレッドセーフではありません。 マルチスレッドプログラムでキャッシュを使う場合は、キャッシュをatomでラップしてください。

(use data.cache)
(use file.util)
(use gauche.threads)

(define file->string/cached
  (let1 file-cache (atom (make-lru-cache 10 :comparator string-comparator))
    (^[path]
      (atomic file-cache (cut cache-through! <> path file->string)))))

キャッシュに共通の性質

どんなキャッシュにも、比較器とストレージがあります。 比較器はキーを比較するのに使われます。上の例ではパス名を比較するために string-comparatorを渡しています 比較器について詳しくは基本的な比較器を参照してください。

ストレージは、キーとキャッシュ内部の構造とをマッピングする辞書です。 デフォルトでは与えられた比較器を使うハッシュテーブルが使われるので、 比較器はハッシュ関数を持っていなければなりません。 比較器が省略された場合はdefault-comparatorが使われます。

あるいは、 (同じ種類のキャッシュからコピーされた)辞書をストレージとして渡すことで、 既にエントリがある状態のキャッシュを作ることもできます。 キャッシュが辞書に登録している構造はキャッシュアルゴリズムごとに異なるので、 何でも辞書を渡せるわけではないことに注意してください。 同じ種類のキャッシュによって作られた辞書しか渡せません。 ストレージとなる辞書を渡した場合、比較器はその辞書から取られます。

従ってキャッシュのコンストラクタは共通してcomparatorstorageの キーワード引数を取ります。デフォルトの動作で良ければ、 どちらかひとつ、あるいは両方とも省略することができます。

定義済みのキャッシュ

storagecomparatorキーワード引数については上の節を参照してください。

Function: make-fifo-cache capacity :key storage comparator

{data.cache} capacity個までのエントリを保持できる、FIFO(先入れ先出し)キャッシュを作って返します。 エントリ数がcapacityを越えそうになった場合、一番古いものから削除されます。

Function: make-lru-cache capacity :key storage comparator

{data.cache} capacity個までのエントリを保持できる、 LRU(least recently used)キャッシュを作って返します。 エントリ数がcapacityを越えそうになった場合、一番長く使われなかったものから削除されます。

Function: make-ttl-cache timeout :key storage comparator timestamper

{data.cache} タイムアウト値timeoutを持つTTL(生存時間)キャッシュを作って返します。 各エントリには、挿入された時間が記録されます。timeoutを経過したエントリは削除されます。 実際の削除は、キャッシュがアクセスされた時に行われます。

デフォルトではUnixシステム時間(Epochからの秒数)がタイムスタンプに使われます。 1秒より短い間隔でたくさんのエントリが追加される場合にはこれでは分解能が足りないかもしれません。 timestamperにサンクを与えることで、タイムスタンプをカスタマイズすることができます。 キャッシュは時刻が必要になる度にtimestamperを引数無しで呼び出します。 timestamperは単調非減少な実数を返さねばなりません(物理的な時間と結びついている必要は ありません)。 timestamperを与えた場合、timeout引数の単位は timestamperが返す値の単位と同じでなければなりません。

Function: make-ttlr-cache timeout :key storage comparator timestamper

{data.cache} TTLキャッシュのバリエーションで、エントリは書き込まれた時だけでなく、 読み出された時にもタイムスタンプが更新されます。 手続きの名前TTLRは、リフレッシュ付きTTL(TTL with refresh)という意味です。 ただ、これをタイムアウト付きLRUキャッシュと見ることもできます。

タイムアウトの単位およびtimestamper引数の役割については、 make-ttl-cacheと同じです。

キャッシュに共通の操作

以下のAPIはキャッシュのユーザに向けたものです。

Function: cache-lookup! cache key :optional default

{data.cache} cacheからkeyに結びつけられたエントリを探し、見つかれば返します。 エントリが無い場合は、defaultが与えられていればそれを返し、 与えられていなければエラーを投げます。

キャッシュアルゴリズムによってはこの操作でcacheがアップデートされる場合があるため、 名前にエクスクラメーションマークがついています。

Function: cache-through! cache key value-fn

{data.cache} cacheからkeyに結びつけられたエントリを探し、見つかれば返します。 見つからなかった場合、value-fnkeyを引数として呼び出され、 その結果がcacheに新たなエントリとして追加され、またcache-through!の 戻り値として返されます。

Generic function: cache-write! cache key value

{data.cache} cacheに、keyvalueの関係を追加します。既にkeyに 結びつけられたエントリがあった場合は上書きされ、そうでなければ新たなエントリが作られます。

同じ効果は、cache-evict!を呼んでからcache-through!を呼ぶことでも 達成できますが、アルゴリズムによってはcache-write!に対して効率のよい 実装を提供しているかもしれません。

Generic function: cache-evict! cache key

{data.cache} cacheからkeyに結びついたエントリを(もしあれば)削除します。

Generic function: cache-clear! cache

{data.cache} cache内のエントリを全て取り除きます。

キャッシュアルゴリズムの実装

新たなキャッシュアルゴリズムを提供するには、<cache>を継承したクラスを定義し、 次の二つの必須メソッドを実装します。高レベルAPIはこれらの必須メソッドを呼び出します。

Generic function: cache-check! cache key

{data.cache} cacheからkeyに結びついたエントリを探します。 見つかれば、keyとその値とのペアを、見つからなければ#fを返します。 この時、必要ならばキャッシュを更新して構いません。 例えば読み出されたエントリのタイムスタンプを更新するなどです。

Generic function: cache-register! cache key value

{data.cache} cacheに、keyと対応するvalueを追加します。 このメソッドは、cachekeyに対応するエントリが無いことが確認された後で 呼び出されます。

アルゴリズムの実装は、また以下の点を考慮しなければなりません。

キャッシュのサブクラスを実装するのに便利な手続きがいくつか用意してあります:

Function: cache-comparator cache
Function: cache-storage cache

{data.cache} キャッシュのcomparatorstorageを返します。

典型的なキャッシュは、storageとしての辞書と、キューで作られます。 ここでstorageは、キーを(<n> . <value>)にマップし、 キューは(<key> . <n>)を保持します。 ただし<n>はタイムスタンプやカウンタなど何からの数値です。 キャッシュがこの「キューと辞書」を使って実装されている場合は、 以下の共通手続きが使えるでしょう:

Function: cache-populate-queue! queue storage

{data.cache} initializeメソッドの中でこの手続きを呼ぶことにより、 キューを初期化できます。この手続きは、キーを(<n> . <value>)にマップする辞書である storageを走査し、(<key> . <n>)というペアを作り、 <n>の昇順にソートしてそれをqueueにプッシュします。

Function: cache-compact-queue! queue storage

{data.cache} キューに、同じキーを持つエントリが複数含まれることがあります。 しばしば、そういった重複エントリが多くなりすぎる場合があります (例えばキーが読み出される度にタイムスタンプをキューにプッシュしていて、 同じキーが何度も読まれた場合)。この手続きはキューを走査し、 キーが重複しているエントリは最新のもの以外を取り除きます。 この操作の後では、キューの長さとstorageのエントリ数は一致しているはずです。

Function: cache-renumber-entries! queue storage

{data.cache} この手続きはキュー内の<n>を、順序を変えることなく、0から昇順に付け直し、 <n>の最大値を返します。キーが重複するエントリはcache-compact-queue!と 同様に、最新のもの以外取り除かれます。

<n>に単調増加する数を使っていて、長い時間の後では<n>がbignum になって効率が落ちる心配があれば、この手続きを適宜呼ぶことで<n>を適切な 範囲内に収めることができるでしょう。


Next: , Previous: , Up: ライブラリモジュール - ユーティリティ   [Contents][Index]


For Gauche 0.9.12Search (procedure/syntax/module):