[Haskell-cafe] function result caching

[Ketil Malde]

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. 

> 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.

> 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. 

-k
-- 
If I haven't seen further, it is by standing in the footprints of giants