Go: cmd/compile: combine append calls

[quasilyte]

// A)
xs = append(xs, v1)
xs = append(xs, v2)
// B)
xs = append(xs, v1, v2)

Currently, compiler does not rewrite A into B and generates 2 append sequences for A (or, more generally, N append sequences for N consecutive appends to the same slice).

Synthetic benchmarks show quite significant difference between these two forms.

package slices
import "testing"
func BenchmarkAppend(b *testing.B) {
    for i := 0; i < b.N; i++ {
        var xs []int
        xs = append(xs, i)
        xs = append(xs, 1)
        xs = append(xs, 2)
    }
}
func BenchmarkAppendOnce(b *testing.B) {
    for i := 0; i < b.N; i++ {
        var xs []int
        xs = append(xs, i, 1, 2)
    }
}

```
$ go test -v -benchmem -bench=.
goos: linux
goarch: amd64
BenchmarkAppend-8 10000000 164 ns/op 56 B/op 3 allocs/op
BenchmarkAppendOnce-8 20000000 61.7 ns/op 32 B/op 1 allocs/op

There are multiple spots inside Go sources that can use this kind of rewrite:

$GOROOT/src/net/http/socks_bundle.go:106:3: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/vet/asmdecl.go:425:4: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/vet/asmdecl.go:430:3: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/vet/asmdecl.go:434:3: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/vet/asmdecl.go:438:3: append-combine: can combine chain of 3 appends into one
$GOROOT/src/cmd/vet/asmdecl.go:443:3: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/vet/asmdecl.go:448:3: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/dist/test.go:605:3: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/dist/test.go:674:4: append-combine: can combine chain of 2 appends into one
$GOROOT/src/net/dnsclient.go:30:3: append-combine: can combine chain of 4 appends into one
$GOROOT/src/net/mac.go:21:3: append-combine: can combine chain of 2 appends into one
$GOROOT/src/net/interface_linux_test.go:19:2: append-combine: can combine chain of 2 appends into one
$GOROOT/src/net/interface_linux_test.go:44:2: append-combine: can combine chain of 2 appends into one
$GOROOT/src/strconv/quote.go:31:4: append-combine: can combine chain of 2 appends into one
$GOROOT/src/strconv/quote.go:54:3: append-combine: can combine chain of 2 appends into one
$GOROOT/src/strconv/quote.go:87:4: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/cgo/util.go:48:3: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/go/internal/envcmd/env.go:93:2: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/compile/internal/ssa/deadcode_test.go:146:4: append-combine: can combine chain of 2 appends into one
$GOROOT/src/archive/tar/writer_test.go:36:4: append-combine: can combine chain of 2 appends into one
$GOROOT/src/crypto/tls/handshake_server_test.go:515:2: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/link/internal/ld/dwarf.go:1397:3: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/link/internal/ld/lib.go:1208:2: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/link/internal/ld/lib.go:1164:3: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/link/internal/ld/lib.go:1312:3: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/nm/nm_test.go:223:3: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/nm/nm_test.go:226:4: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/nm/nm_test.go:229:4: append-combine: can combine chain of 2 appends into one
$GOROOT/src/crypto/x509/name_constraints_test.go:1728:2: append-combine: can combine chain of 2 appends into one
$GOROOT/src/crypto/x509/name_constraints_test.go:1711:3: append-combine: can combine chain of 6 appends into one
$GOROOT/src/cmd/compile/internal/gc/range.go:225:3: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/compile/internal/gc/select.go:338:2: append-combine: can combine chain of 3 appends into one
$GOROOT/src/cmd/compile/internal/gc/walk.go:3325:2: append-combine: can combine chain of 2 appends into one
$GOROOT/src/cmd/compile/internal/gc/inl_test.go:152:3: append-combine: can combine chain of 3 appends into one

Most of them are not performance-critical.

I've done some impact measurements for real code:

net/dnsclient.go
name old time/op new time/op delta
ReverseAddress-8 4.10µs ± 3% 3.94µs ± 1% -3.81% (p=0.000 n=10+9)

strconv/quote.go
name old time/op new time/op delta
AppendQuoteRune-8 85.5ns ± 0% 83.8ns ± 0% -1.92% (p=0.000 n=9+8)

Note that `AppendQuoteRune` needs to be modified in order to see difference because otherwise it does not execute path with appends:
```go
func BenchmarkAppendQuoteRune(b *testing.B) {
    for i := 0; i < b.N; i++ {
        benchQuoteRuneBuf = AppendQuoteRune(benchQuoteRuneBuf[:0], '\a')
        benchQuoteRuneBuf = AppendQuoteRune(benchQuoteRuneBuf[:0], '\'')
        benchQuoteRuneBuf = AppendQuoteRune(benchQuoteRuneBuf[:0], '\x00')
    }
}

The major problem I see is potential hit to things like line info and debugging experience (one append sequence instead of extected N). I also believe that slice expression should be "safe". Arguments may also require this property to avoid panic line info changes where evaluation may lead to it.

I would like to dig into that and provide optimization implementation, as soon as it gets approved.

I've sent CL117615 - net: combine append calls in reverseaddr as it seems beneficial there. In case this optimization is never implemented inside the compiler, we'll get that boost regardless.

[randall77]

Sounds fine if we can figure out a reasonable answer for what debugging info looks like.

[josharian]

Also might be a good candidate hint for a performance-oriented vet-like tool. cc @dominikh

[quasilyte]

Well.. https://go-critic.github.io/overview.html#appendCombine-ref
I hope this will not result in some kind of tool wars. :)

[quasilyte]

There are some differences in observable behavior that can be demonstrated by this example:
https://play.golang.org/p/LTV703gJTYR

This makes me think that this optimization is not valid for compiler.

Copying code here for convenience:

package main

import (
    "fmt"
)

func before() {
    xs := make([]int, 1, 1)
    xs[0] = 6
    ys := xs[:0]
    ys = append(ys, 1)
    ys = append(ys, 2)
    fmt.Println(xs, ys) // [1] [1 2]
}

func after() {
    xs := make([]int, 1, 1)
    xs[0] = 6
    ys := xs[:0]
    ys = append(ys, 1,2)    
    fmt.Println(xs, ys) // [6] [1 2]
}

func main() {
    before()
    after()
}

[quasilyte]

Example provided by @TocarIP

[randall77]

Punting to unplanned, too late for anything major in 1.12.