(* ::Package:: *) (* ::Package:: *) (* ......................................................................*) (* :Title: Cache *) (* :Author: Leonid B. Shifrin *) (* :Summary: Functions to create and manage internal caches which store a fixed number of the most recent results for a given function. Can speed-up certain computations where lots of repetetive function calls are performed *) (* :Context: Cache` *) (* :Package version: 1.0 *) (* :Copyright: Copyright 2008, Leonid B.Shifrin. Permission is granted to distribute verbatim copies of this package together with any of your packages that use it, provided the following acknowledgement is printed in a standard place: "UnsortedOperations.m is distributed with permission by Leonid B. Shifrin." *) (* :History: Version 1.0 April 2008 *) (* :Keywords: cache, speedup *) (* :Mathematica version: 5.0 *) (* :Discussion: The goal of the package is to provide a functionality to make a "cached" version of a given function, so that, while when called, it produces the same results as the original one, it keeps certain number of results of the most recent function calls, and does not recompute the r.h.s. on the corresponding arguments, but rather fetches the results from the cache. The crucial feature for the present implementation is the existence of the option for the DownValues built-in. Setting it to False allows to monitor the definitions in the order they were entered. Other features are the use of local variables produced by Module to implement auxilliary local functions which store the cache and also clear or remove it, but which are hidden from the user. ********************* Unresolved issues ********************* A general unresolved issue here is the possible dependencies in the function on symbols which may change their value in the future. Our is defined through DownValues, there could be some variables or symbols on the r.h.s, on which depends. The general solution would be to analyze an entire dependency tree and create a full local copy of all the rules involved in a definition of . There can be only two distinct behaviors which are well-defined: either to make the cached version "follow" entirely, or create a cached version which is completely independent of all the parameters, variables and functions involved in a definition of (closure). The latter may actually be not possible in the symbolic environment, since some symbols may remain as symbols and these will then determine . But it should be possible to determine whether or not it is possible in a given situation and issue a message if not. Also, as an intermediate possibility, one could explicitly provide the names of symbols dependence on which is allowed. *) (* ....................................................................*) BeginPackage["Cache`"]; If[Not@ValueQ[MakeCached::usage], MakeCached::usage = "MakeCache[fn,cachedfn,cachsize] creates a cached version of a function of single argument. It takes the name of an existing function (which should be either a symbol or a pure function), the name for the cached version of - , which should be a Symbol, the size of the cache (integer), and the options. It then creates a definition for such that it will automatically cache most recent results and also use them in the computation rather than recomputing the r.h.s. of the definition of . One may create many cached functions for a single \"normal\" one - they will be completely independent from each other. They will however depend of the original function and \"follow\" all possible changes in the definition of , unless is defined through DownValues (not a pure function), and the option is set to True. This function may give an advantage if all of the following conditions are fulfilled: 1. Cached function is rather computationally intensive (say,takes a couple of milliseconds or more on a single input). 2. It is frequently called on same arguments. 3. The memory is constrained - for instance, in a long unattended computation. If it is possible to use the standard memoization construct f[x_]:=f[x] = r.h.s. (in terms of memory), the latter is better - it is 10 - 15 times faster than the present implementation (neglecting the cost of the computation of )." ]; If[Not@ValueQ[DestroyCached::usage], DestroyCached::usage = "DestroyCached[cachedfn] is a destructor to remove all definitions (cache content) associated with the cached function" ]; If[Not@ValueQ[CreateCacheFunction::usage], CreateCacheFunction::usage = "CreateCacheFunction[cachedf, newf] can be used to \"look inside\" the cache content, which corresponds to cached function , by copying cached results into another function () definitions. The should be a Symbol." ]; If[Not@ValueQ[BufferSize::usage], BufferSize::usage = "BufferSize->n is an option that sets the size of the temporary buffer used by MakeCached. The default is BufferSize->1. This option allows the cache to grow to a maximum of +n before the buffer is emptied and the cache size becomes < again. This may speed up caching in some cases, since it is faster to flush the entire buffer than to maintain a constant cache size throughout" ]; If[Not@ValueQ[IndependentCache::usage], IndependentCache::usage = "IndependentCache is an option for MakeCached. Setting IndependentCache->True is possible only if the input function is pattern-defined (non-pure). Then this setting makes the resulting cached funtion independent of the possible future changes in definitions of . Setting IndependentCache->False makes the resulting cached function dependent on the (possibly changing) definition of . The dafault is IndependentCache->False" ]; If[Not@ValueQ[EmptyCache::usage],EmptyCache::usage = "EmptyCache[cachedfn] clears the current cached values but keeps the function definition, so that the function can be used \"afresh\". This is needed to ensure that the cached results will not get in the way in a new computation" ]; (*************** Error messages *****************) MakeCached::"badopt" = "The option `1` can not be used with an input function being a pure function"; CreateCacheFunction::"badarg" = "The new function name has to be a Symbol"; CreateCacheFunction::"twarg" = "The function CreateCacheFunction was called with `1` argument(s). Exactly 2 arguments are expected"; Cache::"nofun" = "No cached function with the name `1` exists"; MakeCached::"badfun" = "The first argument of MakeCached must have a head Function or Symbol"; MakeCached::"badcfn" = "The second argument of MakeCached must have a head Symbol"; MakeCached::"badcsz" = "The third argument of MakeCached must be a positive integer"; MakeCached::"badarg" = "Something is wrong with the types and/or number of arguments. MakeCached expects three arguments plus possibly an option"; (* ============ THE CODE STARTS HERE ==============*) Begin["`Private`"]; Options[MakeCached]={BufferSize-> 1,IndependentCache->False}; MakeCached[fn:_Symbol|_Function,cachedfn_Symbol,cachsize_Integer?Positive, opts___?OptionQ]:= Module[{counter = 1,temp,deletelist,auxilliaryF,localfn, buffsize = BufferSize/.Flatten[{opts}]/.Options[MakeCached], independentQ = IndependentCache/.Flatten[{opts}] /.Options[MakeCached]}, (* If the cache with this name of the cached function already exists - remove it *) If[ValueQ[GetAuxilliaryFunction[cachedfn]],RenewCached[cachedfn]]; (* copy function's definition into a local function, to make it independent of *) If[TrueQ[independentQ], If[Head[fn]=!=Symbol, Message[MakeCached::badopt,IndependentCache], (* else *) DownValues[Evaluate[localfn]] =DownValues[fn]/.fn->localfn ], (* else *) localfn = fn ]; cachedfn[x_]:= CompoundExpression[ If[ValueQ[auxilliaryF[x]], (* Use cached value*) temp=auxilliaryF[x]; (* need this to move definition to the end *) auxilliaryF[x]=.; auxilliaryF[x]=temp, (* else *) If[++counter>cachsize+buffsize, (* The Sort->False option is essential *) deletelist = Extract[DownValues[auxilliaryF,Sort->False], Table[{i,1,1},{i,buffsize}],Hold]; Apply[Unset,deletelist,1,Heads->False]; counter-=buffsize ]; auxilliaryF[x]=localfn[x] ] ]; (* Have to define these functions within Module, so that they will have access to $(hidden) variable auxilliaryF*) Unprotect[EmptyCache,DestroyCached]; With[{auxF =auxilliaryF}, EmptyCache[cachedfn]:=(Clear[auxF];counter = 1); RenewCached[cachedfn]:=Remove[auxF]; GetAuxilliaryFunction[cachedfn]:=auxF; DestroyCached[cachedfn]:=Remove[cachedfn,auxF]; ]; Protect[EmptyCache,DestroyCached]; ]; (* == Error messages == *) MakeCached[_,_Symbol,_Integer?Positive,___?OptionQ]:= "never happens"/;Message[MakeCached::"badfun"]; MakeCached[_Symbol|_Function,_,_Integer?Positive,___?OptionQ]:= "never happens"/;Message[MakeCached::"badcfn"]; MakeCached[_Symbol|_Function,_Symbol,_,___?OptionQ]:= "never happens"/;Message[MakeCached::"badcsz"]; MakeCached[___]:= "never happens"/;Message[MakeCached::"badarg"]; EmptyCache[x_]:="never happens"/;Message[Cached::"nofun",x]; EmptyCache[x__]:="never happens"/;Message[General::"argx", "EmptyCache",Length[{x}]]; DestroyCached[x_]:="never happens"/;Message[Cached::"nofun",x]; DestroyCached[x__]:="never happens"/;Message[General::"argx", "DestroyCached",Length[{x}]]; CreateCacheFunction[cachedf_,fn_Symbol] := With[{auxF = GetAuxilliaryFunction[cachedf],fn1 = fn}, If[Head[auxF]===GetAuxilliaryFunction, Return[Message[Cache::nofun,cachedf]] ]; DownValues[fn1]=DownValues[auxF,Sort->False]/.auxF->fn1; ]; CreateCacheFunction[cachedf_,fn_] := "never happens"/;Message[CreateCacheFunction::"badarg"]; CreateCacheFunction[x__]:="never happens"/; Message[CreateCacheFunction::"twarg",Length[{x}]]; End[]; (* Cache`Private` *) Protect[MakeCached,CreateCacheFunction,EmptyCache, DestroyCached,IndependentCache,BufferSize, Cache]; EndPackage[];