cmd/compile: better optimization/inlining for sort.Search

[yangwenmai]

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

$ go version
go 1.15.6

Does this issue reproduce with the latest release?

go 1.15.6

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

go env Output

$ go env

What did you do?

When I use a helper func SearchLineInfos() and SearchFiles similar as searchInts(), I test those func benchmark

benchmark result:

name               old time/op  new time/op  delta
SearchLineInfos-8  20.7ns ±19%   6.0ns ± 2%  -70.98%  (p=0.000 n=10+10)
SearchFiles-8      9.48ns ±19%  3.22ns ± 1%  -66.05%  (p=0.000 n=10+8)

CL: https://go-review.googlesource.com/c/go/+/279447

What did you expect to see?

In position.go, we impl helper func for sort.Search.

What did you see instead?

if i := sort.Search(len(f.lines), func(i int) bool { return f.lines[i] > offset }) - 1; i>= 0 {
	line, column = i+1, offset-f.lines[i]+1
}

...

Remove func searchInts(a []int, x int) int

cc @mdempsky

[mdempsky]

So sort.Search is a relatively simple function that takes a function argument and then calls it at exactly one call site. The compiler should be able to discount the cost of inlining when sort.Search is called with an inlinable function.

[dr2chase]

It's a good idea, but has there been any progress on this? I.e., can we move it to the 1.19 milestone?

A "modest proposal" for how we might approach this in general -- if a function f takes a function-valued parameter g, bump the threshold for possibly inlining f (more detail -- if g is passed to f and f calls g). If (1) that new threshold puts f into the maybe-inline category and (2) an inlineable g is passed to f at a particular call site, then do the inlining.

[mknyszek]

Since there hasn't been any movement since 2020 at this point, I think it's fine to put this in the backlog, personally.

[dr2chase]

I'd rather re-milestone to 1.19; the hack I contrived above, might just work, likely to have low impact, and improving sort performance would float a lot of boats.

[ianlancetaylor]

@dr2chase Should this to move to Backlog? To 1.20 milestone?

[dr2chase]

Bump it to 1.20, and I should pay more attention. Assign it to me, maybe.