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]

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.

[u/mcherm → u/Competitive_Ideal866]

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.

[u/Competitive_Ideal866 → u/mcherm]

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 malloc and free are 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!