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. Thanks, Andrew -- http://www.acooke.org/andrew
On Sun, 2 Nov 2003 22:58:41 -0300 (CLST) "andrew cooke" <andrew@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
G'day all. On Sun, 2 Nov 2003 22:58:41 -0300 (CLST) "andrew cooke" <andrew@acooke.org> wrote:
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.
It sounds to me like separating out the reclamation algorithm is going to go better for you, so you can play with different approaches. Quoting Ben Escoto <bescoto@stanford.edu>:
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.
I think that periodically rebuilding the cache is almost certainly the best approach. However, I would caution against LRU-based policies, because the work pessimally when your working set is just larger than the size of your cache. One approach that I used once was that when my data structure reached a certain size, I would randomly drop N% (in my application, N == 50) of the items in it. This greatly simplifies bookkeeping, as you only need to keep track of the number of items in the cache, which you usually get for free anyway. If recomputation isn't _that_ expensive, this is a good approach. Another possibility is to use a "not recently used" algorithm. You record the last, say, 10% of accesses, keep those, and randomly eject 50% of what remains. If recent entries are very precious, this can be a good compromise. If you can wait a day or two, I have some code which needs to be cleaned up which does pretty much this. Cheers, Andrew Bromage
ajb@spamcop.net said: [...]
If you can wait a day or two, I have some code which needs to be cleaned up which does pretty much this.
Thanks to everyone who's replied (including some replies I see in the inbox that I have not read yet). Yes, I can certainly wait (and would be interested to see the code, although it's not critical for me) - I work shifts and won't have free time (this isn't work-related) until next Wednesday (although I'm taking Saturday as a holiday to watch the ll3 webcast ;o). Cheers, Andrew -- http://www.acooke.org/andrew
Hi Andrew. This situation is what weak pointers [1] are for. You keep weak rather than regular pointers to your cache data. The garbage collector clears out the weak pointers and reclaims cache data when necessary. However, I don't think there is any policy to make discriminating choices about *which* cache data gets discarded, for instance least recently (or frequently) used. Doing so would seem to be an interesting and useful extension. Regards, - Conal [1] Stretching the storage manager: weak pointers and stable names in Haskell, Simon Peyton Jones, Simon Marlow, and Conal Elliott. Proc Workshop on Implementing Functional Languages, 1999. http://research.microsoft.com/~simonpj/Papers/weak.htm -----Original Message----- From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of andrew cooke Sent: Sunday, November 02, 2003 5:59 PM To: haskell@haskell.org Subject: Expiring cached data? 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. Thanks, Andrew -- http://www.acooke.org/andrew _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
Conal Elliott writes: | Hi Andrew. This situation is what weak pointers [1] are for. You keep | weak rather than regular pointers to your cache data. The garbage | collector clears out the weak pointers and reclaims cache data when | necessary. However, I don't think there is any policy to make | discriminating choices about *which* cache data gets discarded, for | instance least recently (or frequently) used. : How about adapting splay trees so that their pointers become weak after a certain depth? The advantage for caching is that the more frequently used elements move closer to the root, so you wouldn't have to add much code for tracking recent use, just a depth threshold. See the book Purely Functional Data Structures for more details on implementing splay trees in a functional setting. - Tom
Cool idea! Still, this discussion suggests to me the idea of "relatively weak pointers". Instead of a pointer being either strong or weak, what if it could have a strength attribute (estimated value to the app), e.g., in the real interval of zero to one? The garbage collector would prefer breaking weaker pointers over stronger ones. The strength required to survive a GC would depend on available memory and on the distribution of existing pointer strengths and the reclamation benefits of breaking weaker ones. - Conal -----Original Message----- From: haskell-bounces@haskell.org [mailto:haskell-bounces@haskell.org] On Behalf Of Tom Pledger Sent: Monday, November 03, 2003 12:18 PM To: haskell@haskell.org Subject: RE: Expiring cached data? Conal Elliott writes: | Hi Andrew. This situation is what weak pointers [1] are for. You keep | weak rather than regular pointers to your cache data. The garbage | collector clears out the weak pointers and reclaims cache data when | necessary. However, I don't think there is any policy to make | discriminating choices about *which* cache data gets discarded, for | instance least recently (or frequently) used. : How about adapting splay trees so that their pointers become weak after a certain depth? The advantage for caching is that the more frequently used elements move closer to the root, so you wouldn't have to add much code for tracking recent use, just a depth threshold. See the book Purely Functional Data Structures for more details on implementing splay trees in a functional setting. - Tom _______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell
G'day all. Tom Pledger wrote:
How about adapting splay trees so that their pointers become weak after a certain depth? The advantage for caching is that the more frequently used elements move closer to the root, so you wouldn't have to add much code for tracking recent use, just a depth threshold.
Nice idea, but I think it wouldn't be generally useful. Splay trees optimise themselves for static frequency distributions. Caches, on the other hand, are generally used more for changing working sets (i.e. dynamic frequency distributions). It seems to me that splay trees are therefore not necessarily a good fit. Cheers, Andrew Bromage
ajb@spamcop.net writes: | G'day all. | | Tom Pledger wrote: | | > How about adapting splay trees so that their pointers become weak | > after a certain depth? The advantage for caching is that the more | > frequently used elements move closer to the root, so you wouldn't have | > to add much code for tracking recent use, just a depth threshold. | | Nice idea, but I think it wouldn't be generally useful. Splay trees | optimise themselves for static frequency distributions. Caches, on | the other hand, are generally used more for changing working sets (i.e. | dynamic frequency distributions). It seems to me that splay trees are | therefore not necessarily a good fit. Hi. It sounds like the term "splay tree" means different things to different people. I was thinking in particular of one which, whenever it finds a key it was looking for, does some rotation so that the key's node's depth is reduced. e.g. finding g in this initial tree causes this rotation d d / \ / \ T1 h T1 h / \ / \ weak f T2 g T2 pointer ------ / \ -------------------------- / \ ------- threshold T3 g f T5 / \ / \ T4 T5 T3 T4 This is admittedly a side effect on the cache lookup, but we'd be in the IO monad anyway if we're using weak pointers. - Tom
G'day all. Quoting Tom Pledger <Tom.Pledger@peace.com>:
It sounds like the term "splay tree" means different things to different people. I was thinking in particular of one which, whenever it finds a key it was looking for, does some rotation so that the key's node's depth is reduced.
The one I'm thinking of (and I believe it's "the original") is Sleator and Tarjan's "Self-adjusting binary search trees" from JACM some time in the mid-80s. Their algorithm moves the just-accessed key to the root. Cheers, Andrew Bromage
ajb@spamcop.net wrote:
G'day all.
Tom Pledger wrote:
How about adapting splay trees so that their pointers become weak after a certain depth? The advantage for caching is that the more frequently used elements move closer to the root, so you wouldn't have to add much code for tracking recent use, just a depth threshold.
Nice idea, but I think it wouldn't be generally useful. Splay trees optimise themselves for static frequency distributions. Caches, on the other hand, are generally used more for changing working sets (i.e. dynamic frequency distributions). It seems to me that splay trees are therefore not necessarily a good fit.
The key here is the pattern in which the data in the tree are accessed -- and it seems that whether or not that pattern changes over time is not terribly significant. If there's a degree of locality of reference, i.e. accessing a certain value means there's likely an enhanced probability of values `near' (in terms of whatever ordering is being used) it being accessed in the short term, it's likely a big win. Otherwise the constant factors likely clobber you, as accesses `drag along' the neighbors. As far as taking a modified LRU approach is concerned (since, as mentioned elsethread, when LRU goes bad, it goes *really* bad), you might want to look at: http://www.cc.gatech.edu/~yannis/eelru.ps Cheers, (with hopes I'm not out of my league) --ag -- Artie Gold -- Austin, Texas Oh, for the good old days of regular old SPAM.
participants (6)
-
ajb＠spamcop.net -
andrew cooke -
Artie Gold -
Ben Escoto -
Conal Elliott -
Tom Pledger