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: improve escape analysis understanding of tree structures #14858

Open
josharian opened this Issue Mar 18, 2016 · 4 comments

Comments

Projects
None yet
4 participants
@josharian
Contributor

josharian commented Mar 18, 2016

package x

type N struct {
    left *N
    t    string
}

func f(n *N) {
    n.t = n.left.t
}
$ go tool compile -m -m e.go
e.go:8: leaking param content: n
e.go:8:     from n.left (dot of pointer) at e.go:9
e.go:8:     from n.left.t (dot of pointer) at e.go:9
e.go:8:     from n.t (star-dot-equals) at e.go:9

I believe that n should not escape here.

This arises in the compiler. It is one of the reasons that typecheck1's np argument escapes. (The new escape analysis explainer is very exciting.) 15% of the allocations in the compiler are *gc.Node, almost all of them due to moving *gc.Node parameters to the heap for calls to typecheck1. (After *gc.Node come gc.Nodes at 9%, gc.Node at 8.5%, []*gc.Node at 5.5%, and string at 5%.)

This strikes me as hard to fix in the general case, but figured it was worth checking.

@dr2chase

@josharian josharian added this to the Unplanned milestone Mar 18, 2016

@dsnet

This comment has been minimized.

Member

dsnet commented Mar 18, 2016

This is related to (if not a duplicate of) #13493.

@gopherbot

This comment has been minimized.

gopherbot commented Mar 21, 2016

CL https://golang.org/cl/20959 mentions this issue.

gopherbot pushed a commit that referenced this issue Mar 22, 2016

cmd/compile: reduce use of **Node parameters
Escape analysis has a hard time with tree-like
structures (see #13493 and #14858).
This is unlikely to change.
As a result, when invoking a function that accepts
a **Node parameter, we usually allocate a *Node
on the heap. This happens a whole lot.

This CL changes functions from taking a **Node
to acting more like append: It both modifies
the input and returns a replacement for it.

Because of the cascading nature of escape analysis,
in order to get the benefits, I had to modify
almost all such functions. The remaining functions
are in racewalk and the backend. I would be happy
to update them as well in a separate CL.

This CL was created by manually updating the
function signatures and the directly impacted
bits of code. The callsites were then automatically
updated using a bespoke script:
https://gist.github.com/josharian/046b1be7aceae244de39

For ease of reviewing and future understanding,
this CL is also broken down into four CLs,
mailed separately, which show the manual
and the automated changes separately.
They are CLs 20990, 20991, 20992, and 20993.

Passes toolstash -cmp.

name       old time/op     new time/op     delta
Template       335ms ± 5%      324ms ± 5%   -3.35%        (p=0.000 n=23+24)
Unicode        176ms ± 9%      165ms ± 6%   -6.12%        (p=0.000 n=23+24)
GoTypes        1.10s ± 4%      1.07s ± 2%   -2.77%        (p=0.000 n=24+24)
Compiler       5.31s ± 3%      5.15s ± 3%   -2.95%        (p=0.000 n=24+24)
MakeBash       41.6s ± 1%      41.7s ± 2%     ~           (p=0.586 n=23+23)

name       old alloc/op    new alloc/op    delta
Template      63.3MB ± 0%     62.4MB ± 0%   -1.36%        (p=0.000 n=25+23)
Unicode       42.4MB ± 0%     41.6MB ± 0%   -1.99%        (p=0.000 n=24+25)
GoTypes        220MB ± 0%      217MB ± 0%   -1.11%        (p=0.000 n=25+25)
Compiler       994MB ± 0%      973MB ± 0%   -2.08%        (p=0.000 n=24+25)

name       old allocs/op   new allocs/op   delta
Template        681k ± 0%       574k ± 0%  -15.71%        (p=0.000 n=24+25)
Unicode         518k ± 0%       413k ± 0%  -20.34%        (p=0.000 n=25+24)
GoTypes        2.08M ± 0%      1.78M ± 0%  -14.62%        (p=0.000 n=25+25)
Compiler       9.26M ± 0%      7.64M ± 0%  -17.48%        (p=0.000 n=25+25)

name       old text-bytes  new text-bytes  delta
HelloSize       578k ± 0%       578k ± 0%     ~     (all samples are equal)
CmdGoSize      6.46M ± 0%      6.46M ± 0%     ~     (all samples are equal)

name       old data-bytes  new data-bytes  delta
HelloSize       128k ± 0%       128k ± 0%     ~     (all samples are equal)
CmdGoSize       281k ± 0%       281k ± 0%     ~     (all samples are equal)

name       old exe-bytes   new exe-bytes   delta
HelloSize       921k ± 0%       921k ± 0%     ~     (all samples are equal)
CmdGoSize      9.86M ± 0%      9.86M ± 0%     ~     (all samples are equal)

Change-Id: I277d95bd56d51c166ef7f560647aeaa092f3f475
Reviewed-on: https://go-review.googlesource.com/20959
Reviewed-by: Dave Cheney <dave@cheney.net>
Reviewed-by: Ian Lance Taylor <iant@golang.org>
@gopherbot

This comment has been minimized.

gopherbot commented Jul 27, 2018

Change https://golang.org/cl/126395 mentions this issue: cmd/compile/internal/gc: better handling of self-assignments in esc.go

@Quasilyte

This comment has been minimized.

Contributor

Quasilyte commented Jul 27, 2018

I may be wrong, but this kind of inference may be impossible in the current model.

type N struct {
  left *N
  t    *object
}

func f(n *N) {
  // What if n.left allocated on stack, and n.left.t also does not escape.
  // Here, if we not assume n param as leaking contents,
  // and if n.left happens to have shorter lifetime than n,
  // we will store dead pointer into n.t that violates memory
  // guarantees, as far as I can tell.
  n.t = n.left.t
}

So, the conservative (and safe) action is to leak param content.

gopherbot pushed a commit that referenced this issue Sep 3, 2018

cmd/compile/internal/gc: better handling of self-assignments in esc.go
Teach escape analysis to recognize these assignment patterns
as not causing the src to leak:

	val.x = val.y
	val.x[i] = val.y[j]
	val.x1.x2 = val.x1.y2
	... etc

Helps to avoid "leaking param" with assignments showed above.
The implementation is based on somewhat similiar xs=xs[a:b]
special case that is ignored by the escape analysis.

We may figure out more generalized version of this,
but this one looks like a safe step into that direction.

Updates #14858

Change-Id: I6fe5bfedec9c03bdc1d7624883324a523bd11fde
Reviewed-on: https://go-review.googlesource.com/126395
Run-TryBot: Iskander Sharipov <iskander.sharipov@intel.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: David Chase <drchase@google.com>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment