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

Jump to bottom

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

Open
yangwenmai opened this issue Dec 29, 2020 · 6 comments
Open

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

yangwenmai opened this issue Dec 29, 2020 · 6 comments
Assignees
@mdempsky @dr2chase
Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FeatureRequest NeedsFix The path to resolution is known, but the work has not been done. Performance
Milestone
Backlog

Comments

@yangwenmai
Copy link
Contributor

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
@yangwenmai yangwenmai changed the title go/token: maybe we an improve compiler smarter about inlining sort.Search go/token: maybe we can improve compiler smarter about inlining sort.Search Dec 29, 2020
@mdempsky mdempsky self-assigned this Dec 29, 2020
@mdempsky mdempsky added FeatureRequest NeedsFix The path to resolution is known, but the work has not been done. Performance labels Dec 29, 2020
@mdempsky mdempsky added this to the Go1.17 milestone Dec 29, 2020
@mdempsky mdempsky changed the title go/token: maybe we can improve compiler smarter about inlining sort.Search cmd/compile: better optimization/inlining for sort.Search Dec 29, 2020
@mdempsky
Copy link
Member

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.

@mdempsky mdempsky modified the milestones: Go1.17, Go1.18 Apr 29, 2021
@dr2chase
Copy link
Contributor

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
Copy link
Contributor

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
Copy link
Contributor

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.

@dr2chase dr2chase modified the milestones: Go1.18, Go1.19 Nov 12, 2021
@ianlancetaylor
Copy link
Contributor

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

@dr2chase
Copy link
Contributor

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

@seankhliao seankhliao modified the milestones: Go1.19, Go1.20 Jun 24, 2022
@gopherbot gopherbot added the compiler/runtime Issues related to the Go compiler and/or runtime. label Jul 13, 2022
@aclements aclements modified the milestones: Go1.20, Backlog Nov 8, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees

@mdempsky mdempsky

@dr2chase dr2chase

Labels
compiler/runtime Issues related to the Go compiler and/or runtime. FeatureRequest NeedsFix The path to resolution is known, but the work has not been done. Performance
Projects
Go Compiler / Runtime
Status: Triage Backlog
Release Status & Release Blockers
Status: No status
Milestone
Backlog
Development

No branches or pull requests
8 participants
@mdempsky @mknyszek @yangwenmai @dr2chase @aclements @ianlancetaylor @gopherbot @seankhliao