ringbuf

KO | EN

gitlite — search

#javascript #python #hacktoberfest #react #ai #typescript #llm #go #golang #android #machine-learning #rust #deep-learning #linux

(★ 27)

An STL-like ring buffer for C++11.

ringbuf Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

# baudvine::RingBuf

- [Overview](#overview)
- [The present](#the-present)
    - [Using](#using)
    - [Building](#building)
- [The Future](#the-future)
    - [TODO](#todo)
    - [NOT TODO](#not-todo)
    - [MAYBE TODO](#maybe-todo)
- [Performance](#performance)
- [FAQ](#faq)
- [License](#license)

## Overview

For detailed documentation, see https://barometz.github.io/ringbuf/.

This is a header-only
[ring/circular buffer](https://en.wikipedia.org/wiki/Circular_buffer)
implementation in C++11, with the following goals:

- Reasonably performant.
- Readable.
- STL-compatible and STL-like.

There are two implementations: `baudvine::RingBuf` and `baudvine::DequeRingBuf`.
They're meant to be functionally equivalent (mostly), but behave differently
under water. Tests ideally cover both, expecting the same behaviour. Both behave
like double-ended queues up until the point where they fill up, at which point
pushing/emplacing at the front causes the element in the back to fall off (and
vice versa).

`baudvine::RingBuf` is the primary implementation: it stores elements in a
fixed-size, dynamically allocated array, and provides the usual container
operations as well as `baudvine::copy` for efficient copying.

`baudvine::DequeRingBuf` is included primarily for testing purposes. Because
it's based on `std::deque` it's a bit less efficient (time, memory
fragmentation) than the array-based one, but it's also a lot easier to trust
since all the hairy math and allocation happens in the standard library.

## The present

### Using

```c++
#include <baudvine/ringbuf.h>

void demo()
{
 baudvine::RingBuf<std::string, 2> buffer;
 buffer.push_back("Testing, ");
 buffer.push_back("one, ");
 buffer.push_back("two.");
 assert(buffer.front() == "one, ");
 assert(buffer.back() == "two.");
}
```

See [test/examples.cpp](test/examples.cpp) for further usage examples. The
high-level pitch is this: you can use it as an STL container, except it wraps
like a ring buffer. You get iterators, `front()`, `back()`, `push_back()`,
`pop_front()`, `emplace_back()`, range-for, all\* the things you expect from a
standard library container.

### Building
The project is header-only, so you only have to copy
`include/baudvine/ringbuf.h` into your project. You should also be able
to include it as a CMake subproject, but that's untested.

To build and run the tests, install [CMake](https://cmake.org/), then run:

```
mkdir build
cmake -S . -B build
cmake --build build
build/test/ringbuf-test
```

Or use your editor or IDE with CMake integration of choice.

## The Future

### TODO
What can't it do? Well:

- [x] Support for user-defined/provided allocators.
- [x] Reverse iterators.
- [x] Generic tests for the iterators of the different implementations.
- [x] Doesn't quite implement
  [SequenceContainer](https://en.cppreference.com/w/cpp/named_req/SequenceContainer).
- [x] The tests for Container aren't as well organized as they could be either.
- [x] Needs more ~~cowbell~~ `noexcept`
- [x] Moved-from RingBuf instances can't be reused.
- [x] The iterator is not std::random_access_iterator.
- [x] Docs.
- [x] Better code examples.
- [x] Document iterator invalidation.
- [x] Compare to `boost::circular_buffer`
- [ ] ~~Special case for emplace/push members when T's lifetime doesn't matter (e.g. int)~~  
  The performance benefit turned out to be hard to measure -
  `std::allocator_traits` is probably reasonably smart about this. 
- [x] Compiler warning cleanup
- [x] Compare to boost's spsc queue

### NOT TODO
What won't it do?

- Don't want to bother with optional features based on C++ version. Strictly C++11.
- Runtime checks are limited to the occasional `assert`.
- Doesn't have `insert()` or range constructors (`RingBuf(other.begin(), other.end())`),
  because that'd require choosing what to discard in case of overflow.

### MAYBE TODO

- [x] It's meant to be C++11-compatible without a lot of optional chunks for
  newer standards, but maybe we can show that it *does* match the relevant C++20
  iterator concepts.
- [ ] An implementation with mutable capacity (drop the template parameter, add
  a ctor parameter and a `set_capacity` member) would be slightly slower and
  slightly nicer to use.
- [ ] DequeRingBuf could possibly be a container adapter.
- [ ] A variant of RingBuf with automatic storage duration (so no dynamic
  allocation) is possible. Would be nice for embedded targets.

## Performance

The tests in [test/test_speed.cpp](test/test_speed.cpp) perform a number of
comparisons between `RingBuf` and `DequeRingBuf`. Some typical (but completely
unscientific) results:

- Hardware: Intel Core i5-7600 @ 3.5 GHz
- GCC: 12.2, `-O3 -DNDEBUG`
- Clang: 14.0, `-O3 -DNDEBUG`

| Name | Description | RingBuf (GCC) (ms) | RingBuf (Clang) (ms) | DequeRingBuf (GCC) (ms) | DequeRingBuf (Clang) (ms) |
|------|-------------|-------------------:|---------------------:|------------------------:|--------------------------:|
| PushBackToFull | `push_back` until the buffer is filled to capacity (225 elements) | 106 | 108 | 353 | 322 |
| PushBackOverFull | `push_back` 225 times on a buffer with capacity 3 | 119 | 105 | 138 | 195 |
| IterateOver | range-for over a buffer with 225 elements | 83 | 57 | 77 | 72 |

PushBackToFull is *completely* unfair because `std::deque` has to allocate
memory much more frequently. In a debug build, the results are roughly
proportional (~10x).

## FAQ

### Why does this allocate "manually" and not just wrap `std::array`?

A functional requirement of `baudvine::Ringbuf` is that element lifetime is
controlled by the `push` and `pop` member functions: a T is constructed when it
is pushed into the buffer, and it is destroyed when popped. The tests using the
`Instance` class in `tests/test_ringbuf.cpp` demonstrate this.

Neither C-style arrays nor `std::array` allow for this:
`std::array<std::string, 5>` default-initializes five strings (calling its
default constructor), and if you destroy it in-place it'll get re-destroyed when
the array goes out of scope.

See also https://barometz.github.io/ringbuf/design-notes.html#memory-allocation.

### Why isn't this an adapter for existing containers?

No underlying container would provide all three of:

- Single allocation (`std::array`, `std::vector`)
- Push and pop on opposing ends (`std::deque`, `std::list`)
- Control over element lifetime (`std::vector`, `std::list`, `std::deque`)

See also: https://barometz.github.io/ringbuf/design-notes.html#not-an-adapter.

## License
I chose the [MIT license](LICENSE) for this project, because I have a bad habit
of wanting to be useful and MIT's a good one for maximizing that paperclip.
One exception: `deque_ringbuf.h` is MIT-0, which is effectively public domain.

ringbuf

ringbuf Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

ringbuf

ringbuf Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README