Search code examples
c++circular-buffer

Why is the circular buffer not standardized in C++?

I want to know the history of the standardization of the circular buffer(circular queue or deque).

AFAIK, the current C++ standard(C++ 2023) doesn't provide a circular buffer in the STL. I googled and found only one proposal, ring_span around 2015. Boost has the circular_buffer. Some provide in-house implementations, such as cqueue.

If you repeat push and pop operations with a std::deque, you repeat allocating and freeing heap blocks. In Qt(one of largest C++ projects), the situation is worse, where QQueue keeps allocating heap blocks(and never freeing).

I'm not asking for opinions. I want to know the history. I expect good reasons why it was so hard to standardize the circular buffer.

Solution

  • Coauthor of P0059R1–R4 here. As Sebastian said above, there's some information relevant to why P0059R4 was abandoned in "View types with metadata cause problems" (2018-05-30). P0059R4 proposed a "view with metadata," basically like this:

    struct ring_span {
  std::span<T> data_;
  T *actual_front_;
  T *actual_back_;
};

    The problem with that is, suppose you say:

    ring_span a = (something with 10 elements);
ring_span b = a;
a.pop_front();

    Then surely either b will be a valid ringbuffer with 9 elements (just like a), or else b will be a valid ringbuffer with 10 elements (just like a disjoint copy of a)? With P0059R4 ring_span, neither thing happens. Instead, b remains a view onto the same underlying array as a, but a.actual_front_ has incremented while b.actual_front_ has not — therefore, b cannot be used safely anymore. That's bad.

    Now, if you go back and look at P0059R0, you'll see a different design. P0059R0's ring adaptor wasn't a view-with-metadata; it was properly owning, like priority_queue. Ownership is the correct choice here. (I say that despite being the person who pushed the non-owning design into R1!) But the problem with ownership is that we end up needing two different adaptors. P0059R0 called them dynamic_ring and fixed_ring. The former adapts a vector; the latter adapts an array. The former can be constructed with a capacity, like dynamic_ring<T>(100); the latter can't (because the capacity is fixed as part of the underlying container type). SG14 was unable to come up with any way to "merge" these two designs (dynamic and fixed) into a single vocabulary type; and yet, it seems silly to put two subtly different ring-buffer types into the STL. Ring-buffer doesn't "deserve" that much real estate; it's a niche problem.

    Besides, the "container adaptor" has another problem. Suppose I have a ringbuffer of a million elements. I'm using a vector<T> to hold them. So when I construct the ringbuffer, I must resize the vector, eagerly constructing a million elements? And then push_back/pop_front will use assignment to modify them? That means I can't make a ringbuffer of non-assignable T? That's bad. (P0059R1 tackled this problem by allowing the underlying array to be stored in raw memory so that the ring_span and/or Popper could control element lifetimes, instead of having to manage those lifetimes via something like a vector.)

    This indicates the real problem with ringbuffers in C++: Everyone who "wants ringbuffers" wants something slightly different! In the comments above, @Timmmm points to Rust's VecDeque as a good ringbuffer. But (at least as I read those docs), VecDeque actually has no upper bound on its capacity — as you increase its size, it will reallocate, invalidating pointers and references to the existing elements! To at least some people (myself included), if your data structure can arbitrary relocate elements in memory, it's not a ringbuffer at all. It's just a dynamically allocated deque; and the C++ STL already has one of those.

    Other SG14 participants wanted a ringbuffer that could be used from two threads concurrently — a SPSC queue. (See Lawrence Crowl's perennial P0260.) We decided that thread-safety was far out-of-scope for P0059. But if the people want a SPSC queue, then why should we pursue P0059's thread-unsafe version at all? It's just sucking up committee time that could be used for more desirable things.

    Finally, let me challenge your frame a little bit: You write,

    If you repeat push and pop operations with a std::deque, you repeat allocating and freeing heap blocks. In Qt (one of largest C++ projects), the situation is worse, where QQueue keeps allocating heap blocks (and never freeing).

    That sounds like you should be filing bug reports and feature requests about the existing implementations, not asking for the paper standard to specify something new. I'm well aware that there's a ton of vendor divergence around deque implementations (I owe a blog post to Asclepius on that subject), so you would be absolutely correct if you'd said "...you risk allocating and deallocating heap blocks." But for example libc++ has a pretty good implementation that can be used as a fixed-capacity ringbuffer with zero heap traffic at all: Godbolt. When the subarray on the front is emptied, libc++ simply shuffles it to the back, ready to accept new elements. libstdc++ fails to implement this obvious optimization; but that's not the paper standard's fault, it's libstdc++'s fault. Worse, Microsoft STL famously implements deque with only 16 bytes per subarray: Microsoft's deque<string> is strictly worse than forward_list<string>. But again that's an obvious defect in Microsoft's code — it can't be resolved on the level of the paper standard. Someone should file a bug report and then fix it.

    TLDR: Especially if you're happy with Rust's VecDeque, then libc++'s deque is exactly the ringbuffer you're looking for; and if your library vendor's deque is worse than libc++'s, you should just file a bug report. Or, if your notion of "ringbuffer" is different from deque, then statistically you wouldn't have been happy with P0059's solution either — the word "ringbuffer" just means too many different things to too many different constituencies.