Stack growing is inefficient
350 views
Skip to first unread message
tapi...@gmail.com
Jun 30, 2021, 3:25:59 AM6/30/21
to golang-nuts
It looks this line https://github.com/golang/go/blob/master/src/runtime/stack.go#L1078 never gets executed.
An example:
package main
const N = 512 * 1024 * 1024 // 500M
var v byte = 123
func main() {
var s = []byte{N: 0}
for i := range s { s[i] = v }
println(s[v])
}
I added a println line: println (oldsize, "=>", newsize)
and got the following output:
2048 => 4096
4096 => 8192
8192 => 16384
16384 => 32768
32768 => 65536
65536 => 131072
131072 => 262144
262144 => 524288
524288 => 1048576
1048576 => 2097152
2097152 => 4194304
4194304 => 8388608
8388608 => 16777216
16777216 => 33554432
33554432 => 67108864
67108864 => 134217728
134217728 => 268435456
268435456 => 536870912
536870912 => 1073741824
runtime: goroutine stack exceeds 1000000000-byte limit
runtime: sp=0xc0400dff70 stack=[0xc0200e0000, 0xc0400e0000]
fatal error: stack overflow
tapi...@gmail.com
Jun 30, 2021, 3:38:22 AM6/30/21
to golang-nuts
It looks all stacks start from 2048 bytes,
even if gc has estimated the start function of a goroutine will use much larger stack.
Why not initialize the stack with a large size as needed?
For example:
package main
const N = 300 * 1024 * 1024
const N = 300 * 1024 * 1024
var v byte = 123
func f(c chan struct{}) {
var s = []byte{N: 0}
for i := range s { s[i] = v }
println(s[v])
close(c)
}
func main() {
c := make(chan struct{})
go f(c)
<-c
}
}
func main() {
c := make(chan struct{})
go f(c)
<-c
}
-gcflags=-S shows the function f will use 314572840 bytes on stack:
TEXT "".f(SB), ABIInternal, $314572840-8
But the stack of the new goroutine still starts from 2048 bytes.
Brian Candler
Jun 30, 2021, 5:08:30 AM6/30/21
to golang-nuts
On Wednesday, 30 June 2021 at 08:25:59 UTC+1 tapi...@gmail.com wrote:
It looks this line https://github.com/golang/go/blob/master/src/runtime/stack.go#L1078 never gets executed.
Can you quote the line you're referring to? Line numbers can shift up and down as commits are made to the master branch. Right now, L1078 is a blank line.
Axel Wagner
Jun 30, 2021, 6:41:11 AM6/30/21
to golang-nuts
and/or link to a specific commit (press y in the github UI to get redirected to the specific commit you are looking at).
--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/90b6fe58-c810-4be1-b5d6-01cea9c0cc2an%40googlegroups.com.
tapi...@gmail.com
Jun 30, 2021, 9:21:21 AM6/30/21
to golang-nuts
Sorry, I post the wrong anchor. It is line 1068: https://github.com/golang/go/blob/d19a53338fa6272b4fe9c39d66812a79e1464cd2/src/runtime/stack.go#L1068
Brian Candler
Jun 30, 2021, 11:56:45 AM6/30/21
to golang-nuts
So I think what you're asking is, "under what scenario does the code in L1066-1069 get run?" - is that right?
tapi...@gmail.com
Jun 30, 2021, 8:34:27 PM6/30/21
to golang-nuts
On Wednesday, June 30, 2021 at 11:56:45 AM UTC-4 Brian Candler wrote:
So I think what you're asking is, "under what scenario does the code in L1066-1069 get run?" - is that right?
Almost true.
Whether or not it should run, growing the stack from 2048 to 512M in 18+ steps looks not right.
Axel Wagner
Jun 30, 2021, 8:46:19 PM6/30/21
to tapi...@gmail.com, golang-nuts
On Wednesday, June 30, 2021 at 11:56:45 AM UTC-4 Brian Candler wrote:So I think what you're asking is, "under what scenario does the code in L1066-1069 get run?" - is that right?Almost true.Whether or not it should run, growing the stack from 2048 to 512M in 18+ steps looks not right.
Why? 2048 • 2^18 = 2^11 • 2^18 = 2^29 = 536870912.
Seems like exactly the expected result.
On Wednesday, 30 June 2021 at 14:21:21 UTC+1 tapi...@gmail.com wrote:Sorry, I post the wrong anchor. It is line 1068: https://github.com/golang/go/blob/d19a53338fa6272b4fe9c39d66812a79e1464cd2/src/runtime/stack.go#L1068On Wednesday, June 30, 2021 at 5:08:30 AM UTC-4 Brian Candler wrote:On Wednesday, 30 June 2021 at 08:25:59 UTC+1 tapi...@gmail.com wrote:It looks this line https://github.com/golang/go/blob/master/src/runtime/stack.go#L1078 never gets executed.Can you quote the line you're referring to? Line numbers can shift up and down as commits are made to the master branch. Right now, L1078 is a blank line.
--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/5fab5a6e-5dd5-4df2-8b31-4a51aa825f92n%40googlegroups.com.
tapi...@gmail.com
Jun 30, 2021, 9:03:37 PM6/30/21
to golang-nuts
On Wednesday, June 30, 2021 at 8:46:19 PM UTC-4 axel.wa...@googlemail.com wrote:
On Wednesday, June 30, 2021 at 11:56:45 AM UTC-4 Brian Candler wrote:So I think what you're asking is, "under what scenario does the code in L1066-1069 get run?" - is that right?Almost true.Whether or not it should run, growing the stack from 2048 to 512M in 18+ steps looks not right.Why? 2048 • 2^18 = 2^11 • 2^18 = 2^29 = 536870912.Seems like exactly the expected result.
It looks each step calls copystack once.
Isn't one step more efficient?
Axel Wagner
Jul 1, 2021, 2:23:45 AM7/1/21
to tapi...@gmail.com, golang-nuts
Okay, *now* I get what you are trying to say. I agree that it seems inefficient to call it more than once, which is why the code tries to optimize for that. I don't know why that optimization doesn't trigger in your case - you might want to try and investigate that. There might be a good reason why it doesn't (for example, I'll note that your code might be using the system stack, which, AIUI, is special).
As always, if you are experiencing a real problem due to this, you might want to open an issue.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/a06d022b-06c2-4379-b33b-56886ebaf1dbn%40googlegroups.com.
Volker Dobler
Jul 1, 2021, 4:13:40 AM7/1/21
to golang-nuts
Note that the compiler should generate efficient code for
common, typical, real-world code. Optimising the compiler
to generate the most efficient code for pathological code
can be a waste of time, both for the compiler writers and
for the users waiting longer for their "normal" code to be
compiled. Nevertheless the compiler should emit "decent"
code for pathological cases. The quadratic stack growth
seems decent to me.
V.
Axel Wagner
Jul 1, 2021, 4:27:10 AM7/1/21
to Volker Dobler, golang-nuts
On Thu, Jul 1, 2021, 10:14 Volker Dobler <dr.volke...@gmail.com> wrote:
The quadratic stack growthseems decent to me.
Nit: Depending on what we are talking about the growth is either exponential (it's doubled on every growth operation, so the size grows exponentially) or linear (the cost to grow the stack to a given size is proportional to that size). There is no quadratic growth either way.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/d15c19c1-6844-4454-91f5-e21add1bf1fan%40googlegroups.com.
tapi...@gmail.com
Jul 1, 2021, 8:34:25 AM7/1/21
to golang-nuts
It is not rare a function will use 10M+ stack.
Jan Mercl
Jul 1, 2021, 8:42:41 AM7/1/21
to tapi...@gmail.com, golang-nuts
On Thu, Jul 1, 2021 at 2:34 PM tapi...@gmail.com <tapi...@gmail.com> wrote:
> It is not rare a function will use 10M+ stack.
What's the source of this claim? If it's not rare, it should be easy
> It is not rare a function will use 10M+ stack.
to find an example in the stdlib, I guess. Do you know of one?
Note that stacks of such size, if common in the wild, would
significantly limit the number of goroutines a process can handle.
tapi...@gmail.com
Jul 1, 2021, 9:22:57 AM7/1/21
to golang-nuts
Firstly, the current gc runtime implementation allows declare 10M arrays on stack.
So I anticipate that some user code will make use of this threshold.
Secondly, when I built the Go toolchain, I found there are many 32768 stack uses.
Even for 32768, 5 copystack operations are needed.
I have just studied the code a little deeper, and I confidently think line 1067 should be
for newsize-(gp.stack.hi - gp.sched.sp) < max+_StackGuard
Instead.
With this change, the time needed to build the toolchain is reduced to 2m40.123s (from 3m3.897s).
tapi...@gmail.com
Jul 1, 2021, 10:26:21 AM7/1/21
to golang-nuts
I tried to find a way to initialize the size of the stack of a new created goroutine in advance to avoid several stack copies.
Before this fix, the efficiencies of the two new goroutines are almost the same.
After the fix, the second goroutine uses much less time than the first one.
package main
import "fmt"
import "time"
const N = 1024 * 1024
var n byte = 123
func f(v [N]byte, n int) {
if n > 0 {
f(v, n-1)
}
}
func main() {
var c = make(chan time.Duration, 1)
go func() {
start := time.Now()
f([N]byte{}, 32)
c <- time.Since(start)
}()
fmt.Println(<-c)
go func() {
start := time.Now()
if n == 0 {
var a, b, c, d, e, f, g [N*10]byte
n = a[n] + b[n] + c[n] + d[n] + e[n] + f[n] + g[n]
}
f([N]byte{}, 32)
c <- time.Since(start)
}()
fmt.Println(<-c)
}
import "fmt"
import "time"
const N = 1024 * 1024
var n byte = 123
func f(v [N]byte, n int) {
if n > 0 {
f(v, n-1)
}
}
func main() {
var c = make(chan time.Duration, 1)
go func() {
start := time.Now()
f([N]byte{}, 32)
c <- time.Since(start)
}()
fmt.Println(<-c)
go func() {
start := time.Now()
if n == 0 {
var a, b, c, d, e, f, g [N*10]byte
n = a[n] + b[n] + c[n] + d[n] + e[n] + f[n] + g[n]
}
f([N]byte{}, 32)
c <- time.Since(start)
}()
fmt.Println(<-c)
}
Robert Engels
Jul 1, 2021, 10:46:50 AM7/1/21
to tapi...@gmail.com, golang-nuts
If you are doing “anything” which such large objects - doesn’t that dwarf the time to increase the stack?
On Jul 1, 2021, at 9:28 AM, tapi...@gmail.com <tapi...@gmail.com> wrote:
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/42aabf7f-7aa5-43f9-915b-f49f41f8856fn%40googlegroups.com.
Axel Wagner
Jul 1, 2021, 11:00:27 AM7/1/21
to tapi...@gmail.com, golang-nuts
It is not rare a function will use 10M+ stack.
FWIW, it being rare is one side of the equation. The other side is how large the overhead is - and ISTM that overhead is ~2x. That's not nothing, but it's also not extreme, for something that takes very little time.
The other thing, of course, is that *there is code* to avoid that overhead - it just isn't triggered by your example, for some reason (as I said, I could imagine it has something to do with running on the system stack). It's not unreasonable to assume that *in general*, a function using a 10M+ will use the more efficient growth path. So that even if it's not uncommon to use a large stack, it *is* uncommon for that to be a problem.
I genuinely don't know. For that, I would have to know *why* your example isn't more efficient. I don't care enough to find out. But it might be completely reasonable behavior.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/9e869b98-f3e0-4bfd-8a24-56c9a8dea8a4n%40googlegroups.com.
Axel Wagner
Jul 1, 2021, 11:21:45 AM7/1/21
to tapi...@gmail.com, aus...@google.com, golang-nuts
+Austin Clements, who introduced the check in its current form.
--
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.
To view this discussion on the web visit https://groups.google.com/d/msgid/golang-nuts/aa2b50ca-209a-4f78-b5e4-5a0399c07231n%40googlegroups.com.
tapi...@gmail.com
Jul 1, 2021, 11:24:44 AM7/1/21
to golang-nuts
tapi...@gmail.com
Jul 1, 2021, 11:28:16 AM7/1/21
to golang-nuts
On Thursday, July 1, 2021 at 10:46:50 AM UTC-4 ren...@ix.netcom.com wrote:
If you are doing “anything” which such large objects - doesn’t that dwarf the time to increase the stack?
Yes, the unreachable code in the 2nd goroutine dwarts the stack grow time much.
Reply all
Reply to author
Forward
0 new messages