15
$\begingroup$

Segmented stacks are one method to enable the growth of execution stacks in multi-threaded paradigms at runtime, instead of having to statically pre-allocate a fixed-sized stack at compile time.

Some languages including Go and Rust at one point in their design considered using segmented stacks for their runtime concurrent stack management. However, they eventually sought other options, partially due to the problem of hot splits.

Hot splits refer to the constant allocation and deallocation of stack memory when a tight loop straddles an allocation boundary. However, it seems to me a way to mitigate the problem is to allocate stack memory as needed, but only deallocate when the stack pointer reaches the previous stack segment. As an example:

|-------| --> |-------| --> |-------|
                             ^SP    New segment just allocated    

|-------| --> |-------| --> |-------|
                     ^SP            New segment still maintained

|-------| --> |-------|
       ^SP                          New segment only now gets deallocated

While this doesn't resolve the issue of having to jump around in memory at stack boundaries, this does (at least on paper) seem to significantly mitigate the issue of hot swapping without too much extra bookkeeping. Am I missing something? What are some of the other problems with segmented stacks?

$\endgroup$

1 Answer 1

9
$\begingroup$

Even if the new segment is maintained, crossing that boundary in a tight loop can be expensive. The better solution is that when a new segment is allocated, a few frames are moved from the youngest existing segment into the new segment. Before the segment boundary can be crossed again, those frames have to finish their work. This trick is a way of introducing hysteresis into the boundary-crossing computation.

The best work I know of on segmented stacks and performance is described in the paper "Representing Control in the Presence of One-Shot Continuations" by Carl Bruggeman, Oscar Waddell, and Kent Dybvig. The predecessor paper on first-class continuations is also good. Regrettably, both papers omit a lot of detail.

$\endgroup$
1
  • 1
    $\begingroup$ Thank you for the information. These are exactly the kind of papers I was looking for. Moving some stack frames to the new segment seems like an interesting mitigation technique as well. It seems that regardless, some compile time analysis and heuristics are needed to make this option viable, which is likely why programming languages moved away from this model in favor of other solutions. $\endgroup$
    – WormholeX
    Commented May 22, 2023 at 17:25

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .