On Sun, 2 Nov 2003 22:58:41 -0300 (CLST) "andrew cooke" <[EMAIL PROTECTED]> 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
pgp00000.pgp
Description: PGP signature
_______________________________________________ Haskell mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell
