Re: [Haskell-cafe] weak pointers and memoization (was Re: memoization)
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
[Haskell-cafe] weak pointers and memoization (was Re: memoization)
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
Re: [Haskell-cafe] Re: [Haskell] ANNOUNCE: testrunner-0.9
When I run Example.lhs for test-framework I get [0] [1] in the test results, just as you show on your web page. If I run Example.lhs under ghci rather than compiled, I find the [0] [1] mingled with the test results in random ways. This leads me to believe that whatever is printing out [0] [1] is running is a separate thread. Does this [0] [1] have any meaning? If not, how do I get rid of it? Thanks, -Rod On Mon, 8 Jun 2009 19:07:52 +0100 Max Bolingbroke batterseapo...@hotmail.com wrote: 2009/6/8 Reinier Lamers tux_roc...@reinier.de: I checked out testpack and that did not meet my requirements. I don't know if I considered test-framework. If I did, it may be that I was turned off by the fact that the 'home page' link on cabal just goes to a web presentation of the source tree on github. Reinier, You are quite right that this is a weakness. I've been meaning to put a site together for a while, and your comment gave me the impetus to do it: http://batterseapower.github.com/test-framework/ That's much friendlier! All the best, Max ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe The following line is added for your protection and will be used for analysis if this message is reported as spam: (Raytheon Analysis: IP=128.36.229.215; e-from=haskell-cafe-boun...@haskell.org; from=batterseapo...@hotmail.com; date=Jun 8, 2009 6:08:07 PM; subject=[Haskell-cafe] Re: [Haskell] ANNOUNCE: testrunner-0.9) ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
