Add generic buffer.TypedRingGrowing and shrinkable buffer.Ring

[nojnhuh]

What type of PR is this? /kind feature

What this PR does / why we need it:

This PR adds a new type, buffer.Ring which is a buffer.RingGrowing with 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 of queue.FIFO (and its copy in k8s.io/dynamic-resource-allocation/internal/queue). Behavior of the existing buffer.RingGrowing should be unchanged.

Which issue(s) this PR fixes:

First step of https://github.com/kubernetes/kubernetes/issues/131032

Special notes for your reviewer:

I verified that this new implementation passes the existing unit tests for k8s.io/client-go/tools/cache where buffer.RingGrowing is currently in use without any changes to that package, and for k8s.io/kubernetes/pkg/scheduler/util/assumecache and k8s.io/dynamic-resource-allocation/resourceslice/tracker replacing its use of queue.FIFO: https://github.com/kubernetes/kubernetes/compare/master...nojnhuh:kubernetes:typed-ring-buffer.

Release note:

Add new, generic buffer.TypedRingGrowing type to succeed buffer.RingGrowing which is now deprecated. Add new buffer.Ring type, which is equivalent to buffer.TypedRingGrowing, but shrinks to its original size after its elements have been totally consumed.

[nojnhuh]

/cc @pohly

[nojnhuh]

AFAICT the apidiff failure is a false-positive, maybe it doesn't fully understand generics? I've at least checked that client-go will still compile without any changes with this PR.

@apelisse @cheftako If you could PTAL that would be great, thanks!

[pohly]

/wg device-management /priority important-soon

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.

[nojnhuh]

Looks good to me with perhaps one small doc tweak.

Please squash into one commit to make it ready for merging.

Updated and squashed.

[pohly]

/assign @aojea

For a second review and approval.

[ash2k]

/lgtm

[aojea]

ok, this seems to work as expected, it sacrifices allocations for long term memory usage

const (
	spikeSize   = 100 // Number of items to write during a spike
	normalSize  = 64  // Normal capacity for the Ring type after shrinking
	initialSize = 16  // Initial capacity for buffers
)

func BenchmarkTypedRingGrowing_Spike(b *testing.B) {
	b.ReportAllocs()
	var item int // ensure item is used

	for i := 0; i < b.N; i++ {
		buffer := NewTypedRingGrowing[int](RingGrowingOptions{InitialSize: initialSize})

		for j := 0; j < spikeSize; j++ {
			buffer.WriteOne(j)
		}

		for buffer.Len() > 0 {
			item, _ = buffer.ReadOne()
		}
	}
	_ = item // use item
}

func BenchmarkRing_Spike_And_Shrink(b *testing.B) {
	b.ReportAllocs()
	var item int // ensure item is used

	for i := 0; i < b.N; i++ {
		// Create a new buffer for each benchmark iteration
		buffer := NewRing[int](RingOptions{
			InitialSize: initialSize,
			NormalSize:  normalSize,
		})

		for j := 0; j < spikeSize; j++ {
			buffer.WriteOne(j)
		}

		for buffer.Len() > 0 {
			item, _ = buffer.ReadOne()
		}
	}
	_ = item // use item
}

go test  -run=^$ -bench=. k8s.io/utils/buffer -v -count 1
goos: linux
goarch: amd64
pkg: k8s.io/utils/buffer
cpu: Intel(R) Xeon(R) CPU @ 2.60GHz
BenchmarkTypedRingGrowing_Spike
BenchmarkTypedRingGrowing_Spike-48        953743              1094 ns/op            1920 B/op          4 allocs/op
BenchmarkRing_Spike_And_Shrink
BenchmarkRing_Spike_And_Shrink-48         819721              1325 ns/op            2432 B/op          5 allocs/op
PASS
ok      k8s.io/utils/buffer     2.166s

The apidiff does not seems to cause any issue with the existing code as it is able to infer the type IIRC It also fixes a bug where a buffer not initialized or initialized as zero will not be able to grow

There is an outstanding discussion about the default size, https://github.com/kubernetes/utils/pull/323#discussion_r2111230407

[aojea]

+1 if we change the magic 1 by a constant and we use a more larger default as 16 per example https://github.com/kubernetes/utils/pull/323/files#r2113869115

[aojea]

/approve

@ash2k for final lgtm

Thanks

[ash2k]

/lgtm

Thank you, @nojnhuh!

[k8s-ci-robot]

[APPROVALNOTIFIER] This PR is APPROVED

This pull-request has been approved by: aojea, ash2k, nojnhuh, pohly

The full list of commands accepted by this bot can be found here.

The pull request process is described here

Needs approval from an approver in each of these files:

• ~~OWNERS~~ [aojea]

Approvers can indicate their approval by writing /approve in a comment Approvers can cancel approval by writing /approve cancel in a comment

[aojea]

/override

[k8s-ci-robot]

@aojea: /override requires failed status contexts to operate on, but none was given

In response to this:

/override

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes-sigs/prow repository.

[aojea]

/override apidiff

The apidiff does not seems to cause any issue with the existing code as it is able to infer the type IIRC

[k8s-ci-robot]

@aojea: aojea unauthorized: /override is restricted to Repo administrators.

In response to this:

/override apidiff

The apidiff does not seems to cause any issue with the existing code as it is able to infer the type IIRC

Instructions for interacting with me using PR comments are available here. If you have questions or suggestions related to my behavior, please file an issue against the kubernetes-sigs/prow repository.

[aojea]

@dims we need your help :)

[aojea]

hmm, this is an incompatible change based on https://go-review.googlesource.com/c/tools/+/618215/3/internal/apidiff/testdata/tests.go#535

@nojnhuh should we leave the old buffer as it was to avoid breaking compatibility?

[dims]

/skip

[dims]

i am gonna merge by hand :)