2
\$\begingroup\$

I tried to explain in detail everything there should be of concern regarding this particular implementation, and non-code body turned out quite long, scroll down if you just want to read the implementation.

I needed memory storage for a bounded thread-safe queue, so I wrote a ring buffer. It's not really relevant here, but to avoid any confusion I think I need to mention that it's not going to be anything special like lock-free. That is why this buffer uses non-atomic types for tracking state and is completely self-contained.

The difference between types like std::vector and this buffer is that it is a lot stricter with object initialization and exceptions. Types that throw on move are a hard no-go, because I think it's harder to reason about and cannot even be implemented correctly with just a single function call without losing the object.

While it's fine for std::vector because user controls when and where element vector[x] is moved or copied, I believe that because this buffer is opaque, putting this kind of burden onto the user isn't going to help anyone. User would have to not only access the element by reference, but also call pop, without pop, unlike in a std::vector where it's okay to leave dead elements, here it is possible to cause undefined behavior. Read and write also can cause undefined behavior, by design, but unlike this particular problem, they will not propagate out into public interface and burden is only on me. Meanwhile, it's not actually that hard to not throw in move constructor and destructor and is highly preferred in any case.

I will most likely just wrap it in a std::shared_ptr and build on top of that, therefore I have no need for move and copy constructors for this buffer as of now, so I didn't write them, but they're possible to implement. Copy may have strong exception guarantee; that's important to consider as most objects can throw while copying.

ring_buffer::write provides strong exception guarantee to allow constructing types in-place or by copying using constructors that may throw, on top of ability to move the object in exception-free, the latter being the primary intended use case. This matches the good part of C++ programming in general - the one allocating resources is burdened with correctness, while whoever receives already allocated resources can simply enjoy them and pass them on without a single worry.

What's also different, is that it wastes no elements in a given allocation unlike most popular implementations, that's great. In this implementation, choice to use bit masking over remainder operator is not an optimization but a necessity for correctness which is what also allows to utilize all elements, as non-power of two capacities simply do not work correctly. Which leads us to the biggest downside...

You cannot allocate just any amount of elements you please. There's no buts and ifs like "maybe I can take a performance hit to fine-tune memory usage", you cannot choose even this. It can manage 1 (maybe nobody needs this, but it's certainly possible), 2, 4, 8, ..., 65536... elements, and I think most problems that require a bounded queue can easily use one of these sizes, which are optimal for performance, if not memory.

This is not anything new, I found out about it recently from a code review on Linux kernel mailing list that was related to ring buffers. It's quite old, and it's surprising to me that more people don't do this, not even mention this particular way at all when talking about this data structure. Maybe I'm missing something important, but this is now my favorite implementation.

The problem is, it's deceptively hard to implement even this basic data structure correctly, even more so in C++, and I'd like to know if I didn't miss some edge case regarding (correctly-behaving) types that user can supply to break this internal detail.

While code below requires C++20 to compile, it should be C++17 compatible by replacing std::has_single_bit(N) with N && !(N & (N - 1)).

#include <array>
#include <bit>
#include <cstddef>
#include <new>
#include <type_traits>
#include <utility>

template <typename T>
using uninitialized = alignas(T) std::byte[sizeof (T)];

template <typename T, std::size_t N>
class ring_buffer {
    // Wrap it in a well-behaved class if you need this.
    static_assert(!std::is_array<T>::value);
    static_assert(!std::is_union<T>::value);
    static_assert(!std::is_reference<T>::value);
    // It's rare for throwing in these to not be a terrible design. It's even
    // rarer to not have a move constructor.
    static_assert(std::is_nothrow_move_constructible<T>::value);
    static_assert(std::is_nothrow_destructible<T>::value);
    // *Very* important for this implementation to be correct. You *cannot*
    // just replace `Index & (N - 1)` with `Index % N` here, because that would
    // result in discontinuity of indices when type of value N overflows.
    static_assert(std::has_single_bit(N), "capacity must be a power of two");
public:
    ring_buffer() noexcept
    : read_{},
      write_{}
    {}

    ~ring_buffer()
    {
        if constexpr (!std::is_trivially_destructible<T>::value) {
            while (!empty()) {
                read_reference_().~T();
            }
        }
    }

    ring_buffer(ring_buffer const&) = delete;
    ring_buffer&
    operator=(ring_buffer other) = delete;

    bool
    empty() const noexcept
    {
        return read_ == write_;
    }

    bool
    full() const noexcept
    {
        return write_ - read_ == N;
    }

    // Undefined behavior if `empty() == true`.
    T
    read() noexcept
    {
        T& stored = read_reference_();
        T value = std::move(stored);
        stored.~T();
        return value;
    }

    // Undefined behavior if `full() == true`.
    template <typename... Args>
    void
    write(Args&&... args)
    {
        new (&storage_[wrap_(write_)]) T(std::forward<Args>(args)...);
        ++write_; // Strong exception guarantee.
    }
private:
    T&
    read_reference_() noexcept
    {
        return *std::launder(reinterpret_cast<T*>(&storage_[wrap_(read_++)]));
    }

    static
    std::size_t
    wrap_(std::size_t const index) noexcept
    {
        return index & (N - 1);
    }

    std::array<uninitialized<T>, N> storage_;
    std::size_t read_;
    std::size_t write_;
};
\$\endgroup\$

1 Answer 1

1
\$\begingroup\$

You need to write copy constructor and copy assignment operator. I see you have done so (with = delete).

I would prefer to use constraints to ensure ring_buffer isn't instantiable for unsuitable T, rather than static_assert to cause an error when one is instantiated. I'm not convinced that T can't be an array type (but it's unlikely to be a problem, given std::array is available).

You will have problems if you try to access this from multiple threads, as there's no guards at all on the read and write pointers. The set of problems for which a buffer is useful is small compared with those that can use a properly synchronised ring buffer.

I can't see any violations of the strong exception guarantee, given the requirement for non-throwing ~T() - your logic looks good to me.

I think that wrap_() can be constexpr.

I would have liked to have seen the unit tests included in the review.

\$\endgroup\$
4
  • \$\begingroup\$ What makes you think that I need to write a copy constructor? Also yes, I know that this is not thread-safe, and it's not meant to be, because it's a basic class that only concerns itself with storage and nothing else, and is not intended to ever be used directly. I also have tests for most things, including checks for how many times an object being written to the buffer is constructed/copied/moved/destructed, whether indices wrap correctly, even on overflow and so on, but that is a lot of extra code to add here. \$\endgroup\$
    – yotsugi
    Commented Aug 31, 2022 at 13:36
  • \$\begingroup\$ The main thing is that if you write no copy constructor at all, you'll get a default one that does the Wrong Thing. Nobody wants that. Writing a deleted constructor as you have done is absolutely correct. \$\endgroup\$ Commented Aug 31, 2022 at 14:27
  • \$\begingroup\$ If it's not intended to be used directly, then consider hiding it in a suitable namespace (or perhaps even inside its public interface class, if there's just one of those). \$\endgroup\$ Commented Aug 31, 2022 at 14:29
  • \$\begingroup\$ I did, and I explained all of that, I just copied it over so it's easy to copy paste and try out. \$\endgroup\$
    – yotsugi
    Commented Aug 31, 2022 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.