Expiring cached data?

[Ben Escoto]

On Sun, 2 Nov 2003 22:58:41 -0300 (CLST)
"andrew cooke" <andrew at acooke.org> wrote:
> I have a Haskell program that caches data in a tree.  Unfortunately,
> the tree grows to exceed the available memory over time.  In a
> different language, where I might be handling the caching myself,
> rather than relying on laziness within the language, I might work
> round this by keeping track of which leaves in the tree were more
> recently used, and, when memory run slow, deleting those that have
> not been used for some time (by the nature of the problem, access to
> particular caches tend to be grouped, so a long-unused cache can be
> deleted without much performance penalty).
> 
> What options do I have in Haskell?  I'm interested both in general
> solutions (maybe some compilers do this anyway?) and in approaches
> to structuring the program so that I can control caching in more
> detail.

I'm new to Haskell, so take this with a grain of salt.  More
experienced coders will probably have better advice, but no one else
has responded yet.

Anyway, what you could do pair the tree with some data structure which
keeps track of what parts of the tree have been recently read.
Functions that read the tree could return a new pair (tree,
other_data_structure).  Usually read functions would just return the
tree as-is and just update that other data structure.

However, once in a while (every N reads?), the tree could be rebuilt
based on the data stored in the other data structure.  Leaves that you
want to expire could be recreated, and the leaves you want to save
could be copied directly from the old tree.  The new tree would be
returned, and the cached stuff you don't want would be garbaged
collected.

Maybe you could stick the tree and the data structure that monitors
tree reads into a state monad to simply some of the bookkeeping.


-- 
Ben Escoto
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: not available
Url : http://haskell.org/pipermail/haskell/attachments/20031102/048b1ba9/attachment.bin