For Gauche 0.9.5

Next: , Previous: , Up: Library modules - Utilities   [Contents][Index]

12.7 data.cache - Cache

Module: data.cache

A cache is similar to a dictionary, associating keys to values, but its entries may dissapear according to the policy of the cache algorithm. This module defines a common protocol for cache datatypes, and also provides several typical cache implementations.


Let’s start from simple examples to get the idea.

Suppose you want to read files and you want to cache the frequently read ones. The following code defines a cached version of 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))))

The procedure closes a variable file-cache, which is an LRU (least recently used) cache that associates string pathnames to the file contents. The actual logic is in cache-through!, which first consults the cache if it has an entry for the path. If the cache has the entry, its value (the file content) is returned. If not, it calls file->string with the path to fetch the file content, register it to the cache, and return it. The capacity of cache is set to 10 (the first argument of make-lru-cache), so when the 11th file is read, the least recently used file will be purged from the cache.

The effect of cache isn’t very visible in the above example. You can insert some print stubs to see the cache is actually in action:

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

Caveat: A cache itself isn’t MT-safe. If you are using it in multithreaded programs, you have to wrap it with an atom (see Synchronization primitives):

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

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

Common properties of caches

A cache of any kind has a comparator and a storage. The comparator is used to compare keys; in the example above, we use string-comparator to compare string pathnames (See Basic comparators, for more about comparators).

The storage is a dictionary that maps keys to internal structures of the cache. By default, a hashtable is created automatically using the given comparator (or, if a comparator is omitted, using default-comparator). The comparator must have hash function.

Alternatively, you can give a pre-filled dictionary (copied from another instance of the same kind of cache) to start cache with some data already in it. Note that what the cache keeps in the dictionary totally depends on the cache algorithm, so you can’t just pass a random dictionary; it has to be created by the same kind of cache. If you pass in the storage, the comparator is taken from it.

Thus, the comparator constructors uniformly take keyword arguments comparator and storage; you can specify either one, or omit both to use the defaults.

Predefined caches

For storage and comparator keyword arguments, see above.

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

Creates and returns a FIFO (first-in, first-out) cache that can hold up to capacity entries. If the number of entries exceeds capacity, the oldest entry is removed.

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

Creates and returns an LRU (least recently used) cache that can hold up to capacity entries. If the number of entries exceeds capacity, the least recently used entry is removed.

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

Creates and returns a TTL (time to live) cache with the timeout value timeout. Each entry is timestamped when it’s inserted, and it is removed when the current time passes timeout unit from the timestamp. The actual entry removal is done when the cache is accessed.

By default, the Unix system time (seconds from Epoch) is used as a timestamp, and timeout is in seconds. It may not be fine-grained enough if you add multiple entries in shorter intervals than seconds. You can customize it by giving a thunk to timestamper; the thunk is called to obtain a timestamp, which can be any monotonically increasing real number. If you give timestamper, the unit of timeout value should be the same as whatever timestamper returns.

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

A variation of TTL cache, but the entry’s timestamp is updated (refreshed) whenever the entry is read. Hence we call it TTL with refresh (TTLR). But you can also think it as a variation of LRU cache with timeout.

The unit of timeout, and the role of timestamper argument, are the same as make-ttl-cache.

Common operations of caches

The following APIs are for the users of a cache.

Function: cache-lookup! cache key :optional default

Look for an entry with key in cache, and returns its value if it exists. If there’s no entry, the procedure returns default if it is provided, or throws an error otherwise.

Some types of cache algorithms update cache by this operation, hence the bang is in the name.

Function: cache-through! cache key value-fn

Look for an entry with key in cache, and returns its value if it exists. If there’s no entry, a procedure value-fn is called with key as the argument, and its return value is inserted into cache and also returned.

Generic function: cache-write! cache key value

This inserts association of key and value into cache. If there’s already an entry with key, it is overwritten. Otherwise a new entry is created.

The same effect can be achieved by calling cache-evict! then cache-through!, but cache algorithms may provide efficient way through this method.

Generic function: cache-evict! cache key

Removes an entry with key from cache, if it exists.

Generic function: cache-clear! cache

Removes all entries from cache.

Implementing a cache algorithm

Each cache algorithm must define a class inheriting <cache>, and implement the following two essential methods. The higher-level API calls them.

Generic function: cache-check! cache key

Looks for an entry with key in cache. If it exists, returns a pair of key and the associated value. Otherwise, returns #f. It may update the cache, for example, the timestamp of the entry for being read.

Generic function: cache-register! cache key value

Add an entry with key and associated value into cache. This is called after key is confirmed not being in cache.

Additionally, the implementation should consider the following points.

There are several procedures that help implementing cache subclasses:

Function: cache-comparator cache
Function: cache-storage 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:

Function: cache-populate-queue! queue storage

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.

Function: cache-compact-queue! queue storage

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.

Function: cache-renumber-entries! queue storage

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: Library modules - Utilities   [Contents][Index]