promql(histogram): apply kahan summation algorithm to native histograms #14325
Conversation
|
I don't handle I don't apply Kahan summation algorithm to other operations, i.e., subtraction, multiplication, and division. |
79f52ae to
0b472a8
Compare
|
Sorry, I will only get to this next week. |
0b472a8 to
56b0f37
Compare
Signed-off-by: Zhang Zhanpeng <zhangzhanpeng.zzp@alibaba-inc.com>
56b0f37 to
0898d62
Compare
There was a problem hiding this comment.
Thank for doing this, but as said in the comments below, we need Kahan summation for all the fields of the histogram that are involved in a summation.
We also don't want additional fields in the FloatHistogram struct as this struct is already big enough.
This is definitely not as easy as it might have looked. I'll try to write down a few ideas later.
| @@ -30,6 +30,8 @@ import ( | |||
| type FloatHistogram struct { | |||
| // Counter reset information. | |||
| CounterResetHint CounterResetHint | |||
| // KahanSumHint runs compensation for lost low-order bits. | |||
| KahanSumHint float64 | |||
There was a problem hiding this comment.
I don't think we should add a field to every single histogram. It takes another 8 bytes for every histogram, including those that never need the summation.
Also, just one Kahan hint isn't enough, see below.
| y := other.Sum - h.KahanSumHint | ||
| t := h.Sum + y | ||
| h.KahanSumHint = (t - h.Sum) - y | ||
| h.Sum = t |
There was a problem hiding this comment.
Note that there already is a function kahanSumInc in promql/engine.go. (Which cannot simply be used here because it would cause a circular package dependency. Let's discuss that later.)
More importantly: This only handles the Sum field, but Kahan summation should be used on all the fields that get added up. I think we need a very different approach here.
|
Broadly, I believe we need an equivalent of the Maybe it could be a method for Once we have this, we can use the new @KofClubs as alluded to above, this is way harder than anticipated. It would be totally OK if you preferred to tackle a more light-weight issue first. |
|
I'm closing this PR as the approach we have to take will be quite different and should probably happen in a separate PR, see comments above. |
|
Ah, I'm actually still working on this issue. I shall open a new PR later:) |
Related to #14105