Hacker News Reader

Comment by jpollock | Hacker News Reader

The hot split problem is an example of a poor grow/shrink algorithm, and the contiguous stack would exhibit the same behaviour if the growth and shrink thresholds are the same.

How about avoiding hot split by changing the deallocation algorithm to allow empty blocks and see what happens?

View on HN

> The hot split problem is an example of a poor grow/shrink algorithm

Not really. With segmented stacks, when you hit the end of a stack, you must (1) allocate a new segment to extend the stack and (2) copy the current function frame to the new segment and resume execution. Then, when the function returns, you have to (3) deallocate the new segment and shrink the stack, and (4) resume execution of the last function frame on the previous stack segment.

Now, steps (1) and (3) are optional, but steps (2) and (4) are not, and incur a significant overhead (compared with non-segmented, contiguous stack, e.g. C stack).

You could add step (5) recognize that you have a hot split and amend step #2 to copy all of the hot frames to the new segment.

Their point is that if you have done something wrong if you have to dynamically turn on profiling to keep the stack from catching on fire.

That's a possible solution, but it requires that stack is relocatable (i.e. that you can find and rewrite all pointers to data on the stack), which is a significant complication with regards to a segmented stacks implementation. If you have a relocatable stack, you might as well use copy-the-whole-stack strategy with continuous stacks.

Segmented stacks are better even if you have a relocatable stack. GHC switched from monolithic copy-the-whole-thing-to-grow-it to segmented stacks a while ago, and it was a big win. Not just because we waste less space, but because the GC knows when individual stack segments are dirty so that it doesn't need to traverse the whole stack. To avoid the thrashing issue we copy the top 1KB of the previous stack chunk into the new stack chunk when we allocate a new chunk.

The idea is to leave the growing to the MMU. And a contiguous stack does not have to shrink immediately when its size goes down, whereas a segmented stack does (or at least it has to do something that causes it to set its stack pointer back to the initial smaller stack segment).

Still there is a problem with finite virtual address space (though not so significant on 64-bit architectures).

Reply on news.ycombinator.com