37
$\begingroup$

I have a function of two variables, e.g.:

f[a_, b_] := f[a, b] = something f[a - 1, b - 1] etc

With the above code I used the concept of memoization to speed up the computation.

However, I have the problem that I run out of memory for large values of a and b.

Since my recursion is not very deep, I would like to clear the memory from time to time; for example, I calculate f[1000, 1000] and then remove all values of f[a, b] for a, b between 1 and something close to 1000.

However, I only found the Clear/ClearAll functions, which (unless I am missing something) clear everything indiscriminately. This is not what I want.

Is there a built-in function that does not clear all values of f[a, b], but just a specific range?

$\endgroup$

3 Answers 3

31
$\begingroup$

This is quite easy to achieve by direct manipulation of downvalues. Here's a simple example:

ClearAll[removeDownValues];
SetAttributes[removeDownValues, HoldAllComplete];
removeDownValues[p : f_[___]] :=
  DownValues[f] = DeleteCases[
    DownValues[f, Sort -> False],
    HoldPattern[Verbatim[HoldPattern][p] :> _]
   ];

Now let's memoize some values:

Do[f[1, i] = i, {i, 1, 10}];
DownValues[f]
(* -> {HoldPattern[f[1, 1]] :> 1, HoldPattern[f[1, 2]] :> 2, 
       HoldPattern[f[1, 3]] :> 3, HoldPattern[f[1, 4]] :> 4, 
       HoldPattern[f[1, 5]] :> 5, HoldPattern[f[1, 6]] :> 6, 
       HoldPattern[f[1, 7]] :> 7, HoldPattern[f[1, 8]] :> 8, 
       HoldPattern[f[1, 9]] :> 9, HoldPattern[f[1, 10]] :> 10} *)

If we no longer need some of these, we can remove them as follows:

removeDownValues[f[_, x_ /; 4 <= x <= 7]]
(* -> {HoldPattern[f[1, 2]] :> 2, HoldPattern[f[1, 1]] :> 1, 
       HoldPattern[f[1, 3]] :> 3, HoldPattern[f[1, 8]] :> 8, 
       HoldPattern[f[1, 9]] :> 9, HoldPattern[f[1, 10]] :> 10} *)

Performance will probably be fairly good if you need to remove a large number of memoized values at the same time, but you should bear in mind that resetting downvalues in this way requires rebuilding the hash table from scratch. As such, if you want to remove a few specific downvalues but do so many times, using Unset is probably a better choice. A timing comparison demonstrates that if you don't need to pattern match downvalues and can simply iterate over them instead, Unset is indeed preferable:

Do[f[1, i] = i, {i, 1, 1*^6}]; (* evaulated before each timing run below *)

removeDownValues[f[1, x_ /; 1000 <= x <= 999000]]; (* 3.67 seconds *)
removeDownValues[f[1, _]]; (* 3.39 seconds *)
Do[f[1, x] =., {x, 1000, 999000}]; (* 2.03 seconds *)
$\endgroup$
3
  • 4
    $\begingroup$ One comment (+1,of course) - with the Sort->False option, DownValues are not listed in the order they were entered (which is what I used to think for some time in the past), but in whatever order they are internally stored - which is rather arbitrary in general. This is probably known to you, but some of those reading the answer may be unaware of this. $\endgroup$ Feb 13, 2013 at 19:17
  • $\begingroup$ @LeonidShifrin this is a very good point. Can you think of any situations where using the internal ordering to redefine the downvalues could result in different rules being applied afterwards? Am I right in thinking the difference between the internal and definitional order only exists for hashed values? $\endgroup$ Feb 13, 2013 at 19:41
  • $\begingroup$ Yes, I think this is correct - the option only governs the hashed values, not pattern-based rules. And as long as we don't count on the ordering of DownValues with the Sort->False option setting being some specific ordering (like e.g. the order in which they were entered), I think the results will not depend on the particular ordering. Of course, the main reason to use Sort->False option is for speed, since we then skip the sorting step when extracting the DownValues. $\endgroup$ Feb 13, 2013 at 19:49
19
$\begingroup$

Preamble

I will present a sort of a packaged and automated solution, which uses deques and metaprogramming to automate caching. This should work for most normal pattern-based functions.

Deques

I will use Daniel Lichtblau's implementation for a deque, taken from his great account on Data Structures and Efficient Algorithms in Mathematica. Here it is:

newQueue[sym_Symbol] := {Unique[sym], 0, Null, 0, 0}
Clear[queueLength, emptyQueue, enQueue, deQueue];
qptr = 1; qlen = 2; qelem = 3; qfront = 4; qback = 5;
queueLength[Q_] := Q[[qlen]]
emptyQueue[Q_] := Q[[qlen]] == 0
SetAttributes[enQueue, HoldFirst]
enQueue[Q_, elem_] := 
  (Q[[qlen]]++; Q[[qfront]]++;Q[[qptr]][Q[[qfront]]] = elem;)
SetAttributes[deQueue, HoldFirst]
deQueue[Q_] := (
  Q[[qlen]]--; Q[[qback]]++;
  Q[[qelem]] = Q[[qptr]][Q[[qback]]];Q[[qptr]][Q[[qback]]] =.; 
  Q[[qelem]]
)

I refer to his treatment for details on how this works.

Automating caching via metaprogramming

The idea will be to inject certain caching code into a definition of a function. The deque will be used to store the arguments of a last given number of function calls, and remove older cache values when a function is called again, if the cache is full. Here is an implementation:

ClearAll[makeCached];
SetAttributes[ makeCached, HoldAll];
makeCached::incrlim =
  "The cache size is too small. Increase the cache size. Further \
    computation will use an uncached function";

makeCached[SetDelayed[f_[args___], rhs_], limit_Integer] :=
   Module[{qq, faux, queue, cache, myHold, dv},
     dv = DownValues[f];
     SetAttributes[myHold, HoldAll];
     queue = newQueue[qq];
     faux[a : PatternSequence[args]] :=
       With[{result = cache[a]},
          result /; ! MatchQ[result, _cache]
       ];
     faux[a : PatternSequence[args]] /; queueLength[queue] < limit :=
       (
          enQueue[queue, {a}];
          cache[a] = rhs
       );
     faux[a : PatternSequence[args]] :=
       With[{argums = Sequence @@ deQueue[queue]},
          If[Head[cache[argums]] === cache,
            Message[makeCached::incrlim];
            Throw[myHold[f[a]], makeCached],
            (* else *)
            cache[argums] =.;
            faux[a]]
       ];

     f[argums___] :=
       Catch[faux[argums], makeCached] /.
          myHold[code_] :> 
              Block[{f},
                 DownValues[f] = dv;
                 f[args] := rhs;
                 code
              ]
];

What is happening here is that we introduce cache as a storage for cached results, queue and qq to keep the queue of function arguments, and we define f so that it basically uses faux to do the computation. If the cache becomes full in the process of a computation (which may happen for deeply recursive functions), we bail out of the computation via Throw and then use the un-cached definition for f to compute that piece of code (technically, I use Block-trick to accomplish that across the execution stack).

Example

Here will be our function:

ClearAll[ff];
ff[_?Negative, _?Negative] = 0;
makeCached[ff[x_, y_] := 1 + ff[x - 1, y - 1], 1000];

and we also define it's non-cached counter-part:

ClearAll[fff];
fff[_?Negative, _?Negative] = 0;
fff[x_, y_] := 1 + fff[x - 1, y - 1];

Now, the benchmarks:

MapThread[ff,{#,#}&@Range[10000]]//Short//Timing

(* {0.796875,{2,3,4,5,6,<<9990>>,9997,9998,9999,10000,10001}} *)

while for non-cached version:

Block[{$RecursionLimit=Infinity},MapThread[fff,{#,#}&@Range[10000]]]//Short//Timing

(* {107.437500,{2,3,4,5,6,<<9990>>,9997,9998,9999,10000,10001}}  *)

Remarks

The above code should be able to deal with most pattern-based functions. It may have some problems with functions which hold their arguments, or have many definitions that have to be cached. The non-cached definitions (like base definitions for recursion, etc), must be given before makeCached is called.

Another problem which I did not yet deal with here is that the internal variables like faux, cache etc won't be garbage-collected even after we Remove ff. This can be dealt with by introducing an explicit function to release that memory.

$\endgroup$
15
$\begingroup$

For individual cases I believe the most straight forward solution is simply using Unset: For instance:

f[x_] := f[x] = x
f[1];
f[2];
f[5];

DownValues[f]
f[5] =.
f[3];
DownValues[f]

 (* {HoldPattern[f[1]] :> 1, HoldPattern[f[2]] :> 2, HoldPattern[f[5]] :> 5,     
        HoldPattern[f[x_]] :> (f[x] = x)}  *)
 (* {HoldPattern[f[1]] :> 1, HoldPattern[f[2]] :> 2, HoldPattern[f[3]] :> 3, 
        HoldPattern[f[x_]] :> (f[x] = x)} *)

If you want to clear using patterns on the set values, then the other answers dealing with manipulating downvalues will prove more useful. Though you can also clear multiple definitions using code similar to: Table[f[n] =., {n, 1, 2}].

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.