/go

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: possible infinite recursion in Type.cmp #19869

Open
josharian opened this Issue Apr 6, 2017 · 2 comments

Comments

Assignees
No one assigned
Labels
NeedsInvestigation
Projects
None yet
Milestone
  Unplanned
4 participants
@josharian @gopherbot @mdempsky @ALTree
@josharian
Contributor

josharian commented Apr 6, 2017

If two of the types in fixedbugs/bug398.go make it into the backend and get passed to Type.cmp, they can cause infinite recursion. See https://go-review.googlesource.com/c/39710/ patch set 3 for a roundabout example.

It is non-obvious how to fix this, because if we detect infinite recursion, how should the types compare?

@josharian josharian added this to the Unplanned milestone Apr 6, 2017

@gopherbot

This comment has been minimized.

Sign in to view

gopherbot commented Apr 6, 2017

CL https://golang.org/cl/39710 mentions this issue.
@mdempsky

This comment has been minimized.

Sign in to view
Member

mdempsky commented Apr 6, 2017

We need a "Sisypheanterfaces" label.

gopherbot pushed a commit that referenced this issue Apr 6, 2017

@josharian
cmd/compile: make typenamesym do less work 
typenamesym is called from three places:
typename, ngotype, and Type.Symbol.
Only in typename do we actually need a Node.
ngotype and Type.Symbol require only a Sym.
And writing the newly created Node to
Sym.Def is unsafe in a concurrent backend.
Rather than use a mutex protect to Sym.Def,
make typenamesym not touch Sym.Def.

The assignment to Sym.Def was serving a second purpose,
namely to prevent duplicate entries on signatlist.
Preserve that functionality by switching signatlist to a map.
This in turn requires that we sort signatlist
when exporting it, to preserve reproducibility.

We'd like to use Type.cmp for sorting,
but that causes infinite recursion at the moment;
see #19869.

For now, use Type.LongString as the sort key,
which is a complete description of the type.
Type.LongString is relatively expensive,
but we calculate it only once per type,
and signatlist is generally fairly small,
so the performance impact is minimal.

Updates #15756

name       old alloc/op    new alloc/op    delta
Template      39.4MB ± 0%     39.4MB ± 0%    ~     (p=0.222 n=5+5)
Unicode       29.8MB ± 0%     29.8MB ± 0%    ~     (p=0.151 n=5+5)
GoTypes        113MB ± 0%      113MB ± 0%    ~     (p=0.095 n=5+5)
SSA           1.25GB ± 0%     1.25GB ± 0%  +0.04%  (p=0.008 n=5+5)
Flate         25.3MB ± 0%     25.4MB ± 0%    ~     (p=0.056 n=5+5)
GoParser      31.8MB ± 0%     31.8MB ± 0%    ~     (p=0.310 n=5+5)
Reflect       78.3MB ± 0%     78.3MB ± 0%    ~     (p=0.690 n=5+5)
Tar           26.7MB ± 0%     26.7MB ± 0%    ~     (p=0.548 n=5+5)
XML           42.2MB ± 0%     42.2MB ± 0%    ~     (p=0.222 n=5+5)

name       old allocs/op   new allocs/op   delta
Template        387k ± 0%       388k ± 0%    ~     (p=0.056 n=5+5)
Unicode         320k ± 0%       321k ± 0%  +0.32%  (p=0.032 n=5+5)
GoTypes        1.14M ± 0%      1.15M ± 0%    ~     (p=0.095 n=5+5)
SSA            9.70M ± 0%      9.72M ± 0%  +0.18%  (p=0.008 n=5+5)
Flate           234k ± 0%       235k ± 0%  +0.60%  (p=0.008 n=5+5)
GoParser        317k ± 0%       317k ± 0%    ~     (p=1.000 n=5+5)
Reflect         982k ± 0%       983k ± 0%    ~     (p=0.841 n=5+5)
Tar             252k ± 1%       252k ± 0%    ~     (p=0.310 n=5+5)
XML             393k ± 0%       392k ± 0%    ~     (p=0.548 n=5+5)

Change-Id: I53a3b95d19cf1a7b7511a94fba896706addf84fb
Reviewed-on: https://go-review.googlesource.com/39710
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
91433eb

lparth added a commit to lparth/go that referenced this issue Apr 13, 2017

@josharian @lparth
cmd/compile: make typenamesym do less work 
typenamesym is called from three places:
typename, ngotype, and Type.Symbol.
Only in typename do we actually need a Node.
ngotype and Type.Symbol require only a Sym.
And writing the newly created Node to
Sym.Def is unsafe in a concurrent backend.
Rather than use a mutex protect to Sym.Def,
make typenamesym not touch Sym.Def.

The assignment to Sym.Def was serving a second purpose,
namely to prevent duplicate entries on signatlist.
Preserve that functionality by switching signatlist to a map.
This in turn requires that we sort signatlist
when exporting it, to preserve reproducibility.

We'd like to use Type.cmp for sorting,
but that causes infinite recursion at the moment;
see golang#19869.

For now, use Type.LongString as the sort key,
which is a complete description of the type.
Type.LongString is relatively expensive,
but we calculate it only once per type,
and signatlist is generally fairly small,
so the performance impact is minimal.

Updates golang#15756

name       old alloc/op    new alloc/op    delta
Template      39.4MB ± 0%     39.4MB ± 0%    ~     (p=0.222 n=5+5)
Unicode       29.8MB ± 0%     29.8MB ± 0%    ~     (p=0.151 n=5+5)
GoTypes        113MB ± 0%      113MB ± 0%    ~     (p=0.095 n=5+5)
SSA           1.25GB ± 0%     1.25GB ± 0%  +0.04%  (p=0.008 n=5+5)
Flate         25.3MB ± 0%     25.4MB ± 0%    ~     (p=0.056 n=5+5)
GoParser      31.8MB ± 0%     31.8MB ± 0%    ~     (p=0.310 n=5+5)
Reflect       78.3MB ± 0%     78.3MB ± 0%    ~     (p=0.690 n=5+5)
Tar           26.7MB ± 0%     26.7MB ± 0%    ~     (p=0.548 n=5+5)
XML           42.2MB ± 0%     42.2MB ± 0%    ~     (p=0.222 n=5+5)

name       old allocs/op   new allocs/op   delta
Template        387k ± 0%       388k ± 0%    ~     (p=0.056 n=5+5)
Unicode         320k ± 0%       321k ± 0%  +0.32%  (p=0.032 n=5+5)
GoTypes        1.14M ± 0%      1.15M ± 0%    ~     (p=0.095 n=5+5)
SSA            9.70M ± 0%      9.72M ± 0%  +0.18%  (p=0.008 n=5+5)
Flate           234k ± 0%       235k ± 0%  +0.60%  (p=0.008 n=5+5)
GoParser        317k ± 0%       317k ± 0%    ~     (p=1.000 n=5+5)
Reflect         982k ± 0%       983k ± 0%    ~     (p=0.841 n=5+5)
Tar             252k ± 1%       252k ± 0%    ~     (p=0.310 n=5+5)
XML             393k ± 0%       392k ± 0%    ~     (p=0.548 n=5+5)

Change-Id: I53a3b95d19cf1a7b7511a94fba896706addf84fb
Reviewed-on: https://go-review.googlesource.com/39710
Run-TryBot: Josh Bleecher Snyder <josharian@gmail.com>
TryBot-Result: Gobot Gobot <gobot@golang.org>
Reviewed-by: Matthew Dempsky <mdempsky@google.com>
0b9dd42

@ALTree ALTree added the NeedsInvestigation label Sep 22, 2018

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment