Re: [container] Contributing 'stationary_vector' to Boost

From: Mehrdad Niknami (mniknami_at_[hidden])
Date: 2021-01-05 22:25:11

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 <mniknami_at_[hidden]>
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 <
> boost_at_[hidden]> wrote:
>
>> On Tue, Jan 5, 2021 at 12:53 PM Mehrdad Niknami via Boost <
>> boost_at_[hidden]> 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 <hans.dembinski_at_[hidden]
>> >
>> > wrote:
>> >
>> > >
>> > > > On 4. Jan 2021, at 19:45, Mehrdad Niknami <mniknami_at_[hidden]>
>> > 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
>>
>