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: for-loops cannot be inlined #14768

Open
dsnet opened this issue Mar 11, 2016 · 20 comments
Open

cmd/compile: for-loops cannot be inlined #14768

dsnet opened this issue Mar 11, 2016 · 20 comments
Assignees
Milestone

Comments

@dsnet
Copy link
Member

@dsnet dsnet commented Mar 11, 2016

Using go devel +ed4a27a

Currently, functions with for-loops are not inline-able, would be nice if they did. Not long ago, I used a non-idiomatic goto in order to cheat around the inliner.

@dr2chase

@bradfitz bradfitz added this to the Unplanned milestone Mar 11, 2016
@dr2chase dr2chase self-assigned this Mar 13, 2016
@ALTree
Copy link
Member

@ALTree ALTree commented Mar 28, 2016

For reference, the easy part (inlining for loops with no range and no continue/break)
inlines 924 additional calls in go install std and gives mixed results on the go1 benchmarks

name                     old time/op    new time/op    delta
BinaryTree17-4              3.00s ± 3%     2.96s ± 4%     ~             (p=0.548 n=5+5)
Fannkuch11-4                2.29s ± 0%     2.29s ± 0%     ~             (p=0.056 n=5+5)
FmtFprintfEmpty-4          50.4ns ± 0%    50.7ns ± 2%     ~             (p=0.556 n=4+5)
FmtFprintfString-4          134ns ± 0%     134ns ± 0%     ~     (all samples are equal)
FmtFprintfInt-4             133ns ± 0%     133ns ± 0%     ~     (all samples are equal)
FmtFprintfIntInt-4          201ns ± 0%     198ns ± 0%     ~             (p=0.079 n=4+5)
FmtFprintfPrefixedInt-4     201ns ± 0%     197ns ± 0%   -1.79%          (p=0.000 n=5+4)
FmtFprintfFloat-4           291ns ± 2%     284ns ± 1%   -2.20%          (p=0.040 n=5+5)
FmtManyArgs-4               845ns ± 0%     841ns ± 1%     ~             (p=0.056 n=5+5)
GobDecode-4                7.81ms ± 1%    7.90ms ± 1%   +1.22%          (p=0.008 n=5+5)
GobEncode-4                6.55ms ± 1%    6.27ms ± 0%   -4.24%          (p=0.008 n=5+5)
Gzip-4                      268ms ± 0%     269ms ± 1%     ~             (p=0.690 n=5+5)
Gunzip-4                   36.8ms ± 0%    36.6ms ± 0%   -0.60%          (p=0.008 n=5+5)
HTTPClientServer-4         58.5µs ± 1%    61.8µs ± 0%   +5.65%          (p=0.008 n=5+5)
JSONEncode-4               17.2ms ± 1%    16.9ms ± 2%   -1.77%          (p=0.016 n=5+5)
JSONDecode-4               51.5ms ± 0%    52.1ms ± 1%   +1.16%          (p=0.008 n=5+5)
Mandelbrot200-4            4.77ms ± 0%    4.74ms ± 1%     ~             (p=0.151 n=5+5)
GoParse-4                  3.58ms ± 0%    3.54ms ± 1%   -1.10%          (p=0.016 n=5+5)
RegexpMatchEasy0_32-4      81.5ns ± 0%    82.1ns ± 0%   +0.74%          (p=0.016 n=4+5)
RegexpMatchEasy0_1K-4       199ns ± 2%     196ns ± 0%   -1.51%          (p=0.048 n=5+5)
RegexpMatchEasy1_32-4      81.2ns ± 1%    82.9ns ± 0%   +2.04%          (p=0.016 n=5+4)
RegexpMatchEasy1_1K-4       360ns ± 2%     356ns ± 1%     ~             (p=0.167 n=5+5)
RegexpMatchMedium_32-4      125ns ± 1%     124ns ± 0%     ~             (p=0.167 n=5+5)
RegexpMatchMedium_1K-4     38.8µs ± 1%    37.9µs ± 1%   -2.54%          (p=0.008 n=5+5)
RegexpMatchHard_32-4       1.98µs ± 0%    1.95µs ± 0%   -1.73%          (p=0.000 n=5+4)
RegexpMatchHard_1K-4       59.7µs ± 0%    58.6µs ± 0%   -1.85%          (p=0.016 n=4+5)
Revcomp-4                   437ms ± 0%     448ms ± 1%   +2.65%          (p=0.008 n=5+5)
Template-4                 62.8ms ± 0%    62.8ms ± 0%     ~             (p=0.841 n=5+5)
TimeParse-4                 328ns ± 0%     295ns ± 0%  -10.17%          (p=0.000 n=5+4)
TimeFormat-4                357ns ± 1%     349ns ± 3%     ~             (p=0.111 n=5+5)
@dsnet
Copy link
Member Author

@dsnet dsnet commented Mar 28, 2016

Thanks for doing this; it was not exactly the results I was hoping for ;)

Are you aware of which loops in HTTPClientServer were inlined? I'm curious about the 5% increase in time.

@ALTree
Copy link
Member

@ALTree ALTree commented Mar 28, 2016

grepping for "http" in the diff between the outputs for go install -gcflags -m std says

> ../go/src/net/http/cgi/host.go:191: inlining call to filepath.Split
> ../go/src/net/http/cgi/host.go:191: inlining call to filepath.VolumeName
> ../go/src/net/http/cgi/host.go:191: inlining call to filepath.volumeNameLen
> ../go/src/net/http/cgi/host.go:191: inlining call to os.IsPathSeparator
> ../go/src/net/http/cookie.go:215: inlining call to parseCookieValue
> ../go/src/net/http/cookie.go:215: inlining call to validCookieValueByte
> ../go/src/net/http/cookie.go:58: inlining call to parseCookieValue
> ../go/src/net/http/cookie.go:58: inlining call to validCookieValueByte
> ../go/src/net/http/cookie.go:78: inlining call to parseCookieValue
> ../go/src/net/http/cookie.go:78: inlining call to validCookieValueByte
> ../go/src/net/http/cookiejar/punycode.go:136: inlining call to ascii
> ../go/src/net/http/cookiejar/punycode.go:141: inlining call to ascii
> ../go/src/net/http/cookiejar/punycode.go:89: inlining call to adapt
> ../go/src/net/http/fs.go:163: inlining call to filepath.Ext
> ../go/src/net/http/fs.go:163: inlining call to os.IsPathSeparator
> ../go/src/net/http/fs.go:483: inlining call to filepath.Split
> ../go/src/net/http/fs.go:483: inlining call to filepath.VolumeName
> ../go/src/net/http/fs.go:483: inlining call to filepath.volumeNameLen
> ../go/src/net/http/fs.go:483: inlining call to os.IsPathSeparator
> ../go/src/net/http/h2_bundle.go:2962: inlining call to http2validHeaderFieldValue
> ../go/src/net/http/h2_bundle.go:3015: inlining call to http2validHeaderFieldValue
> ../go/src/net/http/h2_bundle.go:4541: inlining call to textproto.isASCIISpace
> ../go/src/net/http/h2_bundle.go:4541: inlining call to textproto.TrimString
> ../go/src/net/http/h2_bundle.go:4550: inlining call to textproto.isASCIISpace
> ../go/src/net/http/h2_bundle.go:4550: inlining call to textproto.TrimString
> ../go/src/net/http/h2_bundle.go:6014: inlining call to http2validHeaderFieldValue
> ../go/src/net/http/h2_bundle.go:6401: inlining call to http2validHeaderFieldValue
> ../go/src/net/http/header.go:154: inlining call to textproto.isASCIISpace
> ../go/src/net/http/header.go:154: inlining call to textproto.TrimString
> ../go/src/net/http/internal/chunked.go:124: inlining call to isASCIISpace
> ../go/src/net/http/internal/chunked.go:124: inlining call to trimTrailingWhitespace
> ../go/src/net/http/lex.go:139: inlining call to isOWS
> ../go/src/net/http/lex.go:139: inlining call to trimOWS
> ../go/src/net/http/lex.go:141: inlining call to isOWS
> ../go/src/net/http/lex.go:141: inlining call to trimOWS
> ../go/src/net/http/server.go:1105: inlining call to textproto.isASCIISpace
> ../go/src/net/http/server.go:1105: inlining call to textproto.TrimString
> ../go/src/net/http/server.go:1114: inlining call to textproto.isASCIISpace
> ../go/src/net/http/server.go:1114: inlining call to textproto.TrimString
> ../go/src/net/http/server.go:723: inlining call to validHostHeader
> ../go/src/net/http/server.go:731: inlining call to isCTL
> ../go/src/net/http/server.go:731: inlining call to isLWS
> ../go/src/net/http/server.go:731: inlining call to validHeaderValue
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:101: inlining call to constantTimeStringCompare
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:127: inlining call to (*dynamicTable).evict
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:127: inlining call to (*dynamicTable).setMaxSize
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:127: inlining call to (*HeaderField).size
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:141: inlining call to (*dynamicTable).evict
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:141: inlining call to (*dynamicTable).setMaxSize
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:141: inlining call to (*HeaderField).size
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:154: inlining call to appendVarInt
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:187: inlining call to appendVarInt
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:196: inlining call to appendVarInt
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:225: inlining call to HuffmanEncodeLength
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:228: inlining call to appendVarInt
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:232: inlining call to appendVarInt
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:42: inlining call to (*dynamicTable).evict
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:42: inlining call to (*dynamicTable).setMaxSize
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:42: inlining call to (*HeaderField).size
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:55: inlining call to appendTableSize
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:55: inlining call to appendVarInt
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:58: inlining call to appendTableSize
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:58: inlining call to appendVarInt
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:63: inlining call to appendIndexed
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:63: inlining call to appendVarInt
> ../go/src/vendor/golang.org/x/net/http2/hpack/encode.go:92: inlining call to constantTimeStringCompare
> ../go/src/vendor/golang.org/x/net/http2/hpack/hpack.go:137: inlining call to (*dynamicTable).evict
> ../go/src/vendor/golang.org/x/net/http2/hpack/hpack.go:137: inlining call to (*dynamicTable).setMaxSize
> ../go/src/vendor/golang.org/x/net/http2/hpack/hpack.go:137: inlining call to (*HeaderField).size
> ../go/src/vendor/golang.org/x/net/http2/hpack/hpack.go:160: inlining call to (*dynamicTable).evict
> ../go/src/vendor/golang.org/x/net/http2/hpack/hpack.go:160: inlining call to (*HeaderField).size
> ../go/src/vendor/golang.org/x/net/http2/hpack/hpack.go:175: inlining call to (*dynamicTable).evict
> ../go/src/vendor/golang.org/x/net/http2/hpack/hpack.go:175: inlining call to (*HeaderField).size
> ../go/src/vendor/golang.org/x/net/http2/hpack/hpack.go:217: inlining call to constantTimeStringCompare
> ../go/src/vendor/golang.org/x/net/http2/hpack/hpack.go:226: inlining call to constantTimeStringCompare
> ../go/src/vendor/golang.org/x/net/http2/hpack/hpack.go:443: inlining call to (*dynamicTable).evict
> ../go/src/vendor/golang.org/x/net/http2/hpack/hpack.go:443: inlining call to (*dynamicTable).setMaxSize
> ../go/src/vendor/golang.org/x/net/http2/hpack/hpack.go:443: inlining call to (*HeaderField).size
> ../go/src/vendor/golang.org/x/net/http2/hpack/hpack.go:97: inlining call to (*dynamicTable).evict
> ../go/src/vendor/golang.org/x/net/http2/hpack/hpack.go:97: inlining call to (*dynamicTable).setMaxSize
> ../go/src/vendor/golang.org/x/net/http2/hpack/hpack.go:97: inlining call to (*HeaderField).size

No idea which one of these is the culprit for the slowdown.

@mvdan mvdan changed the title cmd/compile: for-loops cant be inlined cmd/compile: for-loops cannot be inlined Aug 17, 2017
wallyqs added a commit to wallyqs/nats-server that referenced this issue Sep 8, 2017
Using a goto based loop makes it become a leaf function which can be
inlined, making us get a slight performance increase in the fast path.
See: golang/go#14768
wallyqs added a commit to wallyqs/nats-server that referenced this issue Sep 8, 2017
Using a goto based loop makes it become a leaf function which can be
inlined, making us get a slight performance increase in the fast path.
See: golang/go#14768
@OneOfOne
Copy link
Contributor

@OneOfOne OneOfOne commented May 1, 2018

Any news on this?

@dr2chase
Copy link
Contributor

@dr2chase dr2chase commented May 1, 2018

I will give it a look, I have a "adjust inlining parameters" CL up for review and I can try adding this one top see if it helps or hurts.

@dr2chase
Copy link
Contributor

@dr2chase dr2chase commented May 2, 2018

Turns out that inlining for loops tickles (at least) two other bugs, don't start the party yet.

@ugorji
Copy link
Contributor

@ugorji ugorji commented Nov 7, 2018

@dr2chase Is it now ok to enable inlining of functions with for loops?

@dr2chase
Copy link
Contributor

@dr2chase dr2chase commented Nov 7, 2018

In theory, yes. I am doing some benchmarking right now to see what the overall impact is likely to be, with a very naive cost model (i.e., a default cost model). It also requires change to some test output, or some noinline annotations. I don't know if this qualifies for 1.12; though it is technically "an open bug" and the change is trivial.

@gopherbot
Copy link

@gopherbot gopherbot commented Nov 9, 2018

Change https://golang.org/cl/148777 mentions this issue: cmd/compile: enable inline of functions containing "for" loops

@mvdan
Copy link
Member

@mvdan mvdan commented Mar 14, 2019

Given that the fix is trivial and already somewhat-ready - any chance this could go in for 1.13? :)

@dr2chase
Copy link
Contributor

@dr2chase dr2chase commented Mar 14, 2019

When I tried to revive it, there was some weird failure that it caused.
It looks like inlining of a break or continue caused confusion, not sure how yet.
I just rebased and retested, the problem remains.

# go run run.go -- fixedbugs/issue15838.go
exit status 1
panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x1 addr=0x30 pc=0x18b7362]

goroutine 1 [running]:
cmd/compile/internal/ssa.(*Block).AddEdgeTo(...)
	/Users/drchase/work/go/src/cmd/compile/internal/ssa/block.go:150
cmd/compile/internal/gc.(*state).stmt(0xc0000731e0, 0xc000426200)
	/Users/drchase/work/go/src/cmd/compile/internal/gc/ssa.go:1067 +0x10f2
cmd/compile/internal/gc.(*state).stmtList(0xc0000731e0, 0xc000071780)
	/Users/drchase/work/go/src/cmd/compile/internal/gc/ssa.go:758 +0x59
cmd/compile/internal/gc.(*state).stmt(0xc0000731e0, 0xc000426180)
@ugorji
Copy link
Contributor

@ugorji ugorji commented Jun 29, 2019

Any chance for this being fixed sometime soon? I would love to undo my re-writes where I wrote my loops using goto instead of for, so they can be inlined.

@dr2chase
Copy link
Contributor

@dr2chase dr2chase commented Jul 1, 2019

Not in 1.13, maybe 1.14.

@elichai
Copy link

@elichai elichai commented Aug 11, 2020

Go 1.14 is long gone, any chance this is getting fixed? Right now I'm manually inlining functions :/

@cristaloleg
Copy link

@cristaloleg cristaloleg commented Aug 11, 2020

@elichai goto still works, still not the best solution but may prevent bugs with a manual inline.

@gopherbot
Copy link

@gopherbot gopherbot commented Sep 22, 2020

Change https://golang.org/cl/256459 mentions this issue: cmd/compile: allow inlining of "for" loops

gopherbot pushed a commit that referenced this issue Oct 15, 2020
We already allow inlining "if" and "goto" statements, so we might as
well allow "for" loops too. The majority of frontend support is
already there too.

The critical missing feature at the moment is that inlining doesn't
properly reassociate OLABEL nodes with their control statement (e.g.,
OFOR) after inlining. This eventually causes SSA construction to fail.

As a workaround, this CL only enables inlining for unlabeled "for"
loops. It's left to a (yet unplanned) future CL to add support for
labeled "for" loops.

The increased opportunity for inlining leads to a small growth in
binary size. For example:

$ size go.old go.new
   text	   data	    bss	    dec	    hex	filename
9740163	 320064	 230656	10290883	 9d06c3	go.old
9793399	 320064	 230656	10344119	 9dd6b7	go.new

Updates #14768.
Fixes #41474.

Change-Id: I827db0b2b9d9fa2934db05caf6baa463f0cd032a
Reviewed-on: https://go-review.googlesource.com/c/go/+/256459
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Trust: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: David Chase <drchase@google.com>
Reviewed-by: Cuong Manh Le <cuong.manhle.vn@gmail.com>
@gopherbot
Copy link

@gopherbot gopherbot commented Oct 16, 2020

Change https://golang.org/cl/263037 mentions this issue: compress/flate: revert a goto for-loop

gopherbot pushed a commit that referenced this issue Oct 16, 2020
In https://golang.org/cl/16528, a goto loop was chosen over a regular
for loop since that would make the function inlinable.

Thanks to the recent https://golang.org/cl/256459, for loops without a
label can now be inlined. So we can undo the workaround and simplify the
code.

Also add the function to TestIntendedInlining, which passes both before
and after the change, as expected.

For #14768.

Change-Id: Ie5df55a6bcb07c538ca331eef2f908807ff0b516
Reviewed-on: https://go-review.googlesource.com/c/go/+/263037
Trust: Daniel Martí <mvdan@mvdan.cc>
Run-TryBot: Daniel Martí <mvdan@mvdan.cc>
Reviewed-by: Brad Fitzpatrick <bradfitz@golang.org>
TryBot-Result: Go Bot <gobot@golang.org>
@dsnet
Copy link
Member Author

@dsnet dsnet commented Nov 13, 2020

As of 30ba798, it seems that for range loops are not inlineable.

For example:

func consumeWhitespace(b []byte) int {
	for i, c := range b {
		if !(c == ' ' || c == '\t' || c == '\r' || c == '\n') {
			return i
		}
	}
	return 0
}

cannot be inlined, but:

func consumeWhitespace(b []byte) int {
	for i := 0; i < len(b); i++ {
		if c := b[i]; !(c == ' ' || c == '\t' || c == '\r' || c == '\n') {
			return i
		}
	}
	return 0
}

is inlineable.

I'm not sure if this is deliberate or an oversight.

@mdempsky
Copy link
Member

@mdempsky mdempsky commented Nov 13, 2020

I'm not sure if this is deliberate or an oversight.

A little of both. Some range loops desugar into non-trivial code (e.g., ranging over maps), so I punted on this because I expected it would be too complex... but in retrospect, all of that complexity happens after inlining anyway, so it would probably be pretty trivial actually.

We should be able to easily address this for next release, along with labeled for loops.

@gopherbot
Copy link

@gopherbot gopherbot commented Nov 25, 2020

Change https://golang.org/cl/273270 mentions this issue: cmd/compile: fix latent issue import/export issue with break/continue

gopherbot pushed a commit that referenced this issue Nov 25, 2020
…ontinue

In CL 145200, I changed OBREAK, OCONTINUE, OGOTO, and OLABEL to just
use Sym instead of Node. However, within the export data, I forgot to
update the code for OBREAK and OCONTINUE.

This isn't currently an issue because the inliner currently disallows
these anyway, but it'll be an issue in the future once we add support
for inlining them. Also, Russ independently ran into it in CL 273246.

Updates #14768.

Change-Id: I94575df59c08a750b0dce1d3ce612aba7bfeeb76
Reviewed-on: https://go-review.googlesource.com/c/go/+/273270
Run-TryBot: Matthew Dempsky <mdempsky@google.com>
TryBot-Result: Go Bot <gobot@golang.org>
Trust: Matthew Dempsky <mdempsky@google.com>
Reviewed-by: Russ Cox <rsc@golang.org>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet