4 ms·

PDGC would make a lot of sense as the GC system for Haskell. The key change you need to make to the RTS is, when you evaluate a thunk, rather than overwriting

PDGC would make a lot of sense as the GC system for Haskell. The key change you need to make to the RTS is, when you evaluate a thunk, rather than overwriting it with the final value, instead append the evaluated value to the thunk. Then, the GC should be free at any time to erase the "evaluated" part of the thunk if doing so would allow it to free up a lot of memory. When a thunk is entered it should return the evaluated value if present, otherwise it should use the code pointer and closure data to create the evaluated value again. The key challenge is designing the algorithm that decides what is beneficial to lose references to. Probably you want to keep some stats around about frequency of access of thunks and so on. I haven't seen anything like this proposed for Haskell, so I would be interested in reading a paper, should you implement it :-)

eru 17y ago
Thunks can be arbitrarily bigger than their evaluated value. (Say, the value is an Int.) So expanding and replacing thunks usually even saves memory and gets rid of live references.
jganetsk 17y ago
The key change you need to make to the RTS is, when you evaluate a thunk, rather than overwriting it with the final value, instead append the evaluated value to the thunk. This already happens in GHC. Any thunk that is to get updated has one word reserved as a slot for the update result. This is necessary for proper operation in SMP systems, when two processors race to evaluate the same thunk. The only data that gets overwritten is the thunk's code pointer. There is one standard routine in the binary, known as the indirection code, which just returns the value in the update slot of the currently active thunk. The thunk's pointer is set to point to the well-known address of the indirection code. In all this, the thunk's payload remains untouched. GHC's GC short circuits these indirection nodes, and ignores pointers in the thunk payload (since the thunk payload has become effectively unreachable). In order to accomplish your goal, we would have to recover the original value of the code pointer. This can be done by storing a copy of this value in the payload (similar to what you are suggesting). A way to do this without increasing the size of any heap object is for the compiler to generate a copy of the indirection code per thunk code block... such that the original thunk code address can be recovered from the particular indirection code address via a lookup (or potentially, via arithmetic). This bloats the emitted code by a small fraction, but may be worth it.

eru 17y ago

Thunks can be arbitrarily bigger than their evaluated value. (Say, the value is an Int.) So expanding and replacing thunks usually even saves memory and gets rid of live references.

jganetsk 17y ago

The key change you need to make to the RTS is, when you evaluate a thunk, rather than overwriting it with the final value, instead append the evaluated value to the thunk. This already happens in GHC. Any thunk that is to get updated has one word reserved as a slot for the update result. This is necessary for proper operation in SMP systems, when two processors race to evaluate the same thunk. The only data that gets overwritten is the thunk's code pointer. There is one standard routine in the binary, known as the indirection code, which just returns the value in the update slot of the currently active thunk. The thunk's pointer is set to point to the well-known address of the indirection code. In all this, the thunk's payload remains untouched. GHC's GC short circuits these indirection nodes, and ignores pointers in the thunk payload (since the thunk payload has become effectively unreachable). In order to accomplish your goal, we would have to recover the original value of the code pointer. This can be done by storing a copy of this value in the payload (similar to what you are suggesting). A way to do this without increasing the size of any heap object is for the compiler to generate a copy of the indirection code per thunk code block... such that the original thunk code address can be recovered from the particular indirection code address via a lookup (or potentially, via arithmetic). This bloats the emitted code by a small fraction, but may be worth it.