Re: Memory leak in function using dynamic programming
- To: mathgroup at smc.vnet.net
- Subject: [mg18431] Re: [mg18341] Memory leak in function using dynamic programming
- From: David Withoff <withoff at wolfram.com>
- Date: Wed, 7 Jul 1999 00:11:20 -0400
- Sender: owner-wri-mathgroup at wolfram.com
> In[1]:=
> memTest1[] :=
> Module[
> {p, aj},
> p[j_] := p[j] = Array[Random[]&, 1000];
> aj[j_] := (p[j].p[j]);
> Plus@@Table[aj[j], {j, 1, 20}]
> ]
>
> Calling this function consumes 166kBytes of memory each time the function
> is called.
>
> In[2]:=
> mem1 = MemoryInUse[];
>
> In[3]:=
> SeedRandom[11]; memTest1[]
>
> Out[3]=
> 6670.45
>
> In[4]:=
> MemoryInUse[] - mem1
>
> Out[4]=
> 166596
>
> It seems that Mathematica cannot retrieve the memory used in the dynamic
> assignment when the function which uses dynamic programming is mentioned in
> the definition of another function (the function aj[j_] in the above
> example).
>
> If the value of this function is cleared before the function exits, the
> memory occupied by the local variables is retrieved as expected.
>
> In[5]:=
> memTest2[] :=
> Module[
> {p, a, aj},
> p[j_] := p[j] = Array[Random[]&, 1000];
> aj[j_] := (p[j].p[j]);
> a = Table[aj[j], {j, 1, 20}];
> Clear[aj];
> Plus@@a
> ]
Yes, the recommended way to retrieve the memory in this example is to
clear the local rules, as your definition of memTest2.
Module doesn't clear rules for local symbols automatically. It just sets
the Temporary attribute so that local symbols (and their rules) will be
removed if they aren't being used elsewhere. If local symbols are used
elsewhere, such as when Module is used to construct other rules, then it
is important that rules for the local symbols not be cleared, which is
why Module doesn't clear them automatically. (One could argue that people
ought not to use Module in that way, but that is a separate issue.) In any
case, if you don't want the rules for the local symbols, and they aren't
removed automatically, the recommended solution is to clear them yourself.
This effect is not related to dynamic programming (caching of rules).
The essential characteristic of this example that makes memory retrieval
difficult is the use of nested rules: one local symbol (p) with a rule
is used in a rule for another local symbol (aj). The only effect of
caching is to make the unretrieved memory bigger. The memory still
wouldn't be retrieved, even without caching.
The explanation for this effect is actually quite simple. Mathematica
will only retrieve memory if that memory is not being used. Since p is
used in the rule for aj, p can only be removed when aj is cleared.
The aforementioned reason that Module doesn't clear rules for local
symbols automatically only applies when those rules are used outside of
the Module. In this example, since the only use of the symbol to be
cleared is in a rule for another local symbol in the same Module, one
could argue that both symbols should be cleared and removed. That is a
viable argument. Perhaps a facility for doing that will be added in some
future version of Mathematica, if someone can figure out a way to track
down all of those nested rule references efficiently. In the meantime,
the recommended solution is to clear the rules yourself.
Some rules for local symbols are cleared automatically. For example,
if you simply reverse the order of the local variables in memTest1
(that is, use {aj, p} as the local variable list rather than {p, aj}),
then this memory will also be retrieved. The reason for this curious
behavior is that Module goes through the variable list in order and
removes symbols that aren't being used. It can't remove p, because p
is being used in the rule for aj. It can, however, remove aj, so if
aj is removed first, then p will also be removed.
That observation is a curiosity rather than a recommendation, however.
The recommendation is to clear the local rules, as you did, or to redesign
the program so that rules for local symbols aren't needed.
Dave Withoff
Wolfram Research