cmd/compile: detect and optimize slice-extending idiom append(a, make([]T, n)...) #21266
Comments
|
Seems reasonable if we can detect it easily. |
ALTree
changed the title
faiface
changed the title
|
Detection can be very easy, just look for anything that matches |
|
@faiface, if you believe it's a very easy fix, perhaps you'd like to make the change and contribute a fix? |
|
cc @martisch |
|
I was already looking at some other growslice performance optimizations for go1.10 and have worked on that code in the past. While at it i would be happy to have a go at this if @faiface does not have preference to contribute a CL for it himself? It might turn out not be as very easy as it first looks - we first need to investigate if the information that appends second argument is a make(...) is still directly present once the frontend/ssa backend gets to the part where it inserts the growslice runtime call. If that info has already been obstructed by ordering and evaluating arguments we might need to insert some detection code for it earlier. |
|
@dsnet @martisch I'll be happy to leave this to someone more experienced in the Go compiler. If needed, I can try and implement it, but it will probably take unreasonably long, since I've never worked with the Go compiler source before and there might be unexpected troubles as mentioned by @martisch. So, if anyone wants to have a go, my preference is to leave it to them ;) |
|
@martisch the easiest place to implement this is probably walk. I’ll volunteer to review. And please let me know if this falls off your list and I’ll pick it up. |
|
More discussion and example benchmarks in #23906 |
|
@martisch do you still plan to do this this cycle? |
|
yes, was just today looking at teaching the order pass not to mess with node structure when its needed to detect the pattern in walk later for this and another cl. Should have a cl sometime next week for you to review. |
|
Change https://golang.org/cl/109517 mentions this issue: |
|
Change https://golang.org/cl/109816 mentions this issue: |
name old alloc/op new alloc/op delta Template 35.0MB ± 0% 35.0MB ± 0% -0.05% (p=0.008 n=5+5) Unicode 29.3MB ± 0% 29.3MB ± 0% ~ (p=0.310 n=5+5) GoTypes 115MB ± 0% 115MB ± 0% -0.08% (p=0.008 n=5+5) Compiler 519MB ± 0% 519MB ± 0% -0.08% (p=0.008 n=5+5) SSA 1.59GB ± 0% 1.59GB ± 0% -0.05% (p=0.008 n=5+5) Flate 24.2MB ± 0% 24.2MB ± 0% -0.06% (p=0.008 n=5+5) GoParser 28.2MB ± 0% 28.1MB ± 0% -0.04% (p=0.016 n=5+5) Reflect 78.8MB ± 0% 78.7MB ± 0% -0.10% (p=0.008 n=5+5) Tar 34.5MB ± 0% 34.4MB ± 0% -0.07% (p=0.008 n=5+5) XML 43.3MB ± 0% 43.2MB ± 0% -0.09% (p=0.008 n=5+5) [Geo mean] 77.5MB 77.4MB -0.06% name old allocs/op new allocs/op delta Template 330k ± 0% 329k ± 0% -0.32% (p=0.008 n=5+5) Unicode 337k ± 0% 336k ± 0% -0.10% (p=0.008 n=5+5) GoTypes 1.15M ± 0% 1.14M ± 0% -0.34% (p=0.008 n=5+5) Compiler 4.78M ± 0% 4.77M ± 0% -0.25% (p=0.008 n=5+5) SSA 12.9M ± 0% 12.9M ± 0% -0.12% (p=0.008 n=5+5) Flate 221k ± 0% 220k ± 0% -0.32% (p=0.008 n=5+5) GoParser 275k ± 0% 274k ± 0% -0.34% (p=0.008 n=5+5) Reflect 944k ± 0% 940k ± 0% -0.42% (p=0.008 n=5+5) Tar 323k ± 0% 322k ± 0% -0.31% (p=0.008 n=5+5) XML 384k ± 0% 383k ± 0% -0.26% (p=0.008 n=5+5) [Geo mean] 749k 747k -0.28% Updates #21266 Change-Id: I926ee3ba009c068239db70cdee8fdf85b5ee6bb4 Reviewed-on: https://go-review.googlesource.com/109816 Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com> TryBot-Result: Gobot Gobot <gobot@golang.org> Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
|
Change https://golang.org/cl/112595 mentions this issue: |
…lice Using the extendslice init node list to add the init nodes for the memclr call could add init nodes for memclr function before the growslice call created by extendslice. As all arguments of the memclr were explicitly set in OAS nodes before the memclr call this does not change the generated code currently. ./all.bash runs fine when replacing memclr init with nil suggesting there are currently no additional nodes added to the init of extendslice by the memclr call. Add the init nodes for the memclr call directly before the node of the memclr call to prevent additional future init nodes for function calls and argument evaluations to be evaluated too early when other compiler code is added. passes toolstash -cmp Updates #21266 Change-Id: I44bd396fe864bfda315175aa1064f9d51c5fb57a Reviewed-on: https://go-review.googlesource.com/112595 Reviewed-by: Josh Bleecher Snyder <josharian@gmail.com> Run-TryBot: Martin Möhrmann <moehrmann@google.com> TryBot-Result: Gobot Gobot <gobot@golang.org>
|
FYI, the slice extension idiom doesn't work in go tip for non-int func BenchmarkExtendInt(b *testing.B) {
var buf []byte
b.ReportAllocs()
n := int(12345)
for i := 0; i < b.N; i++ {
buf = append(buf[:0], make([]byte, n)...)
}
}
func BenchmarkExtendUint64(b *testing.B) {
var buf []byte
b.ReportAllocs()
n := uint64(12345)
for i := 0; i < b.N; i++ {
buf = append(buf[:0], make([]byte, n)...)
}
}Benchmark results: As you can see, if |
Hi!
In Slice tricks we read that in order to extend a slice by
jnew elements, we should do this:As far as I know, this is the only one-liner way to do it anyway. However, this code most likely does more than required, because this is usually faster:
It's obvious that in the former code, allocating the
make([]T, j)slice is not required. As this is an often and useful pattern, I suggest this construct should be specially optimized by the compiler, so that no extra allocations are required.Thanks,
Michal Štrba
The text was updated successfully, but these errors were encountered: