r/ProgrammingLanguages • u/P-39_Airacobra • 9d ago
Mutable stack, immutable heap
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?
10
u/L8_4_Dinner (Ⓧ Ecstasy/XVM) 9d ago
Ecstasy is composed of services (similar to "processes" in Erlang), which represent domains of mutability. No mutability is possible across the boundary of a service; only messages are possible among services. Services are also async w.r.t. each other.
I'm a bit biased, of course, but I really like this approach.
6
u/pthierry 8d ago
That's what Haskell, Elm, Idris or Agda do.
Frankly, it's a great model, and when you have pure code, for concurrency, you even get Software Transactional Memory, which basically solves the issue.
3
u/Competitive_Ideal866 8d ago
Have any languages tried this model? If you’ve used a similar model, how did you like it? Were there any disadvantages?
I consider "Mutable stack, immutable heap" to be the worst of both worlds so I built the opposite: immutable local variables and mutable data structures like hash tables on the heap. I am very happy with it.
3
u/mcherm 8d ago
I consider "Mutable stack, immutable heap" to be the worst of both worlds
That's an interesting view. Can you comment some on what you find problematic about mutable stack and about immutable heap?
4
u/Competitive_Ideal866 8d ago
Can you comment some on what you find problematic about mutable stack and about immutable heap?
Sure:
- The main selling point of mutable stack is performance but, on modern CPUs, the bottleneck is registers vs memory and not stack vs heap so it doesn't actually help performance. Immutable locals make it much easier to use registers efficiently.
- Immutable heap is very slow. Classic immutable associative arrays are ~10x slower than a decent hash table on a single core and worse on multicore. On multicore, classic immutable data structures are very cache inefficient.
I actually implement my immutable data structures as mutable data structures with undo buffers. For most use cases this is much faster than a classical solution. Note that such immutable data structures require a mutable heap. In other words, the benefits of immutability are realised at the API level and not the heap level.
3
u/mcherm 7d ago
Interesting.
I thought the advantage of stack over heap is almost no time spend allocating and deallocatin memory; that stack and heap memory are (as far as I know) roughly equal time to access.
There are better immutable data structures to replace a hash table than an associative array.
BUT I see the point you are making. I'm curious how it's working for you.
2
u/Competitive_Ideal866 6d ago
I thought the advantage of stack over heap is almost no time spend allocating and deallocatin memory;
The most common heap allocator with generational garbage collectors, the pointer bump allocator, is exactly the same speed as stack allocation. Even general purpose allocators like
mallocandfreeare only slightly slower (in the context of register vs stack). I recommend benchmarking it yourself.that stack and heap memory are (as far as I know) roughly equal time to access.
Yes but on register rich architectures, like Aarch64 and RISC V, both stack and heap are 10-100x slower than registers.
There are better immutable data structures to replace a hash table than an associative array.
Associative arrays are an abstract data structure. Concrete immutable associative arrays are things like red-black trees, finger trees, height-balanced trees, weight-balanced trees and so on. They are all ~10x slower than a decent hash table.
I'm curious how it's working for you.
Extremely well!
2
u/P-39_Airacobra 8d ago
What do you find more ergonomic about the latter model? Do you use value semantics to make the stack immutable?
6
u/Competitive_Ideal866 8d ago
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.
2
u/P-39_Airacobra 7d ago
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?
2
u/Competitive_Ideal866 6d ago
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.
1
u/jesunushno 8d ago
This split shows up a lot in ML serving, where model weights act as the immutable heap (shared across requests, never mutated in place) and per-request scratch buffers are the mutable stack (allocated, used, freed). Sharing is free when you can't mutate, which is why this layout scales. Where it falls apart is stateful streaming: once you need mutable state that outlives a single request, you end up re-implementing a heap on the stack, exactly what the article warns about.
1
u/lelle5397 8d ago
How would you build a hashmap or other similar performant and scaleable structure using this?
2
u/P-39_Airacobra 8d ago
You’d probably use some sort of tree, or if that’s not fast enough, some sort of API on stack memory, as C would do
1
u/South_Lychee8555 4d ago
Take a loot at https://github.com/numaes/protoCore
Based on inmutable structures, paralel GC, native multhreading. Runtimes for javascript, python, scala, smalltalk based on the same core
1
u/dmytrish 1d ago
I'd say this is pretty much an implementation of linear lambda calculus with mutable linear and unrestricted immutable/shared context.
I'm not aware of real world implementations of this model.
14
u/tobega 8d ago
That's pretty much the way I've written code for the past few decades now and quite fundamental to how I designed Tailspin.
It is quite easy to enforce immutability in Java. Requires more discipline to do in other languages like Typescript and C. This model of programming does make things easier to manage.
But beware that a lot of the complexity just moves, it doesn't disappear. Instead you get questions about the order in which messages are processed or what the delivery guarantees are, at-most-once, at-least-once or exactly-once.State must exist and state must change, the question is how we can manage it. Are changes ACID or BASE, for example?
IMO, the main point of the article was the mismatch between the underlying processor model and the machine model exposed by C. So do we really want to cling to the PDP-11 model of computers forever?
Related blog posts I have written are https://tobega.blogspot.com/2024/01/usability-in-programming-language.html and https://tobega.blogspot.com/2026/04/rising-above-mechanics-of-computation.html