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: avoid allocations for some return values #22081

Open
crawshaw opened this Issue Sep 28, 2017 · 3 comments

Comments

Projects
None yet
5 participants
@crawshaw
Contributor

crawshaw commented Sep 28, 2017

A non-inlinable function that returns new memory always allocates it on the heap. For example, in the base64 package the DecodeString method returns a heap-allocated byte slice:

func (enc *Encoding) DecodeString(s string) ([]byte, error)

It is common for this return value to have limited life, easily scoped to the stack:

b, err := enc.DecodeString(s)
if err != nil { ... }
data = append(data, b...)

For cases like this, the DecodeString method could have been made more efficient by writing in a style where the []byte was passed as an argument:

func (enc *Encoding) AppendDecodeString(out []byte, s string) ([]byte, error)

No heap allocation is necessary for calling this version. This transformation has been manually applied in many places in the standard library, from the Append* functions in strconv to io.Reader itself.

The compiler could do this automatically.

For concrete methods, the original function signature can be satisfied by a wrapper function, that allocates the value on the heap and calls a variant where return values containing pointers are passed as "out" arguments. When compiling code that can keep the output on the stack, the caller can be modified to use the generated functions.

For example, the implementation of DecodeString is:

func (enc *Encoding) DecodeString(s string) ([]byte, error) {
        dbuf := make([]byte, enc.DecodedLen(len(s)))
        n, _, err := enc.decode(dbuf, []byte(s))
        return dbuf[:n], err
}       

Currently, escape analysis determines that dbuf escapes to the heap without ever seeing how the value is used. Instead, the compiler can split this function in two, an inlinable allocation function, and a body:

func (enc *Encoding) ΨDecodeString(s string) []byte {
        return make([]byte, enc.DecodedLen(len(s)))
}

func (enc *Encoding) ΦDecodeString(s string, dbuf *[]byte) error {
        n, _, err := enc.decode(*dbuf, []byte(s))
        *dbuf = dbuf[:n]
        return err
}

func (enc *Encoding) DecodeString(s string) ([]byte, error) {
        out := enc.ΨDecodeString(s) // inlined
        err := enc.ΦDecodeString(s, &out)
        return out, err
}

Then the compiler can transform callers of DecodeString where the return value would fit on the stack to two calls to ΨDecodeString and ΦDecodeString. The first is inlined, determined not to escape and so dbuf lives on the stack.

The general analysis of can the Ψ allocation function be inlined, and how does it pass data dependencies to the Φ function could get complicated.

@mvdan

This comment has been minimized.

Member

mvdan commented Sep 28, 2017

Has there been research into whether the extra compiler work would be worth it? Don't get me wrong - this would be great - just wondering if it has been taken into account.

Also, would this be transitive, e.g. also work through multiple calls instead of just one?

@crawshaw

This comment has been minimized.

Contributor

crawshaw commented Sep 28, 2017

I haven't done any research on how it would affect compiler time, or how often it would trigger. I suspect the easiest way to answer both would be to build a prototype. (I don't intend to anytime soon, just wanted to write the idea down.)

As described, I believe it would work through multiple calls. The Ψ-function would be inlined into the intermediate function, and a new Ψ-function for that intermediate function would be extracted from the inlined body. A lot would depend on inlining at the right time.

@mvdan mvdan added the Performance label Sep 28, 2017

@valyala

This comment has been minimized.

Contributor

valyala commented Sep 30, 2017

As for Append*-style functions for encoding/base64 package, see the proposal #19366

@ianlancetaylor ianlancetaylor added this to the Go1.11 milestone Mar 29, 2018

@bradfitz bradfitz modified the milestones: Go1.11, Unplanned May 18, 2018

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