Thanks for this.

If it's not in the first postings, I would expect seek() to examine further postings until it finds one with the target or reaches the end.

I expect it still works in your implementation because you're calling it from a loop that will call it again. But this is not the standard behaviour of seek(). Maybe calling it something else would be fine.

I'll rename it to seekHead or updateHead to make it clear it's only operating on the top element. ig seekHead sounds better?

I'll rename it to seekHead or updateHead to make it clear it's only operating on the top element. ig seekHead sounds better?

Yes, ok with seekHead.

BTW there is a tool benchstat which will analyze the differences before and after.
https://pkg.go.dev/golang.org/x/perf/cmd/benchstat

I created a reproduction benchmark BenchmarkLabelValues_SlowPath

Why not use BenchmarkLabelValuesWithMatchers ?

If you have a good reason to need a new benchmark, please include this in your PR.

I created a reproduction benchmark BenchmarkLabelValues_SlowPath

Why not use BenchmarkLabelValuesWithMatchers ?

If you have a good reason to need a new benchmark, please include this in your PR.

the existing one covers the high-overlap case (like 90% match) where Next() already flies, so it wouldn't catch this regression. The new one specifically hits that "sparse" case where the matcher is way ahead, which was causing the timeouts in #14551. Figured it's worth keeping to lock in the fix for that scenario.

I have now studied the actual algorithmic change you made; it's a great find. Thanks again.
I can fix up the cosmetic stuff if you don't have time. Let me know.

I have now studied the actual algorithmic change you made; it's a great find. Thanks again. I can fix up the cosmetic stuff if you don't have time. Let me know.

Happy to know u liked the changes, i would like to modify the stuff on my own this time although it might take 3-4hrs as am currently engaged with one thing but surely i will do it

hey @bboreham i renamed seek to seekHead so it's less confusing, and I nuked that unused next() method entirely (plus updated the tests to use seekHead instead).
Also tidied up the comments and fixed a few lint issues in the benchmark file while I was at it. The benchmark itself is now properly set up for dense candidates (100k series for one label value), and the results are looking solid~846ns/op.

I have now studied the actual algorithmic change you made; it's a great find. Thanks again. I can fix up the cosmetic stuff if you don't have time. Let me know.

Hey @bboreham, just a reminder to check out this PR

the existing one covers the high-overlap case (like 90% match) where Next() already flies, so it wouldn't catch this regression.

I get a pretty good speedup on the existing benchmark:

goos: darwin
goarch: arm64
pkg: github.com/prometheus/prometheus/tsdb
cpu: Apple M2
                          │   before    │               after                │
                          │   sec/op    │   sec/op     vs base               │
LabelValuesWithMatchers-8   2.718m ± 4%   1.408m ± 3%  -48.20% (p=0.002 n=6)

But yours is a bigger percentage:

                       │     before     │               after                │
                       │     sec/op     │   sec/op     vs base               │
LabelValues_SlowPath-8   919901.0n ± 2%   836.6n ± 2%  -99.91% (p=0.002 n=6)