You are looking at historical revision 45623 of this page. It may differ significantly from its current revision.

lru-cache

Description

An LRU (least recently used) cache for Chicken Scheme 5.

Keys and values may be of any type. The cache uses a hash table for O(1) lookup and a doubly-linked list to maintain access ordering. When the cache reaches capacity, the least recently used entry is evicted.

This implementation shares no lineage with the lru-cache egg, for Chicken Scheme 4, by Jim Ursetto.

Author

Christopher Harrison (Tweag)

Repository

https://github.com/tweag/lru-cache

Requirements

• srfi-69
• matchable

API

Cache creation

[procedure] (make-lru-cache [capacity])

Create a new LRU cache. capacity is the maximum number of entries the cache will hold before evicting the least recently used entry; defaulting to 64.

Lookup and mutation

[procedure] (lru-cache-ref cache key)

Returns the value associated with key in cache, promoting it to the most recently used position. Signals an error if key is not present.

[procedure] (lru-cache-ref cache key thunk)

Returns the value associated with key in cache if present, promoting it to the most recently used position. If key is not present, calls thunk (a procedure of zero arguments) to compute the value, caches the result and returns it.

[procedure] (lru-cache-set! cache key value)

Associates key with value in cache. If key already exists, updates its value and promotes it to the most recently used position. If key is new and the cache is at capacity, the least recently used entry is evicted.

[procedure] (lru-cache-delete! cache key)

Removes the entry for key from cache. Signals an error if key is not present.

[procedure] (lru-cache-clear! cache)

Removes all entries from cache.

Inspection

[procedure] (lru-cache-size cache)

Returns the number of entries currently in cache.

[procedure] (lru-cache-capacity cache)

Returns the maximum number of entries cache can hold.

[procedure] (lru-cache-has-key? cache key)

Returns #t if key is present in cache, #f otherwise. Does not affect the access ordering.

Iteration

[procedure] (lru-cache-for-each cache proc)

Apply proc (a procedure of two arguments: the entry key and value, respectively) to each entry in cache, ordered from most recently used to least recently used. Does not affect the access ordering.

Note: proc must not mutate cache.

[procedure] (lru-cache-fold cache proc init)

Calls proc (a procedure of three arguments: the entry key, value and accumulator, respectively) with each entry in cache, ordered from most recently to least recently used; the initial folded value is init, returns the final folded value. Does not affect the access ordering.

Note: proc must not mutate cache.

[procedure] (lru-cache->alist cache)

Returns an association list of all key-value pairs in cache, ordered from most recently used to least recently used. Does not affect the access ordering.

[procedure] (lru-cache-keys cache)

Returns a list of all keys in cache, ordered from most recently used to least recently used. Does not affect the access ordering.

[procedure] (lru-cache-values cache)

Returns a list of all values in cache, ordered from most recently used to least recently used. Does not affect the access ordering.

Memoisation

[syntax] (define-memoised/lru [capacity] (name arg ...) body ...)

Defines a top-level procedure name, with its argument list and body definition per usual, but return values are cached based on the arguments (compared as a list). capacity defaults to 64.

[procedure] (memoise/lru proc [capacity])

Returns a new procedure that caches the results of calling proc. Arguments are used as the cache key (compared as a list). capacity defaults to 64.

Note: For recursive procedures, the memoised version must replace the original binding for recursive calls to benefit from caching. It is better to use define-memoised/lru in such cases, wherever possible.

(define (fib n)
  (cond
    ((= n 0) 1)
    ((= n 1) 1)
    (else (+ (fib (- n 1)) (fib (- n 2))))))

(set! fib (memoise/lru fib))

Examples

(import lru-cache
        (chicken format))

;; Create a cache with capacity 3
(define cache (make-lru-cache 3))

;; Add some entries
(lru-cache-set! cache 'a 1)
(lru-cache-set! cache 'b 2)
(lru-cache-set! cache 'c 3)

(lru-cache-keys cache)  ; => (c b a)

;; Accessing an entry promotes it
(lru-cache-ref cache 'a)  ; => 1
(lru-cache-keys cache)    ; => (a c b)

;; Adding a fourth entry evicts the LRU
(lru-cache-set! cache 'd 4)
(lru-cache-keys cache)        ; => (d a c)
(lru-cache-has-key? cache 'b) ; => #f

;; Using a thunk for cache-or-compute
(lru-cache-ref cache 'e
  (lambda () (+ 40 2)))   ; => 42

;; Memoisation
(define-memoised/lru (fib n)
  (printf "computing fib ~A~N" n)
  (cond
    ((= n 0) 1)
    ((= n 1) 1)
    (else (+ (fib (- n 1)) (fib (- n 2))))))

(fib 5)  ; prints "computing fib 5" .. "computing fib 0", returns 8
(fib 5)  ; returns 8, no printing

License

LGPL-3.0-or-later

Version history

0.1.0

Initial release