The function-cache Reference Manual

Table of Contents

The function-cache Reference Manual

This is the function-cache Reference Manual, version 1.0.3, generated automatically by Declt version 3.0 "Montgomery Scott" on Wed Feb 19 20:32:48 2020 GMT+0.

1 Introduction

function-cache

A common lisp library that provides extensible function result caching based on arguments (an expanded form of memoization).

Differences from fare-memoization

• By default uses separate tables for each function
• Supports other cache structures (eg: optimization for thunks, mru-heaps)
• Supports optional caching for functions that are called in transient cache contexts (eg: http-context, web application session etc)
• Supports timeouts to invalidate caches, and purging of expired cached results
• A more robust cache clearing scheme, clear all caches, all caches in a package, or just a specific cache

API

DEFCACHED

Creates a cached function named SYMBOL and a cache object named *{FN-NAME}-CACHE* SYMBOL can also be a list

(FN-NAME &rest cache-init-args &key CACHE-CLASS TABLE TIMEOUT SHARED-RESULTS?)

• CACHE-CLASS - controls what cache class will be instantiated (uses default-cache-class if not provided)
• TABLE - a shared cache-store to use, usually a hash-table, a function that returns a hashtable, or a symbol whose value is a hash-table
• TIMEOUT - how long entries in the cache should be considered valid for, in seconds
• SHARED-RESULTS? - do we expect that we are sharing cache space with other things defaults to t if TABLE is provided

(defcached symbol (lambda-list) ...)
(defcached (symbol &key table cache-class timeout shared-results?) (lambda-list) ...)
EG:

(defcached (foo :timeout 10) (arg0)
  (sleep 3)
  arg0)
(foo 1) ;; waits 3s then returns 1
(foo 1) ;; returns 1 immediately
(foo 0) ;; waits 3s then returns 0
(foo 0) ;; returns 0 immediately
(foo 2) ;; waits 3s then returns 2
(foo 3) ;; waits 3s then returns 3
(foo 1) ;; has timedout, waits 3s then returns 1

Cache-objects and Names

Each cached function will have a cache object associated with it in special-variable *{FN-NAME}-CACHE*. You can find a cache object for a function name using find-function-cache-for-name if necessary. In most of the api, a function-name or a cache-object should be interchangable.

function-cache, thunk-cache, hash-table-function-cache, single-cell-function-cache

The basic types of function-caches currently provided.

• Function-cache - abstract class for all function-caches
• thunk-cache - a cache specialized for storing the results of thunks
• automatically chosen, for functions of 0 args
• hash-table-function-cache
• A hash-table backed function-cache, supports shared hash-tables, but defaults to a unique hash-table for each cache
• Supports dynamically available caching (eg: web-request contexts), by setting cache-results to a function or symbol that will possibly return a hashtable. If either of these return nil, then caching is bypassed for that call
• single-cell-function-cache
• caches the single most recently used call
• lru-cache
• A cache with a fixed capacity
• Backed by a combination of a hash table and doubly-linked list
• When the maximimum capacity is reached the least recently used cache entries are deleted.
• mru-cache
• A cache with a fixed capacity
• Backed by a combination of a hash table and doubly-linked list
• When the maximum capacity is reached the most recently used cache entries are deleted.

get-cached-value, (setf get-cached-value)

One of the main expansion points for new cache subclasses. These place and retrieve values from whatever backing store the cache is using

Returns (values results cached-at) and stores the results of executing the underlying function.

purge-cache, purge-all-caches

A function that will remove expired entries from the cache, allowing them to be garbage collected

clear-cache, clear-all-caches

A function that will remove all cached results from the cache.

clear-cache accepts either a cache or the name of a cached function

clear-cache-partial-arguments

This function will go through the cached-results removing keys that partially match the to-match list.

This is used to clear the cache of shared? caches, but is also useful in other cases, where we need to clear cache for some subset of the arguments (eg: a cached funcall might wish to clear the cache of a specific funcalled function).

Matches arguments for those provided. Anything not provided is considered function-cache:dont-care. Anything specified as function-cache:dont-care is not used to determine if there is a match

uses partial-argument-match? to determine if the key should be removed

partial-argument-match?

Trys to see if the cache-key matches the to-match partial key passed in.

The basic implementation is to go through the cache-keys and match in order, skipping to-match component that is function-cache:dont-care

compute-cache-key, defcached-hashkey

Compute-cache-key, takes a cache and a list of arguments and turns those into a valid cache-key for the cache, by calling defcached-hashkey recursively through the argument tree.

Shared cache-backings will ensure the function name is the first token in this cache-key

cacher

Cacher is responsible for looking up memoized results in the cache, checking if they are expired/missing and running the body if so, caching and returning the result

*cache-names*

A list of all the special variables created by defcached. Used to ease clearing/purging all the caches, and for introspective purposes.

Authors

• Acceleration.net
• Russ Tyndall
• Nathan Bird
• Ryan Davis

;; Copyright (c) 2013 Russ Tyndall , Acceleration.net http://www.acceleration.net
;; All rights reserved.
;;
;; Redistribution and use in source and binary forms, with or without
;; modification, are permitted provided that the following conditions are
;; met:
;;
;;  - Redistributions of source code must retain the above copyright
;;    notice, this list of conditions and the following disclaimer.
;;
;;  - Redistributions in binary form must reproduce the above copyright
;;    notice, this list of conditions and the following disclaimer in the
;;    documentation and/or other materials provided with the distribution.
;;
;; THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
;; "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
;; LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
;; A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT
;; OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
;; SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
;; LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
;; DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
;; THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
;; (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
;; OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

2 Systems

The main system appears first, followed by any subsystem dependency.

2.1 function-cache

Author

Acceleration.net <programmers@acceleration.net>

License

BSD

Description

A Simple Caching Layer for functions

Version

1.0.3

Dependencies

• alexandria
• cl-interpol
• iterate
• symbol-munger
• closer-mop

Source

function-cache.asd (file)

Component

src (module)

3 Modules

Modules are listed depth-first from the system components tree.

3.1 function-cache/src

Parent

function-cache (system)

Location

src/

Components

• packages.lisp (file)
• protocol.lisp (file)
• capacity.lisp (file)
• metering.lisp (file)
• function-cache.lisp (file)
• thunk.lisp (file)
• single-cell.lisp (file)
• hash-table.lisp (file)
• ordered.lisp (file)
• cache.lisp (file)

4 Files

Files are sorted by type and then listed depth-first from the systems components trees.

4.1 Lisp

4.1.1 function-cache.asd

Location

function-cache.asd

Systems

function-cache (system)

Packages

function-cache-system

4.1.2 function-cache/src/packages.lisp

Parent

src (module)

Location

src/packages.lisp

Packages

function-cache

4.1.3 function-cache/src/protocol.lisp

Dependency

packages.lisp (file)

Parent

src (module)

Location

src/protocol.lisp

Exported Definitions

• at-cache-capacity? (generic function)
• at-cache-capacity? (method)
• cached-results-count (generic function)
• cached-results-count (method)
• cached-results-count (method)
• cached-results-count (method)
• clear-cache (generic function)
• defcached-hashkey (generic function)
• defcached-hashkey (method)
• get-cached-value (generic function)
• (setf get-cached-value) (generic function)
• (setf get-cached-value) (method)
• purge-cache (generic function)
• reduce-cached-set (generic function)

Internal Definitions

• *cache* (special variable)
• *cached-at* (special variable)
• cache (method)
• (setf cache) (method)
• cache-value-condition (condition)
• cached-a-value (condition)
• cached-at (method)
• (setf cached-at) (method)
• expired-a-value (condition)
• expired? (generic function)
• expired? (method)
• key (method)
• (setf key) (method)
• key-cached? (generic function)
• key-cached? (method)
• make-cache-backing (generic function)
• make-cache-backing (method)
• removed-a-value (condition)
• removed-at (method)
• (setf removed-at) (method)
• value (method)
• (setf value) (method)

4.1.4 function-cache/src/capacity.lisp

Dependency

protocol.lisp (file)

Parent

src (module)

Location

src/capacity.lisp

Exported Definitions

• at-cache-capacity? (method)
• cache-capacity-mixin (class)
• capacity (method)
• (setf capacity) (method)
• (setf get-cached-value) (method)
• reduce-by-ratio (method)
• (setf reduce-by-ratio) (method)

Internal Definitions

number-to-remove (function)

4.1.5 function-cache/src/metering.lisp

Dependency

capacity.lisp (file)

Parent

src (module)

Location

src/metering.lisp

Exported Definitions

• accesses (function)
• get-cached-value (method)
• hit-ratio (function)
• hits (method)
• (setf hits) (method)
• metered-mixin (class)
• misses (method)
• (setf misses) (method)
• reset-counters (generic function)
• reset-counters (method)
• reset-counters (method)

Internal Definitions

• get-cached-object-stats (function)
• incf-hash (function)

4.1.6 function-cache/src/function-cache.lisp

Dependency

metering.lisp (file)

Parent

src (module)

Location

src/function-cache.lisp

Exported Definitions

• *bypass-cache* (special variable)
• cached-results (method)
• cached-results (method)
• (setf cached-results) (method)
• clear-cache (method)
• compute-cache-key (generic function)
• compute-cache-key (method)
• purge-cache (method)
• timeout (method)
• (setf timeout) (method)

Internal Definitions

• %insert-into-cache (function)
• body-fn (method)
• (setf body-fn) (method)
• cacher (generic function)
• cacher (method)
• function-cache (class)
• lambda-list (method)
• (setf lambda-list) (method)
• name (method)
• (setf name) (method)
• shared-results? (method)
• (setf shared-results?) (method)

4.1.7 function-cache/src/thunk.lisp

Dependency

function-cache.lisp (file)

Parent

src (module)

Location

src/thunk.lisp

Exported Definitions

• cached-results-count (method)
• get-cached-value (method)
• (setf get-cached-value) (method)
• purge-cache (method)
• thunk-cache (class)

Internal Definitions

key-cached? (method)

4.1.8 function-cache/src/single-cell.lisp

Dependency

thunk.lisp (file)

Parent

src (module)

Location

src/single-cell.lisp

Exported Definitions

• cached-results-count (method)
• get-cached-value (method)
• (setf get-cached-value) (method)
• purge-cache (method)
• single-cell-function-cache (class)

Internal Definitions

• key-cached? (method)
• make-cache-backing (method)
• test (method)
• (setf test) (method)

4.1.9 function-cache/src/hash-table.lisp

Dependency

single-cell.lisp (file)

Parent

src (module)

Location

src/hash-table.lisp

Exported Definitions

• cached-results-count (method)
• clear-cache (method)
• clear-cache-partial-arguments (generic function)
• clear-cache-partial-arguments (method)
• get-cached-value (method)
• (setf get-cached-value) (method)
• hash-table-function-cache (class)
• hash-table-function-cache-with-capacity (class)
• partial-argument-match? (generic function)
• partial-argument-match? (method)
• purge-cache (method)
• reduce-cached-set (method)

Internal Definitions

• *default-hash-init-args* (special variable)
• hash-init-args (method)
• (setf hash-init-args) (method)
• key-cached? (method)
• make-cache-backing (method)
• metered-hash-table-cache (class)

4.1.10 function-cache/src/ordered.lisp

Dependency

hash-table.lisp (file)

Parent

src (module)

Location

src/ordered.lisp

Exported Definitions

• clear-cache (method)
• clear-cache-partial-arguments (method)
• get-cached-value (method)
• (setf get-cached-value) (method)
• lru-cache (class)
• mru-cache (class)
• purge-cache (method)
• reduce-cached-set (method)
• reduce-cached-set (method)

Internal Definitions

• %add-cached-node (function)
• %move-cached-node (function)
• %remove-cached-node (function)
• cache-node (type)
• cnode (function)
• cnode (structure)
• cnode-cache-key (function)
• (setf cnode-cache-key) (function)
• cnode-newer (function)
• (setf cnode-newer) (function)
• cnode-older (function)
• (setf cnode-older) (function)
• cnode-p (function)
• cnode-result (function)
• (setf cnode-result) (function)
• copy-cnode (function)
• newest-node (method)
• (setf newest-node) (method)
• oldest-node (method)
• (setf oldest-node) (method)
• ordered-cache-mixin (class)
• sync-ordered-cache (function)

4.1.11 function-cache/src/cache.lisp

Dependency

ordered.lisp (file)

Parent

src (module)

Location

src/cache.lisp

Exported Definitions

• *cache-names* (special variable)
• *default-cache-class* (special variable)
• clear-cache (method)
• clear-cache (method)
• clear-cache-all-function-caches (function)
• defcached (macro)
• find-function-cache-for-name (function)
• purge-all-caches (function)
• purge-cache (method)

Internal Definitions

• %call-list-for-lambda-list (function)
• %ensure-unquoted (function)
• default-cache-class (generic function)
• default-cache-class (method)
• do-caches (function)

5 Packages

Packages are listed by definition order.

5.1 function-cache-system

Source

function-cache.asd

Use List

• asdf/interface
• common-lisp

5.2 function-cache

A simple caching layer for functions

Source

packages.lisp (file)

Use List

• iterate
• common-lisp

Exported Definitions

• *bypass-cache* (special variable)
• *cache-names* (special variable)
• *default-cache-class* (special variable)
• accesses (function)
• at-cache-capacity? (generic function)
• at-cache-capacity? (method)
• at-cache-capacity? (method)
• cache-capacity-mixin (class)
• cached-results (generic function)
• cached-results (method)
• cached-results (method)
• (setf cached-results) (method)
• (setf cached-results) (generic function)
• cached-results-count (generic function)
• cached-results-count (method)
• cached-results-count (method)
• cached-results-count (method)
• cached-results-count (method)
• cached-results-count (method)
• cached-results-count (method)
• capacity (generic function)
• capacity (method)
• (setf capacity) (method)
• (setf capacity) (generic function)
• clear-cache (generic function)
• clear-cache (method)
• clear-cache (method)
• clear-cache (method)
• clear-cache (method)
• clear-cache (method)
• clear-cache-all-function-caches (function)
• clear-cache-partial-arguments (generic function)
• clear-cache-partial-arguments (method)
• clear-cache-partial-arguments (method)
• compute-cache-key (generic function)
• compute-cache-key (method)
• defcached (macro)
• defcached-hashkey (generic function)
• defcached-hashkey (method)
• find-function-cache-for-name (function)
• get-cached-value (generic function)
• get-cached-value (method)
• (setf get-cached-value) (method)
• get-cached-value (method)
• (setf get-cached-value) (method)
• get-cached-value (method)
• (setf get-cached-value) (method)
• get-cached-value (method)
• (setf get-cached-value) (method)
• get-cached-value (method)
• (setf get-cached-value) (generic function)
• (setf get-cached-value) (method)
• (setf get-cached-value) (method)
• hash-table-function-cache (class)
• hash-table-function-cache-with-capacity (class)
• hit-ratio (function)
• hits (generic function)
• hits (method)
• (setf hits) (method)
• (setf hits) (generic function)
• lru-cache (class)
• metered-mixin (class)
• misses (generic function)
• misses (method)
• (setf misses) (method)
• (setf misses) (generic function)
• mru-cache (class)
• partial-argument-match? (generic function)
• partial-argument-match? (method)
• purge-all-caches (function)
• purge-cache (generic function)
• purge-cache (method)
• purge-cache (method)
• purge-cache (method)
• purge-cache (method)
• purge-cache (method)
• purge-cache (method)
• reduce-by-ratio (generic function)
• reduce-by-ratio (method)
• (setf reduce-by-ratio) (method)
• (setf reduce-by-ratio) (generic function)
• reduce-cached-set (generic function)
• reduce-cached-set (method)
• reduce-cached-set (method)
• reduce-cached-set (method)
• reset-counters (generic function)
• reset-counters (method)
• reset-counters (method)
• single-cell-function-cache (class)
• thunk-cache (class)
• timeout (generic function)
• timeout (method)
• (setf timeout) (method)
• (setf timeout) (generic function)

Internal Definitions

• %add-cached-node (function)
• %call-list-for-lambda-list (function)
• %ensure-unquoted (function)
• %insert-into-cache (function)
• %move-cached-node (function)
• %remove-cached-node (function)
• *cache* (special variable)
• *cached-at* (special variable)
• *default-hash-init-args* (special variable)
• body-fn (generic function)
• body-fn (method)
• (setf body-fn) (method)
• (setf body-fn) (generic function)
• cache (generic function)
• cache (method)
• (setf cache) (method)
• (setf cache) (generic function)
• cache-node (type)
• cache-value-condition (condition)
• cached-a-value (condition)
• cached-at (generic function)
• cached-at (method)
• (setf cached-at) (method)
• (setf cached-at) (generic function)
• cacher (generic function)
• cacher (method)
• cnode (function)
• cnode (structure)
• cnode-cache-key (function)
• (setf cnode-cache-key) (function)
• cnode-newer (function)
• (setf cnode-newer) (function)
• cnode-older (function)
• (setf cnode-older) (function)
• cnode-p (function)
• cnode-result (function)
• (setf cnode-result) (function)
• copy-cnode (function)
• default-cache-class (generic function)
• default-cache-class (method)
• do-caches (function)
• expired-a-value (condition)
• expired? (generic function)
• expired? (method)
• function-cache (class)
• get-cached-object-stats (function)
• hash-init-args (generic function)
• hash-init-args (method)
• (setf hash-init-args) (method)
• (setf hash-init-args) (generic function)
• incf-hash (function)
• key (generic function)
• key (method)
• (setf key) (method)
• (setf key) (generic function)
• key-cached? (generic function)
• key-cached? (method)
• key-cached? (method)
• key-cached? (method)
• key-cached? (method)
• lambda-list (generic function)
• lambda-list (method)
• (setf lambda-list) (method)
• (setf lambda-list) (generic function)
• make-cache-backing (generic function)
• make-cache-backing (method)
• make-cache-backing (method)
• make-cache-backing (method)
• metered-hash-table-cache (class)
• name (generic function)
• name (method)
• (setf name) (method)
• (setf name) (generic function)
• newest-node (generic function)
• newest-node (method)
• (setf newest-node) (method)
• (setf newest-node) (generic function)
• number-to-remove (function)
• oldest-node (generic function)
• oldest-node (method)
• (setf oldest-node) (method)
• (setf oldest-node) (generic function)
• ordered-cache-mixin (class)
• removed-a-value (condition)
• removed-at (generic function)
• removed-at (method)
• (setf removed-at) (method)
• (setf removed-at) (generic function)
• shared-results? (generic function)
• shared-results? (method)
• (setf shared-results?) (method)
• (setf shared-results?) (generic function)
• sync-ordered-cache (function)
• test (generic function)
• test (method)
• (setf test) (method)
• (setf test) (generic function)
• value (generic function)
• value (method)
• (setf value) (method)
• (setf value) (generic function)

6 Definitions

Definitions are sorted by export status, category, package, and then by lexicographic order.

6.1 Exported definitions

6.1.1 Special variables

Special Variable: *bypass-cache*

if non-nil, skip any kind of caching

Package

function-cache

Source

function-cache.lisp (file)

Special Variable: *cache-names*

A list of all function-caches

Package

function-cache

Source

cache.lisp (file)

Special Variable: *default-cache-class*

cache class to use if unspecified and thunk is not applicable

Package

function-cache

Source

cache.lisp (file)

6.1.2 Macros

Macro: defcached SYMBOL LAMBDA-LIST &body BODY

Creates a cached function named SYMBOL and a cache object named *{FN-NAME}-CACHE* SYMBOL can also be a list (FN-NAME &rest CACHE-INIT-ARGS
&key CACHE-CLASS TABLE TIMEOUT SHARED-RESULTS?)

TABLE - a shared cache-store to use, usually a hash-table, a function that returns a hashtable, or a symbol whose value is a hash-table
TIMEOUT - how long entries in the cache should be considered valid for CACHE-CLASS - controls what cache class will be instantiated (uses default-cache-class if not provided)
SHARED-RESULTS? - do we expect that we are sharing cache space with other things defaults to t if TABLE is provided
CACHE-INIT-ARGS - any other args that should be passed to the cache

Package

function-cache

Source

cache.lisp (file)

6.1.3 Functions

Function: accesses CACHE

how many total accesses this cache has seen

Package

function-cache

Source

metering.lisp (file)

Function: clear-cache-all-function-caches &optional PACKAGE

Clear all the packages we know about. If there is a package mentioned, clear only those caches whose names are in that package

Package

function-cache

Source

cache.lisp (file)

Function: find-function-cache-for-name CACHE-NAME

given a name get the cache object associated with it

Package

function-cache

Source

cache.lisp (file)

Function: hit-ratio CACHE

Package

function-cache

Source

metering.lisp (file)

Function: purge-all-caches &optional PACKAGE

Call purge on all matching cache objects. If package is provided, purge only caches located within that package

Package

function-cache

Source

cache.lisp (file)

6.1.4 Generic functions

Generic Function: at-cache-capacity? CACHE

is the cache full?

Package

function-cache

Source

protocol.lisp (file)

Methods

Method: at-cache-capacity? (CACHE cache-capacity-mixin)

Source

capacity.lisp (file)

Method: at-cache-capacity? CACHE

Generic Function: cached-results OBJECT

Generic Function: (setf cached-results) NEW-VALUE OBJECT

Package

function-cache

Methods

Method: cached-results (CACHE function-cache) around

Coerce the refernce to the results into something we can use

Source

function-cache.lisp (file)

Method: cached-results (FUNCTION-CACHE function-cache)

automatically generated reader method

Source

function-cache.lisp (file)

Method: (setf cached-results) NEW-VALUE (FUNCTION-CACHE function-cache)

automatically generated writer method

Source

function-cache.lisp (file)

Generic Function: cached-results-count CACHE

A function to compute the number of results that have been cached. DOES NOT CHECK to see if the entries are expired

Package

function-cache

Source

protocol.lisp (file)

Methods

Method: cached-results-count (CACHE hash-table-function-cache) &aux CACHED

Source

hash-table.lisp (file)

Method: cached-results-count (CACHE single-cell-function-cache)

Source

single-cell.lisp (file)

Method: cached-results-count (CACHE thunk-cache)

Source

thunk.lisp (file)

Method: cached-results-count (X null)

Method: cached-results-count (RES list)

Method: cached-results-count (RES hash-table)

Generic Function: capacity OBJECT

Generic Function: (setf capacity) NEW-VALUE OBJECT

Package

function-cache

Methods

Method: capacity (CACHE-CAPACITY-MIXIN cache-capacity-mixin)

Method: (setf capacity) NEW-VALUE (CACHE-CAPACITY-MIXIN cache-capacity-mixin)

The maximum number of objects cached, when we hit this we will reduce the number of cached entries by reduce-by-ratio

Source

capacity.lisp (file)

Generic Function: clear-cache CACHE &optional ARGS

Clears a given cache

Package

function-cache

Source

protocol.lisp (file)

Methods

Method: clear-cache (CACHE-NAME symbol) &optional ARGS

Source

cache.lisp (file)

Method: clear-cache (CACHE-NAME null) &optional ARGS

Source

cache.lisp (file)

Method: clear-cache (CACHE ordered-cache-mixin) &optional ARGS after

Source

ordered.lisp (file)

Method: clear-cache (CACHE hash-table-function-cache) &optional ARGS &aux NAME HASH SHARED-RESULTS?

Source

hash-table.lisp (file)

Method: clear-cache (CACHE function-cache) &optional ARGS

Source

function-cache.lisp (file)

Generic Function: clear-cache-partial-arguments CACHE TO-MATCH

This function will go through the cached-results removing
keys that partially match the to-match list.

This is used to clear the cache of shared? caches, but is also useful in other cases, where we need to clear cache for some subset of the arguments (eg: a cached funcall might wish to clear the cache of a specific funcalled function).

Matches arguments for those provided. Anything not provided is considered function-cache:dont-care. Anything specified as function-cache:dont-care is not used to determine if there is a match

Package

function-cache

Source

hash-table.lisp (file)

Methods

Method: clear-cache-partial-arguments (CACHE ordered-cache-mixin) TO-MATCH after

Source

ordered.lisp (file)

Method: clear-cache-partial-arguments (CACHE hash-table-function-cache) TO-MATCH

Generic Function: compute-cache-key CACHE THING

Used to assemble cache keys for function-cache objects

Package

function-cache

Source

function-cache.lisp (file)

Methods

Method: compute-cache-key (CACHE function-cache) THING

Generic Function: defcached-hashkey THING

Turns a list of arguments into a valid cache-key (usually a tree of primatives)

Package

function-cache

Source

protocol.lisp (file)

Methods

Method: defcached-hashkey THING

Generic Function: get-cached-value CACHE CACHE-KEY

returns the result-values-list and at what time it was cached

Package

function-cache

Source

protocol.lisp (file)

Writer

(setf get-cached-value) (generic function)

Methods

Method: get-cached-value (CACHE ordered-cache-mixin) CACHE-KEY around

Source

ordered.lisp (file)

Method: get-cached-value (CACHE hash-table-function-cache) CACHE-KEY

Source

hash-table.lisp (file)

Method: get-cached-value (CACHE single-cell-function-cache) CACHE-KEY

Source

single-cell.lisp (file)

Method: get-cached-value (CACHE thunk-cache) CACHE-KEY

Source

thunk.lisp (file)

Method: get-cached-value (CACHE metered-mixin) CACHE-KEY around

Source

metering.lisp (file)

Generic Function: (setf get-cached-value) NEW CACHE CACHE-KEY

Set the cached value for the cache key

Package

function-cache

Source

protocol.lisp (file)

Reader

get-cached-value (generic function)

Methods

Method: (setf get-cached-value) NEW (CACHE ordered-cache-mixin) CACHE-KEY around

Source

ordered.lisp (file)

Method: (setf get-cached-value) NEW (CACHE hash-table-function-cache) CACHE-KEY

Source

hash-table.lisp (file)

Method: (setf get-cached-value) NEW (CACHE single-cell-function-cache) CACHE-KEY

Source

single-cell.lisp (file)

Method: (setf get-cached-value) NEW (CACHE thunk-cache) CACHE-KEY

Source

thunk.lisp (file)

Method: (setf get-cached-value) NEW (CACHE cache-capacity-mixin) CACHE-KEY before

Source

capacity.lisp (file)

Method: (setf get-cached-value) NEW CACHE CACHE-KEY around

Generic Function: hits OBJECT

Generic Function: (setf hits) NEW-VALUE OBJECT

Package

function-cache

Methods

Method: hits (METERED-MIXIN metered-mixin)

Method: (setf hits) NEW-VALUE (METERED-MIXIN metered-mixin)

how many cache hits

Source

metering.lisp (file)

Generic Function: misses OBJECT

Generic Function: (setf misses) NEW-VALUE OBJECT

Package

function-cache

Methods

Method: misses (METERED-MIXIN metered-mixin)

Method: (setf misses) NEW-VALUE (METERED-MIXIN metered-mixin)

how many cache hits

Source

metering.lisp (file)

Generic Function: partial-argument-match? CACHE CACHED-KEY TO-MATCH &key TEST

Trys to see if the cache-key matches the to-match partial
key passed in.

The basic implementation is to go through the cache-keys and match in order, skipping to-match component that is function-cache:dont-care

Package

function-cache

Source

hash-table.lisp (file)

Methods

Method: partial-argument-match? (CACHE hash-table-function-cache) CACHED-KEY TO-MATCH &key TEST

Generic Function: purge-cache CACHE

A function that will remove expired entries from the cache, allowing them to be garbage collected

Package

function-cache

Source

protocol.lisp (file)

Methods

Method: purge-cache (CACHE-NAME symbol)

Source

cache.lisp (file)

Method: purge-cache (CACHE ordered-cache-mixin) after

Source

ordered.lisp (file)

Method: purge-cache (CACHE hash-table-function-cache) &aux HASH

Source

hash-table.lisp (file)

Method: purge-cache (CACHE single-cell-function-cache)

Source

single-cell.lisp (file)

Method: purge-cache (CACHE thunk-cache)

Source

thunk.lisp (file)

Method: purge-cache (CACHE function-cache) around

Source

function-cache.lisp (file)

Generic Function: reduce-by-ratio OBJECT

Generic Function: (setf reduce-by-ratio) NEW-VALUE OBJECT

Package

function-cache

Methods

Method: reduce-by-ratio (CACHE-CAPACITY-MIXIN cache-capacity-mixin)

Method: (setf reduce-by-ratio) NEW-VALUE (CACHE-CAPACITY-MIXIN cache-capacity-mixin)

Remove the oldest reduce-by-ratio entries (eg: .2 or 20%)

Source

capacity.lisp (file)

Generic Function: reduce-cached-set CACHE N

evict n items from the cache

Package

function-cache

Source

protocol.lisp (file)

Methods

Method: reduce-cached-set (CACHE mru-cache) N

Source

ordered.lisp (file)

Method: reduce-cached-set (CACHE lru-cache) N

Source

ordered.lisp (file)

Method: reduce-cached-set (CACHE hash-table-function-cache) N

Source

hash-table.lisp (file)

Generic Function: reset-counters CACHE

When we clear the full cache, reset the counters

Package

function-cache

Source

metering.lisp (file)

Methods

Method: reset-counters (CACHE symbol)

Method: reset-counters (CACHE metered-mixin)

Generic Function: timeout OBJECT

Generic Function: (setf timeout) NEW-VALUE OBJECT

Package

function-cache

Methods

Method: timeout (FUNCTION-CACHE function-cache)

automatically generated reader method

Source

function-cache.lisp (file)

Method: (setf timeout) NEW-VALUE (FUNCTION-CACHE function-cache)

automatically generated writer method

Source

function-cache.lisp (file)

6.1.5 Classes

Class: cache-capacity-mixin ()

Package

function-cache

Source

capacity.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

• hash-table-function-cache-with-capacity (class)
• ordered-cache-mixin (class)

Direct methods

• (setf get-cached-value) (method)
• at-cache-capacity? (method)
• reduce-by-ratio (method)
• reduce-by-ratio (method)
• capacity (method)
• capacity (method)

Direct slots

Slot: capacity

The maximum number of objects cached, when we hit this we will reduce the number of cached entries by reduce-by-ratio

Initargs

:capacity

Readers

capacity (generic function)

Writers

(setf capacity) (generic function)

Slot: reduce-by-ratio

Remove the oldest reduce-by-ratio entries (eg: .2 or 20%)

Initargs

:reduce-by-ratio

Initform

0.2

Readers

reduce-by-ratio (generic function)

Writers

(setf reduce-by-ratio) (generic function)

Class: hash-table-function-cache ()

a function cache that uses a hash-table to store results

Package

function-cache

Source

hash-table.lisp (file)

Direct superclasses

function-cache (class)

Direct subclasses

• hash-table-function-cache-with-capacity (class)
• metered-hash-table-cache (class)
• lru-cache (class)
• mru-cache (class)

Direct methods

• reduce-cached-set (method)
• purge-cache (method)
• clear-cache (method)
• clear-cache-partial-arguments (method)
• partial-argument-match? (method)
• key-cached? (method)
• get-cached-value (method)
• get-cached-value (method)
• cached-results-count (method)
• make-cache-backing (method)
• hash-init-args (method)
• hash-init-args (method)

Direct slots

Slot: hash-init-args

Initargs

:hash-init-args

Initform

function-cache::*default-hash-init-args*

Readers

hash-init-args (generic function)

Writers

(setf hash-init-args) (generic function)

Class: hash-table-function-cache-with-capacity ()

a function cache that uses a hash-table to store results with a max capacity

Package

function-cache

Source

hash-table.lisp (file)

Direct superclasses

• hash-table-function-cache (class)
• cache-capacity-mixin (class)

Class: lru-cache ()

LRU cache backed by a hash-table.
Maintains capacity by removing least recently used cached values.

Package

function-cache

Source

ordered.lisp (file)

Direct superclasses

• hash-table-function-cache (class)
• ordered-cache-mixin (class)

Direct methods

reduce-cached-set (method)

Class: metered-mixin ()

adds some recording for caches hits/misses

Package

function-cache

Source

metering.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

metered-hash-table-cache (class)

Direct methods

• reset-counters (method)
• get-cached-value (method)
• misses (method)
• misses (method)
• hits (method)
• hits (method)

Direct slots

Slot: hits

how many cache hits

Initform

0

Readers

hits (generic function)

Writers

(setf hits) (generic function)

Slot: misses

how many cache hits

Initform

0

Readers

misses (generic function)

Writers

(setf misses) (generic function)

Class: mru-cache ()

MRU cache backed by a hash-table.
Maintains capacity by removing the most recently used cached value.s

Package

function-cache

Source

ordered.lisp (file)

Direct superclasses

• hash-table-function-cache (class)
• ordered-cache-mixin (class)

Direct methods

reduce-cached-set (method)

Class: single-cell-function-cache ()

a cache that stores only the most recent result of running the body

Package

function-cache

Source

single-cell.lisp (file)

Direct superclasses

function-cache (class)

Direct methods

• key-cached? (method)
• purge-cache (method)
• get-cached-value (method)
• get-cached-value (method)
• cached-results-count (method)
• make-cache-backing (method)
• test (method)
• test (method)

Direct slots

Slot: test

Initargs

:test

Initform

(function equal)

Readers

test (generic function)

Writers

(setf test) (generic function)

Class: thunk-cache ()

a cache optimized for functions of no arguments (uses a cons for caching)

Package

function-cache

Source

thunk.lisp (file)

Direct superclasses

function-cache (class)

Direct methods

• key-cached? (method)
• purge-cache (method)
• cached-results-count (method)
• get-cached-value (method)
• get-cached-value (method)

6.2 Internal definitions

6.2.1 Special variables

Special Variable: *cache*

Package

function-cache

Source

protocol.lisp (file)

Special Variable: *cached-at*

Package

function-cache

Source

protocol.lisp (file)

Special Variable: *default-hash-init-args*

Package

function-cache

Source

hash-table.lisp (file)

6.2.2 Functions

Function: %add-cached-node CACHE NODE

Add a node to the last position of the cache.

Package

function-cache

Source

ordered.lisp (file)

Function: %call-list-for-lambda-list LAMBDA-LIST

Turns a lambda list into a list that can be applied to functions of that lambda list

Package

function-cache

Source

cache.lisp (file)

Function: %ensure-unquoted THING

Package

function-cache

Source

cache.lisp (file)

Function: %insert-into-cache CACHE ARGS &key CACHE-KEY

Simple helper to run the body, store the results in the cache and then return them

Package

function-cache

Source

function-cache.lisp (file)

Function: %move-cached-node CACHE NODE

Move a node to the end of the cache, should be called when a cached result has been used.

Package

function-cache

Source

ordered.lisp (file)

Function: %remove-cached-node CACHE NODE

Remove a node from the cache.

Package

function-cache

Source

ordered.lisp (file)

Function: cnode CACHE-KEY RESULT &optional OLDER NEWER

Package

function-cache

Source

ordered.lisp (file)

Function: cnode-cache-key INSTANCE

Function: (setf cnode-cache-key) VALUE INSTANCE

Package

function-cache

Source

ordered.lisp (file)

Function: cnode-newer INSTANCE

Function: (setf cnode-newer) VALUE INSTANCE

Package

function-cache

Source

ordered.lisp (file)

Function: cnode-older INSTANCE

Function: (setf cnode-older) VALUE INSTANCE

Package

function-cache

Source

ordered.lisp (file)

Function: cnode-p OBJECT

Package

function-cache

Source

ordered.lisp (file)

Function: cnode-result INSTANCE

Function: (setf cnode-result) VALUE INSTANCE

Package

function-cache

Source

ordered.lisp (file)

Function: copy-cnode INSTANCE

Package

function-cache

Source

ordered.lisp (file)

Function: do-caches FN &key PACKAGE

Iterate through caches calling fn on each matching cache

Package

function-cache

Source

cache.lisp (file)

Function: get-cached-object-stats CACHE &aux TYPE-COUNTS CYCLES RES

Package

function-cache

Source

metering.lisp (file)

Function: incf-hash KEY HT &optional DELTA DEFAULT

Package

function-cache

Source

metering.lisp (file)

Function: number-to-remove CACHE

Package

function-cache

Source

capacity.lisp (file)

Function: sync-ordered-cache CACHE

Remove any nodes from the dlist that are no longer in the actual cache.

Package

function-cache

Source

ordered.lisp (file)

6.2.3 Generic functions

Generic Function: body-fn OBJECT

Generic Function: (setf body-fn) NEW-VALUE OBJECT

Package

function-cache

Methods

Method: body-fn (FUNCTION-CACHE function-cache)

automatically generated reader method

Source

function-cache.lisp (file)

Method: (setf body-fn) NEW-VALUE (FUNCTION-CACHE function-cache)

automatically generated writer method

Source

function-cache.lisp (file)

Generic Function: cache CONDITION

Generic Function: (setf cache) NEW-VALUE CONDITION

Package

function-cache

Methods

Method: cache (CONDITION cache-value-condition)

Method: (setf cache) NEW-VALUE (CONDITION cache-value-condition)

Source

protocol.lisp (file)

Generic Function: cached-at CONDITION

Generic Function: (setf cached-at) NEW-VALUE CONDITION

Package

function-cache

Methods

Method: cached-at (CONDITION cache-value-condition)

Method: (setf cached-at) NEW-VALUE (CONDITION cache-value-condition)

Source

protocol.lisp (file)

Generic Function: cacher CACHE ARGS

A function that takes a cache object and an arg list
and either runs the computation and fills the caches or retrieves the cached value

Package

function-cache

Source

function-cache.lisp (file)

Methods

Method: cacher (CACHE function-cache) ARGS &aux CACHE-KEY

Generic Function: default-cache-class SYMBOL LAMBDA-LIST

A function that takes symbol lambda-list and perhaps a cache-class

Package

function-cache

Source

cache.lisp (file)

Methods

Method: default-cache-class SYMBOL LAMBDA-LIST

Generic Function: expired? CACHE RESULT-TIMEOUT

Determines if the cache entry is expired

Package

function-cache

Source

protocol.lisp (file)

Methods

Method: expired? CACHE RESULT-TIMEOUT

Generic Function: hash-init-args OBJECT

Generic Function: (setf hash-init-args) NEW-VALUE OBJECT

Package

function-cache

Methods

Method: hash-init-args (HASH-TABLE-FUNCTION-CACHE hash-table-function-cache)

automatically generated reader method

Source

hash-table.lisp (file)

Method: (setf hash-init-args) NEW-VALUE (HASH-TABLE-FUNCTION-CACHE hash-table-function-cache)

automatically generated writer method

Source

hash-table.lisp (file)

Generic Function: key CONDITION

Generic Function: (setf key) NEW-VALUE CONDITION

Package

function-cache

Methods

Method: key (CONDITION cache-value-condition)

Method: (setf key) NEW-VALUE (CONDITION cache-value-condition)

Source

protocol.lisp (file)

Generic Function: key-cached? CACHE CACHE-KEY

Check if the cache contains a cached value for the key.
This should not have any side affects, even if GET-CACHED-VALUE does (for instance in an LRU cache). Return non-nil if the cache contains an entry with the specified key.

Note that this returns non-nil if the key is cached but expired.

Package

function-cache

Source

protocol.lisp (file)

Methods

Method: key-cached? (CACHE hash-table-function-cache) CACHE-KEY

Source

hash-table.lisp (file)

Method: key-cached? (CACHE single-cell-function-cache) CACHE-KEY

Source

single-cell.lisp (file)

Method: key-cached? (CACHE thunk-cache) CACHE-KEY

Source

thunk.lisp (file)

Method: key-cached? CACHE KEY

Generic Function: lambda-list OBJECT

Generic Function: (setf lambda-list) NEW-VALUE OBJECT

Package

function-cache

Methods

Method: lambda-list (FUNCTION-CACHE function-cache)

automatically generated reader method

Source

function-cache.lisp (file)

Method: (setf lambda-list) NEW-VALUE (FUNCTION-CACHE function-cache)

automatically generated writer method

Source

function-cache.lisp (file)

Generic Function: make-cache-backing CACHE

make a new backing storage for the cache

Package

function-cache

Source

protocol.lisp (file)

Methods

Method: make-cache-backing (CACHE hash-table-function-cache)

Source

hash-table.lisp (file)

Method: make-cache-backing (CACHE single-cell-function-cache)

Source

single-cell.lisp (file)

Method: make-cache-backing CACHE

Generic Function: name OBJECT

Generic Function: (setf name) NEW-VALUE OBJECT

Package

function-cache

Methods

Method: name (FUNCTION-CACHE function-cache)

automatically generated reader method

Source

function-cache.lisp (file)

Method: (setf name) NEW-VALUE (FUNCTION-CACHE function-cache)

automatically generated writer method

Source

function-cache.lisp (file)

Generic Function: newest-node OBJECT

Generic Function: (setf newest-node) NEW-VALUE OBJECT

Package

function-cache

Methods

Method: newest-node (ORDERED-CACHE-MIXIN ordered-cache-mixin)

automatically generated reader method

Source

ordered.lisp (file)

Method: (setf newest-node) NEW-VALUE (ORDERED-CACHE-MIXIN ordered-cache-mixin)

automatically generated writer method

Source

ordered.lisp (file)

Generic Function: oldest-node OBJECT

Generic Function: (setf oldest-node) NEW-VALUE OBJECT

Package

function-cache

Methods

Method: oldest-node (ORDERED-CACHE-MIXIN ordered-cache-mixin)

automatically generated reader method

Source

ordered.lisp (file)

Method: (setf oldest-node) NEW-VALUE (ORDERED-CACHE-MIXIN ordered-cache-mixin)

automatically generated writer method

Source

ordered.lisp (file)

Generic Function: removed-at CONDITION

Generic Function: (setf removed-at) NEW-VALUE CONDITION

Package

function-cache

Methods

Method: removed-at (CONDITION removed-a-value)

Method: (setf removed-at) NEW-VALUE (CONDITION removed-a-value)

Source

protocol.lisp (file)

Generic Function: shared-results? OBJECT

Generic Function: (setf shared-results?) NEW-VALUE OBJECT

Package

function-cache

Methods

Method: shared-results? (FUNCTION-CACHE function-cache)

automatically generated reader method

Source

function-cache.lisp (file)

Method: (setf shared-results?) NEW-VALUE (FUNCTION-CACHE function-cache)

automatically generated writer method

Source

function-cache.lisp (file)

Generic Function: test OBJECT

Generic Function: (setf test) NEW-VALUE OBJECT

Package

function-cache

Methods

Method: test (SINGLE-CELL-FUNCTION-CACHE single-cell-function-cache)

automatically generated reader method

Source

single-cell.lisp (file)

Method: (setf test) NEW-VALUE (SINGLE-CELL-FUNCTION-CACHE single-cell-function-cache)

automatically generated writer method

Source

single-cell.lisp (file)

Generic Function: value CONDITION

Generic Function: (setf value) NEW-VALUE CONDITION

Package

function-cache

Methods

Method: value (CONDITION cache-value-condition)

Method: (setf value) NEW-VALUE (CONDITION cache-value-condition)

Source

protocol.lisp (file)

6.2.4 Conditions

Condition: cache-value-condition ()

Package

function-cache

Source

protocol.lisp (file)

Direct superclasses

condition (condition)

Direct subclasses

• cached-a-value (condition)
• removed-a-value (condition)

Direct methods

• cached-at (method)
• cached-at (method)
• value (method)
• value (method)
• key (method)
• key (method)
• cache (method)
• cache (method)

Direct slots

Slot: cache

Initargs

:cache

Initform

(quote nil)

Readers

cache (generic function)

Writers

(setf cache) (generic function)

Slot: key

Initargs

:key

Initform

(quote nil)

Readers

key (generic function)

Writers

(setf key) (generic function)

Slot: value

Initargs

:value

Initform

(quote nil)

Readers

value (generic function)

Writers

(setf value) (generic function)

Slot: cached-at

Initargs

:cached-at

Initform

(quote nil)

Readers

cached-at (generic function)

Writers

(setf cached-at) (generic function)

Condition: cached-a-value ()

Package

function-cache

Source

protocol.lisp (file)

Direct superclasses

cache-value-condition (condition)

Condition: expired-a-value ()

Package

function-cache

Source

protocol.lisp (file)

Direct superclasses

removed-a-value (condition)

Condition: removed-a-value ()

Package

function-cache

Source

protocol.lisp (file)

Direct superclasses

cache-value-condition (condition)

Direct subclasses

expired-a-value (condition)

Direct methods

• removed-at (method)
• removed-at (method)

Direct slots

Slot: removed-at

Initargs

:removed-at

Initform

(quote (get-universal-time))

Readers

removed-at (generic function)

Writers

(setf removed-at) (generic function)

6.2.5 Structures

Structure: cnode ()

Package

function-cache

Source

ordered.lisp (file)

Direct superclasses

structure-object (structure)

Direct slots

Slot: cache-key

Readers

cnode-cache-key (function)

Writers

(setf cnode-cache-key) (function)

Slot: result

Readers

cnode-result (function)

Writers

(setf cnode-result) (function)

Slot: older

Type

function-cache::cache-node

Readers

cnode-older (function)

Writers

(setf cnode-older) (function)

Slot: newer

Type

function-cache::cache-node

Readers

cnode-newer (function)

Writers

(setf cnode-newer) (function)

6.2.6 Classes

Class: function-cache ()

an object that contains the cached results of function calls
the original function to be run, to set cached values
and other cache configuration parameters. This class is mostly intended to be abstract with hash-table-function-cache, and thunk-cache being the current concrete classes

Package

function-cache

Source

function-cache.lisp (file)

Direct superclasses

standard-object (class)

Direct subclasses

• thunk-cache (class)
• single-cell-function-cache (class)
• hash-table-function-cache (class)

Direct methods

• cacher (method)
• compute-cache-key (method)
• purge-cache (method)
• clear-cache (method)
• initialize-instance (method)
• cached-results (method)
• print-object (method)
• shared-results? (method)
• shared-results? (method)
• lambda-list (method)
• lambda-list (method)
• name (method)
• name (method)
• body-fn (method)
• body-fn (method)
• timeout (method)
• timeout (method)
• cached-results (method)
• cached-results (method)

Direct slots

Slot: cached-results

Initargs

:cached-results

Readers

cached-results (generic function)

Writers

(setf cached-results) (generic function)

Slot: timeout

Initargs

:timeout

Readers

timeout (generic function)

Writers

(setf timeout) (generic function)

Slot: body-fn

Initargs

:body-fn

Readers

body-fn (generic function)

Writers

(setf body-fn) (generic function)

Slot: name

Initargs

:name

Readers

name (generic function)

Writers

(setf name) (generic function)

Slot: lambda-list

Initargs

:lambda-list

Readers

lambda-list (generic function)

Writers

(setf lambda-list) (generic function)

Slot: shared-results?

Initargs

:shared-results?

Readers

shared-results? (generic function)

Writers

(setf shared-results?) (generic function)

Class: metered-hash-table-cache ()

cache backed by a hash-table, keeps metrics

Package

function-cache

Source

hash-table.lisp (file)

Direct superclasses

• hash-table-function-cache (class)
• metered-mixin (class)

Class: ordered-cache-mixin ()

Mixin that keeps track of the order of cached results in a doubly linked list. FIRST references the oldest cached result, and LAST references the most recent.

Package

function-cache

Source

ordered.lisp (file)

Direct superclasses

cache-capacity-mixin (class)

Direct subclasses

• lru-cache (class)
• mru-cache (class)

Direct methods

• purge-cache (method)
• clear-cache (method)
• clear-cache-partial-arguments (method)
• get-cached-value (method)
• get-cached-value (method)
• newest-node (method)
• newest-node (method)
• oldest-node (method)
• oldest-node (method)

Direct slots

Slot: oldest

Type

function-cache::cache-node

Readers

oldest-node (generic function)

Writers

(setf oldest-node) (generic function)

Slot: newest

Type

function-cache::cache-node

Readers

newest-node (generic function)

Writers

(setf newest-node) (generic function)

6.2.7 Types

Type: cache-node ()

Package

function-cache

Source

ordered.lisp (file)

Appendix A Indexes

A.1 Concepts

A.2 Functions