Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: Benedek Thaler (thalerbenedek_at_[hidden])
Date: 2017-10-05 07:04:53

On Wed, Oct 4, 2017 at 1:30 AM, Ion Gaztañaga via Boost <
boost_at_[hidden]> wrote:

> On 21/09/2017 19:38, Thorsten Ottosen via Boost wrote:
>
>> Dear users and members of Boost,
>>
>> I'm proud to announce that the formal review of Benedek Thaler's
>> Boost.DoubleEnded library starts today, September 21, and runs through
>> September 30. This library is the result of Benedek's participation in
>> Google Summer of Code 2015.
>>
>
> Hi, this is my review of Boost.DoubleEnded.
>

Thank you for your time and effort!

> 2) Defaulting size_type to unsigned int is arbitrary and against existing
> practice. [snip]
>

To satisfy sizeof(devector) == sizeof(std::vector)
It was an initial goal to make devector resemble vector, as close as
possible, to ease transition. The familiarity makes it easy use, but also
produces some imbalance, you also note below. Unfortunate indeed.

> 5) reserve() / resize(): I think they have no sensible meaning in the
> container (capacity() could be useful, depending on the reallocation
> strategy). We should not treat back insertion as the “default” insertion.
> IMHO the API of devector should be symmetrical.
>

Again, compatibility.

> 6) unsafe_push_back/front: I think they can be useful, many times we
> iterate until a known upper bound and capacity checks might be redundant in
> some code, just like we do with arrays. I suggest replacing “unsafe” with
> “unchecked” and “push” with “emplace” (which is much more general):
> “unchecked_emplace_back/front(Args&&….)”.
>

s/unsafe/unchecked, agreed. Also, we need the emplace methods as well.

> 8) Regarding "move_if_noexcept", Boost.Container does not use it as it
> consider a pessimized design for a situation (throwing moves) that will
> occur nearly never and few times will be handled using the provided strong
> guarantees.
>

Right, this should be fixed in devector, at the expense of compatibility.

> 2) Segment_iterators: Raw pointers are stored in segment iterators. That
> means that those could not be placed in the memory that the allocator
> allocates, if the allocator does not defined ::pointer as T*.
> Also, it seems strange that there is not segment_type/segment_info class.
> The iterator itself has members that return the address and the size of a
> segment. I think that’s unexpected, the expected segment iterator would
> return a reference to a class (e.g. segment_type) that represents the
> segment, which has the required operations, and also internal begin()/end()
> operations to obtain segment-local iterators (a la unordered containers).
> This could allow some optimized segment-based algorithms (see
> lafstern.org/matt/segmented.pdf, for more information)
>

Thanks, this can be improved.

>
>
> --------------------------
> devector
> --------------------------
>
> emplace_slow_path: The forced temporary creation should be avoided, it is
> overkill for containers of containers, devector<static_vector> or
> containers with sentinel nodes. IMHO supporting references to already
> included elements is a bad feature of std::vector (a corner case supported
> in single element insertion, ignored for ranges, etc.) Boost.Container
> chose not to support it and no one has demanded that feature:
> http://www.boost.org/doc/libs/1_65_1/doc/html/container/Cpp1
> 1_conformance.html#container.Cpp11_conformance.container_
> const_reference_parameters
>
>
True.

Reallocation strategy: First, I considered this strategyunnatural, but now
> I am not sure. For a push_front, if no free front capacity is found, but
> there is free back capacity, then all data is shifted to insert the
> element. If interleaved front and back insertions are performed, I don’t
> know if this will lead to too many data movements. [snip]
>

If it does not shift, it has to reallocate - and then copy/move everything
over. I don't see how is that any better.

> emplace_slow_path:
>       // construct at back + 1 from back (no guard)
>       alloc_construct(end(), std::move(back()));
>       // move back half right
>       std::move_backward(position, end() - 1, end());
>       ++_back_index;
> This does not seem exception safe “++_back-index” should be done just
> after alloc_construct, same for front insertion.
>

I'll take a look.

>
> insert_range_slow_path_near_front/back: I see that construction +
> rotation is done, but I think this is not optimal, the implementation might
> be simplier, but more than necessary data movement is done.
>

I'll take a look.

>
>
> Documentation is correct, but I expected more detail. If one of the goals
> of the library is efficiency, benchmarks should be there (maybe against
> Boost and Std vector and deque).
>
>
I posted some micro-benchmarks on the list recently. I think that's a
start, but those should be reviewed/reproduced as well. I kind of don't
trust such benchmarks.

> -------------------------------------
> -------------------------------------
> Did you try to use the library? With which compiler(s)? Did you have any
> problems?
> -------------------------------------
> -------------------------------------
> Just executed tests and examples and debugged to help code review. MSVC
> 2017 triggers quite a lot of warnings, mainly about constant conditional
> expressions.
>

That wasn't available back then. Otherwise, it is a definite goal to make
it warning free (as it is on some other compilers).

> -------------------------------------
> -------------------------------------
> ¿Should we accept the library?
> -------------------------------------
> -------------------------------------
> I think the library (see my design comments) and the documentation still
> need improvements, but it's not the main issue. I’m reluctant to accept the
> library because I don’t see substantial benefits of batch_deque against
> deque (configurable segment size could be added to Boost.Container if that
> feature is considered useful), and I don’t know if the use cases where
> devector is supposed to shine needs a whole new library (we have no clear
> rules about how tiny a library can be, but in this case it would be a new
> container and reimplementation of another).
>
> Joaquín has proposed to merge this proposal to Boost.Container, but
> supported compilers and goals are quite different and a direct merge would
> be problematic as Boost.Container would loose coherency, common goals and
> minimum requirements between all containers.
>
> A middle solutions is to:
>
> 1) Start “porting” devector, after all issues have been agreed, (without
> small vector optimization, at least in the first version) to
> Boost.Container’s requirements (including some pre C++11 compilers)
>
> 2) Improve Boost.Container’s deque to support features (and maybe code)
> from batch_deque (configurable segment size, local iterators, etc.).
>
> That’s a lot of work, discards a lot of batch_queue code and I don’t know
> if Benedek would agree to help on this task after I spoke against this
> option when it was proposed and after doing so much work to write the
> library.
>
>
The interest of the community should be put first. If we think adding
pieces to Container would improve situations, we should find a way. On the
other hand, I wouldn't love to port code to C++03, for two reasons: It is a
soul crushing work, and, we should not encourage writing new code using old
standards (I know, there's no other option in certain cases.).

Thanks,
Benedek