|
|
Boost : |
Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: Joaquin M López Muñoz (joaquinlopezmunoz_at_[hidden])
Date: 2017-09-26 21:43:52
El 21/09/2017 a las 19:38, Thorsten Ottosen via Boost escribió:
> 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. 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. A bit of elaboration:
* 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.
* 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.
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
DESIGN
1. The container is presented as a "hybrid of the standard vector and
deque containers,
as well as the small_vector of Boost.Container.". It's hard to see what
the selling point
is. To me, the main feature (and the only one worth retaining) of
devector is
amortized constant insertion at both ends with memory contiguity. So,
I'd present
devector as a "contiguous memory container with amortized constant
insertion at both
ends of the sequence". Note that this characterizes the container to the
point of
nearly fixing its implementation and (assuming STL style is followed)
its interface.
2. SBO is orthogonal to devector's raison d'être (I mean, SBO can be
added to any container)
and violates the "don't pay for what you don't use" principle. I'd
remove it. If someone
asks for it, provide a separate small_devector, but I doubt there'll be
huge demand for
this (devector, to begin with, is likely to be used only in very
specialized scenarios, so
the probability that SFO comes in handy as well is, IMHO, vanishingly
small).
3. Unsafe methods are poorly justified: if std::vector does not have
them, why add them
here? Such degree of unsafety should be backed up with hard data on its
superior
performance. I'd remove this bit.
4. Same goes for the growing policy. Not even boost::container::vector
features a growing
policy, which seems an indication that this is not a heavily demanded
customization point.
I'd remove it.
5. Defining size_type as unsigned int for the sake of class size seems
to me overzealous.
6. reserve_only_tag construction looks like too much hassle to avoid
default construction
followed by proper reserving calls, which is what everybody already does
with
std::vector. Again, I'd remove this one.
7. Modulo the points discussed above, the interface of devector follows
closely that
of std::vector (with the obvious additions, e.g.
[push|pop_emplace]_front), which is
very good. The only interface decisions I'm not fully convinced about is
capacity/
resize/reserve/shrink_to_fit without "front" or "back" qualification:
 - capacity() seems to be (from what I can infer reading the docs
only) the sum of
 front capacity and back capacity. I can't find any sensible use of
this info, and, besides,
 the careless reader could assume capacity() works as
std::vector::capacity(), which
 raises usability concerns. My suggestion is to remove this. FWIW, we
had a similar
 discussion about capacity() in Boost.PolyCollection, and that member
function finally
 was dropped.
 - front_free_capacity/back_free_capacity could be more aptly named
 front_capacity/back_capacity.
 - reserve as an alias to reserve_back has usability problems as
discussed with capacity.
 I'd remove them.
 - For symmetry, shrink_to_fit could be complemented with
[front|back]_shrink_to_fit
 member functions --note I'm not proposing that shrink_to_fit be
removed, as its
 semantics are perfectly clear.
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?
3. I have issues with growing and capacity handling. If I'm reading the
code right,
growth factor is x4 (!!) and whether the new space is given to the front
or back side
depends on whether the insertion that triggered the expansion is closer
to one
or the other. x4 is much larger than any growing factor I've seen so far
for std::vector
(typically x1.5 or x2), I suggest this should be brought down to what's
customary. As
for the policy for giving the space to front or back, I think it makes
sense but needs to
be documented officially. I'm assuming that erasure behaves analogously
(i.e. space
is given back to the side that's closer to the erasure point) --in
particular, inserting
an element and erasing it immediately after should return front and back
capacities
to their original values.
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.
5. I wonder why serialization code is so complicated: doesn't it suffice
to rely on
boost::serialization::stl::collection_load_impl|save_collection?
6. Tests look very good, with corner cases and all.
DOCUMENTATION
1. If the extra features are removed, the design rationale would
consequently be much
shorter.
2. I confess I don't get what "devector implements the NAD (Not A
Defect) resolution
of LWG Issue 526" is about.
3. The examples section is 90% devoted to the extra features I advocate
to suppress.
4. The benchmark section should go (IMHO). The display of assembly
outputs is anecdotal
at best, since it is quite plain to guess that devector::push_back
should be basically the same
code as std::vector::push_back. I don't think devector needs any
benchmark backup to be
bought by potential users.
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).
POTENTIAL USEFULNESS OF DEVECTOR
I can only use my intuition here, but memory contiguity plus constant
insertion at both
ends looks a general enough proposition to meet potential users. FIFO
queues jump to mind.
Time will tell.
OTHER
1. I didn't try to use the library.
2. I spent aroud four hours reviewing devector.
3. I have some experience writing STL-style containers.
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.
2. As for segment access, I think the chosen interface is very odd. From
what I can gather after
looking at the code and testing (because the reference does not document
this), a
segment_iterator dereferences to the first element of the pointed to
segment and has
additional data() and data_size() member functions to access the full
segment. This is a sort
of hybrid entity I fail to see the utility of (for instance, what can I
do with referencing?). I have
some experience with segmented structures and think a better approach
would be for
segment_iterator to dereference to a segment descriptor with begin() and
end() member
functions ranging over the segment elements. This way, one can write
stuff like:
 for(auto it=d.segment_begin(),end=d.segment_end();it!=end;++it){
   for(auto& element:*it){
     // do something with element
   }
 }
The thing can be further stylized by dropping segment_[begin|end] and
having a
segments() member functon returning an object with equivalent begin()
and end()
member functions, i.e., one would write d.segments().[begin|end]()
rather than
d.segment_[begin|end](), which allows us to use a range for in:
 for(auto segment:d.segments){
   for(auto& element:segment){
     // do something with element
   }
 }
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:
 [](int x){return x;}
 segment size: 32
 n      plain  segmented
 10E3   25.5472 23.6305
 10E4   24.5778 23.6907
 10E5   24.5821 22.8076
 10E6   25.5007 23.1037
 10E7   27.1452 24.0339
 segment size: 512
 n      plain  segmented
 10E3   23.8384 23.6638
 10E4   23.0284 23.8705
 10E5   22.8449 22.8187
 10E6   23.8485 23.7454
 10E7   24.1711 23.5404
 [](int x){return x%4?x:-x;}
 segment size: 32
 n      plain  segmented
 10E3   33.9795 23.6662
 10E4   32.4817 24.023
 10E5   32.8731 23.3803
 10E6   33.5396 22.9298
 10E7   33.1034 23.0206
 segment size: 512
 n      plain  segmented
 10E3   25.0623 23.3205
 10E4   25.1048 23.5812
 10E5   25.3343 21.7686
 10E6   25.6961 22.4639
 10E7   25.8664 22.9964
(Time is nanoseconds, the lambda functions encapsulate the operation
done on each
element before accumulating the result.) So, there is some performance
gain, though
nothing spectacular. Whether this justifies providing segment access is
not clear to
me.
4. Stable insertion looks to me a nice feature without a real-world use
case... Is there
some more or less obvious application I'm missing? Otherwise, I'd drop it.
5. A default segment size of 512 looks too big: typical numbers for
std::queue range
in 8-16. Any reason for this?
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>
?
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".
8. As for devector, unsafe operations do not seem justified.
9. resize_[front|back] are IMHO a nice addition over std::deque in full
accordance with
its double-ended nature. I'm not so sure about reserve, capacity and
shrink_to_fit, more
so when the number of segments is expected to be much lower than the
number of
elements and segment index (map_t) reallocation should not affect
overall performance
significatively. Either way, the same concerns over naming and capacity
handling apply
here.
10. A bit of bikeshedding: what's the rationale for "batch_deque"? Not
that I have a better
name for this, though.
IMPLEMENTATION
1. From a cursory look, everything looks clean and beatiful.
2. As with devector, why is serialization code is so complicated and
does not
simply rely on
boost::serialization::stl::collection_load_impl|save_collection?
3. Tests look good.
DOCUMENTATION
1. The design rationale, as commented above, does not really specify what a
batch_deque is all about.
2. The reference is in general quite complete, but:
3. [const_]segment_iterator is not documented at all.
4. Postconditions on front and back capacity are not documented.
5. Maybe a performance section could be added showing how tuning the
segment size
can affect performance.
POTENTIAL USEFULNESS OF BATCH_DEQUE
Can't tell. Controlling segment size seems a potentially wanted feature
for users of
std::deque. Others with greater practical experience with this type of
structures
can have a more informed opinion.
OTHER
1. I briefly used the batch_deque sub-library with MSVC 2015 for
performance testing
and some basic exploration of segment_[begin|end]. No problem foud.
2. I spent aroud three hours reviewing batch_deque.
3. I have some experience writing STL-style containers.
SECTION ON BUILD AND TEST
1. I don't think this is really needed if the library finally makes it
into Boost.
Thanks to Benedek Thaler for his effort in writing and submitting this
library, and
to Thorsten in his dual role as mentor / review manager.
Best,
JoaquÃn M López Muñoz
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk