New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

cmd/compile: combine append calls #25828

Open
Quasilyte opened this Issue Jun 11, 2018 · 5 comments

Comments

Projects
None yet
3 participants
@Quasilyte
Contributor

Quasilyte commented Jun 11, 2018

// 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:

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 randall77 added this to the Go1.12 milestone Jun 11, 2018

@randall77

This comment has been minimized.

Contributor

randall77 commented Jun 11, 2018

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

@josharian

This comment has been minimized.

Contributor

josharian commented Jun 11, 2018

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

@Quasilyte

This comment has been minimized.

Contributor

Quasilyte commented Jun 11, 2018

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

@Quasilyte

This comment has been minimized.

Contributor

Quasilyte commented Jul 24, 2018

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

This comment has been minimized.

Contributor

Quasilyte commented Jul 24, 2018

Example provided by @TocarIP

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment