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: optimize slice copy via make+copy #26252

Closed
ghost opened this issue Jul 6, 2018 · 9 comments
Closed

cmd/compile: optimize slice copy via make+copy #26252

ghost opened this issue Jul 6, 2018 · 9 comments

Comments

@ghost
Copy link

ghost commented Jul 6, 2018

go version devel +b0155e3424 Fri Jul 6 14:45:29 2018 +0000 linux/amd64

Two different slice copying techniques are mentioned on the Slice Tricks wiki page:

  • b = make([]T, len(a))
    copy(b, a)
    
  • b = append([]T(nil), a...)
    

Benchmarking the two:

package bin

import "testing"
import "bytes"

var src = bytes.Repeat([]byte("golang"), 1024*10)

func BenchmarkAppend(b *testing.B) {
	for i := 0; i < b.N; i++ {
		_ = append([]byte(nil), src...)
	}
}

func BenchmarkMakeCopy(b *testing.B) {
	for i := 0; i < b.N; i++ {
		s := make([]byte, len(src))
		copy(s, src)
	}
}
goos: linux
goarch: amd64
BenchmarkAppend-8     	  200000	      9804 ns/op	   65536 B/op	       1 allocs/op
BenchmarkMakeCopy-8   	  100000	     12097 ns/op	   65536 B/op	       1 allocs/op

The make + copy call can probably be optimized to operate in the same way append does.

@josharian
Copy link
Contributor

@martisch

@martisch
Copy link
Contributor

martisch commented Jul 6, 2018

Was already experimenting optimizing make+copy for go1.12 as followup of the append improvements for go1.11. Unfortunately the opportunity is not as directly detectable as the append optimizations. If we want to do it before ssa its likely we need to look at a slicemake followed immediately by a copy in a slice of statements during ordering. Which is a kind of lookahead in a statement list i dont think we yet have done an optimization for anywhere else. It will also not detect make+somestatements+copy but code could be rewritten to somestatements+make+copy+somestatements to make it match where performance matters.

@martisch martisch self-assigned this Jul 6, 2018
@martisch martisch added this to the Unplanned milestone Jul 6, 2018
@TocarIP
Copy link
Contributor

TocarIP commented Jul 6, 2018

Looks like this is #23306

@martisch
Copy link
Contributor

I see them as separate concerns. This issue in my view is about optimizing make+copy by e.g. avoiding memclr before the copy if it is not needed for e.g. non pointer containing slices (like growslice for append already does).

#23306 looks more about that a memclr (without the copy) has worse performance then a memcpy.

@ikkerens
Copy link
Contributor

ikkerens commented Jul 12, 2018

Looking into this issue, I've found similar performance to BenchmarkMakeCopy when running this benchmark:

func BenchmarkMakeCapAppend(b *testing.B) {
	for i := 0; i < b.N; i++ {
		s := make([]byte, 0, len(src))
		s = append(s, src...)
	}
}

Assuming the performance drop is due to a memclr, why is memclr being called at all in this particular scenario?

@martisch
Copy link
Contributor

"Assuming the performance drop is due to a memclr, why is memclr being called at all in this particular scenario?" because the compiler has not been coded to detect that append will overwrite all the values in s after make and not doing memclr in make wont result in changed program behaviour.

In general make needs to zero the contents of the newly created slice https://golang.org/ref/spec#The_zero_value. If we can avoid that without changing program behavior than thats a possible valid optimization. For e.g. slices with elements with pointers that wont be possible because the garbage collector could see pointers to weird memory locations in the created slice after make returns and before append runs.

@gopherbot
Copy link

Change https://golang.org/cl/146719 mentions this issue: cmd/compile: optimize make+copy pattern to avoid memclr

@martisch
Copy link
Contributor

martisch commented May 25, 2019

With the current version of https://golang.org/cl/146719 the above benchmark changes to favor make+copy:

name      old time/op  new time/op  delta
Append    5.93µs ± 4%  5.82µs ± 5%   -1.79%  (p=0.047 n=20+20)
MakeCopy  9.75µs ± 2%  5.58µs ± 2%  -42.73%  (p=0.000 n=20+20)

@martisch martisch modified the milestones: Unplanned, Go1.14 Oct 15, 2019
@martisch martisch modified the milestones: Go1.14, Backlog Nov 12, 2019
@odeke-em
Copy link
Member

I spoke to @martisch and we'll push this to Go1.15 as he didn't have time to get it in for Go1.14.

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.
Projects
None yet
Development

No branches or pull requests

7 participants