Clever caching of a recursively defined function

Question

I've got a function of the form f[n,s] where n is a natural number and s is a finite sequence of natural numbers; my final interest is in computing f[n,{}] but the only way I know to compute it is through calling several f[m,s] for smaller m and various sequences s.

I am doing f[n,s]:= f[n,s]= ..., this kind of thing. It works quickly but runs out of memory quite fast. Analyzing self-calls of the function I see this behavior: most calls that f[n,{}] requires are for f[m,s] with m roughly one third of n, but some (relatively few) of the f[m,s] with small m not depending on n are called very frequently too.

So I would like to implement some kind of smart cache which frees up memory by erasing those f[m,s] values which experience steady drop in the number of calls as n increases and leaves those f[m,s] with number of calls growing or staying roughly the same.

What would be an efficient way to do this in Mathematica?

Answer 1

A long time ago, I wrote a note about how to do this with DownValues. Since then, we got Association, which is a much better data structure for caching. MaTeX uses it for its cache (see the store function in MaTeX.m).

Here's a very small example of how we can do this. I tied this cache to a single function, and used a recursive Fibonacci for illustration. A nice implementation could auto-memoize any function. Perhaps someone else will show this in another answer.

You asked to remove only those values from the cache which aren't used often. Instead, I will remove those which were not used recently. To achieve this, I use AppendTo to add to the association, and do this even if the value was already present. The effect is that the value will be moved to the end of the association. Then we remove elements from the beginning only. Note that AssociateTo is a faster way to update associations, but it does not change the order of keys.

asc = <|"a" -> 1, "b" -> 2|>
(* <|"a" -> 1, "b" -> 2|> *)

AssociateTo[asc, "a" -> 1]; // RepeatedTiming
(* {7.3*10^-7, Null} *)

AppendTo[asc, "a" -> 1]; // RepeatedTiming
(* {1.235*10^-6, Null} *)

Here's the implementation of a recursive Fibonacci with caching, and a limit on the cache size.

Clear[asc, get, store, fib, limit];

(* cache storage *)
asc = <||>;

(* retrieve value *)
get[n_] :=
 store[n]@Lookup[asc, Key[n], fib[n]]

limit = 10; (* max number of entries in cache *)

(* store value; we always do this, even if the value was known, to update the ordering *)
store[n_][val_] := (
  AppendTo[asc, n -> val]; 
  If[Length[asc] > limit, asc = Take[asc, -limit]]; 
  val)

fib[0] = fib[1] = 1;
fib[n_] := get[n - 1] + get[n - 2]

Let's test it:

fib[100]
(* 573147844013817084101 *)

asc
(* <|90 -> 4660046610375530309, 91 -> 7540113804746346429, 
 92 -> 12200160415121876738, 93 -> 19740274219868223167, 
 94 -> 31940434634990099905, 95 -> 51680708854858323072, 
 96 -> 83621143489848422977, 97 -> 135301852344706746049, 
 99 -> 354224848179261915075, 98 -> 218922995834555169026|> *)