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: make the inliner assign unsafe conversions lower costs #42739

Closed
cespare opened this issue Nov 20, 2020 · 8 comments
Closed

cmd/compile: make the inliner assign unsafe conversions lower costs #42739

cespare opened this issue Nov 20, 2020 · 8 comments

Comments

@cespare
Copy link
Contributor

cespare commented Nov 20, 2020

What version of Go are you using (go version)?

go version go1.15.5 linux/amd64

I also tested with tip.

Does this issue reproduce with the latest release?

Yes

What operating system and processor architecture are you using (go env)?

linux/amd64

Details

I have a hash function with an assembly implementation. The function accepts a []byte, but I also supply a string version of the function which accepts a string. In order to avoid copying the string (#2205) the wrapper function does an unsafe []byte to string conversion:

func Sum64String(s string) uint64 {
	var b []byte
	bh := (*reflect.SliceHeader)(unsafe.Pointer(&b))
	bh.Data = (*reflect.StringHeader)(unsafe.Pointer(&s)).Data
	bh.Len = len(s)
	bh.Cap = len(s)
	return Sum64(b)
}

Unfortunately, this trivial function is assigned a cost of 91 by the inliner, which exceeds the budget of 80. This seems unreasonably high to me. I suspect it's to do with the syntactic complexity of using unsafe, which has the appearance of a bunch of function calls/conversions even though it compiles down to nearly nothing.

#17566 is a general issue for overhauling the inliner's cost model. It's not clear if/when that might happen, though.

In the meantime, would it make sense to special-case unsafe conversions in the inliner?


The partial workaround I came up with to trick the inliner (see cespare/xxhash#50) is demonstrated by this repro code (play link):

package main

import (
	"fmt"
	"reflect"
	"unsafe"
)

func main() {
	s := "hello"
	fmt.Println(myHashString(s))
	fmt.Println(myHashString2(s))
}

func myHashString(s string) uint64 {
	// This is the obvious way to write the unsafe conversion, but the
	// inliner assigns it a cost of 91 (threshold is 80).
	var b []byte
	bh := (*reflect.SliceHeader)(unsafe.Pointer(&b))
	bh.Data = (*reflect.StringHeader)(unsafe.Pointer(&s)).Data
	bh.Len = len(s)
	bh.Cap = len(s)
	return myHash(b)
}

func myHashString2(s string) uint64 {
	// This alternative approach has fewer syntactical elements and it just
	// barely makes this function inlineable (it has a cost of exactly 80).
	var b []byte
	(*sliceHeader)(unsafe.Pointer(&b)).s = s
	(*sliceHeader)(unsafe.Pointer(&b)).cap = len(s)
	return myHash(b)
}

// sliceHeader is similar to reflect.SliceHeader, but it assumes that the layout
// of the first two words is the same as the layout of a string.
type sliceHeader struct {
	s   string
	cap int
}

//go:noinline
func myHash(b []byte) uint64 {
	// Pretend this is an optimized hash function with an asm implementation
	// (so not inlineable).
	return 10
}

Unfortunately, that only works for one of the two functions I wish to inline. The other one has a slightly higher cost and I can't get the inliner to assign a weight less than 84.

/cc @mdempsky @dr2chase @randall77 @josharian

@mdempsky
Copy link
Member

It's past the Go 1.16 freeze, so I don't foresee us fixing this for Go 1.16. Maybe for Go 1.17.

But for Go 1.17, we'll also have unsafe.Slice (#19367), which would be considered cheap. Would using that in Go 1.17 suffice for your use cases?

@cespare
Copy link
Contributor Author

cespare commented Nov 20, 2020

But for Go 1.17, we'll also have unsafe.Slice (#19367), which would be considered cheap. Would using that in Go 1.17 suffice for your use cases?

Oh yeah, I forgot about that.

It might help here. I checked out your CL 202080 to give it a spin.

I'm probably being dense, but I wasn't able to find a particularly convenient way to use unsafe.Slice to convert a string to a []byte. Best I could come up with was this monstrosity:

p := (*byte)(unsafe.Pointer((*reflect.StringHeader)(unsafe.Pointer(&s)).Data))
b := unsafe.Slice(p, len(s))

Am I missing something?

Nevertheless, the function I wrote using that conversion was inlined. I don't know what the actual cost was, unfortunately.

Edit: That's because CL 202080 is pretty old now and it predates the better -m=2 output. The following was incorrect:

It seems like sometime after Go 1.15 the -gcflags='-m -m' output stopped including the cost of functions that actually were inlined. I mean text like this (this emitted by 1.15.5):

can inline xxx with cost 70 as: func([]byte) uint64 { s := *(*string)(unsafe.Pointer(&b)); return myHashString(s) }

(Should I file a separate bug?)

@mdempsky
Copy link
Member

I'm probably being dense, but I wasn't able to find a particularly convenient way to use unsafe.Slice to convert a string to a []byte.

Yeah, the accepted unsafe.Slice proposal does not include a way to to get the raw pointer from a string. You still need to use reflect.SliceHeader for that under the currently accepted proposals for Go 1.17.

(The original proposal allowed this though, using the proposed unsafe.String type and conversions.)

It seems like sometime after Go 1.15 the -gcflags='-m -m' output stopped including the cost of functions that actually were inlined.

CL 202080 is from 2019, so it's based on ~1.13 code. It looks like it predates the "with cost" debugging addition for -m=2.

But if I'm mistaken and you can reproduce that failure at tip, then yes, please file an issue.

@cespare
Copy link
Contributor Author

cespare commented Nov 20, 2020

CL 202080 is from 2019, so it's based on ~1.13 code. It looks like it predates the "with cost" debugging addition for -m=2.

I was mistaken about this. You are exactly right.

@josharian
Copy link
Contributor

@cespare to maybe unblock you now, this has cost 70:

func myHashString2(s string) uint64 {
	return myHash(*(*[]byte)(unsafe.Pointer(&sliceHeader{s, len(s)})))
}

Untested, but should work. (Btw, sliceHeader is a nice/horrible trick.)

@cespare
Copy link
Contributor Author

cespare commented Nov 20, 2020

@josharian thanks! That helps -- now I can get both of my functions inlined.

(I'd been discounting methods that don't start by declaring var b []byte thinking that they would violate the unsafe rules, but thinking about it more carefully your version is fine because &sliceHeader{s, len(s)} is a safe expression and then the conversion is just an application of rule 1. That's different from using a reflect.SliceHeader where the pointer is a uintptr.)

@cespare
Copy link
Contributor Author

cespare commented Nov 20, 2020

I went looking for more places where this optimization would apply.

I found many instances of unsafe conversions like this, but very few where the underlying function looked like a candidate for inlining. (In a big private codebase, for instance, many of the unsafe conversions are casting large arrays, such as when loading data with mmap, but these functions aren't small and they aren't being called in a hot loop.)

The closest example I found was a function which works around the issue that strconv.ParseInt(string(b)) allocates (that is #2632):

func ParseIntBytes(b []byte, base, bitSize int) (int64, error) {
	var s string
	sh := (*reflect.StringHeader)(unsafe.Pointer(&s))
	sh.Data = (*reflect.SliceHeader)(unsafe.Pointer(&b)).Data
	sh.Len = len(b)
	n, err := strconv.ParseInt(s, base, bitSize)
	if err != nil {
		// (fixNumError copies the underlying string to make this safe)
		return 0, fixNumError(err, b)
	}
	return n, nil
}

This has a weight of 125 in the inliner currently and I can't get it below 109 using the sort of tricks we used above. However, based on some experiments I did with mutating this function I'm guessing that even if the unsafe conversion were very low-cost, the function would still have an overall cost higher than 80.

My intuition now is that the only cases where my proposed optimization would matter are very similar to my code: a thin wrapper around a hash function (or similar) which has a []byte-to-string or string-to-[]byte conversion. And there is a workaround, so this isn't much worse than other cases where we write code in a certain way to appease the inliner.

Given that, I'll close this issue. I think that #2205 would be the better fix anyway, since it would mean we don't need unsafe conversions in the first place. There has been a tiny bit of activity on #2205 recently so perhaps it will see movement in the next few years.

@cespare
Copy link
Contributor Author

cespare commented Dec 2, 2022

In case someone looks at this later, the situation is a little improved as of Go 1.20. The inliner has changed a bit and assigns slightly lower costs to these functions, and additionally the new way to write this conversion which would be the most natural and concise would use unsafe.Slice and unsafe.StringData.

func myHashString3(s string) uint64 {
	// @josharian's idea from above.
	return myHash(*(*[]byte)(unsafe.Pointer(&sliceHeader{s, len(s)})))
}

func myHashString4(s string) uint64 {
	// New best way to do this in Go 1.20+.
	return myHash(unsafe.Slice(unsafe.StringData(s), len(s)))
}

Here are the numbers I get on tip:

  • myHashString has a cost of 87 (still can't be inlined)
  • myHashString2 has a cost of 76
  • myHashString3 has a cost of 68
  • myHashString4 has a cost of 65

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

No branches or pull requests

4 participants