I just had an excellent time listening to the last Signals and Threads podcast episode on Memory Management, with Stephen Dolan (@stedolan) as the guest and Yaron Minsky (@Yaron_Minsky) as the host discussing:
memory management in programming languages in general
memory management in OCaml
ongoing research by Stephen and Leo White (@lpw25) on memory-management and data-representation features for OCaml (unboxed types, local values on the stack).
I would warmly recommend giving it a try if you are interested in programming language implementation. There is new stuff to learn for everyone, and I also liked the presentation of the parts I was already familiar with.
Would be interesting to read more about the theoretical aspects of stack allocation. My understanding is that there has been tons of research done for JVM and escape analysis has been added, but it turns out to be a hard problem.
If you’re interested in a modern approach of stack allocation, I would suggest looking at Rust and in particular the lifetimes. It’s a bit heavy on the typing side, so it’s not easy to fit into an existing language, but I believe it gives you optimal stack allocations (or something close to it).
If I read Stephen’s answers correctly, what he and Leo are considering is a much simpler concept of lifetime (basically, the only thing they’re tracking in the types is whether functions can unify the lifetime variable of their arguments with lifetimes that are outside the scope of the function). So at least for now this will be only allow stack allocations in limited contexts (if higher-order functions are involved this might not work), but it could still end up quite useful in practice. And it should be possible to fit with the current OCaml compiler.
Thanks for the nice words. Interviewing Dolan was fun and I learned a lot.
Local types are still very new: we’re hoping to start rolling it out in a limited way internally in the next few weeks, and I expect we’ll learn a lot from that. We plan on discussing it more publicly as well, but that’s a bit farther out. In the meantime, the source is all available on Github if anyone wants to poke around.
The approach to stack allocation is different and simpler than the one in Rust, as Dolan explained in the episode. Instead of having implicit, polymorphic lifetime variables, function arguments can be marked as local, which prevents the function in question from stashing a reference to those types. This avoids the need to deal with higher-rank polymorphism, which Rust’s lifetime approach requires, and as a result makes inference work nicely.
Another neat trick is that you can create functions that can allocate on the parent stack frame (by dint of not having their own stack frame). This lets you build smart constructors for stack-allocated values.
Local types are apparently an example of modal types, though I don’t really know enough type theory to have a deep sense of what that means. But it’s a powerful thing, and local types appear to be useful for more than just stack allocation, as we’re just starting to discover.
And, I suppose as I should always mention: we’re looking for people to come and work with Dolan and Leo and the rest of the team on this kind of stuff.
Rather than Rust, the small bits we heard of the “local types” design reminded me of the work on “second-class values” in the Scala community, see
In this brand of work, non-escaping values are mentioned to follow a stack discipline, but the focus of most the article is not memory management, but rather on expressing effect-system and capability-systems-like control over effects and resources. I wonder if the OCaml work would be amenable to similar extensions.
(Of course there is always a trade-off when considering new applications, they encourage you to make the mechanism more general, which can hurt ergonomics for the privileged problem domain. But at least knowing that two things are separate instances of a more general theory gives a lot of information on how they could interact together.)
The JVM can do some nice things with escape analysis and scalar value replacement to avoid allocations. Graal goes further and can do partial escape analysis. This means it can deal with situations where an allocation may escape through some path, which would normally defeat a less sophisticated analysis, and push the allocation to only that path.
The problem with the JVM’s optimisations though is that you can’t always rely on them. It’s very easy to accidentally defeat the escape analysis in unexpected ways, sometimes even at runtime (e.g connecting a JVM agent that adds instrumentation which causes some allocations to now escape). We did a talk a while back that goes in to some of these issues: LJC Virtual Meetup: No Free Lunch? Memory Allocation in the JVM - YouTube
If my understanding of the local allocation work is right, it should give you predictability of placement in a way escape analysis can’t. That’s a really nice property.
Yeah, that’s exactly right. Both local types and unboxed types are type-system features intended to give users more explicit control over performance-relevant details, rather than optimizations that apply whenever the compiler can figure out how to apply them.
Obviously both approaches to optimization are important, but when you’re trying to optimize a program carefully, explicit control is hugely valuable.
It is indeed related to that line of work, and could similarly be used to help with reasoning about capabilities and effects, without needing a full effect system, as in papers like:
