[container] Proposal for ring queues
Hi, Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container: https://github.com/boostorg/container/pull/121 The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit. In his reply in that PR Ion was not very enthusiastic about including these containers into Boost.Container mostly because (a) there was presumably not much interest from users and (b) because the current implementation requires C++17 while Boost.Container supports C++03. I would like to ask if there is interest in the community for these kinds of containers. I know I would find them useful, and at least one person commented in the PR to the same effect. However, I would still like to see if more people need this. If there is interest, what would be the preferred course of action? 1. Should we work on inclusion into Boost.Container or maybe some other library? Candidates? Boost.CircularBuffer was mentioned in the PR, although I'm not sure it is suitable for these components. Creating a new submodule is also a possibility, although it seems like an overkill. 2. Somewhat related to p.1, what minimum C++ version is preferred. E.g. if we agree that Boost.Container is the right place for these components, I could work on lowering minimum C++ version, although C++03 would complicate things considerably. Thanks.
-----Original Message----- From: Boost <boost-bounces@lists.boost.org> On Behalf Of Andrey Semashev via Boost Sent: 21 May 2020 23:18 To: boost@lists.boost.org List <boost@lists.boost.org> Cc: Andrey Semashev <andrey.semashev@gmail.com> Subject: [boost] [container] Proposal for ring queues
Hi,
Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:
https://github.com/boostorg/container/pull/121
The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit.
In his reply in that PR Ion was not very enthusiastic about including these containers into Boost.Container mostly because (a) there was presumably not much interest from users and (b) because the current implementation requires C++17 while Boost.Container supports C++03.
I would like to ask if there is interest in the community for these kinds of containers. I know I would find them useful, and at least one person commented in the PR to the same effect. However, I would still like to see if more people need this.
If there is interest, what would be the preferred course of action?
1. Should we work on inclusion into Boost.Container or maybe some other library? Candidates? Boost.CircularBuffer was mentioned in the PR, although I'm not sure it is suitable for these components. Creating a new submodule is also a possibility, although it seems like an overkill.
2. Somewhat related to p.1, what minimum C++ version is preferred. E.g. if we agree that Boost.Container is the right place for these components, I could work on lowering minimum C++ version, although C++03 would complicate things considerably.
FWIW ... I suspect that code will be easier to write, will work better, be more readable and understandable, and go faster using the most recent C++ std. It ought to be! So I favour a new library Boost.RingQueue. It meets two niche requirements, but neither too small a niche. Paul PS Some links in the docs of all three libraries should refer to a summary of the various pros and cons and use cases. So users can chose the est/right tool for their project.
On Fri, 22 May 2020 at 04:17, Paul A Bristow via Boost < boost@lists.boost.org> wrote:
-----Original Message----- From: Boost <boost-bounces@lists.boost.org> On Behalf Of Andrey Semashev via Boost Sent: 21 May 2020 23:18 To: boost@lists.boost.org List <boost@lists.boost.org> Cc: Andrey Semashev <andrey.semashev@gmail.com> Subject: [boost] [container] Proposal for ring queues
Hi,
Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:
https://github.com/boostorg/container/pull/121
The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit.
In his reply in that PR Ion was not very enthusiastic about including these containers into Boost.Container mostly because (a) there was presumably not much interest from users and (b) because the current implementation requires C++17 while Boost.Container supports C++03.
I would like to ask if there is interest in the community for these kinds of containers. I know I would find them useful, and at least one person commented in the PR to the same effect. However, I would still like to see if more people need this.
If there is interest, what would be the preferred course of action?
1. Should we work on inclusion into Boost.Container or maybe some other library? Candidates? Boost.CircularBuffer was mentioned in the PR, although I'm not sure it is suitable for these components. Creating a new submodule is also a possibility, although it seems like an overkill.
2. Somewhat related to p.1, what minimum C++ version is preferred. E.g. if we agree that Boost.Container is the right place for these components, I could work on lowering minimum C++ version, although C++03 would complicate things considerably.
FWIW ...
I suspect that code will be easier to write, will work better, be more readable and understandable, and go faster using the most recent C++ std. It ought to be!
So I favour a new library Boost.RingQueue. It meets two niche requirements, but neither too small a niche.
What about using *std::circular_list,* an end-to-begin-connected *std::list ?* degski -- @systemdeg "We value your privacy, click here!" Sod off! - degski "Anyone who believes that exponential growth can go on forever in a finite world is either a madman or an economist" - Kenneth E. Boulding "Growth for the sake of growth is the ideology of the cancer cell" - Edward P. Abbey
On Sat, 23 May 2020 at 13:13, Andrey Semashev via Boost < boost@lists.boost.org> wrote:
On 2020-05-23 21:02, degski via Boost wrote:
What about using *std::circular_list,* an end-to-begin-connected *std::list ?*
This *plf::list <https://www.plflib.org/list.htm>* is doing exactly that (allocating in increasingly larger blocks, re-using as possible). It is written on top of *plf::colony*, I seem to remember it was proposed as a Boost addittion but was rejected. degski -- @systemdeg "We value your privacy, click here!" Sod off! - degski "Anyone who believes that exponential growth can go on forever in a finite world is either a madman or an economist" - Kenneth E. Boulding "Growth for the sake of growth is the ideology of the cancer cell" - Edward P. Abbey
On Sat, 23 May 2020 at 13:20, degski <degski@gmail.com> wrote:
On Sat, 23 May 2020 at 13:13, Andrey Semashev via Boost < boost@lists.boost.org> wrote:
On 2020-05-23 21:02, degski via Boost wrote:
What about using *std::circular_list,* an end-to-begin-connected *std::list ?*
This *plf::list <https://www.plflib.org/list.htm>* is doing exactly that (allocating in increasingly larger blocks, re-using as possible). It is written on top of *plf::colony*, I seem to remember it was proposed as a Boost addition but was rejected.
In case my message still was unclear, very possibly. I'm saying is to create a replacement for std::list, this std::list-v2 is in effect a circular_list, the generalization can be done at no cost and overall the design will/can be better even when viewed as a std::list. degski -- @systemdeg "We value your privacy, click here!" Sod off! - degski "Anyone who believes that exponential growth can go on forever in a finite world is either a madman or an economist" - Kenneth E. Boulding "Growth for the sake of growth is the ideology of the cancer cell" - Edward P. Abbey
On Sat, 23 May 2020 at 13:02, degski <degski@gmail.com> wrote:
On Fri, 22 May 2020 at 04:17, Paul A Bristow via Boost < boost@lists.boost.org> wrote:
-----Original Message----- From: Boost <boost-bounces@lists.boost.org> On Behalf Of Andrey Semashev via Boost Sent: 21 May 2020 23:18 To: boost@lists.boost.org List <boost@lists.boost.org> Cc: Andrey Semashev <andrey.semashev@gmail.com> Subject: [boost] [container] Proposal for ring queues
Hi,
Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:
https://github.com/boostorg/container/pull/121
The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit.
In his reply in that PR Ion was not very enthusiastic about including these containers into Boost.Container mostly because (a) there was presumably not much interest from users and (b) because the current implementation requires C++17 while Boost.Container supports C++03.
I would like to ask if there is interest in the community for these kinds of containers. I know I would find them useful, and at least one person commented in the PR to the same effect. However, I would still like to see if more people need this.
If there is interest, what would be the preferred course of action?
1. Should we work on inclusion into Boost.Container or maybe some other library? Candidates? Boost.CircularBuffer was mentioned in the PR, although I'm not sure it is suitable for these components. Creating a new submodule is also a possibility, although it seems like an overkill.
2. Somewhat related to p.1, what minimum C++ version is preferred. E.g. if we agree that Boost.Container is the right place for these components, I could work on lowering minimum C++ version, although C++03 would complicate things considerably.
FWIW ...
I suspect that code will be easier to write, will work better, be more readable and understandable, and go faster using the most recent C++ std. It ought to be!
So I favour a new library Boost.RingQueue. It meets two niche requirements, but neither too small a niche.
What about using *std::circular_list,* an end-to-begin-connected *std::list ?*
Apologies, I meant to write *boost::container::circular_list *an end-to-begin-connected* boost::container::list ?* degski PS: ;) -- @systemdeg "We value your privacy, click here!" Sod off! - degski "Anyone who believes that exponential growth can go on forever in a finite world is either a madman or an economist" - Kenneth E. Boulding "Growth for the sake of growth is the ideology of the cancer cell" - Edward P. Abbey
On Thu, 21 May 2020 at 23:17, Andrey Semashev via Boost <boost@lists.boost.org> wrote:
I would like to ask if there is interest in the community for these kinds of containers. I know I would find them useful, and at least one person commented in the PR to the same effect. However, I would still like to see if more people need this.
I don't understand the use cases for your container. If I want a queue with bounded capacity, I use a circular buffer. If I want a queue with unbounded capacity, I use std::deque. What's the advantage of your approach compared to std::deque? Assuming a decent state of the art implementation.
On 2020-05-22 13:01, Mathias Gaunard wrote:
On Thu, 21 May 2020 at 23:17, Andrey Semashev via Boost <boost@lists.boost.org> wrote:
I would like to ask if there is interest in the community for these kinds of containers. I know I would find them useful, and at least one person commented in the PR to the same effect. However, I would still like to see if more people need this.
I don't understand the use cases for your container. If I want a queue with bounded capacity, I use a circular buffer.
circular_buffer is not a queue. The important difference is that it overwrites older elements as you keep pushing new elements into it. std::queue and ring queues instead preserve all pushed elements until you dequeue them.
If I want a queue with unbounded capacity, I use std::deque.
What's the advantage of your approach compared to std::deque? Assuming a decent state of the art implementation.
As I said, the main advantage is avoiding dynamic memory allocations, which you get with std::queue and std::deque. This can be important if you need a stable latency of push/pop operations or don't want dynamic memory allocations for other reasons.
On Fri, 22 May 2020, 11:24 Andrey Semashev via Boost, <boost@lists.boost.org> wrote:
circular_buffer is not a queue. The important difference is that it overwrites older elements as you keep pushing new elements into it.
That's just the behaviour when you run out of capacity. Nothing prevents you from checking you're out of capacity and have different behaviour instead. As I said, the main advantage is avoiding dynamic memory allocations You cannot avoid memory allocations if your queue is unbounded. If pre-allocation of some size is a concern you can just use an adequate allocator. For full memory management flexibility one can also build a circular buffer view on a manually managed contiguous piece of memory.
On 2020-05-22 14:32, Mathias Gaunard wrote:
On Fri, 22 May 2020, 11:24 Andrey Semashev via Boost, <boost@lists.boost.org <mailto:boost@lists.boost.org>> wrote:
circular_buffer is not a queue. The important difference is that it overwrites older elements as you keep pushing new elements into it.
That's just the behaviour when you run out of capacity. Nothing prevents you from checking you're out of capacity and have different behaviour instead.
Yes, that is a possible workaround, but definitely not the intended use of a circular buffer.
As I said, the main advantage is avoiding dynamic memory allocations
You cannot avoid memory allocations if your queue is unbounded.
If pre-allocation of some size is a concern you can just use an adequate allocator.
One allocation might not be a problem, and small_ring_queue allows to avoid even that, if the optimal capacity is known at compile time. However, std::deque continues to dynamically allocate chunks as you push and pop elements, even if the average number of enqueued elements stays the same. This is avoided by ring queues.
On Fri, 22 May 2020 at 15:08, Andrey Semashev via Boost <boost@lists.boost.org> wrote:
However, std::deque continues to dynamically allocate chunks as you push and pop elements, even if the average number of enqueued elements stays the same. This is avoided by ring queues.
Nothing prevents you from using a pool allocator with a deque.
On Fri, 22 May 2020 at 15:44, Peter Dimov via Boost <boost@lists.boost.org> wrote:
Mathias Gaunard wrote:
Nothing prevents you from using a pool allocator with a deque.
And nothing prevents me from using the proposed ring_queue instead. Do you have a better point than "you can achieve the same effect in a more complicated and stupider way"?
I don't think combining two well-established generic tools in a way they are meant to be is either of "complicated" or "stupid". Of course you can always roll out something special for every use case. But that comes with a lot of overhead of maintaining it compatible with other components, flexible, efficient and bug-free. Less code is better than more. Ultimately the fact that uses are not too niche or that there is significant value on top of existing solutions are criteria for illegibility for Boost. Not that those criteria are very heavily enforced, as we have a lot of libraries that only target domain specialists, so it's up to how strongly people feel about things.
On 2020-05-22 17:31, Mathias Gaunard wrote:
On Fri, 22 May 2020 at 15:08, Andrey Semashev via Boost <boost@lists.boost.org> wrote:
However, std::deque continues to dynamically allocate chunks as you push and pop elements, even if the average number of enqueued elements stays the same. This is avoided by ring queues.
Nothing prevents you from using a pool allocator with a deque.
I agree with Peter in that it is a much more complicated solution. It is likely much less efficient, too. For example, such an allocator has to be prepared that it will be used to allocate buffers of different types and sizes, so it will be difficult to predict, which allocations need to be pooled and which are not. Then the complications from allocator propagation, rebinding, conversion and comparison. It is easier to implement a new container than a non-trivial allocator, really.
On 22/05/2020 16:08, Andrey Semashev via Boost wrote:
One allocation might not be a problem, and small_ring_queue allows to avoid even that, if the optimal capacity is known at compile time.
However, std::deque continues to dynamically allocate chunks as you push and pop elements, even if the average number of enqueued elements stays the same. This is avoided by ring queues.
Independently from a future Boost.RingQueue or integrated into Boost.CircularBufer (which I think it's be correct module), having a boost::container::deque that conserves capacity (already allocated buffers) so that continuous dynamic allocation does not happen is a nice to have feature. Best, Ion
On 2020-05-22 16:08, Andrey Semashev via Boost wrote:
One allocation might not be a problem, and small_ring_queue allows to avoid even that, if the optimal capacity is known at compile time.
This corresponds almost to https://github.com/breese/trial.circular/blob/develop/include/trial/circular... This is a circular buffer that operates on an std::vector. Capacity is only increased when the user calls reserve(). It is trivial to write a wrapper on top of this that automatically increases capacity when the buffer is full.
On 5/21/20 3:17 PM, Andrey Semashev via Boost wrote:
Hi,
Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:
https://github.com/boostorg/container/pull/121
The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit.
In his reply in that PR Ion was not very enthusiastic about including these containers into Boost.Container mostly because (a) there was presumably not much interest from users and (b) because the current implementation requires C++17 while Boost.Container supports C++03.
I would like to ask if there is interest in the community for these kinds of containers. I know I would find them useful, and at least one person commented in the PR to the same effect. However, I would still like to see if more people need this.
If there is interest, what would be the preferred course of action?
1. Should we work on inclusion into Boost.Container or maybe some other library? Candidates? Boost.CircularBuffer was mentioned in the PR, although I'm not sure it is suitable for these components. Creating a new submodule is also a possibility, although it seems like an overkill.
2. Somewhat related to p.1, what minimum C++ version is preferred. E.g. if we agree that Boost.Container is the right place for these components, I could work on lowering minimum C++ version, although C++03 would complicate things considerably.
Thanks.
_______________________________________________ Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
FWIW - I made a ring_view library as part of my talk on how to document your own library. Interesting features: a) It has almost no features - simplest possible implement b) library user provides his own fixed size storage c) so there's not allocation d) supports any pair of forward iterators. So it isn't dependent on the container type the user might prefer. std::array works just fine. e) it's very simple - just one header file - though it depends on a couple others. f) Documentation is already written! You can download the talk, slides and library here: http://www.rrsd.com/software_development/boost/CppCon%202017/CppCon%202017.z... Robert Ramey
On 22/05/2020 10:17, Andrey Semashev wrote:
Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:
https://github.com/boostorg/container/pull/121
The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit.
Boost.Lockfree [1] already contains such a queue (which operates similar to a ring-buffer when set to fixed capacity, but can be configured to be dynamic). The queue doesn't implement a ring buffer, but can be used as if it did. The spsc_queue actually uses a ring buffer internally. They implement "push fails" if the buffer is full when fixed-capacity, but (provided you use the multi-consumer version, or prevent concurrent access some other way) there's no reason why you couldn't pop and retry if you want overwrite-like behaviour. Usually I personally find that if I care about memory allocation then I care about locking as well. [1]: https://www.boost.org/doc/libs/1_73_0/doc/html/lockfree.html
On Sun, 24 May 2020 at 22:38, Gavin Lambert via Boost <boost@lists.boost.org> wrote:
On 22/05/2020 10:17, Andrey Semashev wrote:
Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:
https://github.com/boostorg/container/pull/121
The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit.
Boost.Lockfree [1] already contains such a queue (which operates similar to a ring-buffer when set to fixed capacity, but can be configured to be dynamic).
I reacted earlier in this thread and was erroneously babbling on about unbounded circular lists. You will say I'm a lousy reader, I on the other hand could not imagine you would not use https://www.threadingbuildingblocks.org/docs/help/reference/containers_overv... for one moment (i.e. that that problem was covered). Is Boost.Lockfree being developed? degski -- @systemdeg "We value your privacy, click here!" Sod off! - degski "Anyone who believes that exponential growth can go on forever in a finite world is either a madman or an economist" - Kenneth E. Boulding "Growth for the sake of growth is the ideology of the cancer cell" - Edward P. Abbey
On 2020-05-25 06:37, Gavin Lambert via Boost wrote:
On 22/05/2020 10:17, Andrey Semashev wrote:
Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:
https://github.com/boostorg/container/pull/121
The ring queues work similarly to std::queue with the main difference being that they use a ring buffer internally to store elements. The small_ring_queue also allows to allocate a static storage for a fixed amount of elements. The benefit of this is that dynamic memory allocations can be practically avoided when the number of enqueued elements does not exceed some limit.
Boost.Lockfree [1] already contains such a queue (which operates similar to a ring-buffer when set to fixed capacity, but can be configured to be dynamic).
The obvious difference is that it is lock-free, which is not always needed.
Andrey Semashev wrote:
Hi,
Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:
Interestingly, the committee is now discussing a proposal to make std::queue constexpr, and it came up that no standard container can ever be used with a constexpr std::queue, because no standard container can have a constexpr pop_front. However, it seems to me that both a "ring deque" and a vector-deque as in DoubleEnded can provide a constexpr pop_front (in C++20.) This might or might not be a sufficient reason to pursue these.
On 2020-06-15 18:51, Peter Dimov via Boost wrote:
Andrey Semashev wrote:
Hi,
Some time ago I have proposed to include ring_queue and small_ring_queue containers to Boost.Container:
Interestingly, the committee is now discussing a proposal to make std::queue constexpr, and it came up that no standard container can ever be used with a constexpr std::queue, because no standard container can have a constexpr pop_front.
However, it seems to me that both a "ring deque" and a vector-deque as in DoubleEnded can provide a constexpr pop_front (in C++20.)
This might or might not be a sufficient reason to pursue these.
I see, thanks for the info. I'll see if I can propose ring queues as a separate library then.
On 2020-06-15 19:11, Peter Dimov via Boost wrote:
Andrey Semashev wrote:
I see, thanks for the info. I'll see if I can propose ring queues as a separate library then.
I'd prefer containers and not queues though. That is, {push,pop}_{front,back} instead of push/pop. "Ring deque".
Containers are less appealing for the ring design because erasing and inserting at arbitrary position will be inefficient. Though the same is also true for std::deque and std::vector...
Andrey Semashev wrote:
I'd prefer containers and not queues though. That is, {push,pop}_{front,back} instead of push/pop. "Ring deque".
Containers are less appealing for the ring design because erasing and inserting at arbitrary position will be inefficient. Though the same is also true for std::deque and std::vector...
Erasing/inserting at begin()+k for small k will be considerably more efficient than vector.
On Mon, 15 Jun 2020 at 11:32, Peter Dimov via Boost <boost@lists.boost.org> wrote:
Andrey Semashev wrote:
I'd prefer containers and not queues though. That is, {push,pop}_{front,back} instead of push/pop. "Ring deque".
Containers are less appealing for the ring design because erasing and inserting at arbitrary position will be inefficient. Though the same is also true for std::deque and std::vector...
Erasing/inserting at begin()+k for small k will be considerably more efficient than vector.
Another approach worth exploring in my opinion is *to change 'the allocator' from being a std-node-allocator to being a node=allocator that 'dispenses' from a std::vector.* Such an 'allocator' exists, i.e. 'plf::colony'. Now our LL (the ring) has vector-allocation-patterns behind it [see docs plf::colcony], with an added benefit: the nodes are like with std::allocator never moved. The latter is currently (due to implementation details, which will change) not strictly true, notably reserve() moves objects (reserve() is not usable with non-movable objects), but plf::colony is otherwise well usable for non-movable-non-copyable types (contrary to what is said in the docs). I have written a PoC <https://github.com/degski/this_local/blob/b6305194e14de6c6678cea6a847d1aee0021d2b1/include/this_local/this_local/detail/this_local/detail.hpp#L503> . degski
On 17/06/2020 22:01, degski wrote:
Another approach worth exploring in my opinion is *to change 'the allocator' from being a std-node-allocator to being a node=allocator that 'dispenses' from a std::vector.* Such an 'allocator' exists, i.e. 'plf::colony'. Now our LL (the ring) has vector-allocation-patterns behind it [see docs plf::colcony], with an added benefit: the nodes are like with std::allocator never moved. The latter is currently (due to implementation details, which will change) not strictly true, notably reserve() moves objects (reserve() is not usable with non-movable objects), but plf::colony is otherwise well usable for non-movable-non-copyable types (contrary to what is said in the docs). I have written a PoC <https://github.com/degski/this_local/blob/b6305194e14de6c6678cea6a847d1aee0021d2b1/include/this_local/this_local/detail/this_local/detail.hpp#L503>
Using an interface that requires throwing an exception to indicate "buffer full" (due to failure to allocate a new node from a fixed-capacity buffer, and allocators lacking any other means to indicate allocation failure) doesn't seem entirely desirable.
participants (9)
-
Andrey Semashev -
Bjorn Reese -
degski -
Gavin Lambert -
Ion Gaztañaga -
Mathias Gaunard -
pbristow＠hetp.u-net.com -
Peter Dimov -
Robert Ramey