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

cmd/compile: append should be optmized as copy #57759

Closed
go101 opened this issue Jan 12, 2023 · 8 comments
Closed

cmd/compile: append should be optmized as copy #57759

go101 opened this issue Jan 12, 2023 · 8 comments
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. Performance
Milestone

Comments

@go101
Copy link

go101 commented Jan 12, 2023

What version of Go are you using (go version)?

$ go version
go version go1.20rc2 linux/amd64

Does this issue reproduce with the latest release?

Yes

What did you do?

package main

import "testing"

var m = 10000

var x = make([]byte, m)
var y = x

//go:noinline
func Copy(x, y []byte) {
	copy(x, y)
}

func Benchmark_copy(b *testing.B) {
	for i := 0; i < b.N; i++ {
		Copy(x, y)
	}
}

func Benchmark_append(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_ = append(x[:0], y...)
	}
}

What did you expect to see?

Similar CPU usages.

What did you see instead?

The CPU usages differ much.

Benchmark_copy-4     	350037631	         3.514 ns/op
Benchmark_append-4   	 9449574	       126.0 ns/op

It looks the copy function checks the addresses of the first elements of the two slice argument, but append doesn't. Maybe it should?

@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jan 12, 2023
@mvdan
Copy link
Member

mvdan commented Jan 12, 2023

cc @dsnet as I've seen him involved in similar threads like #55905 (comment). This issue could perhaps be a duplicate.

@randall77 randall77 added this to the Unplanned milestone Jan 12, 2023
@randall77
Copy link
Contributor

append could detect this, but it's not clear it is worth it. It would require a compare/branch on every append, but in the vast majority of cases it wouldn't trigger.

What is the situation in which this occurs in practice?

@go101
Copy link
Author

go101 commented Jan 12, 2023

Yes, such cases are rare. I haven't encountered such case in my serious Go projects.

Maybe, it is good to keep the difference between copy and append here, so that people can choose the best way for different situations.

So does this mean append is a bit faster than copy (if append doesn't need to allocate) for most cases?

@go101
Copy link
Author

go101 commented Jan 13, 2023

Thought it a little more. append will check capacity and copy will check addresses, which may make their performances on par for most no-allocations cases. This means copy is a better choice for no-allocations cases.

Please fell free to close this issue if nothing needs to be done.

@go101
Copy link
Author

go101 commented Jan 16, 2023

It looks append will also check memory overlapping, just as copy.
This is proved by the following program:

package main

import (
	"fmt"
)

func main() {
	var x = []int{0, 1, 2, 3, 4}
	_ = append(x[1:], x[:len(x)-1]...)
	fmt.Println(x) // [0 1 2 3 4]
	               // not [0 0 0 0 0]
}

That means append(dest, src) will execute

   dest = dest[:len(src)]
   srcStart, srcEnd := &src[0], &src[0] + ElemSize * len(src)
   destStart, destEnd := &dest[0], &des[0] + ElemSize * len(src)
   if srcStart < destStart && srcEnd > destEnd {
      ... // need some special handling
   } else {
      ... // copy by normal order
   }

So, I think adding a srcStart == destStart check will not make a big impact on performance, even if for most cases it is needless.

@go101
Copy link
Author

go101 commented Jan 16, 2023

Sorry, the proving example is corrected now.

@gopherbot
Copy link

Change https://go.dev/cl/533276 mentions this issue: slices: use copy instead of append in Delete

@gopherbot
Copy link

Change https://go.dev/cl/536255 mentions this issue: slices: avoid an unnecessary check in Replace

gopherbot pushed a commit that referenced this issue Oct 19, 2023
The current implementation of the builtin copy function will return early
when it is found that the addresses of the first elements of the two
slice arguments are identical, so it is unnecessarily to do this in user code.

See #57759 for details.

Change-Id: I7c101eee496923d7aa59f94720da6c84feb93af8
GitHub-Last-Rev: 4d6819f
GitHub-Pull-Request: #63617
Reviewed-on: https://go-review.googlesource.com/c/go/+/536255
Auto-Submit: Keith Randall <khr@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Keith Randall <khr@google.com>
yunginnanet pushed a commit to yunginnanet/go that referenced this issue Oct 20, 2023
The current implementation of the builtin copy function will return early
when it is found that the addresses of the first elements of the two
slice arguments are identical, so it is unnecessarily to do this in user code.

See golang#57759 for details.

Change-Id: I7c101eee496923d7aa59f94720da6c84feb93af8
GitHub-Last-Rev: 4d6819f
GitHub-Pull-Request: golang#63617
Reviewed-on: https://go-review.googlesource.com/c/go/+/536255
Auto-Submit: Keith Randall <khr@golang.org>
LUCI-TryBot-Result: Go LUCI <golang-scoped@luci-project-accounts.iam.gserviceaccount.com>
Reviewed-by: Keith Randall <khr@golang.org>
Reviewed-by: Ian Lance Taylor <iant@google.com>
Reviewed-by: Keith Randall <khr@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. Performance
Projects
None yet
Development

No branches or pull requests

4 participants