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

Another heap sort improvement? #39676

Closed
Windsooon opened this issue Jun 18, 2020 · 5 comments
Closed

Another heap sort improvement? #39676

Windsooon opened this issue Jun 18, 2020 · 5 comments

Comments

@Windsooon
Copy link

@Windsooon Windsooon commented Jun 18, 2020

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

$ go version
go version go1.12.5 darwin/amd64

Does this issue reproduce with the latest release?

Yes

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

go env Output
$ go env
GOARCH="amd64"
GOOS="darwin"

What did you do?

The heap data structure implemented in src/sort/sort.go, src/container/heap/heap.go and src/runtime/time.go. There are two opened PRs trying to improve the heap sort already and they are doing the same thing.

PR1
PR2

What did you expect to see?

At this moment, there is no PR for src/runtime/time.go, (for the siftupTimer() function). Should we create another similar PR as before or we can somehow just maintain one version of the heap then use it anywhere?

@martisch
Copy link
Contributor

@martisch martisch commented Jun 18, 2020

The runtime wont likely be made depedent on any other package unless its very low dependency and doesnt generate a lot of init work (or needs complex init work). e.g. internal/cpu or internal/bytealg are fine.

The other way around sort and container cant import a runtime function unless it is exported which runtime likely wont for a heap data structure.

This leaves making a new internal/heap package.

The runtime siftupTimer however doesnt use the sorting interface (Swap and Less) and shouldnt to avoid the overhead. There might be an opportunity to use a generic heap package once generics are available but even there its unclear whether this could introduce a performance regression depending on the generics implementation used.

For http://golang.org/cl/237437 I am not sure the added code is a good fit for the sort package as it will be triggered not very often.

If the improvements on runtime timers can be shown to have a good performance impact on timer benchmarks I would encourage to just send a concrete change list that just changes the runtime implementation for review.

@andybons
Copy link
Member

@andybons andybons commented Jun 18, 2020

Hi there,

Unlike many projects, the Go project does not use GitHub Issues for general discussion or asking questions. GitHub Issues are used for tracking bugs and proposals only.

For asking questions, see:

Please ask the question on one of the above forums.

(Quoted from https://golang.org/wiki/Questions)

@andybons andybons closed this Jun 18, 2020
@Windsooon
Copy link
Author

@Windsooon Windsooon commented Jun 18, 2020

@andybons Thank you for pointing it out. I can submit a PR for the src/runtime/time.go. However, maintain several parts of the heap data structure seems not a good idea that is why I want to discuss it before submitting a PR. Maybe I should ask this at The Go Forum?

PR request based on the comment from @Brad Fitzpatrick

Btw, have you looked to see whether the runtime's heap implementation is optimal?
Because speed-ups there affect all programs (all timers, of which real programs have many).

@davecheney
Copy link
Contributor

@davecheney davecheney commented Jun 18, 2020

@Windsooon one of the Go proverbs is "a little copying is better than a little dependency". This advice applies strongly within the runtime and the standard library because it is easy to create import loops -- we even have tooling inside the bootstrap process to catch new inter package dependencies.

I would advise if you are looking to reduce the number of heap sort implementations in the runtime to consider; are these implementations identical? do they take the same inputs? do the have the same guarantees with regards to stability? do they have the same performance requirements? do they operate allocation free, or can they generate temporary allocations -- this is something which cannot happen inside the runtime.

Is the engineering effort spent to make your change, review it, and then the maintenance of having to use a shared code path in the future justified by the reduction in lines of code, or number of implementations.

I don't wish to discourage you from contributing to the project, but I would suggest that this particular area may not be the best place to start.

@Windsooon
Copy link
Author

@Windsooon Windsooon commented Jun 18, 2020

@davecheney Thank you. I agreed with you. I would spend some time to understand the project before submit the PR.

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

Successfully merging a pull request may close this issue.

None yet
4 participants
You can’t perform that action at this time.