Garbage collecting CAFs

[Simon Peyton-Jones]

A quick reply before running to ICFP

The trouble with CAFs is this

ints :: [Int]
ints = [1,2..]

f a b = ...ints...

The 'ints' CAF is alive at any point in program execution at which 'f' can be called in the future.  But a call to 'f' may be represented only by a reference to f's  entry point in some x86 code block; it does not mean that f's closure is reachable by the garbage collector.

GHC fixes this by adding, to each code block, a static table of pointers to other code blocks that it might call; and to any static closures (like 'ints') that it uses directly.  The garbage collector traverses the code graph via these static tables, to find all the CAFs that are still reachable.  Unreachable CAFs are garbage collected as usual.

It's all a major pain, and all the more so because it's usually only naïve programs that contain CAFs.  Real programs tend to depend on data read at runtime, and don't have large CAFs.  Alas, naïve programs are the ones people write on day 1, and we had lots of anguished cries that turned out to be CAF space leaks.  So we bit the bullet some years ago and did the full code-graph thing.  As a result, we removed many optimiser hacks which were there solely to avoid generating new CAFs that the programmer had not written.

Simon 

| -----Original Message-----
| From: glasgow-haskell-users-bounces at haskell.org [mailto:glasgow-haskell-users-
| bounces at haskell.org] On Behalf Of Andrew Cheadle
| Sent: 20 September 2005 20:47
| To: John Meacham
| Cc: glasgow-haskell-users at haskell.org
| Subject: Re: Garbage collecting CAFs
| 
| Hi John,
| 
| Obviously the Simons are most qualified to answer this, however,
| perhaps the following document (page 44-46) is sufficient to explain
| this:
| 
| http://www.haskell.org/ghc/docs/papers/run-time-system.ps.gz
| 
| it was a draft document that wasn't quite finished and was aimed at GHC
| 4.xx. I believe much of it is still applicable (except wrt evaluation
| where the eval-apply mechanism is used over push-enter).
| 
| HTH
| 
| Andy
| 
| On Tue, 20 Sep 2005, John Meacham wrote:
| 
| >I have seen numerous references to CAFs not used to being garbage
| >collected in ghc leading to various contortions of the optimizer to keep
| >from generating them and possible space leaks... then "something" was
| >done and they are now collected.. I am curious what paper (or list
| >message?) describes what that "something" is and what it entails in
| >terms of tradeoffs. thanks.
| >        John
| >
| >
| >--
| >John Meacham - ⑆repetae.net⑆john⑈
| >_______________________________________________
| >Glasgow-haskell-users mailing list
| >Glasgow-haskell-users at haskell.org
| >http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
| >
| 
| *********************************************************************
| *  Andrew Cheadle                    email:  a.cheadle at doc.ic.ac.uk *
| *  Department of Computing           http://www.doc.ic.ac.uk/~amc4/ *
| *  Imperial College                                                 *
| *  University of London                                             *
| *********************************************************************
| _______________________________________________
| Glasgow-haskell-users mailing list
| Glasgow-haskell-users at haskell.org
| http://www.haskell.org/mailman/listinfo/glasgow-haskell-users