What are the uses of circular buffer?

Question

What are some of the uses of circular buffer?

What are the benefits of using a circular buffer?

is it an alternative to double linked list?

Answer 1

I know this is cheating, but wikipedia does have a very good explaination.

http://en.wikipedia.org/wiki/Circular_buffer

A circular buffer, cyclic buffer or ring buffer is a data structure that uses a single, fixed-size buffer as if it were connected end-to-end. This structure lends itself easily to buffering data streams

An example that could possibly use an overwriting circular buffer is with multimedia. If the buffer is used as the bounded buffer in the producer-consumer problem then it is probably desired for the producer (e.g., an audio generator) to overwrite old data if the consumer (e.g., the sound card) is unable to momentarily keep up. Another example is the digital waveguide synthesis method which uses circular buffers to efficiently simulate the sound of vibrating strings or wind instruments.

With regards comparing to double-linked lists, I imagine it really does depend on what you are using the list for... Implementation of cirular buffers seems to be more complex, please (again) refer to the wiki page; this explains implementation, considerations etc and also shows example code.

Thanks, Neil

Answer 2

I've used it for an in-memory log with a restricted size. For example, the application would write log entries while processing user requests. Whenever an exception occurred (that would be disruptive to the processing) the log records currently in memory would be dumped along with it.

The benefit of a circular buffer is, that you don't need infinite amounts of memory, since older entries get overridden automatically. The "challange" is, that you need to find a suitable size for your usecase. In the example above, it would be very unfortunate when the log record with the most vital information about the exception would have already been overridden.

Some systems/applications have tools to let you extract the current content of the buffer on demand, and not only when it would be extract automatically (if ever).

I believe ETW and the CLRs stress log, amongst many other system's kernel or highperformance trace/logging, are implemented that way.

The concept of using such buffers for in-memory tracing/logging is actually pretty common (not to say that this is the only use - certainly not), because it is way faster than written records to a file/database that you might never be interested in unless an error occurs. And on a related note, it conserves harddisk space.

Answer 3

A circular buffer is a nice mechanism for efficiently maintaining a sliding/moving list of values/items in an ordered fashion. One example might be to maintain a sliding average of the last N items. Suppose you want to track the average cost of the last 100 operations of computing some value. To do this, you would need to remove the oldest cost and add in the newest cost.

Without a circular buffer, a costly mechanism for doing this (C style) would be to have an array of 100 elements. Each time a new cost is computed, you could memmove the 99 elements down and put the new one in at the last position. This is obviously costly. Using a circular buffer idea, you would just track the “end” of the buffer (position 0-99). It would mark the position of the oldest (or newest … whichever you choose) cost item. After reading the old value (for updating the running average), you replace it with the newest value and increment the buffer position (if it is at 99, you set it back to 0 … thus, the circular part).

Comparing it to a doubly linked list doesn’t really make sense. A circular buffer could certainly be implemented with a doubly linked list (or even a singly linked list). But comparing them is a little bit like comparing apples and oranges so to speak.

Answer 4

This is also a nice interview question - have been asked at least twice to implement it on the interview ;)

Answer 5

I've used it as an easy way of implementing round-robin scheduling. Basically I had a bunch of different objects that can produce a value that a consumer could then process. I stuck all the producers in a ring and asked each one in turn.

Answer 6

I have used a ring buffer in multi-threaded code. Basically, if all slots are full the producer(s) have to wait. The consumers simply process items in slots that are "full".

Here's a thread I started on it. It has some good advice on implementation.

http://stackoverflow.com/questions/1182423/net-multi-threaded-variable-access

Answer 7

Circular buffers are good for serial data streams in embedded systems. Microcontrollers often have a UART to handle a serial byte coming in, these need to be stored in order and dealt with later (bytes often come in at a faster rate than they can be handled).

The buffer effectively splits the timing-critical response required (when the bytes come in, in microseconds) to the non timing-critical response to the whole message (for example displaying the message which came in, in milliseconds), e.g.:

1) Upon the receipt of a byte the UART can generate an interrupt to which the software responds by quickly taking the received byte and shoves it onto the end of the buffer.

2) Background software routines can then regularly check if the buffer has anything in it yet and empty it as required.

As the circular buffer size can be defined pre-compilation the size is then limited. This helps improve space efficiency and should eliminate memory corruption at a trade off to how many bytes can be received before data starts to become lost.