[rust-dev] What of semi-automated segmented stacks ?

Niko Matsakis niko at alum.mit.edu
Fri Jan 31 13:54:10 PST 2014


One option that might make a lot of sense is having an API like this:

    start_extensible_stack(initial_size, || ...)
    consider_stack_switch(required, || ...)

The idea is that `start_extensible_stack` allocates a stack chunk of
size `initial_size` and runs the closure in
it. `consider_stack_switch` basically does what the old prelude did:
compare the bounds and jump if needed. If you failed to insert
`consider_stack_switch` at all the required place, you'd wind up with
stack overruns. Presumably some mechanism for detecting stack overrun
(e.g. guard pages) is still required.

Unlike the older system, which was intended for universal use, this
would be a power user's API. You get precise control over when to
switch and how much to grow the stack by. This could help avoid the
performance pitfalls we encountered when trying to find a "one size
fits all" heuristic for stack growth. For example, it'd be trivial to
create a system where you start out with a very small stack per
request but switch over to a large stack if the request proves complex
-- but perhaps you only switch once, since you don't want to grow
indefinitely. You should also be better able to avoid performance
pathologies where the stack switch occurs on a frequently traversed
call edge.

On the flip side, of course, it's not clear to me that the API is
really *usable* -- certainly static analysis could identify points of
arbitrary recursion where a call to `consider_stack_switch` may be
needed. One downside is the `start_extensible_stack` routine, since
there is already a start frame to start from. Maybe it's not needed,
and we can just always set the "end of stack" register, but not
necessarily read its contents. That'd be nicer.

Anyway, just thinking aloud here.


Niko


On Thu, Jan 30, 2014 at 06:27:27PM +0100, Matthieu Monrocq wrote:
> Hello,
> 
> Segmented stacks were ditched because of performance issues that were never
> fully resolved, especially when every opaque call (C, ...) required
> allocated a large stack up-front.
> 
> Still, there are platforms (FreeBSD) with small stacks where the idea of
> segmented tasks could ease development... so what if we let the developer
> ship in ?
> 
> 
> The idea of semi-automated segmented stacks would be:
> 
> - to expose to the user how many bytes worth of stack are remaining
> 
> - to let the user trigger a stack switch
> 
> 
> This system should keep the penalty close to null for those who do not
> care, and be relatively orthogonal to the rest of the implementation:
> 
> - how many bytes remaining carries little to no penalty: just a pointed
> substraction between the current stack pointer and the "end-of-stack"
> pointer (which can be set once and for all at thread start-up)
> 
> - the stack switch is voluntary, and can include a prelude on the new stack
> that automatically comes back to its parent so that most code should not
> care, no penalty in regular execution (without it)
> 
> - I foresee some potential implementation difficulty for the unwinder, did
> it ever work on segmented stacks ? Was it difficult/slow ? Does performance
> of unwind matter that much ?
> 
> 
> Work-around:
> 
> In the absence of segmented stacks, the user can only resolve to using
> another task to get a "free" stack. Unfortunately, because of the (great!)
> memory safety of Rust this other task cannot readily access its parent
> task's memory.
> 
> 
> I do not remember whether this idea was investigated when segmented tasks
> were removed. I thought it might be interesting to consider, although... it
> is probably useless for 1.0 anyway.
> 
> -- Matthieu

> _______________________________________________
> Rust-dev mailing list
> Rust-dev at mozilla.org
> https://mail.mozilla.org/listinfo/rust-dev



More information about the Rust-dev mailing list