This repository contains an implementation of a ring buffer (also known as a
circular buffer or circular queue) written for use with the
Hopac concurrency library. The ring buffer provided here is similar to the
BoundedMb<'a> provided by Hopac, except that this implementation
uses a circular array instead of a
Queue<T> as provided by the Base Class
Libraries. When used in the context of the Hopac libraries, this ring buffer
RingBuffer.fs in your own project
This file can be added directly into your project or, if you are using Paket to
manage your dependencies, it can be incorporated as a github dependency by adding the
following line to your
github logary/RingBuffer RingBuffer.fs
About the RingBuffer
RingBuffer<'a> provides back-pressure to the upstream
producer of items in the event that the buffer is full. The
additionally provides the ability to dequeue batches of items as part of a single
takeAll operation. The
takeBatch operation allows the caller to
specify a maximum batch size that they will accept.
This implementation also provides utility functions to produce and consume Hopac-style streams.
As currently implemented, the
RingBuffer<'a> is take-biased. This means that if
the buffer is partially filled and a producer is ready to put to the buffer at the
same time that a consumer is ready to take from the buffer, the take operation is
preferred. This precedence can be altered by modifying the order in which
take () and
put () appear in the final match expression of the
create function. Fairness can be guaranteed at the expense of some additional
overhead by using the Hopac
chooser function. Do not just
<~> as the latter does not have the expected effect
in chains of three or more alternatives.
RingBuffer.fsx in fsharpi. This will run the Expecto tests.
Possible future improvements
- Separate the notion of a buffer that produces single items from one that can produce batches.
- Allow for a hybrid precedence mode for batching, such that in the event of put/take-contention, puts will be preferred while the number of buffered events is below a certain limit. When the number of buffered events exceeds that limit, then takes will be preferred. This would ensure that batches are as large as possible while also freeing up space for additional items to be added to the buffer.
- Make a minor change to allow
ringSizeto be the actual capacity instead of
ringSize-1as currently implemented. All that needs to be done here is have a boolean that tracks whether or not the last operation was a put or a take. Given an operation that results in
tail's index becoming equal to
head's index, if the last operation was a put, then the buffer is now full. If the last operation was a take, then the buffer is now empty.
- Streams produced by
tapAllcompete with each other to consume items from the ring buffer. In the case of a ring buffer, there is generally only one consumer of the stream. When there is more than one consumer, the competing model is likely the intended one. Other use cases may prefer that tapped streams are independent from each other such that each consumer sees the same set of generated batches from the point at which they tapped the buffer.
- When the buffer holds reference types,
null/zero-out items once they have been taken from the buffer. Right now, the buffer array will hold references to items that have been taken but which have not yet been overwritten by a cycle of the ring buffer. This can result in certain objects making it into Gen 2, thus contributing to an increased managed heap size and additional Gen 2 collections.