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: detect and optimize slice-extending idiom append(a, make([]T, n)...) #21266

Closed
faiface opened this issue Aug 1, 2017 · 14 comments

Comments

Projects
None yet
8 participants
@faiface
Copy link

commented Aug 1, 2017

Hi!

In Slice tricks we read that in order to extend a slice by j new elements, we should do this:

a = append(a, make([]T, j)...)

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:

for i := 0; i < j; i++ {
    a = append(a, 0)
}

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

@randall77 randall77 added this to the Go1.10 milestone Aug 1, 2017

@randall77

This comment has been minimized.

Copy link
Contributor

commented Aug 1, 2017

Seems reasonable if we can detect it easily.

@ALTree ALTree changed the title Extending a slice with append(a, make([]T, n)...) is slow cmd/compile: detect and optimize slice-extending idom append(a, make([]T, n)...) Aug 1, 2017

@faiface faiface changed the title cmd/compile: detect and optimize slice-extending idom append(a, make([]T, n)...) cmd/compile: detect and optimize slice-extending idiom append(a, make([]T, n)...) Aug 1, 2017

@faiface

This comment has been minimized.

Copy link
Author

commented Aug 1, 2017

Detection can be very easy, just look for anything that matches append(a, make([]T, n)...) for any a and any n and that's it.

@dsnet

This comment has been minimized.

Copy link
Member

commented Aug 1, 2017

@faiface, if you believe it's a very easy fix, perhaps you'd like to make the change and contribute a fix?

@josharian

This comment has been minimized.

Copy link
Contributor

commented Aug 2, 2017

@martisch

This comment has been minimized.

Copy link
Member

commented Aug 2, 2017

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.

@faiface

This comment has been minimized.

Copy link
Author

commented Aug 2, 2017

@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 martisch self-assigned this Aug 27, 2017

@martisch martisch modified the milestones: Go1.10, Go1.11 Nov 10, 2017

@josharian

This comment has been minimized.

Copy link
Contributor

commented Feb 13, 2018

@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.

@bradfitz

This comment has been minimized.

Copy link
Member

commented Feb 19, 2018

More discussion and example benchmarks in #23906

@josharian

This comment has been minimized.

Copy link
Contributor

commented Apr 19, 2018

@martisch do you still plan to do this this cycle?

@martisch

This comment has been minimized.

Copy link
Member

commented Apr 19, 2018

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.

@gopherbot

This comment has been minimized.

Copy link

commented Apr 26, 2018

Change https://golang.org/cl/109517 mentions this issue: cmd/compile: optimize append(x, make(T[], y)...) slice extending idiom

@gopherbot

This comment has been minimized.

Copy link

commented Apr 27, 2018

Change https://golang.org/cl/109816 mentions this issue: cmd/compile: use slice extension idiom to grow slices

@gopherbot gopherbot closed this in a8a60ac May 6, 2018

gopherbot pushed a commit that referenced this issue May 6, 2018

cmd/compile: use slice extension idiom in LSym.Grow
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>
@gopherbot

This comment has been minimized.

Copy link

commented May 10, 2018

Change https://golang.org/cl/112595 mentions this issue: cmd/compile: ensure init of memclr happens after growslice in extendslice

gopherbot pushed a commit that referenced this issue May 13, 2018

cmd/compile: ensure init of memclr happens after growslice in extends…
…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>

@GeorgeErickson GeorgeErickson referenced this issue Jul 17, 2018

Merged

[distributions] use dogsketch #2013

2 of 3 tasks complete
@valyala

This comment has been minimized.

Copy link
Contributor

commented Jan 17, 2019

FYI, the slice extension idiom doesn't work in go tip for non-int n in append(a, make([]T, n)...):

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:

BenchmarkExtendInt-4      	10000000	       145 ns/op	       0 B/op	       0 allocs/op
BenchmarkExtendUint64-4   	 1000000	      1576 ns/op	   13568 B/op	       1 allocs/op

As you can see, if n has a type other than int, go doesn't remove the allocation.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.