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.

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

Fix OOB access in Quantile() #32

Open
wants to merge 3 commits into
base: master
Choose a base branch
from

Conversation

hdrodz
Copy link

@hdrodz hdrodz commented Apr 22, 2023

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Panic: tdigest.go:182, index out of range [40] with length 40
1 participant