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
|
/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.
There was a problem hiding this comment.
I agree that an initial size and normal size of 0 is probably not ideal in most cases. For something as generic as this though, I don't think we can realistically determine "sane" defaults for initial size or normal size for everywhere this could be used.
Would it be better to require the initial size and normal size to be set? That would at least prevent users from assuming the implicit default of 0 for each.
There was a problem hiding this comment.
Current default is effectively 1 for the initial size. We all seem to agree this is not a good default for any use case. I think it'd be beneficial to have the default set (for both) to 16 or 32 - even if the buffer is not used that much, it's not wasting a lot of space. If this default does not work for someone, they can set the value they want explicitly (just as you are suggesting). WDYT?
There was a problem hiding this comment.
If 0 isn't good enough (which I think is similar to how the Go runtime behaves with plain slices), I'd still prefer requiring those parameters be set by the user over trying to determine defaults which are more acceptable.
There was a problem hiding this comment.
ok, let's see what maintainers have to say.
There was a problem hiding this comment.
I don't think there are any dedicated maintainers for this code 😬 @aojea is an approver for SIG API machinery, but that doesn't mean that he knows this code or has better insights into how it should behave.
To answer @aojea's question:
why before we didn't initialize to 1 when it was zero?
It's useful to allow usage of the zero value. That's similar to var buffer bytes.Buffer. In that case, r.n is zero and the code must do something reasonable. What "reasonable" means is subjective, it could also be that the ring always only is populated with one entry and then quickly drained again.
I'm fine with any default in the range from 1 to 16.
There was a problem hiding this comment.
I don't object the current behavior in principle, it's not incorrect. I also very much like that the zero value of the type (i.e. when it's declared like var x TypedRingGrowing, now via constructor) is safe to use.
| 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".
There was a problem hiding this comment.
is this effective? allocating and deallocating memory vs reusing it?
A new, smaller array gets allocated here so the old, larger array can be garbage collected. I don't think it's possible to inform the Go runtime that part of an array backing a slice can be garbage collected, only that the entire backing array can be by removing all references to any part of the backing array.
69bc812 to
ed4fc2c
Compare
|
/lgtm |
|
[APPROVALNOTIFIER] This PR is NOT APPROVED This pull-request has been approved by: ash2k, 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 |
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 capabi 8000 lity 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-resource-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: