On Tue, Sep 26, 2017 at 11:43 PM, Joaquin M López Muñoz via Boost < boost@lists.boost.org> 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.exampl... 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
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
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