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-09-27 21:07:27

On Tue, Sep 26, 2017 at 11:43 PM, Joaquin M López Muñoz via Boost <
boost_at_[hidden]> wrote:

>
> Hi, this is my review of Boost.DoubleEnded. As my review approach is
> heavily
> influenced by my acceptance vote, let me begin with that:
>
> I vote for conditional acceptance of both containers after they have been
> presented
> as separate components of Boost.Container and undergone significant
> changes, mostly
> along the line of simplifying their interface.
>

Thanks for the really elaborate review.

> * A library for a familiy of containers (or any other classes) is
> justified when its members
> are related either by shared concepts, constructs and/or implementation.
> This is not
> the case of Boost.DoubleEnded, whose only general theme is the very lax
> notion of
> "double endianness", and for which the amount of common implementation
> code is small
> and mostly utility-level. We already have a bestiary of containers in
> Boost, namely
> Boost.Container, so I think both devector and batch_deque are better
> served if proposed
> as components of this latter libray. Code in boost::double_ended::detail
> can go to / merge
> into boost::container[::detail] --for instance,
> boost::double_ended::detail::allocator_traits
> seems to be redundant with boost::containter::allocator_traits.
>

Originally, a new library wasn't planned, but Boost.Container was targeted.
Ion, however, considered that the design (or the execution) is not aligned
with Container (I suppose),
so we were left with this option.

> * The main characteristics of both containers are obscured by many
> "extras" that feel
> insufficiently justified to me or even detrimental (I'll discuss in more
> detail below), so my
> vote is for this fat to be removed prior to acceptance in Boost. I can see
> much work
> and love have gone into adding this many niceties, and the author could
> understansably
> resist to simplification, but libraries, in my opinion, should start with
> a minimal and
> well grounded design and add more stuff as demand proves their need.
>

On the contrary. Removing unnecessary code is always a pleasure.

> So, since I see this library as a pair of two unrelated classes, let me
> continue with the
> review for each separately.
>
> REVIEW FOR DEVECTOR
>
> [snip]
>
> IMPLEMENTATION
>
> 1. I've taken just  cursory look at the code, but everything looks very
> good in general.
> 2. I take that lines 2367-8 (and similar) in devector.hpp:
>
>   // avoid invalidating any reference in args later
>   T tmp(std::forward<Args>(args)...);
>
> are somehow related to LWG Issue 526, right?
>

Yes. As noted below, a more aggressive approach might be taken here.

[snip]
>
4. I'm not comfortable with the fact that shifting on insertion turns to
> the opposite
> side when the favored side (the one closer to the insertion point) happens
> to be
> full. This makes it very hard to reason about post-insertion front and
> back capacities.
> Also, the reference statement that insertion is "linear in half the size
> of *this [...]"
> is currently not true (when the favored side is full insertion takes
> longer than that).
> I'd rather drop this optimization and document that shifting always happen
> to the
> direction where the least operations are needed.
>

Point taken.

> DOCUMENTATION
>
>
> 2. I confess I don't get what "devector implements the NAD (Not A Defect)
> resolution
> of LWG Issue 526" is about.
>

It says that the implementation ignores corner cases when an already
inserted element is to be
inserted again, e.g:
v.insert(v.begin(), v[2]);

>
> 5. The reference section is very good. Capacity handling and which side
> shifting goes
> on insertion/erasure should IMHO be documented exhaustively (see my points
> above on
> this matter).
>

Noted.

> REVIEW FOR BATCH_DEQUE
>
> DESIGN
>
> 1. In the design rationale, batch_deque is presented as a deque with
> configurable segment
> size, which is true, but not the end of the story: segment access
> (segment_[begin|end]) is not
> mentioned, neither is stable insertion.
>

Noted.

[snip - better interface of segment iterator]
>
> 3. The question arises of whether segment access can gain us some speed.
> I've
> written a small test to measure the performance of a plain std::for_each
> loop
> over a batch_deque vs. an equivalent sequence of segment-level loops
> (attached, batch_deque_for_each.cpp), and this is what I got for Visual
> C++ 2015
> 32-bit (x86) release mode in a Windows 7 64-bit box with an Intel Core
> i5-2520M
> @2.5GHz:
>
> [snip]
>

A better use-case is when elements are processed in a batch (hence the
name):
http://erenon.hu/double_ended/double_ended/examples.html#double_ended.examples.batch_deque_usage
It's especially useful when doing scatter/gather IO.

>
> 6. Why a batch_deque_policy wrapper rather than directly providing the
> segment size
> to batch_queue as in
>
>   boost::double_ended::batch_deque<int,512>
>

This is to allow further customization points without an additional policy
argument.
One issue with the approach above: It isn't clear whether 512 is a number
of elements or bytes.
de::batch_deque<int, de::elements_per_segment<512>> is conceivable tough.

> 7.  BTW, batch_deque_policy::segment_size should be defined as constexpr
> so as to
> fully honor the promise that "using a power of two increases performance
> because
> of the cheaper division and modulo operations".
>

Noted.

> 10. A bit of bikeshedding: what's the rationale for "batch_deque"? Not
> that I have a better
> name for this, though.
>

It is because of the segment iteration. Any better name would do.

>
> Thanks to Benedek Thaler for his effort in writing and submitting this
> library, and
> to Thorsten in his dual role as mentor / review manager.
>
>
>
Thanks for your time and precise points,
Benedek