# Garbage collection for memoized functions on subkernels

I have a top-level function which operates on some data:

findBestIntegers[data_]:=ParallelMap[optimize,data]


which makes parallelized calls to an optimization routine which tries to find the best integers associated with the data point. The optimization function is shown here in highly simplified form:

optimize[dataPoint_]:=Module[{bestGuess,newGuess,bestCost,newCost},
bestGuess=RandomInteger[{1,20},3];
bestCost=cost[dataPoint,bestGuess];
Do[
newGuess=RandomInteger[{1,20},3];
newCost=cost[dataPoint,newGuess];
If[newCost<bestCost,bestCost=newCost;bestGuess=newGuess],
{i,1,bigNumber}
];
Return[bestGuess]
]


which itself makes many calls to a memoized cost function (the real optimization method I'm using makes a fair number of duplicate calls to the cost function, and achieves a ~2x performance boost from memoization):

cost[dataPoint_,{n1_,n2_,n3_}]:=cost[dataPoint,{n1,n2,n3}]=RHS


After running this for a long time on a large data set, I noticed the subkernels' memory footprints expanding to hundreds of megabytes, due to the memoized cost functions being cached locally, and I worry about slowdowns from the garbage piling up. However, I also know that data will never contain duplicate points, due to it being essentially random floating point numbers.

That means if I write the top-level function as a loop which optimizes for a batch of datapoints in parallel, there should be no downside to clearing the memoized functions in all subkernels to free up memory before moving on to the next batch of datapoints.

I have been unable to get this to work (referencing this question: Clearing distributed definitions from remote kernels). After a ParallelEvaluate[Clear[cost]], I'm unable to refresh the function definition on the subkernels, and errors result.

Furthermore, I'm not certain there is any speed to be gained by doing this. I suppose it depends on the data structure used for memoization within each subkernel. Hash tables, for example, have basically constant lookup time.

Does anyone know if there is performance to be gained, and if so, how to implement this sort of parallel-memoized garbage collection?

-

I can't say for sure but I wouldn't expect much speedup from deleting the existing memoized values as long as everything fits into memory. I don't know the internals so I can't say how exactly the lookup is implemented but could well imagine that hash tables are used for constant arguments, at least largish amounts of memoized values haven't bothered me in the past. Anyway, here is how you can delete just the memoized values (of course that does a somewhat inefficient pattern matching itself...):

ParallelEvaluate[DownValues[cost] = DeleteCases[
DownValues[cost],
Verbatim[RuleDelayed][HoldPattern[_[cost[{__Integer}, {__Integer}]]], _]
]


for other definitions of cost you might need to adopt the pattern. You could also try something like:

Select[DownValues[cost], Not[FreeQ[#, Pattern]] &]


instead of the DeleteCases. If you have the impression that deleting the memoized values could help but the deletion with the above is too slow I'm sure there is more efficient code which would achieve the same but probably be more effort to get working...

-
Thanks, I will experiment with this method. – phosgene Apr 27 '14 at 16:57