Next: ヒープ, Previous: パスワードハッシュ, Up: ライブラリモジュール - ユーティリティ [Contents][Index]
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->stringがpathを引数として呼ばれ、
それが返したファイルの中身がキャッシュに登録され、返されます。
キャッシュの容量は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が使われます。
あるいは、 (同じ種類のキャッシュからコピーされた)辞書をストレージとして渡すことで、 既にエントリがある状態のキャッシュを作ることもできます。 キャッシュが辞書に登録している構造はキャッシュアルゴリズムごとに異なるので、 何でも辞書を渡せるわけではないことに注意してください。 同じ種類のキャッシュによって作られた辞書しか渡せません。 ストレージとなる辞書を渡した場合、比較器はその辞書から取られます。
従ってキャッシュのコンストラクタは共通してcomparatorとstorageの キーワード引数を取ります。デフォルトの動作で良ければ、 どちらかひとつ、あるいは両方とも省略することができます。
storageとcomparatorキーワード引数については上の節を参照してください。
{data.cache} capacity個までのエントリを保持できる、FIFO(先入れ先出し)キャッシュを作って返します。 エントリ数がcapacityを越えそうになった場合、一番古いものから削除されます。
{data.cache} capacity個までのエントリを保持できる、 LRU(least recently used)キャッシュを作って返します。 エントリ数がcapacityを越えそうになった場合、一番長く使われなかったものから削除されます。
{data.cache} タイムアウト値timeoutを持つTTL(生存時間)キャッシュを作って返します。 各エントリには、挿入された時間が記録されます。timeoutを経過したエントリは削除されます。 実際の削除は、キャッシュがアクセスされた時に行われます。
デフォルトではUnixシステム時間(Epochからの秒数)がタイムスタンプに使われます。 1秒より短い間隔でたくさんのエントリが追加される場合にはこれでは分解能が足りないかもしれません。 timestamperにサンクを与えることで、タイムスタンプをカスタマイズすることができます。 キャッシュは時刻が必要になる度にtimestamperを引数無しで呼び出します。 timestamperは単調非減少な実数を返さねばなりません(物理的な時間と結びついている必要は ありません)。 timestamperを与えた場合、timeout引数の単位は timestamperが返す値の単位と同じでなければなりません。
{data.cache} TTLキャッシュのバリエーションで、エントリは書き込まれた時だけでなく、 読み出された時にもタイムスタンプが更新されます。 手続きの名前TTLRは、リフレッシュ付きTTL(TTL with refresh)という意味です。 ただ、これをタイムアウト付きLRUキャッシュと見ることもできます。
タイムアウトの単位およびtimestamper引数の役割については、
make-ttl-cacheと同じです。
以下のAPIはキャッシュのユーザに向けたものです。
{data.cache} cacheからkeyに結びつけられたエントリを探し、見つかれば返します。 エントリが無い場合は、defaultが与えられていればそれを返し、 与えられていなければエラーを投げます。
キャッシュアルゴリズムによってはこの操作でcacheがアップデートされる場合があるため、 名前にエクスクラメーションマークがついています。
{data.cache}
cacheからkeyに結びつけられたエントリを探し、見つかれば返します。
見つからなかった場合、value-fnがkeyを引数として呼び出され、
その結果がcacheに新たなエントリとして追加され、またcache-through!の
戻り値として返されます。
{data.cache} cacheに、keyとvalueの関係を追加します。既にkeyに 結びつけられたエントリがあった場合は上書きされ、そうでなければ新たなエントリが作られます。
同じ効果は、cache-evict!を呼んでからcache-through!を呼ぶことでも
達成できますが、アルゴリズムによってはcache-write!に対して効率のよい
実装を提供しているかもしれません。
{data.cache} cacheからkeyに結びついたエントリを(もしあれば)削除します。
{data.cache} cache内のエントリを全て取り除きます。
新たなキャッシュアルゴリズムを提供するには、<cache>を継承したクラスを定義し、
次の二つの必須メソッドを実装します。高レベルAPIはこれらの必須メソッドを呼び出します。
{data.cache}
cacheからkeyに結びついたエントリを探します。
見つかれば、keyとその値とのペアを、見つからなければ#fを返します。
この時、必要ならばキャッシュを更新して構いません。
例えば読み出されたエントリのタイムスタンプを更新するなどです。
{data.cache} cacheに、keyと対応するvalueを追加します。 このメソッドは、cacheにkeyに対応するエントリが無いことが確認された後で 呼び出されます。
アルゴリズムの実装は、また以下の点を考慮しなければなりません。
next-method first, which sets up
the comparator and storage slots. You should check
if storage has pre-filled entries, and if so, set up other
internal structures appropriately.
cache-evict! and cache-clear! only
takes care of the storage of the cache. You should implement them
if your auxiliary structure needs to be taken care of.
cache-write! is just cache-evict!
followed by cache-register!. You may provide alternative method
if you can do it more efficiently, which is often the case.
There are several procedures that help implementing cache subclasses:
{data.cache} Returns the comparator and the storage of the cache, respectively.
Typical caches may be constructed with a storage (dictionary) and
a queue, where the storage maps keys to (<n> . <value>),
and queues holds (<key> . <n>), <n> being a number
(timestamp, counter, etc.) Here are some common operations work
on this queue-and-dictionary scheme:
{data.cache}
You can call this in the initialize method to set up the
queue. This procedure walks storage to construct (<key> . <n>)
pairs, sorts it in increasing order of <n>, and pushes them
into the queue.
{data.cache} The queue may contain multiple pairs with the same key. Sometimes the queue gets to have too many duplicated entries (e.g. the same entry is read repeatedly). This scans the queue and removes duplicated entries but the up-to-date one. After this operation, the length of the queue and the number of entries in the storage should match.
{data.cache}
This procedure renumbers <n>s in the queue and the storage
starting from 0, without changing their order, and returns the
maximum <n>. The duplicated entries in the queue is removed
as in cache-compact-queue!.
When you’re using monotonically increasing counter for <n> and
you don’t want <n> to get too big (i.e. bignums), you can
call this procedure occasionally to keep <n>’s in reasonable
range.
Next: ヒープ, Previous: パスワードハッシュ, Up: ライブラリモジュール - ユーティリティ [Contents][Index]