runtime: >100ms mark termination times

[aclements]

The program posted in https://groups.google.com/d/msg/golang-dev/_qY3IugLlAc/5ZIFjYHTHUwJ experiences very long mark termination times:

$ GODEBUG=gctrace=1 goscheme test.scm
gc #1 @0.240s 37%: 0+37+18+9+43 ms clock, 0+37+0+0/9/0+43 ms cpu, 4->5->2 MB, 4 MB goal, 1 P
gc #2 @0.514s 48%: 0+69+88+14+73 ms clock, 0+69+0+0/14/0+73 ms cpu, 4->5->3 MB, 4 MB goal, 1 P
gc #3 @0.756s 59%: 0+88+12+19+97 ms clock, 0+88+0+0/19/0+97 ms cpu, 4->6->4 MB, 5 MB goal, 1 P
gc #4 @1.107s 66%: 0+111+14+60+144 ms clock, 0+111+0+9/20/0+144 ms cpu, 5->8->6 MB, 7 MB goal, 1 P
gc #5 @1.664s 65%: 0+148+13+60+160 ms clock, 0+148+0+14/20/0+160 ms cpu, 6->10->7 MB, 8 MB goal, 1 P
gc #6 @2.166s 70%: 0+188+12+60+205 ms clock, 0+188+0+23/20/0+205 ms cpu, 7->12->9 MB, 8 MB goal, 1 P
gc #7 @2.812s 73%: 0+239+14+80+258 ms clock, 0+239+0+35/20/0+258 ms cpu, 14->16->12 MB, 15 MB goal, 1 P
gc #8 @3.934s 70%: 0+316+11+82+330 ms clock, 0+316+0+47/21/0+330 ms cpu, 19->20->14 MB, 19 MB goal, 1 P

It is also ~2x slower than it was on Go 1.4, which may be related.

@RLH

[aclements]

It appears we're entering mark termination when there's still quite a bit of work on the work queues. Curiously, the work isn't trapped in the per-P work cache (which was what I originally suspected) because there's only one P and hence only one background mark worker, which disposes its per-P cache when it ends the concurrent mark phase. Rather, it's on the global work list.

entering mark termination:
P 0 cache => nil wbuf
full wbuf list: 24+24+24+24+24+24+24+24+24+24+24+24=288
partial wbuf list: 10=10
gc #14 @11.172s 69%: 0+578+13+120+595 ms clock, 0+578+0+74/37/0+595 ms cpu, 16->87->37 MB, 16 MB goal, 1 P

[aclements]

The pending work isn't the problem. (It's almost certainly all recent allocations and write barriers for publishing these recent allocations, which means the pending pointers have almost no depth. That is, there's no choke-point in the work queue, so while there is pending work, it will be scanned in almost no time during mark termination.)

The problem is that this program has a G with a ~70MB stack, which takes >150ms to scan. We see this cost both during the concurrent scan phase and during the re-scan in mark termination (which is why the two durations closely align in each cycle). This probably also explains the 2x slowdown compared to 1.4: this program spends most of its time in GC, and each GC cycle is doing roughly twice as much as it did in 1.4 because of the stack re-scan.

I'm going to try implementing stack barriers to address this. While this example is just a toy program, it's easy to imagine that there are real programs that have large stacks like this and right now we can't deliver on our low-latency promise when active goroutines have large stacks. Assuming only the top of the stack changes during the concurrent GC phases, this should drastically reduce the stack re-scan time during mark termination.

[minux]

I don't think we can assume that only top of stack changes (it might be
true today due to deficiencies in escape analysis).

For example, the following contrived program can make the stack grow
arbitrarily large, yet the topmost frame can write to slot in the bottom
most frame.

package main

func F(x **int, i int) {
if i == 0 {
*x = &i
return
}
F(x, i-1)
}

func main() {
var x *int
F(&x, 10000)
}

And -gcflags -m confirms that x in main is allocated on stack, so this
problem is not theoretical.
$ go build -gcflags -m stk.go

command-line-arguments

./stk.go:3: moved to heap: i
./stk.go:5: &i escapes to heap
./stk.go:3: F x does not escape
./stk.go:13: main &x does not escape

[aclements]

If you have multi-megabyte stacks and you've gone to the trouble of threading a stack pointer through 50 megabytes worth of stack, then, well, there's only so much we can do to reduce the stack scan cost. Don't do that. But otherwise, stack barriers will dramatically reduce the cost of scanning large stacks.

[minux]

I guess my question is why do we need to treat stacks separately and rescan them in the mark termination step? Writes to slots in stack still have writer barriers, so why are they any different from normal heap objects? Surely I'm missing something, so thanks for the explanations in advance.

[aclements]

Writes to stack slots do not have write barriers. That's why they need to be rescanned.

[randall77]

Only writes to the current frame might be missing write barriers. Writes to the non-current frame still have write barriers (because the compiler can't assume incoming pointer arguments are to the stack).
I'm not sure that helps any, but worth considering.

[minux]

ahh, i see. thanks. I was puzzled by my example program where write to *x has write barrier because the compiler doesn't know whether it's stack slot or heap slot. if the huge stack is not just a single frame, then i think we can be sure that writes to bottom stack slots are using writer barriers, so perhaps we do have a way to know if we need to scan the whole stack or not during mark termination.

[minux]

Yeah, I also think that we only need to scan the most current frame in mark termination. This should fix the problem nicely (unless the user code has a huge frame on the top, but then we can't do anything about it unless we add write barriers for stack writes).

[aclements]

You still need to re-scan all of the frames that were created since the concurrent scan. Any of those frames can still contain a pointer to a white heap object. The stack barriers I'm implementing will tell the GC which set of frames have been created since the first scan of the stack and hence need to be rescanned.

The fact that writes to up-pointers generate write barriers may simplify things, though. I was thinking I could only install stack barriers at frames where there are no pointers to higher frames (which is easy to compute, but does restrict where stack barriers can be installed, especially in examples like minux's). But if there are write barriers for these (and we don't simply ignore those write barriers like we do now), then I could install stack barriers wherever I want and use the write barrier to change the watermark if there's a write to a higher frame via a pointer.

[aclements]

Actually, the fact that we generate write barriers for writes to up-pointers is incredibly useful. I was wrong that we ignore these write barriers: the slot may be in the stack, but if it's a write barrier we care about, the pointer will point to the heap and we'll grey the object. This is exactly what we need to handle up-pointers. Hence, we can put stack barriers between any two frames on the stack without worrying about up-pointers.

[RLH]

I think we are on the same page but just to make sure. A stack barrier
notes a location on the stack where all frames older
than the current frame has been scanned.

1. Mark Termination needs to scan any stack frames created since the last
   time the stack was scanned.
2. The write barrier is responsible for greying any objects written into a
   slot older than the stack frame barrier.
3. Greying objects written into slots younger than the stack barrier is not
   needed for correctness but may help performance/scalability.
   Just checking....

On Tue, May 19, 2015 at 11:39 AM, Austin Clements notifications@github.com
wrote:

Actually, the fact that we generate write barriers for writes to
up-pointers is incredibly useful. I was wrong that we ignore these write
barriers: the slot may be in the stack, but if it's a write barrier we care
about, the pointer will point to the heap and we'll grey the object. This
is exactly what we need to handle up-pointers. Hence, we can put stack
barriers between any two frames on the stack without worrying about
up-pointers.

—
Reply to this email directly or view it on GitHub
#10898 (comment).

[aclements]

Yes, it sounds like we're on the same page.

On Tue, May 19, 2015 at 12:02 PM, Richard L. Hudson <
notifications@github.com> wrote:

I think we are on the same page but just to make sure. A stack barrier
notes a location on the stack where all frames older
than the current frame has been scanned.

... where all frames older than that location were scanned during
concurrent scan. (Just being precise.)

1. Mark Termination needs to scan any stack frames created since the last

time the stack was scanned.
2) The write barrier is responsible for greying any objects written into a
slot older than the stack frame barrier.
3) Greying objects written into slots younger than the stack barrier is not
needed for correctness but may help performance/scalability.
Just checking....

[gopherbot]

CL https://golang.org/cl/10314 mentions this issue.

[gopherbot]

CL https://golang.org/cl/13614 mentions this issue.