It seems that in the recent years, there have been advancements towards the in-place implementations for functional programs, as seen in Lean 4 and Roc and Koka, and several academic papers.
Are there any plans to implement such strategies in Haskell (i.e, GHC)? I did a quick Google search but couldn’t find any discussion.
Dynamic reuse relies on reference counting as garbage collection strategy. Thunks and mutable data structures introduce cycles in the heap, so you cannot use reference counting (exclusively) to collect such a heap. Therefore I don’t see how to apply these techniques to GHC Haskell.
On the other hand, transient data structures offer the same promise of in-place update. It’s just that GHC’s support for mutable data structures (e.g. record fields) is lacking, so there is an inherent overhead to transients.
The results on p31 were mixed, but I think they’d be a win overall if more code was actually written in a way that exploited mutability more (which would’ve required large refactorings).
in order to build and modify heap closures in place, you can exploit the compact region feature. this is deeply cursed territory and has many footguns, but my colleague @tbagrel1 did some explorations on this front and he might be motivated to provide a bit of his experience here
I indeed used Compact Regions as a way to obtain immovable memory area in which the GC won’t go looking. That way, I could do controlled mutations without fear of letting the RTS read uninitialized pointers etc. The end goal was to enable destination-passing style programming in Haskell, but I guess that the same tricks could be used to implement FiP programming too.
AFAIK, doing the same kind of mutations in the garbage-collected heap would require a very precise understanding of garbage collection/RTS in GHC, and alas, I don’t have it. I’m also afraid it would be even more brittle than what I propose in my work, as any modification of the GC implem afterwards would require to review and adapt the mutation system again.
Personnally, I used compact regions almost solely to avoid the GC. But maybe there are alternate memory allocation systems that could be even better for that purpose.
I don’t know the GHC compiler or runtime well at all, but would it not be possible for compile time reuse analysis to produce code that replaces values in single-use constructors of same size?
For example, could a function f :: Int → Int be compiled to not allocate a new I# and instead replace the value in the supplied I# with the result, as long as the caller is the producer of that input and only uses it when passing it to f?
Of course, the compiler might have to produce two versions of f, one of them for cases where this cannot be applied.
So I don’t like making promises on something that isn’t public yet, but this is what I have been doing for the last 2 years during my free time. I have been building a new Haskell compiler entirely from scratch and I plan to use FBIP. I plan on releasing it and make a proper announcement when I get to the MVP (if I get there tbh).
In order to allow reuse of a heap object, you need to know whether the object is dead at the point where you want to reuse it. So we are talking about a static analysis that estimates the lifetime of heap objects. (How reuse is implemented is a different matter, but as you note it is doable.)
I don’t have much experience with such analyses and am having doubts about its precision (i.e., that it justifies much reuse in the end). But one thesis I mentored on this topic is an escape analysis. That is, an analysis that infers whether some heap object does not live longer than its allocating function and hence can be allocated on the stack: https://pp.ipd.kit.edu/uploads/publikationen/scheper22masterarbeit.pdf
The results here need to be taken with a grain of salt: Although the portion of heap objects that can be allocated on the stack is huge, certainly some of the ensuing stack allocation is not safe for space, that is, the stack allocated objects will occupy stack space longer than they are actually alive, which may lead to an asymptotic increase in total memory usage.
However, maybe an escape analysis like this could be useful to estimate whether reuse of some heap object is possible. I’d also hope that there are more advanced attempts to reuse analysis. However, a static reuse analysis will yield far smaller benefits than a dynamic one based on reference counting.
Though it’s okay to have global recursive thunks because they don’t have a reference count. Right now my plan is to use lambda lifting to rewrite all recursive let bindings into global let bindings.
How do you track the lifetime of global thunks if they don’t have a reference count? GHC calls these “constant applicative form” and is careful to release them once they are dead. IIRC it’s kind of a big deal (though I wasn’t around when this hadn’t been implemented yet).
You don’t. They’re global variables, they’re supposed to leak. I don’t want to have a runtime that needs to know what main is doing or what threads are currently running. Being able to write shared library that you can use from C is one of my goals.
I’m fully aware that will break the big O characteristics of certain Haskell programs but I’m okay with that. Haskell 2010 is dead anyway, so almost all packages will need to be ported to avoid GHC features I don’t implement either way.
