Click here to Skip to main content
15,119,116 members
Articles / Programming Languages / C++
Article
Posted 15 Jan 2021

Tagged as

Stats

4.3K views
184 downloads
5 bookmarked

YACB - Yet Another Circular Buffer

Rate me:
Please Sign up or sign in to vote.
3.40/5 (2 votes)
16 Jan 2021CPOL4 min read
A fast and modern circular buffer implementation
This article describes a C++17 template based implementation of the circular buffer structure.

Introduction

Circular buffers, next to producer/consumer queues, are one of those data structures that have been forever in the arsenal of every programmer. What is surprising, is that there is no standard implementation in C++ standard library. There is a circular buffer in Boost but, like many Boost things, it is fairly large and not that easy to integrate in other projects. The implementation shown in this article wants to be small and easy to use.

Background

A circular or ring buffer is a container of a fixed size. When the container is full and a new element is added to it, the oldest element is discarded. Traditionally, ring buffers are implemented as a pre-allocated memory area together with a couple of pointers or indexes that keep track of the insertion point (back) and extraction point (front):

Ring buffer

The pointers must wrap around at the end of the memory area. One solution for reducing the computations required for this wrap around is to have a buffer whose size is a power of 2 and simply truncate the indexes. For example, if the buffer size is 256, the indexes can be kept as 8-bit integers and wrap around is automatic. This was a popular solution in the days of assembler when memory was expensive and CPU cycles valuable.

The two pointers can be equal either when the buffer is empty or when the buffer is completely full:

Buffer Full

Buffer Empty

There are various mechanisms for distinguishing between the two cases. The obvious solution is to also keep a count of the number of elements in buffer. Another solution is to always keep an empty space in the buffer. In this case, if after an insertion the two pointers would become equal, that means the buffer is full and the extraction pointer is also advanced.

Usage

The only file required is the ring_buffer.h header file. Everything else is part of the demo project. The circular buffer structure is implemented as the ring_buffer class. Calling it `circular_buffer` would have been a whooping 4 extra letters to type. This is a plain vanilla implementation that doesn't use any of the smart techniques mentioned before. It is a container class and the access methods are modelled on the std::queue class.

Constructors

C++
ring_buffer ()                                            [1]
ring_buffer (size_t sz)                                   [2]
ring_buffer (std::initializer_list<T> il)                 [3]
ring_buffer (const ring_buffer<T>& other)                 [4]
  • [1] is the default constructor that creates an empty buffer with capacity 0.
  • [2] is the normal constructor that creates a buffer with capacity sz. Keep in mind that, once allocated, the buffer size can be changed only by calling the resize function.
  • [3] is another constructor that accepts an initializer list. This allows you to write something like:
    C++
    ring_buffer<int> my_buffer ({100, 101, 102});
    
  • [4] is the copy constructor that creates a copy of an existing buffer. There is also an assignment operator:
    C++
    ringbuf& operator= (const ringbuf& rhs)
    

It can be used like in this example:

C++
ringbuf<int> b1;            //empty
ringbuf<int> b2(5);         //b2 capacity is 5

b1 = b2;                    //now b1 has capacity of 5

Data Insertion and Extraction

To add an object to circular buffer, you call the push_back function:

C++
void push_back (const T& item)

The element can be accessed using the back function:

C++
T& back ()

The oldest element in buffer can be accessed using the front function:

C++
T& fron ()

And can be removed from buffer using the pop_front function:

C++
void pop_front ()

Iterators

Any well-behaved container must implement some iterators. In our case, ring_buffer implements a bidirectional iterator in two flavors: const and non-const. The usual functions begin and end return those iterator objects:

C++
iterator begin ();
const_iterator begin () const;
const_iterator cbegin ();

iterator end ();
const_iterator end () const;
const_iterator cend ();

The iterator objects provide all the expected functions: increment, decrement, addition, subtraction, comparison.

With these elements, now we can write something like this:

C++
ring_buffer<string> container = {"abc", "def", "ghi"};
for (auto p = container.begin(); p != container.end(); p++)
    cout << *p << ' ';

Or even better:

C++
ring_buffer<string> container = {"abc", "def", "ghi"};
for (auto p : container)
    cout << p << ' ';

More Functions

In addition to the functions described before, there are just a few more functions in the ring_buffer class:

  • empty() checks if the buffer is empty
  • clear() removes all elements from the buffer
  • capacity () returns the buffer capacity
  • resize (size_t n) changes the buffer capacity

One particular note for the vector conversion operator: this allows you to transfer the buffer content into a standard vector where elements are ordered from the oldest to the newest. For instance:

C++
ring_buffer<string> b{ "first", "second", "third" };
b.pop_front ();
b.push_back ("fourth");       //b contains (from newest) "fourth", "third", "second"
v = b6;                       //v[0]="second", v[1]="third", v[2]="fourth"

Implementation Notes

The ring_buffer data is stored as a classical C array, albeit wrapped in a unique_ptr to make it easier to manage. In addition to the data array, the class contains the front and back indexes and size information.

To avoid code duplication between the cons and non-const versions of the iterators, they are implemented using a template with a bool parameter. The const version of the iterator is instantiated with the parameter set to true while the non-const is instantiated with the parameter set to false.

C++
template <bool C_>
class iterator_type
{
//...
}

typedef iterator_type<false> iterator;
typedef iterator_type<true> const_iterator;

Performance

I included a performance test inspired by the article, Performance of a Circular Buffer vs. Vector, Deque, and List. It creates a number of random key-value pairs, shuffles them to a random order and then inserts them in different containers. On my machine, results are like this:

Random vector prepared in 1328ms
ring_buffer push_back of 10000000 elements in 74ms
size is 156250kb
vector push_back of 10000000 elements in 316ms
vector with reserve push_back of 10000000 elements in 97ms
list push_back of 10000000 elements in 575ms
ring to vector conversion of 10000000 elements in 97ms

Pushing 156MB in a vector without pre-allocating memory takes about 316ms. The time drops to only 97ms if the vector pre-allocates memory (using reserve function). Our ring_buffer is still a bit faster at only 74ms. Converting from ring buffer to vector also takes about the same time as filling a pre-allocated vector. This is not surprising as, internally, the vector conversion operator does exactly that: pre-allocates and fills a vector.

Final Thoughts

This class is part of the MLIB project. You can download the latest version from the GitHub page.

History

  • 15th January, 2021 - Initial version

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Mircea Neacsu
Canada Canada
No Biography provided

Comments and Discussions

 
QuestionYACB Thread Safe? Pin
hkswan18-Jan-21 11:00
Memberhkswan18-Jan-21 11:00 
AnswerRe: YACB Thread Safe? Pin
Mircea Neacsu18-Jan-21 11:37
mvaMircea Neacsu18-Jan-21 11:37 
QuestionMissing Attachments Pin
robertjb2016-Jan-21 22:55
professionalrobertjb2016-Jan-21 22:55 
AnswerRe: Missing Attachments Pin
Mircea Neacsu17-Jan-21 1:36
mvaMircea Neacsu17-Jan-21 1:36 
PraiseMessage Closed Pin
16-Jan-21 2:41
MemberЕвгений Леонтьев16-Jan-21 2:41 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.