Clever caching of a recursively defined function

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?

• A long time ago I wrote a small note about how to do this. Since then, we got Association, which is better for this purpose. MaTeX uses it. Here's the function to store values in the cache. Here's how to retrieve them. MaTeX needs to retrieve multiple values at a time, you'll only need a single. Sorry, no time for a proper answer, but these should give you some ideas. – Szabolcs Sep 20 '18 at 20:02
• Also this: mathematica.stackexchange.com/q/19536/12 – Szabolcs Sep 20 '18 at 20:04
• A final idea is that when a certain value is requested, it should be bumped to the top of the association. Consider asc = <|"a" -> 1, "b" -> 2|>, then AssociateTo[asc, "a" -> 1], which is fast but doesn't reorder keys, and AppendTo[asc, "a" -> 1], which is slower, but places the key at the end. With some small performance hit, you can bump values to the top on every hit. Thus when you prune old values, the values that are removed will be the ones that have not been requested recently. – Szabolcs Sep 20 '18 at 20:10

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 = fib = 1;
fib[n_] := get[n - 1] + get[n - 2]

Let's test it:

fib
(* 573147844013817084101 *)

asc
(* <|90 -> 4660046610375530309, 91 -> 7540113804746346429,
92 -> 12200160415121876738, 93 -> 19740274219868223167,
94 -> 31940434634990099905, 95 -> 51680708854858323072,
96 -> 83621143489848422977, 97 -> 135301852344706746049,
99 -> 354224848179261915075, 98 -> 218922995834555169026|> *)
• Excellent, thanks! One remark - I've already tried it, it works very well except when it comes to cutting cache down it slows down terribly. A way out seems to introduce one more parameter, cut amount, and when the size limit is reached, cut by that amount. I've tried it with limit one billion and cut one million, and it works much quicker this way. – მამუკა ჯიბლაძე Sep 21 '18 at 3:48
• It is now running for a while, and I noticed one problem, but I don't know whether it is solvable. As I said, values most frequently used for n are those for about one third of n. This means that when I erase the less used part of the cache, I am also losing values (those with m larger than one third of current n) which are going to be used more frequently later, when I reach larger n... – მამუკა ჯიბლაძე Sep 21 '18 at 9:55