Repository: go
Issue: cmd/compile: slice update with self subslice - write barrier probably not needed (?)
Labels: Performance,compiler/runtime

Commit b8543397 (CL 98757) changes encoding/binary to use explicit offset instead of `buf = buf[1:]` idiom with the rationale that `buf = buf[1:]` is slice data pointer update which in turn is done with write barrier, while using `buf[offset]` explicitly does not need to update buf slice pointer and so does not need to issue GC write barrier. The commit cites significant speedup for encoding/binary under GOGC=1 and notes that While running make.bash, over 5% of all pointer writes come from encoding/binary doing struct reads.

It was then noted there that instead of explicitly using offset and avoiding `buf = buf[1:]` update idiom for performance reasons, it would be better to instead teach the compiler to know that slice updates with destination array pointer pointing to the same array's underlying object as of original slice, e.g. as in
`buf = buf[1:]` does not need write barrier at all.

The conversation there contains the rationale for current compiler behaviour but also brings questions and arguments for why it can be done. It was suggested to move the conversation to the issues, so here it goes.

--------

@josharian thinking out loud maybe it is better to instead teach the compiler to know that slice updates with destination array pointer pointing to the same array's underlying object as of original slice, e.g. as in

```go
buf = buf[1:]
```

does not need write barrier at all?

The rationale (to my limited write barriers understanding) is that it is whole allocated object that is shaded by write barrier:


```
//     writePointer(slot, ptr):
//         shade(*slot)
//         if current stack is grey:
//             shade(ptr)
//         *slot = ptr
...
// 1. shade(*slot) prevents a mutator from hiding an object by moving
// the sole pointer to it from the heap to its stack. If it attempts
// to unlink an object from the heap, this will shade it.
//
// 2. shade(ptr) prevents a mutator from hiding an object by moving
// the sole pointer to it from its stack into a black object in the
// heap. If it attempts to install the pointer into a black object,
// this will shade it.
```
(https://github.com/golang/go/blob/d7eb4901/src/runtime/mbarrier.go#L21)

```go
func shade(b uintptr) {
        if obj, span, objIndex := findObject(b, 0, 0); obj != 0 {
        ...
```
(https://github.com/golang/go/blob/d7eb4901/src/runtime/mgcmark.go#L1211)

```go
func findObject(p, refBase, refOff uintptr) (base uintptr, s *mspan, objIndex uintptr) {
        s = spanOf(p)
        ...
```
(https://github.com/golang/go/blob/d7eb4901/src/runtime/mbitmap.go#L354)

and so for `buf = buf[1:]` the slice, either before or after the update, will be pointing to inside the same allocated object -> thus the mutator for sure won't hide the allocated object from GC and so there is no need to shade it with such updates.

Doing so in the compiler will fix the performance issue this patch solves, as well as automatically remove write barriers in other, probably many, places thus helping not only speed but also code size (#6853).

I appologize if there is something trivial preventing doing this, that I missed.

Kirill

/cc @aclements 

--------

@aclements says:
The danger here is subtle. We haven't done this because the update to buf could be racy and if we did this that race could break GC. Specifically, if one goroutine executes `buf = buf[1:]` without a write barrier while another executes `buf = x` with a write barrier, it's possible for the final value of `buf` to continue pointing to the original buf allocation, but for the garbage collector to think it points to the `x` allocation and free the original `buf` allocation.

Of course, racy Go programs are undefined, but right now the garbage collector is immune to these sorts of non-type-safety-breaking "benign" races (this is obviously a somewhat fuzzy argument, since races let you break type safety and that lets you break memory safety, and saying anything formal about "benign" races is notoriously impossible so what I'm saying is probably not true anyway, but we try :)

--------

@dgryski says:
@aclements It would be interesting to see the effect such an update would have on code size and performance to know how much we're leaving on the table with this safety check on.

--------

me says:
@aclements thanks for explaining. Am I right that with write-barriers enabled for both racy buf updates, the mechanism that prevents GC from deallocating wrong object is that in the current GC written `ptr` is always shaded too (https://github.com/golang/go/blob/go1.10-1-g678dede7bc/src/runtime/mbarrier.go#L162 (go1.10), https://github.com/golang/go/blob/0add9a4dcf/src/runtime/mwbbuf.go#L226 (tip)) ?



By the way the thread that performs `buf = x` with write barrier will always do `shade(*slot)`. If there is `buf = buf[1:]` racing with `buf = x`, even if the former does not use write barrier, the `shade(*slot)` of `buf = x` thread will shade original `buf` object in _any_ case (it either sees `buf` or `buf+1` as `*slot` but they both actually lead to the same allocated object). If so, since `shade` actually greys an object and grey objects never become white - only eventually black, we can say that original `buf` underlying object will stay alive - not deallocated, and so it is safe to do `buf = buf[1:]` without write barrier.

But this goes contrary to what you say, and so there is probably some mistake on my side. Could you please explain where the above logic fails?

I'm GC newbie so please forgive me if I miss something well-known.

--------

@josharian says:
@navytux would you mind opening a new issue and migrating this (interesting) discussion there? We tend to try to keep all conversation on CLs and issues. Thanks!