tdigest icon indicating copy to clipboard operation
tdigest copied to clipboard

Fix OOB access in Quantile()

Open hdrodz opened this issue 2 years ago • 1 comments

Fixes #22. (*TDigest).Quantile() causes an OOB panic when the digest has been provided with values that, due to floating point arithmetic errors, cause the sort.Search call to not find an i such that t.cumulative[i] >= index. (Minimal playground reproduction). This PR fixes this bug by clamping access to processed.Len().

Furthermore, the unit tests as written did not pass on my M2 MacBook Pro: due to differences in how the M2 performs floating point math compared to Intel or AMD CPUs, there are small deltas some 14 digits into the results, so got == tt.expected evaluates to false:

$ go test
--- FAIL: TestTdigest_Quantile (0.00s)
    --- FAIL: TestTdigest_Quantile/uniform_50 (0.00s)
        tdigest_test.go:217: unexpected quantile 0.500000, got 49.99250234584355 want 49.992502345843555
    --- FAIL: TestTdigest_Quantile/uniform_99 (0.00s)
        tdigest_test.go:217: unexpected quantile 0.990000, got 98.98503400959561 want 98.98503400959562
    --- FAIL: TestTdigest_Quantile/uniform_99.9 (0.00s)
        tdigest_test.go:217: unexpected quantile 0.999000, got 99.9010378104362 want 99.90103781043621
FAIL
exit status 1
FAIL    github.com/influxdata/tdigest   1.404s

This PR fixes tests on this hardware by updating to a more recent version of gonum and using its scalar.EqualWithinRel function to compare floats.

hdrodz avatar Apr 22 '23 20:04 hdrodz

Hey 👋🏻 We quickly hit this panic when running on ARM-based VMs, rendering the module unusable. Is there a reason this is not being merged?

vroldanbet avatar Mar 19 '25 10:03 vroldanbet