Add generic buffer.TypedRingGrowing and shrinkable buffer.Ring #323
Conversation
|
/cc @pohly |
|
/wg device-management We need this to replace some custom FIFO implementation in two different places (scheduler plugin and ResourceSlice tracker). Would be nice to get into 1.34 soon to give us time to adapt k/k. |
133f6ff to
bb2bb1b
Compare
Updated and squashed. |
bb2bb1b to
69bc812
Compare
|
[APPROVALNOTIFIER] This PR is NOT APPROVED This pull-request has been approved by: nojnhuh, pohly The full list of commands accepted by this bot can be found here.
Needs approval from an approver in each of these files:
Approvers can indicate their approval by writing |
|
/assign @aojea For a second review and approval. |
| } | ||
| r.readable-- | ||
| element := r.data[r.beg] | ||
| r.data[r.beg] = nil // Remove reference to the object to help GC | ||
| var zero T | ||
| r.data[r.beg] = zero // Remove reference to the object to help GC |
There was a problem hiding this comment.
this is only true if T is a pointer, no?
There was a problem hiding this comment.
Not really. e.g. string, slice, map, any struct that has such fields and/or pointers.
(I'm not the author of the PR but I wrote the original code)
There was a problem hiding this comment.
ok, yeah , I mean , if we have an int this will be 0 , right :) ... maybe pedantic, or nitpicking, just for correctness
There was a problem hiding this comment.
@ash2k: perhaps you can help with the review then?
There was a problem hiding this comment.
@pohly I did have a look earlier today and I have the same questions re. allocations. Overall it looks good.
| if newN == 0 { | ||
| newN = 1 | ||
| } | ||
| newData := make([]T, newN) |
There was a problem hiding this comment.
why before we didn't initialize to 1 when it was zero?
There was a problem hiding this comment.
My understanding is that before this PR we assumed that the initial size is some non-zero value. With this PR the RingOptions may not have the InitialSize set. In that case the NewRing constructor will use 0 as the initial size and multiplying by 2 wouldn't grow it :)
I think it'd be better to use some sane defaults for all parameters in the constructor rather than hacking around like this in the middle of the logic.
Same with NormalSize - I don't think it makes sense to shrink to 0 and then grow to 1, 2, 4, 8, etc. Why not use some sane size if nothing was provided? Maybe 32 or something sufficiently large.
| return r.n | ||
| } | ||
|
|
||
| // RingGrowingOptions sets parameters for [Ring]. |
There was a problem hiding this comment.
| // RingGrowingOptions sets parameters for [Ring]. | |
| // RingOptions sets parameters for [Ring]. |
| if r.growing.readable == 0 && r.growing.n > r.normalSize { | ||
| // The buffer is empty. Reallocate a new buffer so the old one can be | ||
| // garbage collected. | ||
| r.growing.data = make([]T, r.normalSize) | ||
| r.growing.n = r.normalSize | ||
| r.growing.beg = 0 | ||
| } |
There was a problem hiding this comment.
is this effective? allocating and deallocating memory vs reusing it?
There was a problem hiding this comment.
The way I understood this change is that the idea is to shrink the hugely expanded buffer back to some typical size. E.g. there was a spike of usage (as it happens when e.g. a controller starts and fills up a workqueue but the workers only start when all informers have synced). Waiting for it to get to 0 first allows to eliminate the need for copying the data, which is good.
There was a problem hiding this comment.
I.e. it is less effective but the goal is to reduce the amount of ram used so we have to free the "big" buffer and allocate a new one that is "normal".
What type of PR is this?
/kind feature
What this PR does / why we need it:
This PR adds a new type,
buffer.Ringwhich is abuffer.RingGrowingwith a type parameter (generics) and the capability to shrink its underlying buffer when all elements have been read. It should be able to replace the scheduler's use ofqueue.FIFO(and its copy ink8s.io/dynamic-resou 8000 rce-allocation/internal/queue). Behavior of the existingbuffer.RingGrowingshould be unchanged.Which issue(s) this PR fixes:
First step of kubernetes/kubernetes#131032
Special notes for your reviewer:
I verified that this new implementation passes the existing unit tests for
k8s.io/client-go/tools/cachewherebuffer.RingGrowingis currently in use without any changes to that package, and fork8s.io/kubernetes/pkg/scheduler/util/assumecacheandk8s.io/dynamic-resource-allocation/resourceslice/trackerreplacing its use ofqueue.FIFO: kubernetes/kubernetes@master...nojnhuh:kubernetes:typed-ring-buffer.Release note: