These are chat archives for HdrHistogram/HdrHistogram

12th
Jun 2017
Gil Tene
@giltene
Jun 12 2017 11:32
A way to look at the problem is this:
When determining the proper count at a percentile, we will often (usually?) end up with a non-integer count. It makes sense to round the count UP to the nearest integer, because the value that includes the count we are "in" (e.g. count 6 when the percentile math shows 5.01 or 5.99) is still "within" the set of values that are <= the percentile we are looking for.
Gil Tene
@giltene
Jun 12 2017 11:38
This effects outcome when the choice between rounding the count up or down translates to falling in different value sub-buckets.
So rounding UP makes sense.
However, due to fp math accuracy issues, a count computation result that should be a perfect integer will sometimes end up as an fp value that is 1 ulp higher than that integer.
E.g. (((100.0 19961)/20000) / 100.0) 20000) = 19961.000000000004
Which is 1 ulp higher than the 19961 integer it would be equal to in ideal world.
Gil Tene
@giltene
Jun 12 2017 11:44
When rounding UP, this potential 1 ulp overvalue makes the resulting count potentially 1 integer unit higher than it is. And that can result in an incorrect value fir the percentile (a value that is larger than any that the percentile falls within).
My solution is to round UP only values that are MORE than 1 ulp higher than the nearest integer, but to round down otherwise. This is an imperfect solution. Arguably no more correct than the previous round-to-nearest situation, since there are values (the ones that would properly fall within that 1 ulp and should have been rounded up) for which the percentile value will still be underestimated.
But this solution is "better" in that situations where the value at a percentile is "too low" are significantly reduced, while the value is never "too high".
Gil Tene
@giltene
Jun 12 2017 11:51
It allows me to claim (correctly I think) that the returned value result is correct for the [percentile given +/- 1 ulp] (the +/- being on the percentile input, not the resulting value).
Gil Tene
@giltene
Jun 12 2017 11:58
Since this solution is imperfect tho, is love to see if there is some better way to do this. One that would be correct for both the 99.805% of 20000 (which should round to 19961 and not "up" to 19962) and for the 50.00000000000001% of 2 (which should have rounded to 2 and not down to 1).
Can any of you see some math that will meet these two at the same time?