Changing segmented stacks to contiguous stacks

[Keith Randall]

I've been thinking about how to change the stack implementation for Go routines.  I've been poking around with an implementation that keeps stacks contiguous and copies them in order to grow them.  I've written up a design doc and I'm interested in what people think about the idea, both whether it is a good idea at all, or any changes/improvements you might suggest.

[Brad Fitzpatrick]

Doc needs to be made public.

On Wed, May 15, 2013 at 1:27 PM, Keith Randall <k...@google.com> wrote:

I've been thinking about how to change the stack implementation for Go routines.  I've been poking around with an implementation that keeps stacks contiguous and copies them in order to grow them.  I've written up a design doc and I'm interested in what people think about the idea, both whether it is a good idea at all, or any changes/improvements you might suggest.

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

[Keith Randall]

Try this url: https://docs.google.com/document/d/1wAaf1rYoM4S4gtnPh0zOlGzWtrZFQ5suE8qr2sD8uWQ/pub

[Brad Fitzpatrick]

Latter URL works.  First one says:

"You are signed in as brad...@golang.org, but you don't have permission to access this published document. You may need to sign in as a different user."

I shared successfully from drive as my golang.org account the other day twice.  I tested in an incognito window.

[Aram Hăvărneanu]

Copying the whole stack is costly, the cost is variable and

unpredictable, and it's hard to recover the space later. I think

it's better if we have smaller stack segments, perhaps 512bytes or

so, and when we have to grow the stack we create a larger stack

segment and copy the latest stack segment into it doing the kind

of fixups mentioned in your document. That means that a tight loop

that causes a stack split will take the hit only once, after that

it will return in the larger stack segment and won't cross the line

anymore.

This method:

    o) wastes less space than the current implementation.

    o) is faster than both the current implementation (by avoiding

    allocating stag segments in loops) and your proposal (fewer

    things needs copying at a time).

    o) compared to your proposal, space is reclaimed automatically

    when returning yet another segment back.

    o) when you take a performance hit, that hit is constant and

    known.

[Keith Randall]

On Wed, May 15, 2013 at 3:10 PM, Aram Hăvărneanu <ar...@mgk.ro> wrote:

Copying the whole stack is costly, the cost is variable and

unpredictable,

 I don't think it is costly or variable, at least no more so than standard containers (e.g. slice append).  As long as you're growing exponentially, it's at most a constant cost per byte of stack.

and it's hard to recover the space later. I think

That I agree with.

 

it's better if we have smaller stack segments, perhaps 512bytes or

so, and when we have to grow the stack we create a larger stack

segment and copy the latest stack segment into it doing the kind

of fixups mentioned in your document. That means that a tight loop

that causes a stack split will take the hit only once, after that

it will return in the larger stack segment and won't cross the line

anymore.

This confuses me - it sounds exactly like what I am proposing.  When does a split happen in this scheme?

 

This method:

    o) wastes less space than the current implementation.

    o) is faster than both the current implementation (by avoiding

    allocating stag segments in loops) and your proposal (fewer

    things needs copying at a time).

    o) compared to your proposal, space is reclaimed automatically

    when returning yet another segment back.

    o) when you take a performance hit, that hit is constant and

    known.

[roger peppe]

As an adjunct to this change, it would be great if the
compiler could do static analysis of stack sizes so
that goroutines were created with an appropriate
size. This probably affects goroutines with small
stacks more than large ones, but could be advantageous
in both cases.

It would be great if a simple multiplexer didn't need the
usual 4K stack.

go func() {
for x := range in {
out <- msg{id, x}
}
}()

I think Russ has mentioned doing something like this,
but I don't know if it's a current plan.

[Keith Randall]

Yes, that would be nice.  I don't think anyone is signed up to do it at the moment.

BTW, I'm thinking about making the starting stack smaller as part of this change, maybe 1K.

[Russ Cox]

I think being able to start stacks tiny will make precise analysis unnecessary.

[Dmitry Vyukov]

Can you measure the effect on a more realistic program? E.g. an
important computation kernel made to trigger stack split in the loop,
but with inlining enabled. It would be useful to see what is the worst
case effect but with inlining and real work.

It's not obvious that this is a win-win solution. It may be better
than what we have now, or waste memory or has another set of corner
cases (e.g. short running goroutine that triggers split stack once).

I have 2 other solutions to consider.
The first is as simple as:
func runtime.RunWithStack(stackSize int, f func()) // executes f with
at least stackSize bytes stack segment
It is ugly. But it is similar to what we have for slice capacity, map
capacity, bufio buffer size, etc.

The second is to optimize what we have now. It's definitely not
particularly optimized yet.
I have a prototype of morestackfast16/lessstackfast16:
https://codereview.appspot.com/9187048/diff/2001/src/pkg/runtime/asm_amd64.s
It's just current machinery re-implemented in assembly, w/o
unnecessary cases (reflect) and w/o g0 stack switch.

You've reported:
segmented stacks:
no split: 1.25925147s
with split: 5.372118558s <- triggers hot split problem

contiguous stacks:
no split: 1.261624848s
with split: 1.262939769s

With this change it is:
no split: 1.252429208s
with split: 2.483917597s

Not that good as your numbers, but much better than what we have now.
That's why I am interested in a more realistic benchmark.

I have 2 other ideas on how to optimize it futher:
1. The main slowdown comes from memory accesses and data dependencies.
We can use SP to find current stack segment -- ((SP & ~0xfff) + 4024),
this has 0 memory loads instead of 2 loads for g->stackbase.
2. We may keep unused segments in the goorutine linked list (use it as
cache), such segments can be reclaimed when the goroutine blocks or
during GC. This saves some work, and we do not need to access m
(m->stackcache) at all during "fast" switching. So "fast" switching
enables when we already have an appropriate next stack segment in the
goroutine.
I have a prototype of these ideas:
https://codereview.appspot.com/9442043/diff/5001/src/pkg/runtime/asm_amd64.s
but was unable to make it significantly faster yet. There seems to be
some micro architecture penalties for such code (I don't know what
exactly, either messing with SP, or messing with JMP, or just too many
loads and stores).
The results for this change are:
no split: 1.252429208s
with split: 2.28179379s

[Russ Cox]

golang.org/issue/3787 might be worth reinvestigating with the copying stacks. The belief was always that it was a bad stack split moving around.

Russ

[minux]

On Fri, May 17, 2013 at 1:59 AM, Dmitry Vyukov <dvy...@google.com> wrote:

I have 2 other solutions to consider.

The first is as simple as:
func runtime.RunWithStack(stackSize int, f func())  // executes f with
at least stackSize bytes stack segment
It is ugly. But it is similar to what we have for slice capacity, map
capacity, bufio buffer size, etc.

i don't like this interface as it feels too low-level, and because it's difficult for

people to get good estimate of function stack usage (but for channel buffer,

bufio buffer size and slice capacity, one usually can estimate from the input

data)

besides, introducing interfaces like this sounds like bad excuse for not

optimizing the root cause.

[Dmitry Vyukov]

On Thu, May 16, 2013 at 10:15 PM, minux <minu...@gmail.com> wrote:
>> I have 2 other solutions to consider.
>> The first is as simple as:
>> func runtime.RunWithStack(stackSize int, f func()) // executes f with
>> at least stackSize bytes stack segment
>> It is ugly. But it is similar to what we have for slice capacity, map
>> capacity, bufio buffer size, etc.
>
> i don't like this interface as it feels too low-level, and because it's
> difficult for
> people to get good estimate of function stack usage (but for channel buffer,
> bufio buffer size and slice capacity, one usually can estimate from the
> input
> data)

Agree.

[Russ Cox]

On Thu, May 16, 2013 at 1:59 PM, Dmitry Vyukov <dvy...@google.com> wrote:

The first is as simple as:

func runtime.RunWithStack(stackSize int, f func())  // executes f with
at least stackSize bytes stack segment
It is ugly.

Not just to Dmitriy: please remember that performance is almost never a good enough reason to make things ugly. There's been too much of this going on recently. Find a better way.

Russ