Use of segmented stack for DST

What about usage of segmented stacks? One of the implementations is a linked list of stack segments: what if we could use each one for storing one unsized local? What I want to propose is folowing schema: function stack begins with first segment, used for storing Sized types, in the begining of first segment we place the u32 offset which tells where start of next segment is; each segment stores offset of the next one counting from beginning of current. Offset value 0 indicates that there no next stack frame, possible exception is offset in start of first segment: it could indicate that there no use of segemented stacks at all.

Next thing I want to discuss is sizedness of values: in this category we have Sized values and Sized? values which also called unsized. So I propose folowing placement of each kind in segments: first segment is used for storing Sized values, for each unsized value there are a separate stack frame.

The cost of extending stack frame is big: moving all following frames by certain offset (and possible realloc call).

Another thing I want to ask is will it require tweaking calling convention?

This is incorrect. Firstly, it's Sized and ?Sized. Secondly, ?Sized is "maybe sized", ?Sized just relaxed the implicit Sized bound on generics. You can still put a sized type into a generic that is ?Sized and can handle unsized types.

Rust actually used segmented stacks in the olden days! When it moved back to just regular program stack, it was decided to do so because Rust is about choosing your tradeoffs. The idea of Rust is that you have control over any potentially expensive operation so you can have a great understanding of the performance profile of your code.

You can manually segment your stack by using Box: Box<impl FnOnce> for the sync case and Box<impl Future> for the async case.

This is the reason Rust doesn't want to implicitly use segmented stacks. You can make a new stack cheaper with a linked list and separate allocations but that still imposes a surprisingly huge cost on every stack allocation; machine stack allocation is practically free (just increment the stack pointer) whereas on a segmented stack you have to at the least check if you need to allocate a new segment with a highly unpredictable check.

So... sticking the DST in a Box?

7 Likes

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.