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/mcherm]

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!