Skip to content
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

Jump to bottom

cmd/compile: combine append calls #25828

Open
quasilyte opened this issue Jun 11, 2018 · 6 comments
Open

cmd/compile: combine append calls #25828

quasilyte opened this issue Jun 11, 2018 · 6 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. Performance
Milestone
Unplanned

Comments

@quasilyte
Copy link
Contributor

quasilyte commented Jun 11, 2018 •
edited 

// 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
Copy link
Contributor

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

@josharian
Copy link
Contributor

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

@quasilyte
Copy link
Contributor Author

quasilyte commented Jun 11, 2018 •
edited

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

@quasilyte
Copy link
Contributor Author

quasilyte commented Jul 24, 2018 •
edited

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
Copy link
Contributor Author

Example provided by @TocarIP

@randall77
Copy link
Contributor

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

@randall77 randall77 modified the milestones: Go1.12, Unplanned Dec 12, 2018
@rogpeppe rogpeppe mentioned this issue Feb 26, 2021
Open
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. Performance
Projects
None yet
Milestone
Unplanned
Development

No branches or pull requests
4 participants
@josharian @quasilyte @randall77 @gopherbot