Segmented stack mechanism

[yao shucai]

I am doing research on segmented stack mechanisms, and in addition to academic papers, I am surveying whether segmented stack mechanism is still useful on 64-bit machines. On 64 bit machines, why  they don’t just use a big enough stack, for example, 1GB or even larger?  Are segmented stacks only useful for 32 bit machines?  Are there other reasons for segmented stacks on 64 bit machines?

Any response is appreciated. 
Thanks, Shucai

[Ian Taylor]

On Thu, Oct 16, 2014 at 12:49 PM, yao shucai <yao20...@gmail.com> wrote:
>
> I am doing research on segmented stack mechanisms, and in addition to
> academic papers, I am surveying whether segmented stack mechanism is still
> useful on 64-bit machines. On 64 bit machines, why they don’t just use a
> big enough stack, for example, 1GB or even larger? Are segmented stacks
> only useful for 32 bit machines? Are there other reasons for segmented
> stacks on 64 bit machines?

Since goroutine stacks come from the heap so that they can be garbage
collected when the goroutine exits, reserving large amounts of address
space, while cheap, is not free. When you're running a million
goroutines, using up a million gigabytes of your heap for no real
purpose is definitely not free. Though I suppose that if stacks never
grow then stacks would not need to be in the heap, which would make it
somewhat cheaper.

Note that in Go 1.4 stacks are no longer segmented. Instead they are
copied when they need to grow, and the garbage collector will consider
shrinking them if a large stack is no longer being used.

Ian

[Dmitry Vyukov]

On Intel64 architecture virtual address space is 47 bits for
user-space applications. This means that you can have at most 128K 1GB
stacks. I've seen Go programs with 150K goroutines, and heard about
500K. These programs won't be able to work with your approach.

> --
> You received this message because you are subscribed to the Google Groups
> "golang-nuts" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to golang-nuts...@googlegroups.com.
> For more options, visit https://groups.google.com/d/optout.

[Brendan Tracey]

I've written Go programs where I was lazy and instead of doing a dispatcher/worker model I just said

for i := 0; i < 1e6; i++{
     go cpuBoundTask()
}

Overall the scheduling took maybe 1% of the total computation time

[Eduard Castany]

And if you are not lazy you only use 2*NumCPU goroutines?

[tomwilde]

On Thursday, October 16, 2014 10:03:57 PM UTC+2, Ian Lance Taylor wrote:

Note that in Go 1.4 stacks are no longer segmented.

I think that was supposed to read "1.3", not "1.4". 

OP: See here for a good article I just found about this topic: http://agis.io/2014/03/25/contiguous-stacks-in-go.html

[Dmitry Vyukov]

In Go1.3 uses both growable stacks and segmented stacks (individual
segments can grow). Go1.4 uses only growable stacks, every goroutine
has one and only stack segment.

[tomwilde]

On Friday, October 17, 2014 12:54:24 PM UTC+2, Dmitry Vyukov wrote:

In Go1.3 uses both growable stacks and segmented stacks (individual
segments can grow). Go1.4 uses only growable stacks, every goroutine
has one and only stack segment.

 

Thanks for the info! May I hijack the thread and ask why? I'm curious.

[Dmitry Vyukov]

Continous stacks avoid the so called "hot split" problem, when you
have a stack split inside of a hot loop. The hot split can make
execution up to 10 times slower. With continous stacks the stack will
just grow on the first iteration, the rest will be executed w/o any
penalty.

[Ian Taylor]

Which why are you asking?

It seems to us that growable stacks are better because they avoid hot
spots when a stack split occurs in a loop.

In Go 1.3 we did not have fully growable stacks because growable
stacks require precise knowledge of whether every pointer on the stack
is a pointer or not. Without that knowledge you might mess up the
stack if there is a pointer into the stack. In 1.3 we didn't have
that knowledge, in 1.4 we do.

Ian

[tomwilde]

On Friday, October 17, 2014 2:41:16 PM UTC+2, Ian Lance Taylor wrote:

Which why are you asking?

Sorry I was unclear, I meant why 1.3 uses a mixed (segmented/growable) approach.

 

In Go 1.3 we did not have fully growable stacks because growable
stacks require precise knowledge of whether every pointer on the stack
is a pointer or not.

I thought that the GC now could precisely identify any pointer. Coincidentally [1] I was just wondering how that worked.

Does this mean that the information the GC possesses over pointers is not available to the stack-managing mechanism?

[1] http://stackoverflow.com/questions/26422896/how-does-gos-precise-gc-work

[Ian Taylor]

On Fri, Oct 17, 2014 at 5:53 AM, tomwilde <sedevel...@gmail.com> wrote:
> On Friday, October 17, 2014 2:41:16 PM UTC+2, Ian Lance Taylor wrote:
>>
>> Which why are you asking?
>
>
> Sorry I was unclear, I meant why 1.3 uses a mixed (segmented/growable)
> approach.
>
>>
>> In Go 1.3 we did not have fully growable stacks because growable
>> stacks require precise knowledge of whether every pointer on the stack
>> is a pointer or not.
>
>
> I thought that the GC now could precisely identify any pointer.
> Coincidentally [1] I was just wondering how that worked.
>
> Does this mean that the information the GC possesses over pointers is not
> available to the stack-managing mechanism?

No.

In 1.3 the GC did not have precise information for all pointers on the
call stack. It had most of that information, but not all of it.
Specifically, it did not have precise information for pointers on the
stack of runtime functions written in C. In 1.3 the C call stack was
handled conservatively, which works for GC but does not work for stack
copying.

In 1.4 the GC does have precise information for all pointers into the
Go heap.

Ian