influxdata / influxdata/tdigest
ByteSizeForCompression underestimates memory consumption
- Dominant language
- Go
- Stars
- 153
- Forks
- 25
- PR merge metrics
- No merged PRs in 30d
Description
The calculation for ByteSizeForCompression states
> Unprocessed and processed can grow up to length c
https://github.com/influxdata/tdigest/blob/master/tdigest.go#L50
But unprocessed and processed are allocated in https://github.com/influxdata/tdigest/blob/master/tdigest.go#L30 with a capacity of maxUnprocessed and maxProcessed which are 8 and 2 times c (see e.g. https://github.com/influxdata/tdigest/blob/master/tdigest.go#L304)
This leads to ByteSizeForCompression underestimating the memory consumption of these two buffers by a factor of 10 which is not neglible.
I think the result should be
8 * (2 * (8c + 2c) + c) // 8bytes/float * ( (8*c unprocessed + 2*c compresses) * 2 values + c values
cumulative )
= 168 * c
(Btw: the 40 is not correct even if the factors 8 and 2 for the capacity of the unprocessed and processed buffers are ignored.)
BUT: This 168 * c still underestimates the memory consumpotion as in
https://github.com/influxdata/tdigest/blob/master/tdigest.go#L121
t.unprocessed = append(t.unprocessed, t.processed...)
processed gets appended to unprocessed and both slices might be full resulting in unprocessed to grow to (maxUnprocessed + maxProcessed) = 10 * c
So the _correct_ value should be `200 * c`.
This is quite a number. I'm wondering if float32 and smaller unprocessed buffer would allow to reduce memory consumption while keeping enough numerical stability and accuracy.
Contributor guide
No contributing guide indexed for this repository
Research direction
Start in tdigest.go at ByteSizeForCompression and inspect the unprocessed and processed allocations around lines 30, 50, 121, and 304. Trace the slice capacities during append and compare peak memory with the reported estimate. Done means the calculation reflects the actual peak buffer usage and the corrected behavior is covered by tests.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- go
- Domain
- performance
- Issue type
- Bug
- Difficulty
- 3/5
- Estimated time
- 1-2 days
- Activity status
- Stale
- Clarity
- Clearly specified
- Newbie friendliness
- 50/100