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.

Sign up for GitHub

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

Replace ListPostings.Seek's binary search call by the generic slices.BinarySearch #14393

Merged
merged 2 commits into from
Jul 2, 2024
Merged

Replace ListPostings.Seek's binary search call by the generic slices.BinarySearch #14393

merged 2 commits into from
Jul 2, 2024

Conversation

colega
Copy link
Contributor

@colega colega commented Jul 2, 2024 •
edited
Loading

This is a hot path, and I saw it taking a while on some profiles.

First, I inlined the call, then on @bboreham suggestion I tried the generic version of the search, which turned out to be even faster (for some reason).

goos: darwin
goarch: arm64
pkg: github.com/prometheus/prometheus/tsdb/index
                           │    main     │               inlined               │               generic               │
                           │   sec/op    │   sec/op     vs base                │   sec/op     vs base                │
Intersect/LongPostings1-12   30.38µ ± 1%   14.25µ ± 3%  -53.10% (p=0.000 n=10)   11.70µ ± 1%  -61.49% (p=0.000 n=10)
Intersect/LongPostings2-12   43.31m ± 2%   42.73m ± 2%        ~ (p=0.063 n=10)   43.35m ± 3%        ~ (p=0.315 n=10)
Intersect/ManyPostings-12    131.9m ± 2%   126.6m ± 2%   -4.04% (p=0.000 n=10)   133.7m ± 1%    1.41% (p=0.004 n=10)
geomean                      5.578m        4.255m       -23.71%                  4.078m       -26.88%

@colega colega requested a review from jesusvazquez as a code owner July 2, 2024 11:18
@colega colega changed the title Inline ListPostings.Seek's binary search call Replace ListPostings.Seek's binary search call by the generic slices.BinarySearch Jul 2, 2024
@colega
Copy link
Contributor Author

colega commented Jul 2, 2024

@bboreham also pointed out that it might help checking the immedately next posting before doing the complete binary search, as many intersect operations are realized on postings that are a subset of each other. I would like to do that in a follow up PR.

bboreham
bboreham approved these changes Jul 2, 2024
View reviewed changes
Copy link
Member

@bboreham bboreham left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Good find!

@bboreham bboreham merged commit 726ed12 into prometheus:main Jul 2, 2024
25 checks passed
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@bboreham bboreham bboreham approved these changes

@jesusvazquez jesusvazquez Awaiting requested review from jesusvazquez jesusvazquez is a code owner

Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

Successfully merging this pull request may close these issues.
2 participants
@colega @bboreham