Memeozi

Introduction

A library for memoizing functions

git clone https://github.com/garlic0x1/memeozi.git ~/quicklisp/local-projects/memeozi

The name is just “memoize” with vowels shifted :)

Usage

Use defmemo like defun, with a plist of options before the name. Results of the function will be stored and checked before doing work when called again:

(ql:quickload :memeozi)
(use-package :memeozi)

(defmemo () times (a b)
  (* a b))

(is (= 8 (times 2 4)))

Options can be provided to modify the behavior of the memoizer.

Memoize up to 500 values, and do not return results older than 5 seconds.

(defmemo (:size-limit 500 :age-limit 5) do-stuff (in)
    (stuff in))

Specify the :test function of the underlying hash-table to be #’eql, the default is #’equal. Only pass functions that are allowed in (make-hash-table :test #’arg).

(defmemo (:test #'eql) do-more-stuff (a b)
  (more-stuff a b))

When limit is reached, delete entries accessed less than average.

(defmemo (:strategy :mean-freq :size-limit 10) square (x)
  (* x x))

Don’t use locks to access the table (this saves time in single-threaded applications).

(defmemo (:lock? nil) square (x)
  (* x x))

If :lock? is not nill, automatic access and manipulation of the memo table is protected by a lock, so you don’t have to worry about using a memoized function from multiple threads. If you manually touch the table, use the lock to be safe.

For a simpler solution with less overhead, use defmemo/simple, which takes no option list. It is still thread-safe, but it only stores args and result, no timestamps or frequency counts.

(defmemo/simple add (a b)
  (+ a b))

This can also be a nice template for very specific memoizers, like using an array as a table.

Strategies

The options :size-limit and :age-limit allow you to apply limits to the memo table.

Use the :strategy option to use different strategies for purging the table when when :size-limit is reached.

Strategy options:

• :mean-freq (default)

  Deletes entries with lower than average lookup frequencies.

• :mean-age

  Deletes entries with older than average time of calculation.

• :thanos

  Deletes half of entries.

Limitations

You cannot use &rest &optional or &key arguments in a memoized function. (TODO)

:age-limit must be an integer, if you try to use a float, the timestamp will lose precision and things will not work as expected.