[container] Contributing 'stationary_vector' to Boost

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

[container] Contributing 'stationary_vector' to Boost

Boost - Dev mailing list
Hi all,

Happy new year! New mailing list member here.

I've developed an STL-style stationary_vector class that retains elements
in-place when growing.
Very briefly, it is effectively a piecewise-contiguous vector, with the
following advantages over vector:

   - Appending has O(1) overhead in the *worst* case (e.g., push_back() does
   not move elements)
   - Insertion and random-access can be done in parallel, as prior
   iterators & references remain valid

This has a variety of benefits, including better UX (no "hiccups" due to
reallocations), and the ability to simplify parallel processing of
streaming data.
It occurred to me the larger C++ community might find this useful.

I was wondering if there would be interest in incorporating it into
Boost.Container, and if so, what steps I could take to make that happen?

I'm of course happy to discuss the design etc. with anyone who might be
interested.

Summary:
https://github.com/mehrdadn/libvital/blob/master/doc/vital/container/stationary_vector.md
Implementation:
https://github.com/mehrdadn/libvital/blob/master/include/vital/container/stationary_vector.hpp

Thank you,
Mehrdad

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

Re: [container] Contributing 'stationary_vector' to Boost

Boost - Dev mailing list
Hi,

> On 4. Jan 2021, at 13:17, Mehrdad Niknami via Boost <[hidden email]> wrote:
>
> Hi all,
>
> Happy new year! New mailing list member here.
>
> I've developed an STL-style stationary_vector class that retains elements
> in-place when growing.
> Very briefly, it is effectively a piecewise-contiguous vector, with the
> following advantages over vector:
>
>   - Appending has O(1) overhead in the *worst* case (e.g., push_back() does
>   not move elements)
>   - Insertion and random-access can be done in parallel, as prior
>   iterators & references remain valid
>
> This has a variety of benefits, including better UX (no "hiccups" due to
> reallocations), and the ability to simplify parallel processing of
> streaming data.
> It occurred to me the larger C++ community might find this useful.
>
> I was wondering if there would be interest in incorporating it into
> Boost.Container, and if so, what steps I could take to make that happen?

It sounds like you reinvented a deque?
https://en.cppreference.com/w/cpp/container/deque

Best regards,
Hans

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

Re: [container] Contributing 'stationary_vector' to Boost

Boost - Dev mailing list
Hi,

It's similar, but not quite. std::deque uses fixed-size blocks and tends to
be slow in my experience (at least in some implementations).
stationary_vector on the other hand uses variably-sized blocks (with
geometrically increasing sizes).
Its capacity at *least* doubles every round; in fact, it reduces to a
single array when the entire size is reserved beforehand.
This allows it to perform much more competitively with (and similarly to)
std::vector.
It may be what std::deque *should* have been, but isn't currently.

Thanks,
Mehrdad

On Mon, Jan 4, 2021 at 6:17 AM Hans Dembinski <[hidden email]>
wrote:

> Hi,
>
> > On 4. Jan 2021, at 13:17, Mehrdad Niknami via Boost <
> [hidden email]> wrote:
> >
> > Hi all,
> >
> > Happy new year! New mailing list member here.
> >
> > I've developed an STL-style stationary_vector class that retains elements
> > in-place when growing.
> > Very briefly, it is effectively a piecewise-contiguous vector, with the
> > following advantages over vector:
> >
> >   - Appending has O(1) overhead in the *worst* case (e.g., push_back()
> does
> >   not move elements)
> >   - Insertion and random-access can be done in parallel, as prior
> >   iterators & references remain valid
> >
> > This has a variety of benefits, including better UX (no "hiccups" due to
> > reallocations), and the ability to simplify parallel processing of
> > streaming data.
> > It occurred to me the larger C++ community might find this useful.
> >
> > I was wondering if there would be interest in incorporating it into
> > Boost.Container, and if so, what steps I could take to make that happen?
>
> It sounds like you reinvented a deque?
> https://en.cppreference.com/w/cpp/container/deque
>
> Best regards,
> Hans

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

Re: [container] Contributing 'stationary_vector' to Boost

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Tue, Jan 5, 2021 at 12:35 AM Mehrdad Niknami via Boost <
[hidden email]> wrote:

> Hi all,
>
> Happy new year! New mailing list member here.
>
> I've developed an STL-style stationary_vector class that retains elements
> in-place when growing.
>

hello

This looks very similar to stable_vector.

https://www.boost.org/doc/libs/1_75_0/doc/html/boost/container/stable_vector.html

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

Re: [container] Contributing 'stationary_vector' to Boost

Boost - Dev mailing list
Hi,

This shares some similarities to stable_vector, but it has some critical
differences.
One is that elements are *not* fully stable; elements that *follow* the
insertion point are still shifted forward.
Another is that contiguous elements are *mostly* stored contiguously, in
arrays that preserve the logical order.
(The elements are *not* stored in nodes scattered in arbitrary order across
memory and hence there is no per-element overhead, unlike in stable_vector.)

This results in much better performance, closer to that of vector.

Mehrdad

On Mon, Jan 4, 2021 at 4:58 PM Barath Kannan via Boost <
[hidden email]> wrote:

> On Tue, Jan 5, 2021 at 12:35 AM Mehrdad Niknami via Boost <
> [hidden email]> wrote:
>
> > Hi all,
> >
> > Happy new year! New mailing list member here.
> >
> > I've developed an STL-style stationary_vector class that retains elements
> > in-place when growing.
> >
>
> hello
>
> This looks very similar to stable_vector.
>
>
> https://www.boost.org/doc/libs/1_75_0/doc/html/boost/container/stable_vector.html
>
> _______________________________________________
> 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: [container] Contributing 'stationary_vector' to Boost

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

> On 4. Jan 2021, at 19:45, Mehrdad Niknami <[hidden email]> wrote:
>
> It's similar, but not quite. std::deque uses fixed-size blocks and tends to be slow in my experience (at least in some implementations).
> stationary_vector on the other hand uses variably-sized blocks (with geometrically increasing sizes).
> Its capacity at least doubles every round; in fact, it reduces to a single array when the entire size is reserved beforehand.
> This allows it to perform much more competitively with (and similarly to) std::vector.
> It may be what std::deque should have been, but isn't currently.

Ok, that sounds like your container offers the same basic guarantees as a std::deque with a more efficient implementation. If it is indeed more efficient due to the use of variable-sized blocks than boost::container::deque, then could you include your improvements into boost::container::deque?

https://github.com/boostorg/container/blob/develop/include/boost/container/deque.hpp

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

Re: [container] Contributing 'stationary_vector' to Boost

Boost - Dev mailing list
Not quite - my container is single-ended.

Mehrdad

On Tue, Jan 5, 2021 at 9:23 AM Hans Dembinski <[hidden email]>
wrote:

>
> > On 4. Jan 2021, at 19:45, Mehrdad Niknami <[hidden email]> wrote:
> >
> > It's similar, but not quite. std::deque uses fixed-size blocks and tends
> to be slow in my experience (at least in some implementations).
> > stationary_vector on the other hand uses variably-sized blocks (with
> geometrically increasing sizes).
> > Its capacity at least doubles every round; in fact, it reduces to a
> single array when the entire size is reserved beforehand.
> > This allows it to perform much more competitively with (and similarly
> to) std::vector.
> > It may be what std::deque should have been, but isn't currently.
>
> Ok, that sounds like your container offers the same basic guarantees as a
> std::deque with a more efficient implementation. If it is indeed more
> efficient due to the use of variable-sized blocks than
> boost::container::deque, then could you include your improvements into
> boost::container::deque?
>
>
> https://github.com/boostorg/container/blob/develop/include/boost/container/deque.hpp

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

Re: [container] Contributing 'stationary_vector' to Boost

Boost - Dev mailing list
On Tue, Jan 5, 2021 at 12:53 PM Mehrdad Niknami via Boost <
[hidden email]> wrote:

> Not quite - my container is single-ended.
>
I assume this is because you grow your block size as you extend the vector.
Without looking at the implementation of deque, could you not use your
approach when appending on the left side as well?
Both sides of the deque would allocate geometrically increasing block sizes
independently, which would maintain algorithmic complexity.

Jeff

Mehrdad

>
> On Tue, Jan 5, 2021 at 9:23 AM Hans Dembinski <[hidden email]>
> wrote:
>
> >
> > > On 4. Jan 2021, at 19:45, Mehrdad Niknami <[hidden email]>
> wrote:
> > >
> > > It's similar, but not quite. std::deque uses fixed-size blocks and
> tends
> > to be slow in my experience (at least in some implementations).
> > > stationary_vector on the other hand uses variably-sized blocks (with
> > geometrically increasing sizes).
> > > Its capacity at least doubles every round; in fact, it reduces to a
> > single array when the entire size is reserved beforehand.
> > > This allows it to perform much more competitively with (and similarly
> > to) std::vector.
> > > It may be what std::deque should have been, but isn't currently.
> >
> > Ok, that sounds like your container offers the same basic guarantees as a
> > std::deque with a more efficient implementation. If it is indeed more
> > efficient due to the use of variable-sized blocks than
> > boost::container::deque, then could you include your improvements into
> > boost::container::deque?
> >
> >
> >
> https://github.com/boostorg/container/blob/develop/include/boost/container/deque.hpp
>
> _______________________________________________
> 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: [container] Contributing 'stationary_vector' to Boost

Boost - Dev mailing list
I don't think it's possible without hurting the efficiency.

Each block is represented by an (index, pointer) pair. Pushing to the front
would require re-adjusting the indices in every bucket on every push to the
front, and that would be very slow.
On the other hand if I change the representation to, say, a (begin, end)
pair, it would have repercussions. For example, subtracting iterators would
take logarithmic time instead of constant time, as they no longer have
global bucket indices to subtract.

There are also possibly less significant but still nontrivial trade-offs I
can think of. For example, worst-case space usage would become O(infinity)
(like vector) instead of the current ~2n space bound (which is even
slightly worse than a typical deque's n + n/16 or similar in the worst
case). Furthermore, random-indexing could no longer be done in O(log log n)
time. (Note: this last part is something I haven't yet implemented for
stationary_vector, but it's trivial to implement right now due to the
global index maintained for each block. This would no longer be possible
without that information.)

I think there are likely more trade-offs as well, but for ones I could
think of were more than sufficient to rule it out as a drop-in replacement
for any existing container in STL or Boost; that's why I ended up
implementing a new container.

Mehrdad

On Tue, Jan 5, 2021 at 11:12 AM Jeff Hajewski via Boost <
[hidden email]> wrote:

> On Tue, Jan 5, 2021 at 12:53 PM Mehrdad Niknami via Boost <
> [hidden email]> wrote:
>
> > Not quite - my container is single-ended.
> >
> I assume this is because you grow your block size as you extend the vector.
> Without looking at the implementation of deque, could you not use your
> approach when appending on the left side as well?
> Both sides of the deque would allocate geometrically increasing block sizes
> independently, which would maintain algorithmic complexity.
>
> Jeff
>
> Mehrdad
> >
> > On Tue, Jan 5, 2021 at 9:23 AM Hans Dembinski <[hidden email]>
> > wrote:
> >
> > >
> > > > On 4. Jan 2021, at 19:45, Mehrdad Niknami <[hidden email]>
> > wrote:
> > > >
> > > > It's similar, but not quite. std::deque uses fixed-size blocks and
> > tends
> > > to be slow in my experience (at least in some implementations).
> > > > stationary_vector on the other hand uses variably-sized blocks (with
> > > geometrically increasing sizes).
> > > > Its capacity at least doubles every round; in fact, it reduces to a
> > > single array when the entire size is reserved beforehand.
> > > > This allows it to perform much more competitively with (and similarly
> > > to) std::vector.
> > > > It may be what std::deque should have been, but isn't currently.
> > >
> > > Ok, that sounds like your container offers the same basic guarantees
> as a
> > > std::deque with a more efficient implementation. If it is indeed more
> > > efficient due to the use of variable-sized blocks than
> > > boost::container::deque, then could you include your improvements into
> > > boost::container::deque?
> > >
> > >
> > >
> >
> https://github.com/boostorg/container/blob/develop/include/boost/container/deque.hpp
> >
> > _______________________________________________
> > Unsubscribe & other changes:
> > http://lists.boost.org/mailman/listinfo.cgi/boost
> >
>
> _______________________________________________
> 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: [container] Contributing 'stationary_vector' to Boost

Boost - Dev mailing list
Edit: Actually it just occurred to me there might be a solution for the
first issue: an additional "start offset" parameter that gets adjusted by
push_front could potentially avoid the performance hit to iterator
subtraction. I'm a bit tempted to try to implement it and see if it breaks
any assumptions I have, but it might work.

That said though, it still wouldn't substitute for deque, given that the
space complexity difference implies some deque users would now need to
worry about manually calling reserve & shrink_to_fit (and then deal with
having elements get moved), which deque doesn't have any notion of.

Mehrdad

On Tue, Jan 5, 2021 at 11:52 AM Mehrdad Niknami <[hidden email]>
wrote:

> I don't think it's possible without hurting the efficiency.
>
> Each block is represented by an (index, pointer) pair. Pushing to the
> front would require re-adjusting the indices in every bucket on every push
> to the front, and that would be very slow.
> On the other hand if I change the representation to, say, a (begin, end)
> pair, it would have repercussions. For example, subtracting iterators would
> take logarithmic time instead of constant time, as they no longer have
> global bucket indices to subtract.
>
> There are also possibly less significant but still nontrivial trade-offs I
> can think of. For example, worst-case space usage would become O(infinity)
> (like vector) instead of the current ~2n space bound (which is even
> slightly worse than a typical deque's n + n/16 or similar in the worst
> case). Furthermore, random-indexing could no longer be done in O(log log n)
> time. (Note: this last part is something I haven't yet implemented for
> stationary_vector, but it's trivial to implement right now due to the
> global index maintained for each block. This would no longer be possible
> without that information.)
>
> I think there are likely more trade-offs as well, but for ones I could
> think of were more than sufficient to rule it out as a drop-in replacement
> for any existing container in STL or Boost; that's why I ended up
> implementing a new container.
>
> Mehrdad
>
> On Tue, Jan 5, 2021 at 11:12 AM Jeff Hajewski via Boost <
> [hidden email]> wrote:
>
>> On Tue, Jan 5, 2021 at 12:53 PM Mehrdad Niknami via Boost <
>> [hidden email]> wrote:
>>
>> > Not quite - my container is single-ended.
>> >
>> I assume this is because you grow your block size as you extend the
>> vector.
>> Without looking at the implementation of deque, could you not use your
>> approach when appending on the left side as well?
>> Both sides of the deque would allocate geometrically increasing block
>> sizes
>> independently, which would maintain algorithmic complexity.
>>
>> Jeff
>>
>> Mehrdad
>> >
>> > On Tue, Jan 5, 2021 at 9:23 AM Hans Dembinski <[hidden email]
>> >
>> > wrote:
>> >
>> > >
>> > > > On 4. Jan 2021, at 19:45, Mehrdad Niknami <[hidden email]>
>> > wrote:
>> > > >
>> > > > It's similar, but not quite. std::deque uses fixed-size blocks and
>> > tends
>> > > to be slow in my experience (at least in some implementations).
>> > > > stationary_vector on the other hand uses variably-sized blocks (with
>> > > geometrically increasing sizes).
>> > > > Its capacity at least doubles every round; in fact, it reduces to a
>> > > single array when the entire size is reserved beforehand.
>> > > > This allows it to perform much more competitively with (and
>> similarly
>> > > to) std::vector.
>> > > > It may be what std::deque should have been, but isn't currently.
>> > >
>> > > Ok, that sounds like your container offers the same basic guarantees
>> as a
>> > > std::deque with a more efficient implementation. If it is indeed more
>> > > efficient due to the use of variable-sized blocks than
>> > > boost::container::deque, then could you include your improvements into
>> > > boost::container::deque?
>> > >
>> > >
>> > >
>> >
>> https://github.com/boostorg/container/blob/develop/include/boost/container/deque.hpp
>> >
>> > _______________________________________________
>> > Unsubscribe & other changes:
>> > http://lists.boost.org/mailman/listinfo.cgi/boost
>> >
>>
>> _______________________________________________
>> 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: [container] Contributing 'stationary_vector' to Boost

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
While I recognize the approach with geometrically allocated blocks
this makes the stationary_vector unsuitable as a deque replacement.
One of deques virtues is its ability to grow to a large size without
running out of memory. With geometric growth, a stationary_vector
will be unable to grow to more than half of available memory.

On Tue, Jan 5, 2021 at 6:23 PM Hans Dembinski via Boost
<[hidden email]> wrote:

>
>
> > On 4. Jan 2021, at 19:45, Mehrdad Niknami <[hidden email]> wrote:
> >
> > It's similar, but not quite. std::deque uses fixed-size blocks and tends to be slow in my experience (at least in some implementations).
> > stationary_vector on the other hand uses variably-sized blocks (with geometrically increasing sizes).
> > Its capacity at least doubles every round; in fact, it reduces to a single array when the entire size is reserved beforehand.
> > This allows it to perform much more competitively with (and similarly to) std::vector.
> > It may be what std::deque should have been, but isn't currently.
>
> Ok, that sounds like your container offers the same basic guarantees as a std::deque with a more efficient implementation. If it is indeed more efficient due to the use of variable-sized blocks than boost::container::deque, then could you include your improvements into boost::container::deque?
>
> https://github.com/boostorg/container/blob/develop/include/boost/container/deque.hpp
>
> _______________________________________________
> 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: [container] Contributing 'stationary_vector' to Boost

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

> On 5. Jan 2021, at 23:25, Mehrdad Niknami via Boost <[hidden email]> wrote:
>
> Edit: Actually it just occurred to me there might be a solution for the
> first issue: an additional "start offset" parameter that gets adjusted by
> push_front could potentially avoid the performance hit to iterator
> subtraction. I'm a bit tempted to try to implement it and see if it breaks
> any assumptions I have, but it might work.
>
> That said though, it still wouldn't substitute for deque, given that the
> space complexity difference implies some deque users would now need to
> worry about manually calling reserve & shrink_to_fit (and then deal with
> having elements get moved), which deque doesn't have any notion of.

Ok, it sounds like it is sufficiently dissimilar from deque to be its own thing. It sounds like a useful addition to boost::container, would be great to hear what Ion Gaztanaga thinks.

Best regards,
Hans

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

Re: [container] Contributing 'stationary_vector' to Boost

Boost - Dev mailing list
Would you know if he's had a chance to take a look at this?

Thanks,
Mehrdad

On Wed, Jan 6, 2021 at 2:47 AM Hans Dembinski <[hidden email]>
wrote:

>
> > On 5. Jan 2021, at 23:25, Mehrdad Niknami via Boost <
> [hidden email]> wrote:
> >
> > Edit: Actually it just occurred to me there might be a solution for the
> > first issue: an additional "start offset" parameter that gets adjusted by
> > push_front could potentially avoid the performance hit to iterator
> > subtraction. I'm a bit tempted to try to implement it and see if it
> breaks
> > any assumptions I have, but it might work.
> >
> > That said though, it still wouldn't substitute for deque, given that the
> > space complexity difference implies some deque users would now need to
> > worry about manually calling reserve & shrink_to_fit (and then deal with
> > having elements get moved), which deque doesn't have any notion of.
>
> Ok, it sounds like it is sufficiently dissimilar from deque to be its own
> thing. It sounds like a useful addition to boost::container, would be great
> to hear what Ion Gaztanaga thinks.
>
> Best regards,
> Hans

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

Re: [container] Contributing 'stationary_vector' to Boost

Boost - Dev mailing list

> On 18. Jan 2021, at 02:44, Mehrdad Niknami <[hidden email]> wrote:
>
> Would you know if he's had a chance to take a look at this?
>
> Thanks,
> Mehrdad
>
> On Wed, Jan 6, 2021 at 2:47 AM Hans Dembinski <[hidden email]> wrote:
>
> > On 5. Jan 2021, at 23:25, Mehrdad Niknami via Boost <[hidden email]> wrote:
> >
> > Edit: Actually it just occurred to me there might be a solution for the
> > first issue: an additional "start offset" parameter that gets adjusted by
> > push_front could potentially avoid the performance hit to iterator
> > subtraction. I'm a bit tempted to try to implement it and see if it breaks
> > any assumptions I have, but it might work.
> >
> > That said though, it still wouldn't substitute for deque, given that the
> > space complexity difference implies some deque users would now need to
> > worry about manually calling reserve & shrink_to_fit (and then deal with
> > having elements get moved), which deque doesn't have any notion of.
>
> Ok, it sounds like it is sufficiently dissimilar from deque to be its own thing. It sounds like a useful addition to boost::container, would be great to hear what Ion Gaztanaga thinks.
>
> Best regards,
> Hans

Please do not top post. We have a no top-post policy for the mailing list.

I cannot help you with that. If he does not answer here, you could try to submit an issue to https://github.com/boostorg/container. Ion commits frequently to the repo, so I hope he sees that.

Best regards,
Hans

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

Re: [container] Contributing 'stationary_vector' to Boost

Boost - Dev mailing list
On Mon, Jan 18, 2021 at 12:32 AM Hans Dembinski <[hidden email]>
wrote:

> Please do not top post. We have a no top-post policy for the mailing list.
>
> I cannot help you with that. If he does not answer here, you could try to
> submit an issue to https://github.com/boostorg/container. Ion commits
> frequently to the repo, so I hope he sees that.
>
> Best regards,
> Hans


Oh I see, okay thanks!

Best,
Mehrdad

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