Interest in circular span?

classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

Interest in circular span?

Boost - Dev mailing list
I am working on a circular queue library that contains a non-owning
circular span, a fixed-sized circular array, and a dynamically
resizable circular vector.

Would you be interested in adding such a library to Boost?

The design is inspired by Boost.CircularBuffer, std::span, and P0059R4
std::experimental::ring_span.

The code can be found at:

   https://github.com/breese/trial.circular

The documentation can be found at:

   https://github.com/breese/trial.circular/tree/develop/doc

circular::span can be used to implement the P0059R4 ring_span, as shown
in one of the example:

 
https://github.com/breese/trial.circular/blob/develop/example/p0059/ring_span.hpp

circular::span can also be used to implement most parts of
boost::circular_buffer; all except insertions and erasure at arbitrary
positions.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Interest in circular span?

Boost - Dev mailing list
On Thu, Sep 5, 2019 at 11:52 AM Bjorn Reese wrote:
>
> I am working on a circular queue library that contains a non-owning
> circular span, a fixed-sized circular array, and a dynamically
> resizable circular vector.
>
> Would you be interested in adding such a library to Boost?
>
> The design is inspired by Boost.CircularBuffer, std::span, and P0059R4
> std::experimental::ring_span.

I am interested. If you decide to go forward with a formal review,
consider this my endorsement.

Glen

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Interest in circular span?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 9/7/19 7:26 PM, Glen Fernandes wrote:

> I am interested. If you decide to go forward with a formal review,
> consider this my endorsement.

Thank you Glen.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Interest in circular span?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
>
> > I am working on a circular queue library that contains a non-owning
> > circular span, a fixed-sized circular array, and a dynamically
> > resizable circular vector.
> >
> > Would you be interested in adding such a library to Boost?
> >
> > The design is inspired by Boost.CircularBuffer, std::span, and P0059R4
> > std::experimental::ring_span.
>
> I am interested. If you decide to go forward with a formal review,
> consider this my endorsement.
>

As a big user of circular buffer, I'm always interested in seeing
improvements and new ideas on the same concept.
So same here for the endorsement...

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Interest in circular span?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list

> On 5. Sep 2019, at 17:52, Bjorn Reese via Boost <[hidden email]> wrote:
>
> I am working on a circular queue library that contains a non-owning
> circular span, a fixed-sized circular array, and a dynamically
> resizable circular vector.

It looks like circular span can adapt any suitable STL container into a circular one. In fact, circular array and vector are implemented by inheriting privately from std::array and circular::span, which is nice. However, wouldn't it be more general to provide a circular_adaptor, which works with any vector or array, and perhaps even any STL container? Perhaps someone wants a circular set?

> Would you be interested in adding such a library to Boost?
>
> The design is inspired by Boost.CircularBuffer, std::span, and P0059R4 std::experimental::ring_span.
>
> The code can be found at:
>
>  https://github.com/breese/trial.circular
>
> The documentation can be found at:
>
>  https://github.com/breese/trial.circular/tree/develop/doc

This is the source, the renderable documentation is here:

https://github.com/breese/trial.circular/blob/develop/doc/circular.adoc

The rationale is short, I would like to know why I should use this instead of boost.circular_buffer.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Interest in circular span?

Boost - Dev mailing list
On 9/9/19 12:43 AM, Hans Dembinski via Boost wrote:
>
>> On 5. Sep 2019, at 17:52, Bjorn Reese via Boost <[hidden email]> wrote:
>>
>> I am working on a circular queue library that contains a non-owning
>> circular span, a fixed-sized circular array, and a dynamically
>> resizable circular vector.
>
> It looks like circular span can adapt any suitable STL container into a circular one. In fact, circular array and vector are implemented by inheriting privately from std::array and circular::span, which is nice. However, wouldn't it be more general to provide a circular_adaptor, which works with any vector or array, and perhaps even any STL container? Perhaps someone wants a circular set?

FYI - I used such a library as an example in my CppCon Talk about how to
write documentation for a C++ library:

https://www.youtube.com/watch?v=YxmdCxX9dMk&t=3s

The talk was about documentation, but as a side effect produced a
library component similar to the above.  If any one want's to make use
of this - fine by me.  One benefit would be that he who programs
wouldn't have to write documentation - it's already done!

>
>> Would you be interested in adding such a library to Boost?
>>
>> The design is inspired by Boost.CircularBuffer, std::span, and P0059R4 std::experimental::ring_span.
>>
>> The code can be found at:
>>
>>   https://github.com/breese/trial.circular
>>
>> The documentation can be found at:
>>
>>   https://github.com/breese/trial.circular/tree/develop/doc
>
> This is the source, the renderable documentation is here:
>
> https://github.com/breese/trial.circular/blob/develop/doc/circular.adoc
>
> The rationale is short, I would like to know why I should use this instead of boost.circular_buffer.
>
> _______________________________________________
> Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
>



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Interest in circular span?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 9/9/19 9:43 AM, Hans Dembinski wrote:

> It looks like circular span can adapt any suitable STL container into a circular one. In fact, circular array and vector are implemented by inheriting privately from std::array and circular::span, which is nice. However, wouldn't it be more general to provide a circular_adaptor, which works with any vector or array, and perhaps even any STL container? Perhaps someone wants a circular set?

Circular span operates with any container that has contiguous storage.
The circular array and circular vector are there for convenience.

An adapter that works on arbitrary containers is an interesting idea.
Perhaps it should be conceptualized as a circular range instead.

> The rationale is short, I would like to know why I should use this instead of boost.circular_buffer.

I am preparing an appendix for the documentation to address this
question (together with the question of why I redesigned P0059R4
ring_span.)

The main reason is that boost::circular_buffer allocates the storage
for you, whereas you pass your storage to circular::span.

The span gives you greater flexibility; for instance you can use the
span on DMA buffers or static memory.

The span also gives you better performance. circular::array keeps its
storage and its internal state in the same memory block, which gives
better cache performance. We can also constexpr all the things.
Finally, my preliminary investigations show that the compiler is better
at auto-vectorization on circular::array than on boost::circular_buffer.

The boost::circular_buffer::array_range type that is used as the return
type for contiguous sub-ranges is a std::pair<pointer, size_type> so
it cannot be passed directly to standard algorithms or ranges.

boost:circular_buffer has no functions to return the unused contiguous
sub-ranges, which is useful in setups where if you have hardware (e.g.
DMA) that blits into the unused memory, and you only want to update the
circular span when the blit is completed.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Interest in circular span?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Thu, Sep 5, 2019 at 8:52 AM Bjorn Reese via Boost
<[hidden email]> wrote:
> Would you be interested in adding such a library to Boost?

+1 this sounds like a perfectly well-defined problem for which a Boost
library is appropriate.

Thanks

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Interest in circular span?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 9/09/2019 19:43, Hans Dembinski wrote:
> It looks like circular span can adapt any suitable STL container into a circular one. In fact, circular array and vector are implemented by inheriting privately from std::array and circular::span, which is nice. However, wouldn't it be more general to provide a circular_adaptor, which works with any vector or array, and perhaps even any STL container? Perhaps someone wants a circular set?

I'm curious what you mean by that.

Circularity implies the ability to do random indexing (on the underlying
container, even if hiding this from consumers), thus it should in
principle be compatible with any container that produces random access
iterators -- including array and vector, but not including set.

How would you imagine a "circular set" working?

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Interest in circular span?

Boost - Dev mailing list

> On 10. Sep 2019, at 01:32, Gavin Lambert via Boost <[hidden email]> wrote:
>
> On 9/09/2019 19:43, Hans Dembinski wrote:
>> It looks like circular span can adapt any suitable STL container into a circular one. In fact, circular array and vector are implemented by inheriting privately from std::array and circular::span, which is nice. However, wouldn't it be more general to provide a circular_adaptor, which works with any vector or array, and perhaps even any STL container? Perhaps someone wants a circular set?
>
> I'm curious what you mean by that.
>
> Circularity implies the ability to do random indexing (on the underlying container, even if hiding this from consumers), thus it should in principle be compatible with any container that produces random access iterators -- including array and vector, but not including set.
>
> How would you imagine a "circular set" working?

It probably doesn't make much sense. I didn't really think a lot about it, but in my defence, there are set implementations with random access iterators, namely boost::flat_set.
https://www.boost.org/doc/libs/1_71_0/doc/html/boost/container/flat_set.html

The main point of my suggestion was rather (as explained in a private email to Bjorn), that it may be better if the convenience classes circular::vector and circular::array are not hard-wired to use std::vector and std::array, but that the adapted container is a template parameter. There are other vector and array implementations that people may want to use, boost::vector and boost::static_vector come to mind.

The circular::vector template could look like this:

template <class T, class AdaptedContainer = std::vector<T>>
class vector : private AdaptedContainer, private circular::span<T> { … }

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: Interest in circular span?

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On 9/10/19 11:30 AM, Hans Dembinski via Boost wrote:

> The circular::vector template could look like this:
>
> template <class T, class AdaptedContainer = std::vector<T>>
> class vector : private AdaptedContainer, private circular::span<T> { … }

Something like this is doable.

I can easily change circular::array into a circular::basic_array that
takes a contiguous container type as template argument. This makes it
easy to use with other array and vector types. circular::array then
becomes a type alias that uses std::array.

I still have to investigate how feasible this is for circular::vector
which is resizeable.

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost