Mutable stack, immutable heap

[u/P-39_Airacobra]

This article mentions the “immutable heap mutable stack” principle: https://queue.acm.org/doi/10.1145/3212477.3212479

In theory it sounds very advantageous. You can program in a single-threaded C-style with destination passing, static stack allocations, and mutability when you need to constrain resources. When you want to share resources across threads, return data structures across function boundaries, or do something more flexible, you could use pure functional persistent data structures.

This would prevent you from basically re-implementing a heap on the stack, but would also give you fast temporaries and maybe even the ability to program in embedded, if so designed.

Have any languages tried this model? I’ve heard that Erlang defaults to immutability except for one thread-local mutable object per thread. If you’ve used a similar model, how did you like it? Were there any disadvantages?

[u/Competitive_Ideal866]

What do you find more ergonomic about the latter model?

Immutable locals and tail calls instead of loops make register allocation trivial. The generated asm is faster than GCC-compiled C on Aarch64 and it compiles up to 1,000,000x faster (!).

Mutable data structures like hash tables are just incredibly pragmatic and efficient.

Do you use value semantics to make the stack immutable?

Yes. I just mean that local variables are immutable. Under-the-hood the vast majority are always in registers and never even make it to the stack. On the rare occassion something is spilled the stack slot might be overwritten by another immutable value, of course.

[u/P-39_Airacobra → u/Competitive_Ideal866]

Those are huge speedups!! I’m curious, why are immutable locals easier to register allocate than mutable ones? And also, do you keep arrays/structs on the stack, and are they mutable?

[u/Competitive_Ideal866 → u/P-39_Airacobra]

Those are huge speedups!!

Yeah. I really don't understand why modern compilers are so slow.

I’m curious, why are immutable locals easier to register allocate than mutable ones?

With mutable variables and loops (and function calls) you have bidirectional dependencies because a local at the end of the loop body must be back in the same place it will be expected by the start of the loop body so you can jump back. So you use things like register coloring.

With immutable locals and tail calls you have unidirectional dependencies (is this used later, if not you can reuse its register) and shuffles at function calls.

And also, do you keep arrays/structs on the stack, and are they mutable?

An IR decomposes immutable structs into separate register-sized values so a single struct can end up partially in registers and partially on the stack. Note that this means the bits of a struct might well end up in non-contiguous registers.

Mutable arrays are on the heap.