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

runtime: don't allocate for non-escaping conversions to interface{} #8618

Open
randall77 opened this issue Aug 29, 2014 · 22 comments
Open

runtime: don't allocate for non-escaping conversions to interface{} #8618

randall77 opened this issue Aug 29, 2014 · 22 comments
Milestone

Comments

@randall77
Copy link
Contributor

fmt.Fprintf("%d", 8)

Since all interface data fields are now pointers, an int must be allocated and
initialized to 8 so that it can be put in an interface{} to pass to Fprintf.

Since we know the 8 doesn't escape, we could instead allocate that 8 on the stack and
have the interface data word point to that stack slot.  To be safe, we can only do this
when the resulting interface{} doesn't escape.  We probably also need to be sure the
conversion happens at most once so the stack slot is not reused.

We could have a special convT2Enoescape call for the compiler to use when it knows the
result doesn't escape.  Maybe also convT2I, assertT2E, ...
@robpike
Copy link
Contributor

robpike commented Aug 29, 2014

Comment 1:

Status changed to Accepted.

@griesemer
Copy link
Contributor

Comment 2:

Labels changed: added repo-main.

@jeffallen
Copy link
Contributor

This thread explains how this issue causes 2 allocs on every call to os.(*File).Write.
https://groups.google.com/forum/#!topic/golang-nuts/0hfeLJP1LSk

@josharian
Copy link
Contributor

Dmitry started this in CL 3503. Note that this requires improved escape analysis.

@gopherbot
Copy link

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

@navytux
Copy link
Contributor

navytux commented Apr 20, 2017

For the reference until this is fixed some of us use ad-hoc printf-style mini language to do text formatting in hot codepaths without allocations. For example if in fmt speak you have

s := fmt.Sprintf("hello %d %s %x", 1, "world", []byte("data"))

the analog would be

buf := xfmt.Buffer{}
buf .S("hello ") .D(1) .C(' ') .S("world") .C(' ') .Xb([]byte("data"))
s := buf.Bytes()

It is a bit uglier but runs faster and without allocations:

pkg: lab.nexedi.com/kirr/go123/xfmt
BenchmarkFmt-4       5000000           246 ns/op          72 B/op      3 allocs/op
BenchmarkXFmt-4     20000000            57.9 ns/op         0 B/op      0 allocs/op

Details:

https://lab.nexedi.com/kirr/go123/commit/1aa677c8
https://lab.nexedi.com/kirr/go123/blob/c0bbd06e/xfmt/fmt.go

@josharian
Copy link
Contributor

josharian commented Apr 20, 2017

Note that when the arguments are constants, they no longer allocate on tip, so this is a bit better than it was.

@navytux
Copy link
Contributor

navytux commented Apr 20, 2017

@josharian thanks for feedback. For the reference the above benchmark was for tip (go version devel +d728be70f4 Thu Apr 20 01:37:08 2017 +0000 linux/amd64).

@bnjjj
Copy link

bnjjj commented Nov 15, 2017

What are the status about this issue ? Is anyone working on ?

@ianlancetaylor
Copy link
Contributor

@bnjjj I'm not aware of anybody actively working on this.

@rogpeppe
Copy link
Contributor

One data point here. The gio authors are considering an API design choice: whether to use an interface type or a function type. Using the interface type results in nicer code (when there's a literal struct, it can be used directly rather than via a method expression to obtain the function value), but results in allocations, and avoiding allocations is a key consideration in that context.

To illustrate with a couple of small examples:

This program, using a function type, does not incur any allocations. The required closures can all be allocated on the stack. https://play.golang.org/p/FC4taLlhVGz

This equivalent program, using an interface type, incurs an allocation for each interface conversion. https://play.golang.org/p/XPfcNSMPt82

Given that interfaces are often more idiomatic than function types in Go, it would be nice if they could be used interchangeably without a significant performance difference.

@josharian
Copy link
Contributor

As of five years ago(!), this needed escape analysis improvements. Those stalled; see CL 3503. Maybe @mdempsky could weigh in.

fsmv added a commit to fsmv/in.go that referenced this issue Aug 29, 2021
This was quite a struggle to do in a nice way!

1. Due to golang/go#8618
   anything you pass to a fmt.* call gets copied to the heap. Eliminating
   that was simply replacing fmt.Fprintln with the bytes.Buffer calls and
   calling os.Stderr.Write directly.

2. Calling time.Duration.String() unfortunately forces a copy to the
   heap because it returns a string copy of its internal byte slice on
   the stack. So I had to reimplement that in a way that just writes to
   my buffer. The challenge was keeping the implementation under
   100 lines of code. To help with that I skipped the <1s printing case
   the standard lib has. Copying the official implementation and patching
   it would probably result in more efficient code but it is long.
HonoreDB added a commit to HonoreDB/cockroach that referenced this issue Sep 24, 2022
EncodeEscapedChar (which is called in EncodeSQLStringWithFlags)
is pretty optimized, but for escaping a multibyte character it
was using fmt.FPrintf, which means every multibyte character
ended up on the heap due to golang/go#8618.
This had a noticeable impact in changefeed benchmarking.

This commit just hand-compiles the two formatting strings that
were being used into reasonably efficient go, eliminating the allocs.

Benchmark encoding the first 10000 runes shows a 4x speedup:

Before: BenchmarkEncodeNonASCIISQLString-16    	     944	   1216130 ns/op
After: BenchmarkEncodeNonASCIISQLString-16    	    3468	    300777 ns/op

Release note: None
HonoreDB added a commit to HonoreDB/cockroach that referenced this issue Sep 27, 2022
EncodeEscapedChar (which is called in EncodeSQLStringWithFlags)
is pretty optimized, but for escaping a multibyte character it
was using fmt.FPrintf, which means every multibyte character
ended up on the heap due to golang/go#8618.
This had a noticeable impact in changefeed benchmarking.

This commit just hand-compiles the two formatting strings that
were being used into reasonably efficient go, eliminating the allocs.

Benchmark encoding the first 10000 runes shows a 4x speedup:

Before: BenchmarkEncodeNonASCIISQLString-16    	     944	   1216130 ns/op
After: BenchmarkEncodeNonASCIISQLString-16    	    3468	    300777 ns/op

Release note: None
craig bot pushed a commit to cockroachdb/cockroach that referenced this issue Sep 30, 2022
88425: colexec: use tree.DNull when projection is called on null input r=DrewKimball a=DrewKimball

Most projections skip rows for which one or more arguments are null, and just output a null for those rows. However, some projections can actually accept null arguments. Previously, we were using the values from the vec even when the `Nulls` bitmap was set for that row, which invalidates the data in the vec for that row. This could cause a non-null value to be unexpectedly concatenated to an array when an argument was null (nothing should be added to the array in this case).

This commit modifies the projection operators that operate on datum-backed vectors to explicitly set the argument to `tree.DNull` in the case when the `Nulls` bitmap is set. This ensures that the projection is not performed with the invalid (and arbitrary) value in the datum vec at that index.

Fixes #87919

Release note (bug fix): Fixed a bug in `Concat` projection operators for arrays that could cause non-null values to be added to the array when one of the arguments was null.

88671: util: avoid allocations when escaping multibyte characters r=[miretskiy,yuzefovich] a=HonoreDB

EncodeEscapedChar (which is called in EncodeSQLStringWithFlags) is pretty optimized, but for escaping a multibyte character it was using fmt.FPrintf, which means every multibyte character ended up on the heap due to golang/go#8618. This had a noticeable impact in changefeed benchmarking.

This commit just hand-compiles the two formatting strings that were being used into reasonably efficient go, eliminating the allocs.

Benchmark encoding the first 10000 runes shows a 4x speedup:

Before: BenchmarkEncodeNonASCIISQLString-16    	     944	   1216130 ns/op
After: BenchmarkEncodeNonASCIISQLString-16    	    3468	    300777 ns/op

Release note: None

Co-authored-by: DrewKimball <drewk@cockroachlabs.com>
Co-authored-by: Aaron Zinger <zinger@cockroachlabs.com>
blathers-crl bot pushed a commit to cockroachdb/cockroach that referenced this issue Nov 14, 2022
EncodeEscapedChar (which is called in EncodeSQLStringWithFlags)
is pretty optimized, but for escaping a multibyte character it
was using fmt.FPrintf, which means every multibyte character
ended up on the heap due to golang/go#8618.
This had a noticeable impact in changefeed benchmarking.

This commit just hand-compiles the two formatting strings that
were being used into reasonably efficient go, eliminating the allocs.

Benchmark encoding the first 10000 runes shows a 4x speedup:

Before: BenchmarkEncodeNonASCIISQLString-16    	     944	   1216130 ns/op
After: BenchmarkEncodeNonASCIISQLString-16    	    3468	    300777 ns/op

Release note: None
blathers-crl bot pushed a commit to cockroachdb/cockroach that referenced this issue Nov 14, 2022
EncodeEscapedChar (which is called in EncodeSQLStringWithFlags)
is pretty optimized, but for escaping a multibyte character it
was using fmt.FPrintf, which means every multibyte character
ended up on the heap due to golang/go#8618.
This had a noticeable impact in changefeed benchmarking.

This commit just hand-compiles the two formatting strings that
were being used into reasonably efficient go, eliminating the allocs.

Benchmark encoding the first 10000 runes shows a 4x speedup:

Before: BenchmarkEncodeNonASCIISQLString-16    	     944	   1216130 ns/op
After: BenchmarkEncodeNonASCIISQLString-16    	    3468	    300777 ns/op

Release note: None
@thepudds
Copy link
Contributor

thepudds commented Sep 14, 2023

FWIW, I was curious what the current gap is for avoiding allocations with the fmt print function arguments.

As far as I could see, it looks like as of Go 1.21, there are ~6 reasons val escapes here:

 val := 1000
 fmt.Sprintf("%d", val)

I did an exploratory pass on some possible solutions a couple of months ago, which I recently sent as stack of CLs.

Some of the CLs are likely wrong, but part of my hope is that sometimes if someone helps sketch the contours of a problem, then frequently other people are better able to jump in with solutions or their own explorations (whether those "other people" are experts, or just other people who are curious).

Brief summary of the ~6 reasons:

  1. The fmt print methods store the user interface arguments on a pp struct. The pp struct escapes, and the heap can't point to the stack, so the user arguments escape as well. (Sent CL 524938).

  2. reflect.Value.Pointer also causes escapes. (Sent CL 524939).

  3. reflect.Value.Slice also causes escapes. (Sent CL 524940).

  4. Interface conversions and interface methods call like arg.String() in handleMethods also cause the user arguments to escape. This might be the most fundamental reason. (Sent CL 524945 and some related CLs. Matthew Dempsky then said he liked the core idea and he sent an alternative implementation in CL 526520. I also opened #62653 to help discussion on this specific piece).

  5. Within reflect, packEface causes reflect.Value.Interface to escape, which causes the fmt args to escape. (Sent CL 528535).

  6. Also within reflect, method values cause conditional allocation of a methodValue struct, which also causes the fmt args to escape. (Sent CLs 528536, 528537, and 528538. These CLs might be the ugliest).

    • UPDATE: creating a new type of pragma was indeed too ugly, so I abandoned those three CLs and instead sent a hopefully better approach spread across CLs 530095 (runtime), 530096 (compiler), and 530097 (reflect).

By the end of my first-cut stack (as of CL 528538), arguments to Sprintf like the Point struct here no longer get heap allocated:

  type Point struct {x, y int}
  p := Point{1, 2}
  fmt.Sprintf("%v", p)

Some of those CLs are more-or-less shots in the dark, but I tried to put some context in the CL descriptions and elsewhere in the hopes of other gophers jumping in with alternative solutions (or suggestions for corner cases to test, or questions, or ideas for improvement and so on...).

The CLs all pass all.bash and pass the older TryBots (but hit some LUCI-specific issues with the new TryBots).

If you are new to the escape analysis code:

  • The best place to start is probably Matthew Dempsky's nice introduction in escape.go.
  • I tried to add some additional general explanation of how escape analysis currently works, including via some examples here and at the start of here.
  • For the interface method challenges, I tried to give some narrative examples here with the results reflecting the new behavior. Also, the CL 524945 commit message attempts to explain how escape analysis arrives at its result for interface method calls in Go 1.21 and earlier. (Definitely room for improvement in those explanations 😅).

@gopherbot
Copy link

Change https://go.dev/cl/524938 mentions this issue: fmt: avoid storing input arguments on pp to help escape analysis

@gopherbot
Copy link

Change https://go.dev/cl/528535 mentions this issue: reflect: leak packEface input to result rather than heap

@gopherbot
Copy link

Change https://go.dev/cl/530095 mentions this issue: runtime: manually represent reflect.methodValue in stack map for methodValueCall assembly

@gopherbot
Copy link

Change https://go.dev/cl/530096 mentions this issue: cmd/compile/internal/escape: recognize more self-assignment patterns

@gopherbot
Copy link

Change https://go.dev/cl/530097 mentions this issue: reflect: avoid always escaping in Value.Interface

@gopherbot
Copy link

Change https://go.dev/cl/524944 mentions this issue: cmd/compile/internal/escape: reserve space in leaks encoding for interface receiver data

@gopherbot
Copy link

Change https://go.dev/cl/524945 mentions this issue: cmd/compile/internal/escape: analyze receivers in interface method calls

@gopherbot
Copy link

Change https://go.dev/cl/528539 mentions this issue: cmd/compile/internal/escape: propagate method usage for analyzing receivers in interface method calls

@gopherbot
Copy link

Change https://go.dev/cl/524937 mentions this issue: cmd/compile/internal/escape: make escape analysis -m=2 logs more accessible

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

No branches or pull requests