Re: Revert a CAF?
On 12/7/11 5:03 AM, Simon Marlow wrote: It would be possible, but it's not quite as straightforward as you might think. Suppose you have a program like this: xs = [1..10] evens = filter ((==0) . (`mod` 2)) xs and you fully evaluate evens. Now, GHC will garbage collect xs, because it isn't required any more. However, if you revert evens to a CAF, now we require xs again, so we have to either revert that to a CAF or arrange to retain it in the first place on the grounds that we might need it again if some other CAF is reverted. Reverting xs to a CAF is not hard - we could have the GC revert CAFs as soon as they become unreachable. Arranging to retain it is harder. Right. I know it isn't easy to do in the general case, which is why I was looking for an API hook rather than a Haskell function. Luckily my case is like xs. The only free variables are common functions ---functions used by list comprehension notation, methods of Num Int, Enum Int, Ord Int, (||), and ()--- which are almost surely inlined away and would never be reverted anyways. GHCi gets around this by reverting *all* CAFs at the same time when you say :load. There's one other thing: GHC doesn't support reverting CAFs in interpreted code at the moment, you have to reload the module. So you need the following things: - modify the GC to revert CAFs when they become garbage - add a primop to revert a single CAF not too hard, I would think... Good to know. I'll take a look at it over the break and see if I can come up with something. -- Live well, ~wren ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Revert a CAF?
On 07/12/11 15:16, Twan van Laarhoven wrote:
On 06/12/11 18:48, wren ng thornton wrote:
So, I have an optimization/internals question. Does the GHC API have any
hooks for being able to revert a CAF to the original expression, thus
discarding the previously computed result?
...
I could hack something together based on unsafePerformIO and top-level
IORefs, and it's clear that this is in fact a safe thing to do, but I'm
worried about the semantic issues inherent in unsafePerformIOed
top-level IORefs (e.g., the fact that their scope isn't particularly
well defined: is it per library instance? per runtime?...).
Unfortunately, for what I'm doing, it isn't really feasible to just
leave the IO type in there nor to pass around the infinite list so we
can use scoping rules to decide when to free it.
How bad is the IORef solution really? I.e. can someone more well versed
in ghc internals tell me why this wouldn't work?
type CAF a = IORef (() - a, a)
mkCAF :: (() - a) - a
mkCAF f = unsafePerformIO $ newIORef (f, f ())
getCAF :: CAF a - a
getCAF = snd . unsafeDupablePerformIO . readIORef
resetCAF :: CAF a - IO ()
resetCAF = modifyIORef $ \(f,_) - (f, f ())
myCAF :: CAF [Int]
myCAF = mkCAF $ \_ - [1..100]
{-# NOINLINE myCAF #-}
What will happen here is that GHC will transform it to:
x = [1..100]
myCAF = mkCAF $ \_ - x
and you're no better off. This will always happen with a function of
type () - a, because by definition the return value does not depend on
the argument, so the contents will always be lifted out.
You could use -fno-full-laziness I suppose...
Cheers,
Simon
___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Revert a CAF?
On 06/12/2011 17:48, wren ng thornton wrote: So, I have an optimization/internals question. Does the GHC API have any hooks for being able to revert a CAF to the original expression, thus discarding the previously computed result? The reason I'm wanting this is that I have a particular CAF which is an infinite list. Unfolding that list takes a fair deal of work, so we want to share it whenever possible; however it doesn't take an overwhelming amount of work, so if we know we've evaluated more of the list than necessary (for a long while), it'd be nice to be able to revert the evaluation in order to save on memory overhead (e.g., by calling relax :: IO()). I could hack something together based on unsafePerformIO and top-level IORefs, and it's clear that this is in fact a safe thing to do, but I'm worried about the semantic issues inherent in unsafePerformIOed top-level IORefs (e.g., the fact that their scope isn't particularly well defined: is it per library instance? per runtime?...). Unfortunately, for what I'm doing, it isn't really feasible to just leave the IO type in there nor to pass around the infinite list so we can use scoping rules to decide when to free it. (Feel free to offer alternative suggestions to handling this situation too.) It would be possible, but it's not quite as straightforward as you might think. Suppose you have a program like this: xs = [1..10] evens = filter ((==0) . (`mod` 2)) xs and you fully evaluate evens. Now, GHC will garbage collect xs, because it isn't required any more. However, if you revert evens to a CAF, now we require xs again, so we have to either revert that to a CAF or arrange to retain it in the first place on the grounds that we might need it again if some other CAF is reverted. Reverting xs to a CAF is not hard - we could have the GC revert CAFs as soon as they become unreachable. Arranging to retain it is harder. GHCi gets around this by reverting *all* CAFs at the same time when you say :load. There's one other thing: GHC doesn't support reverting CAFs in interpreted code at the moment, you have to reload the module. So you need the following things: - modify the GC to revert CAFs when they become garbage - add a primop to revert a single CAF not too hard, I would think... Cheers, Simon ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Revert a CAF?
On 06/12/11 18:48, wren ng thornton wrote:
So, I have an optimization/internals question. Does the GHC API have any
hooks for being able to revert a CAF to the original expression, thus
discarding the previously computed result?
...
I could hack something together based on unsafePerformIO and top-level
IORefs, and it's clear that this is in fact a safe thing to do, but I'm
worried about the semantic issues inherent in unsafePerformIOed
top-level IORefs (e.g., the fact that their scope isn't particularly
well defined: is it per library instance? per runtime?...).
Unfortunately, for what I'm doing, it isn't really feasible to just
leave the IO type in there nor to pass around the infinite list so we
can use scoping rules to decide when to free it.
How bad is the IORef solution really? I.e. can someone more well versed
in ghc internals tell me why this wouldn't work?
type CAF a = IORef (() - a, a)
mkCAF :: (() - a) - a
mkCAF f = unsafePerformIO $ newIORef (f, f ())
getCAF :: CAF a - a
getCAF = snd . unsafeDupablePerformIO . readIORef
resetCAF :: CAF a - IO ()
resetCAF = modifyIORef $ \(f,_) - (f, f ())
myCAF :: CAF [Int]
myCAF = mkCAF $ \_ - [1..100]
{-# NOINLINE myCAF #-}
Twan
___
Glasgow-haskell-users mailing list
Glasgow-haskell-users@haskell.org
http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Revert a CAF?
So, I have an optimization/internals question. Does the GHC API have any hooks for being able to revert a CAF to the original expression, thus discarding the previously computed result? The reason I'm wanting this is that I have a particular CAF which is an infinite list. Unfolding that list takes a fair deal of work, so we want to share it whenever possible; however it doesn't take an overwhelming amount of work, so if we know we've evaluated more of the list than necessary (for a long while), it'd be nice to be able to revert the evaluation in order to save on memory overhead (e.g., by calling relax :: IO()). I could hack something together based on unsafePerformIO and top-level IORefs, and it's clear that this is in fact a safe thing to do, but I'm worried about the semantic issues inherent in unsafePerformIOed top-level IORefs (e.g., the fact that their scope isn't particularly well defined: is it per library instance? per runtime?...). Unfortunately, for what I'm doing, it isn't really feasible to just leave the IO type in there nor to pass around the infinite list so we can use scoping rules to decide when to free it. (Feel free to offer alternative suggestions to handling this situation too.) -- Live well, ~wren ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
RE: Revert a CAF?
GHCi does this somehow, so it's definitely possible; Simon M will know. | -Original Message- | From: glasgow-haskell-users-boun...@haskell.org [mailto:glasgow-haskell-users- | boun...@haskell.org] On Behalf Of wren ng thornton | Sent: 06 December 2011 17:49 | To: GHC-users List | Subject: Revert a CAF? | | So, I have an optimization/internals question. Does the GHC API have any | hooks for being able to revert a CAF to the original expression, thus | discarding the previously computed result? | | The reason I'm wanting this is that I have a particular CAF which is an | infinite list. Unfolding that list takes a fair deal of work, so we want | to share it whenever possible; however it doesn't take an overwhelming | amount of work, so if we know we've evaluated more of the list than | necessary (for a long while), it'd be nice to be able to revert the | evaluation in order to save on memory overhead (e.g., by calling relax | :: IO()). | | I could hack something together based on unsafePerformIO and top-level | IORefs, and it's clear that this is in fact a safe thing to do, but I'm | worried about the semantic issues inherent in unsafePerformIOed | top-level IORefs (e.g., the fact that their scope isn't particularly | well defined: is it per library instance? per runtime?...). | Unfortunately, for what I'm doing, it isn't really feasible to just | leave the IO type in there nor to pass around the infinite list so we | can use scoping rules to decide when to free it. | | (Feel free to offer alternative suggestions to handling this situation too.) | | -- | Live well, | ~wren | | ___ | Glasgow-haskell-users mailing list | Glasgow-haskell-users@haskell.org | http://www.haskell.org/mailman/listinfo/glasgow-haskell-users ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
Re: Revert a CAF?
Can you use a weak pointer to do what you want? If you keep a weak pointer to the head of your expensive list then itwill be reclaimed at the next major GC I believe. I have used weakpointers for vaugely similar purposes before. I guess a downside is that they will always be reclaimed on GC even ifthere isn't memory pressure, I think. John (resent, accidentally sent to wrong address first) ___ Glasgow-haskell-users mailing list Glasgow-haskell-users@haskell.org http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
