Add ring queues - Githubissues

boostorg / container

STL-like containers from Boost

http://www.boost.org/libs/container/

Boost Software License 1.0

100 stars 116 forks source link

Add ring queues #121

Closed Lastique closed 4 years ago

Lastique commented 5 years ago

This PR proposes two new components for inclusion in Boost.Container:

ring_queue - a FIFO queue, similar to std::queue, which uses a circular buffer to store elements, and
small_ring_queue - same as ring_queue but with a statically allocated internal storage for a (small) number of elements.

The queues are more optimal than std::queue in cases when maximum number of enqueued elements is relatively constant. Circular buffer allows to effectively eliminate dynamic memory allocations, making queue performance more stable. small_ring_queue allows to eliminate memory allocations completely, provided that the queue does not exceed the internal capacity. Given that the circular buffer is contiguous, the queues are also more CPU cache friendly.

This PR adds implementation, tests and documentation. The implementation requires C++17 currently, for this reason I did not include forward declarations in container_fwd.hpp.

Lastique commented 5 years ago

Ping, any feedback?

igaztanaga commented 5 years ago

Thanks for the proprosal.

I haven't received any interest from users on these type of containers. How is different from a circular buffer? Maybe you should propose them for Boost circular buffer library, or start a discussion in the mailing list (maybe there was one but I missed it).

Note: Being C++17-only is also a problem for Boost.Container, it still supports C++03 for all elements.

Lastique commented 5 years ago

circular_buffer has a different design, which is not quite compatible with the ring queue I implemented. In particular, circular_buffer usage pattern implies that the user sets the buffer capacity and then proceeds pushing elements to the container; the container then transparently replaces the oldest elements as it "rolls over". Ring queue does not overwrite enqueued elements, you have to dequeue them, as you normally would with std::queue.

Regarding C++17 requirement, I could probably relax it, although it would complicate code quite a bit. I thought there were C++11-only components in Boost.Container, but I might be mistaken. If there is interest, I can try lowering it to C++11; for C++03 I think it would require quite a lot of effort, while the benefit isn't clear.

SteelBlueVision commented 4 years ago

This actually looks quite useful. Is it still being considered for inclusion?

igaztanaga commented 4 years ago

The proposal was discussed in the mailing list, and Boost.CircularBuffer or an independent library seems a better way to introduce them in Boost.