Yeah it seems like the general solution to the problem would be some sort of map-like datastructure that you add items via a key/value pair, and if the key gets GC'd, that entry gets removed from the structure.
I've been wanting something like this as well, but didn't know about weak references so I didn't know if it was possible, but I think I could make something like this now. I'll give it a shot and let you guys know how it goes. Rodney could you post your memo code that uses the weak references? - Job On Fri, Sep 18, 2009 at 7:56 AM, Peter Verswyvelen <[email protected]>wrote: > I would also like to see a solution for problems like these. > > Haskell provides a lot of nice memoizing / caching data structures - > like a trie - but the ones I know indeed keep growing, so no garbage > collection takes place? > > It would be nice to have a data structure that performs caching but > does not grow unlimited. > > I had a similar problem with stable names; it is not possible to check > if a stable name is still "alive". > > On Fri, Sep 18, 2009 at 1:39 AM, Rodney Price <[email protected]> > wrote: > > In my case, the results of each computation are used to generate a node > > in a graph structure (dag). The key, oddly, is a hash of a two-tuple > > that gets stored in the data structure after the computation of the > > node finishes. If I don't memoize the function to build a node, the > > cost of generating the tree is exponential; if I do, it's somewhere > > between linear and quadratic. > > > > Another process prunes parts of this graph structure as time goes on. > > The entire data structure is intended to be persistent, lasting for > > days at a time in a server-like application. If the parts pruned > > aren't garbage collected, the space leak will eventually be > > catastrophic. Either the memo table or the graph structure itself will > > outgrow available memory. > > > > -Rod > > > > > > On Thu, 17 Sep 2009 13:32:13 -0400 > > Job Vranish <[email protected]> wrote: > > > >> What are you trying to use this for? It seems to me that for memo > >> tables you almost never have references to they keys outside the > >> lookup table since the keys are usually computed right at the last > >> minute, and then discarded (otherwise it might be easier to just > >> cache stuff outside the function). > >> > >> For example with a naive fibs, the values you are passing in are > >> computed, and probably don't exist before you do the recursive call, > >> and then are discarded shortly afterward. > >> > >> It seems like putting a cap on the cache size, and then just > >> overwriting old entries would be better. > >> Am I missing something? > >> > >> - Job > >> > >> > >> > >> On Wed, Sep 16, 2009 at 4:48 PM, Rodney Price <[email protected]> > >> wrote: > >> > >> > How does garbage collection work in an example like the one below? > >> > You memoize a function with some sort of lookup table, which stores > >> > function arguments as keys and function results as values. As long > >> > as the function remains in scope, the keys in the lookup table > >> > remain in memory, which means that the keys themselves always > >> > remain reachable and they cannot be garbage collected. Right? > >> > > >> > So what do you do in the case where you know that, after some > >> > period of time, some entries in the lookup table will never be > >> > accessed? That is, there are no references to the keys for some > >> > entries remaining, except for the references in the lookup table > >> > itself. You'd like to allow the memory occupied by the keys to be > >> > garbage collected. Otherwise, if the function stays around for a > >> > long time, the size of the lookup table always grows. How do you > >> > avoid the space leak? > >> > > >> > I notice that there is a function in Data.IORef, > >> > > >> > mkWeakIORef :: IORef a -> IO () -> IO (Weak (IORef a)) > >> > > >> > which looks promising. In the code below, however, there's only one > >> > IORef, so either the entire table gets garbage collected or none of > >> > it does. > >> > > >> > I've been reading the paper "Stretching the storage manager: weak > >> > pointers and stable names in Haskell," which seems to answer my > >> > question. When I attempt to run the memoization code in the paper > >> > on the simple fib example, I find that -- apparently due to lazy > >> > evaluation -- no new entries are entered into the lookup table, and > >> > therefore no lookups are ever successful! > >> > > >> > So apparently there is some interaction between lazy evaluation and > >> > garbage collection that I don't understand. My head hurts. Is it > >> > necessary to make the table lookup operation strict? Or is it > >> > something entirely different that I am missing? > >> > > >> > -Rod > >> > > >> > > >> > On Thu, 10 Sep 2009 18:33:47 -0700 > >> > Ryan Ingram <[email protected]> wrote: > >> > > >> > > > >> > > memoIO :: Ord a => (a -> b) -> IO (a -> IO b) > >> > > memoIO f = do > >> > > cache <- newIORef M.empty > >> > > return $ \x -> do > >> > > m <- readIORef cache > >> > > case M.lookup x m of > >> > > Just y -> return y > >> > > Nothing -> do let res = f x > >> > > writeIORef cache $ M.insert x res m > >> > > return res > >> > > > >> > > memo :: Ord a => (a -> b) -> (a -> b) > >> > > memo f = unsafePerformIO $ do > >> > > fmemo <- memoIO f > >> > > return (unsafePerformIO . fmemo) > >> > > > >> > > I don't think there is any valid transformation that breaks this, > >> > > since the compiler can't lift anything through unsafePerformIO. > >> > > Am I mistaken? > >> > > > >> > > -- ryan > >> > > >> > _______________________________________________ > >> > Haskell-Cafe mailing list > >> > [email protected] > >> > http://www.haskell.org/mailman/listinfo/haskell-cafe > >> > > > > > _______________________________________________ > > Haskell-Cafe mailing list > > [email protected] > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > > _______________________________________________ > Haskell-Cafe mailing list > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe >
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
