code review 9360043: cmd/gc: avoid a temporary when inlining s = append(s, x)

cmd/gc: avoid a temporary when inlining s = append(s, x)

pkg strconv:
benchmark                              old ns/op    new ns/op    delta
BenchmarkAppendFloatDecimal                  203          198   -2.46%
BenchmarkAppendFloat                         363          348   -4.13%
BenchmarkAppendFloatExp                      335          307   -8.36%
BenchmarkAppendFloatNegExp                   335          318   -5.07%
BenchmarkAppendFloatBig                      526          480   -8.75%
BenchmarkAppendFloat32Integer                203          216   +6.40%
BenchmarkAppendFloat32ExactFraction          307          293   -4.56%
BenchmarkAppendFloat32Point                  367          349   -4.90%
BenchmarkAppendFloat32Exp                    318          302   -5.03%
BenchmarkAppendFloat32NegExp                 322          306   -4.97%
BenchmarkAppendFloat64Fixed1                 243          247   +1.65%
BenchmarkAppendFloat64Fixed2                 283          293   +3.53%
BenchmarkAppendFloat64Fixed3                 248          264   +6.45%
BenchmarkAppendFloat64Fixed4                 287          277   -3.48%
BenchmarkAppendInt                          5676         5640   -0.63%
BenchmarkAppendUint                         1448         1445   -0.21%

pkg time:
benchmark                              old ns/op    new ns/op    delta
BenchmarkFormat                              876          884   +0.91%
BenchmarkFormatNow                           832          845   +1.56%

Stack size is reduced in many cases:

strconv before:
(src/pkg/strconv/ftoa.go:334) TEXT    fmtE+0(SB),$344-120
(src/pkg/strconv/ftoa.go:401) TEXT    fmtF+0(SB),$232-112
(src/pkg/strconv/quote.go:13) TEXT    quoteWith+0(SB),$560-40
(src/pkg/strconv/quote.go:293) TEXT    Unquote+0(SB),$200-48

strconv after:
(src/pkg/strconv/ftoa.go:334) TEXT    fmtE+0(SB),$104-120
(src/pkg/strconv/ftoa.go:401) TEXT    fmtF+0(SB),$88-112
(src/pkg/strconv/quote.go:13) TEXT    quoteWith+0(SB),$208-40
(src/pkg/strconv/quote.go:293) TEXT    Unquote+0(SB),$176-48

time before:
(src/pkg/time/format.go:290) TEXT    appendUint+0(SB),$272-64
(src/pkg/time/format.go:341) TEXT    formatNano+0(SB),$152-72
(src/pkg/time/format.go:382) TEXT    Time.Format+0(SB),$720-56

time after:
(src/pkg/time/format.go:290) TEXT    appendUint+0(SB),$200-64
(src/pkg/time/format.go:341) TEXT    formatNano+0(SB),$128-72
(src/pkg/time/format.go:382) TEXT    Time.Format+0(SB),$416-56

[remyoudompheng, 2013-05-12 15:11:21]

Hello golang-dev@googlegroups.com (cc: golang-dev@googlegroups.com),

I'd like you to review this change to
https://go.googlecode.com/hg/

[bradfitz, 2013-05-12 17:58:36]

https://codereview.appspot.com/9360043/diff/4001/src/cmd/gc/walk.c
File src/cmd/gc/walk.c (right):

https://codereview.appspot.com/9360043/diff/4001/src/cmd/gc/walk.c#newcode2505
src/cmd/gc/walk.c:2505: // The caller may supply its own storage space to use
instead of s.
you don't clarify that "ns" is that storage space. Also: what is "s"?

[DMorsing, 2013-05-12 18:33:13]

https://codereview.appspot.com/9360043/diff/4001/src/cmd/gc/walk.c
File src/cmd/gc/walk.c (right):

https://codereview.appspot.com/9360043/diff/4001/src/cmd/gc/walk.c#newcode573
src/cmd/gc/walk.c:573: // optimization of the common pattern x = append(x, y)
Move this logic down into convas. It handles the special cases like map
indexing.

https://codereview.appspot.com/9360043/diff/4001/src/cmd/gc/walk.c#newcode2507
src/cmd/gc/walk.c:2507: append(Node *n, NodeList **init, Node *ns)
Move ns into the middle of the arguments for consistency with other functions
taking an init list.

[remyoudompheng, 2013-05-18 08:36:01]

Hello golang-dev@googlegroups.com, bradfitz@golang.org, daniel.morsing@gmail.com
(cc: golang-dev@googlegroups.com),

Please take another look.

[remyoudompheng, 2013-05-18 08:36:03]

https://codereview.appspot.com/9360043/diff/4001/src/cmd/gc/walk.c
File src/cmd/gc/walk.c (right):

https://codereview.appspot.com/9360043/diff/4001/src/cmd/gc/walk.c#newcode573
src/cmd/gc/walk.c:573: // optimization of the common pattern x = append(x, y)
On 2013/05/12 18:33:13, DMorsing wrote:
> Move this logic down into convas. It handles the special cases like map
> indexing.

I cannot put this logic after walkexpr(&n->right) which will create the extra
temp variable.
I'm not sure how to do what you say, which could be interesting indeed.

Maybe make convas do the walkexpr itself? That would be more intrusive.

https://codereview.appspot.com/9360043/diff/4001/src/cmd/gc/walk.c#newcode2505
src/cmd/gc/walk.c:2505: // The caller may supply its own storage space to use
instead of s.
On 2013/05/12 17:58:36, bradfitz wrote:
> you don't clarify that "ns" is that storage space. Also: what is "s"?

Done.

https://codereview.appspot.com/9360043/diff/4001/src/cmd/gc/walk.c#newcode2507
src/cmd/gc/walk.c:2507: append(Node *n, NodeList **init, Node *ns)
On 2013/05/12 18:33:13, DMorsing wrote:
> Move ns into the middle of the arguments for consistency with other functions
> taking an init list.

Done.

[DMorsing, 2013-05-18 11:08:42]

LGTM

On 2013/05/18 08:36:03, remyoudompheng wrote:
> https://codereview.appspot.com/9360043/diff/4001/src/cmd/gc/walk.c
> File src/cmd/gc/walk.c (right):
> 
> https://codereview.appspot.com/9360043/diff/4001/src/cmd/gc/walk.c#newcode573
> src/cmd/gc/walk.c:573: // optimization of the common pattern x = append(x, y)
> On 2013/05/12 18:33:13, DMorsing wrote:
> > Move this logic down into convas. It handles the special cases like map
> > indexing.
> 
> I cannot put this logic after walkexpr(&n->right) which will create the extra
> temp variable.
> I'm not sure how to do what you say, which could be interesting indeed.
> 
> Maybe make convas do the walkexpr itself? That would be more intrusive.
> 

Nah, just leave the code in it's current state.

Eventually, we should add some sort of mechanism so that makes it possible to
determine the context given a single node. All these single cases for
optimization are littering walk.c, and it would be nice to have all append
related tree rewrites be centered around one spot in the code.

Having such a mechanism would make it trivial to implement this change for OAS2
as well, which it doesn't cover right now.

[dave_cheney.net, 2013-05-19 02:02:37]

The results aren't quite so impressive on linux/arm (chromebook)

benchmark                              old ns/op    new ns/op    delta
BenchmarkAppendFloatDecimal                  796          787   -1.13%
BenchmarkAppendFloat                        1354         1324   -2.22%
BenchmarkAppendFloatExp                     1186         1120   -5.56%
BenchmarkAppendFloatNegExp                  1174         1158   -1.36%
BenchmarkAppendFloatBig                     2084         2027   -2.74%
BenchmarkAppendFloat32Integer                764          758   -0.79%
BenchmarkAppendFloat32ExactFraction         1073         1039   -3.17%
BenchmarkAppendFloat32Point                 1355         1316   -2.88%
BenchmarkAppendFloat32Exp                   1166         1108   -4.97%
BenchmarkAppendFloat32NegExp                1153         1126   -2.34%
BenchmarkAppendFloat64Fixed1                 826          803   -2.78%
BenchmarkAppendFloat64Fixed2                 841          785   -6.66%
BenchmarkAppendFloat64Fixed3                 852          787   -7.63%
BenchmarkAppendFloat64Fixed4                 890          811   -8.88%
BenchmarkAppendInt                         29791        30703   +3.06%
BenchmarkAppendUint                        19478        19289   -0.97%

benchmark             old ns/op    new ns/op    delta
BenchmarkFormat            5324         5183   -2.65%
BenchmarkFormatNow         5138         5105   -0.64%

[bradfitz, 2013-07-23 16:46:54]

Remy, ping.

Status of this?

[rsc, 2013-08-01 21:12:54]

I think this ends up being correct, because of the calls to cheapexpr, but I
still worry about setting s to a bigger slice and then failing to fill it due to
a panic. 

Could you please add some tests that do things like

var x []int // global

var p *int
var n, d = 1, 0

and check that x = append(x, 1, *p, 2) does not leave x expanded, and similarly
x = append(x, 1, n/d, 2).

Thanks.

[remyoudompheng, 2013-08-14 06:21:24]

On 2013/08/01 21:12:54, rsc wrote:
> I think this ends up being correct, because of the calls to cheapexpr, but I
> still worry about setting s to a bigger slice and then failing to fill it due
to
> a panic. 
> 
> Could you please add some tests that do things like
> 
> var x []int // global
> 
> var p *int
> var n, d = 1, 0
> 
> and check that x = append(x, 1, *p, 2) does not leave x expanded, and
similarly
> x = append(x, 1, n/d, 2).
> 
> Thanks.

[remyoudompheng, 2013-08-14 06:22:09]

R=close

This would have been the source of endless weird potential corruption and the
temp merging optimization takes care much better of stack size reduction.