[Haskell-cafe] weak pointers and memoization (was Re: memoization)

[Job Vranish]

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 <rodprice at 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.spam at 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20090917/0b8aec60/attachment.html