Shower thought: Dynamically sized stack frames


#1

I don’t know much about allocators and the implications of low level optimisations, but this occurred to me a few days ago, and I have been thinking about it a bit. I did a bit of searching online but couldn’t find much information about anything like this being done in other languages.

Is it possible, under some circumstances, for (a future version of) Rust to support dynamically resizable function stack frames?

It seems to me that the following conditions are sufficient:

  1. There is one dynamically sized variable per function.
  2. The function is the owner of that variable.
  3. Mutations of the variable which affect its size may only be performed by:
    a. the owning function or
    b. strictly inlined methods that are called by the function or
    c. other functions where the mutation is the last thing the function does.

If the compiler can be certain that those conditions are met, then the memory holding the variable can be guaranteed to be the top of the stack, and it could be always be resized into contiguous memory.

Has anything similar to this been discussed anywhere? I would be interested to read about it more.


#2

Note that call stacks usually grow down, so the “top” of the stack is actually the lowest address. That doesn’t lend itself well to the sort of resizing you seem to be asking for.

But more generally, in C you can use alloca to make arbitrary stack allocations. I don’t know what it would take for Rust to support this.


#3

In C variable length arrays also achieve dynamic frames in a less ad-hoc fashion.

I wish Rust supported VLA’s too. The argument I’ve heard against them was that llvm doesn’t optimize such functions well, but I haven’t noticed any problems in C.


#4

There’s a proposal to introduce unsized rvalues into the language:

The discussion surrounding both this and an earlier effort to introduce alloca is well worth reading.


#5

Thanks. I knew there had to be some discussion on the topic, I just didn’t know what to search for.


#6

Rust has already had dynamically sized stacks (and removed them), see https://github.com/rust-lang/rust/issues/8345