[SR-8190] Introduce a RingBuffer to the Standard Library

[CodaFi]

Previous ID	SR-8190
Radar	rdar://21885650
Original Reporter	@CodaFi
Type	Improvement
Status	In Progress
Resolution

Additional Detail from JIRA

Votes	1
Component/s	Standard Library
Labels	Improvement, StarterBug, StarterProposal
Assignee	mkita (JIRA)
Priority	Medium

md5: 6b666a5f9322c64149027ee56661cfd2

relates to:

• SR-6868 Add a deque to the standard library
• SR-11956 SynchronizedQueue in SwiftPM has a Quadratic Dequeue Operation

Issue Description:

Introduce a ring buffer abstraction into the Swift Standard Library. This can be used to simplify a few places in e.g. the Sequence algorithms that are independently using an array and index math to simulate such an abstraction.

Tests and benchmarks would also need to be integrated.

[swift-ci]

Comment by Ding Ye (JIRA)

Some attempt has been made earlier here https://github.com/apple/swift/pull/7250, but unfortunately discontinued. Are you interested in moving forward, bnut (JIRA User)? It would be great if we can put this together.

[swift-ci]

Comment by Andrew Bennett (JIRA)

My implementation was only intended for internal usage, but I'm happy to resurrect it. Unfortunately my implementation was overkill for something that's only going to be used internally.

If it were to be exposed in the standard library then I believe that there's two things we'd also probably want:

1. A swift evolution proposal to add a RingBuffer type.

2. A swift evolution proposal to split init() from RangeReplaceableCollection.

The first is needed to be able to make it public.

The second is needed because it makes sense for it to conform to RangeReplaceableCollection, and that will allow it to be used in many places you can currently use an Array. However init, is not truly needed for that protocol, and there is no implementation of init() that makes sense for a RingBuffer.

I'm happy to introduce it as an internal class, but I don't think I have time to give the swift evolution process proper attention at the moment. It'd be great to get the evolution discussions going on the forums, as they can be driven independently.

[swift-ci]

Comment by Ding Ye (JIRA)

Thank you for the reply, Andrew!

CC @airspeedswift. Does it make sense to introduce an internal RingBuffer, since we can make the implementation optimised for some specific internal use? It could be orthogonal to the public version we intend to have for general circumstances.

[swift-ci]

Comment by Andrew Bennett (JIRA)

I’m guessing that the internal implementation is already fairly optimal
https://github.com/apple/swift/blob/master/stdlib/public/core/Sequence.swift#L1154
I think the intention was that it’s reusable.

Perhaps they can share some implementation details if there’s an intention to make a public interface either way.

[weissi]

This is Deque in swift-collections