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