tsdb: faster postings sort with generic slices.Sort#11054
Merged
codesome merged 1 commit intoprometheus:mainfrom Sep 30, 2022
Merged
tsdb: faster postings sort with generic slices.Sort#11054codesome merged 1 commit intoprometheus:mainfrom
codesome merged 1 commit intoprometheus:mainfrom
Conversation
Member
|
/prombench main |
Contributor
|
Benchmark tests are running for 3 days! If this is intended ignore this message otherwise you can cancel it by commenting: |
Member
|
/prombench cancel |
Contributor
|
Benchmark cancel is in progress. |
762754f to
ca3fe69
Compare
Member
Author
|
CI is failing on Windows with an error I can't believe is connected to this change: This appears to the same as described in #10368. |
Member
|
Hmmm, lint is failing for unrelated change as well. Looks like a simple fix of getting rid of a type. Would you be able to do it in this PR? Thanks! |
Use new experimental package `golang.org/x/exp/slices`. Some of the speedup comes from comparing SeriesRef (which is an int64) directly rather than through an interface `.Less()` call; some comes from exp/slices using "pattern-defeating quicksort(pdqsort)". Signed-off-by: Bryan Boreham <bjboreham@gmail.com>
ca3fe69 to
b834de1
Compare
Member
Author
|
I fixed the lint error. |
codesome
approved these changes
Sep 30, 2022
charleskorn
added a commit
to grafana/mimir
that referenced
this pull request
Dec 12, 2022
#3639 (comment), prometheus/prometheus#11054, and prometheus/prometheus#11318 all show substantial performance improvements when using slices.Sort over sort.Strings. I've also added a linting rule to catch usage of sort.Strings and sort.Ints in the future. (We don't currently use sort.Ints anywhere.) We could also replace sort.Float64s with slices.Sort, however, this requires more careful consideration as the documentation for slices.Sort warns that it may not handle NaN values correctly.
charleskorn
added a commit
to grafana/mimir
that referenced
this pull request
Dec 15, 2022
#3639 (comment), prometheus/prometheus#11054, and prometheus/prometheus#11318 all show substantial performance improvements when using slices.Sort over sort.Strings. I've also added a linting rule to catch usage of sort.Strings and sort.Ints in the future. (We don't currently use sort.Ints anywhere.) We could also replace sort.Float64s with slices.Sort, however, this requires more careful consideration as the documentation for slices.Sort warns that it may not handle NaN values correctly.
pracucci
pushed a commit
to grafana/mimir
that referenced
this pull request
Dec 15, 2022
* Use slices.Sort instead of sort.Strings or sort.Ints. #3639 (comment), prometheus/prometheus#11054, and prometheus/prometheus#11318 all show substantial performance improvements when using slices.Sort over sort.Strings. I've also added a linting rule to catch usage of sort.Strings and sort.Ints in the future. (We don't currently use sort.Ints anywhere.) We could also replace sort.Float64s with slices.Sort, however, this requires more careful consideration as the documentation for slices.Sort warns that it may not handle NaN values correctly. * Remove unnecessary comment. * Rename benchmarks file. * Add benchmark for BinaryReader.LabelNames(). * Add benchmark for LabelValues(). * Modify mergeExemplarQueryResponses benchmark to exercise merging exemplars with different sets of labels.
masonmei
pushed a commit
to udmire/mimir
that referenced
this pull request
Dec 16, 2022
…fana#3690) * Use slices.Sort instead of sort.Strings or sort.Ints. grafana#3639 (comment), prometheus/prometheus#11054, and prometheus/prometheus#11318 all show substantial performance improvements when using slices.Sort over sort.Strings. I've also added a linting rule to catch usage of sort.Strings and sort.Ints in the future. (We don't currently use sort.Ints anywhere.) We could also replace sort.Float64s with slices.Sort, however, this requires more careful consideration as the documentation for slices.Sort warns that it may not handle NaN values correctly. * Remove unnecessary comment. * Rename benchmarks file. * Add benchmark for BinaryReader.LabelNames(). * Add benchmark for LabelValues(). * Modify mergeExemplarQueryResponses benchmark to exercise merging exemplars with different sets of labels.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
4 participants
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
Update go.mod to mandate Go 1.18 semantics so we can use generics. This will impact anyone using Prometheus as a library who has not already updated to Go 1.18.Edit: this was done by #11279.Use new experimental package
golang.org/x/exp/slices.For either of the above reasons you might not want to accept the change, but I thought the difference was striking.
Some of the speedup comes from comparing
SeriesRef(which is an int64) directly rather than through an interface.Less()call; some comes from exp/slices using "pattern-defeating quicksort(pdqsort)" which is much better on already-sorted data.Also we don't need the funky trick from #10500.
Across Prometheus there are many other calls to
sort; I think all thesort.Stringsandsort.Intswill benefit from the same change, but I don't often see them show up in profiles. Anyway I thought I'd post this one as a start.