[Haskell-cafe] function result caching

[Robert Dockins]

On Saturday 14 October 2006 13:13, Ketil Malde wrote:
> Robert Dockins <robdockins at fastmail.fm> writes:
> >>> slowFunctionCacheList= [slowFunction (i) | i <-[0..5000000]]
> >>> and use "slowFunctionCacheList !! i" instead of "slowFunction (i)"
> >>
> >> Not much different in principle, but better in practice - you could
> >> use an array rather than a list.  O(1) lookups should make things (a
> >> lot) faster.
> >
> > Well, this is true only if the range of the domain function is small and
> > fairly dense.
>
> I don't think so.
>
> > With 5000000 elements, you're looking at allocating about 20Mb of
> > memory
>
> On the other hand, the lists allocates the 20Mb of pointers, *and*
> another 20Mb of cons cells for the lists.

True, but only if you access deeply into the tail of the list.  If one access 
only the first several hundred elements, say, then you'll only allocate the 
space needed for those.

Of course, if you only want to access a small portion at the begining, then 
why create such a big list in the first place?  Moral: lists will lose this 
contest in almost all cases.

> > to hold pointers to closures_ and then allocating and filling out 5000000
> > closures, all before you get down to doing any real work!
>
> If I interpret you correctly, you want to make the array's contents
> strict?  Not a good idea when the domain is sparse, but on the other
> hand it would let you unbox the contents, which means you'd only need
> to store the actual values. For boolean values, I think GHC
> stores one bit per value, i.e. less than a MB for this range.

No, I didn't suggest that the elements be strict.  That would involve 
precomputing the entire table.  You _could_ do that if you anticipate a LOT 
of access to sufficient to outweigh the initial cost.  But that seems 
unlikely for a sparse domain, as you mentioned.

However, even non-strict arrays are created all at once (ie, they are strict 
in their _structure_), and the closures have to be allocated as the array is 
being created.  Creating a closure isn't terribly expensive, but creating 
5000000 closures might take awhile and cost a lot of memory if the closure 
has a large number of free variables (which depends on the function 
definition and the exact details of the lambda lifter).  Also, large arrays 
tend to play havoc with GHC's garbage collector; it has to scan all elements 
on every major GC, IIRC.  That alone may offset any advantages won.

In the end, the only way to be sure which method is best is to test it against 
your usage profile.  My guess is that the array method will have enough 
overhead that it will lose against a tree.  However I may be wrong, 
especially if the program will have a very long runtime and if a "warm-up" 
period is acceptable.

> > Little-endian patricia trees [...]
>
> Yes, sure, if you can't afford a 20Mb index.  On the other hand,
> changing the function to use an array is a very small modification,
> and probably more than good enough in many cases.

I completely agree; it is good for many cases, and can be a very useful 
technique.  I just don't think it will be good for _this_ case (large, sparse 
domain where f(n) doesn't depend on all f(m) where m < n).  That probability 
is positively correlated with the size of the domain.  Again, the only way to 
really know is to implement and benchmark.  Thankfully, caching techniques 
are completely local and can be changed easily.

> -k

-- 
Rob Dockins

Talk softly and drive a Sherman tank.
Laugh hard, it's a long way to the bank.
       -- TMBG