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 <jvran...@gmail.com> 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 <rodpr...@raytheon.com> > 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 <ryani.s...@gmail.com> 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 > > Haskell-Cafe@haskell.org > > http://www.haskell.org/mailman/listinfo/haskell-cafe > > _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe