Boost logo

Boost :

Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2017-10-03 23:30:33

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.

What is your evaluation of the design?

The library presents two containers, devector and batch_deque. I find
the first one as a relatively simple but interesting vector extension
supporting front insertions. In the future it could maybe take advantage
of the backwards memory expansion (taking the previously adjacent free
memory segment so that new elements could be added to front without
moving the rest of the elements) supported by Boost.Interprocess and the
Boost.Container’s modified DLMalloc.


1) From a design point of view, I would prefer not to include the small
buffer optimization with the data structure, although reviewing code, it
seems many parts are to be optimized. It's like just having small_vector
without having vector, most libraries have two classes for these two use
cases. Different classes also ease that a type erasured base class can
be defined independent from the static storage size (Boost.Container
calls it small_vector_base, LLVM calls it SmallVectorBase) I think we
should have a devector, and add small_devector and static_devector
containers if there is demand.

2) Defaulting size_type to unsigned int is arbitrary and against
existing practice. According to the usual STL rules, size_type shall
come from the allocator, which knows what type can represent the number
of elements that can be allocated. I find interesting the idea of
expressing a different size_type to save space, but I am not sure if
that should come from the allocator or from an option.

3) reserve_only_tag: I would rename it as “reserve_only_t” (similarly to
std::allocator_arg_t and Boost.Container’s “default_init_t”). The front
and back capacity version should be enough as I think devector should
not show preference for back insertion (if a user wants only a back
capacity, then it would use a vector and not a devector). Strictly
speaking, capacity constructors are a bit redundant, but the same could
be said about default constructing constructors:
//it could be implemented as default constructor + resize
explicit vector(size_type n, const Allocator & allocator = Allocator());
A reserve-only constructor plus an “unsafe” emplacement could make a
container similar to an array, where no redundant checks are done when
filling the array. But I don’t expect noticeable performance gains with
this reserve-only constructor.

4) unsafe_uninitialized_tag: I don’t like these non-safe constructors,
which are the cases?. With reserve-only constructors + unsafe emplace
back a user can achieve nearly the same performance. For POD types (like
the socket example mentioned in the documentation), I would suggest
something like Boost.Container’s “default_init_t”. Instead of
“unsafe_uninitialized_resize_front” I suggest resize_front(size_type,

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.

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):

7) growth_policy: This is an option that could be interesting not only
for devector but also for vector. However, I would prefer passing
options as a single argument where options are combined, so that the
class declaration is not modified each time a new option is added.
Something like:
template<class T, class Allocator, class Options= void>
class devector;

using myoptions = make_options_t<growth_factor<G>, size_type<unsigned
short>, new_option<arg>, … >;
usinge mydevector = devector<int, allocator<int>, myoptions>;

a similar approach is used in Boost.Intrusive and will be added to

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. On the other hand, most people will notice the big
slowdown that will receive because their move constructors cannot be
marked as noexcept (pimpl idiom, small buffer optimization,
sentinel-node based lists, devector itself would be copied if
small_buffer_size is used, etc.). I think “move_if_noexcept” was just
added for backwards compatibility with C++03’s strong guarantee, but
devector does not need to follow the same rule. I understand many
(most?) people don’t agree here, but don’t think we should sacrifice
devector performance just to support rare throwing cases.

9) Minor comment 2: IMHO I think iterators would be better as classes
instead of pointers, a user can always use data() to make sure pointers
are returned. Many times unwanted overload resolutions can happen if
pointers are used, so I prefer the type safety offered by a class-based
iterator. It can also offer checked iterators in the future.
10) Default growth factor of 4. Sounds like overkill, 2 or 1.5 sounds
more reasonable and in line with user expectations based on existing
practice in STL and Boost. I’m not sure if shrinking should be part of
the trait.

Many of the comments from devector are applicable here, so I will not
repeat them here.
1) In general, I don’t see the need of batch_deque as a different
container, because it’s basically a deque with some options (segment
size and additional operations). Those could be added to
boost::container::deque without breaking anythying.

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, for more information)

3) stable_insert: I can’t see the usefulness of this operation. A
batch_deque is a sequence, but the user cares about the insertion point
but does not care if additional elements are created somewhere? I fail
to see a real use case.

What is your evaluation of the implementation?
I think it’s solid. Tests look good.


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

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. When memory is
reallocated to make room for a front insertions, the free back capacity
is unchanged and all new free capacity goes to front. This means that
the last operation (front or back) determines where all the new capacity
goes. I find a bit strange that N == front_back_capacity() does not mean
that a reallocation will happen if we push_back N times, as repeated
data movement will happen if front_free_capacity() is available.

Another strategy is to treat both ends independently: if front insertion
has no free space, it could always reallocate and make room at front, so
further push_fronts don’t provoke data movement. This would be similar
to batch_deque, where memory is allocated if there is no free front
capacityregardless of the free back capacity (no data movement),f and
free segment is recycled from back capacity to insert elements at front.
Obviously, this approach consumes more memory. Yet another strategy
would be distribute any new free capacity (after reallocation) between
front and back, indepently from which operation (back or front) has
provoked the allocation.

       // 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());
This does not seem exception safe “++_back-index” should be done just
after alloc_construct, same for front insertion.

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.

Range insert: A temporary temp_devector is used, which means copying
data two times. The inline storage for 32 elements can blow the stack if
T is something big (like static_vector<T, N>)

1) I like that deque_[const_]iterator is lightweight, I don’t know if
iteration/access it’s more efficient than more traditional approaches.
boost::container::deque iterators are really fat and should be improved
to something similar to batch_deque iterator. On the other hand
deque_segment_[const_]iterators are heavier than needed, and I think
they could be just like vector iterators if used to iterate a single
segment. The problem is that deque_segment_iterator works both as
segment information class and as a local iterator. I think a similar
approach to PolyCollection’s “segment_traversal_info” as segment
information could work better, as it allows really lightweight local
iterators that can speed up specialized segmented algorithms (local
iterators could be just vector-like iterators inside a segment).

2) The data structure o batch_deque is slightly bigger than the
traditional one, just asking if it’s intended or it was developed like
this to reuse code. Traditional deque (from SGI) used four elements (map
pointer, map size, iterator to begin, iterator to end). Your
implementation defines the map as a devector, which stores size and
capacity for the map, but this allows you handle the excess capacity of
the map, I’m not sure if it adds performance benefits.

3) I haven’t thoroughly reviewed all the code, but many devector
comments are applicable: rotation, move_if_noexcept, etc.

What is your evaluation of the documentation?
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).

What is your evaluation of the potential usefulness of the library?
devector might be useful, I have doubts with batch_deque. Deque in
general is not the most used STL container, so I don’t expect a lot of
users, maybe for specialized cases.

Did you try to use the library? With which compiler(s)? Did you have any
Just executed tests and examples and debugged to help code review. MSVC
2017 triggers quite a lot of warnings, mainly about constant conditional
How much effort did you put into your evaluation? A glance? A quick
reading? In-depth study?
Several hours analyzing the design and reading the code. An hour playing
with the library with MSVC.
Are you knowledgeable about the problem domain?
I do think so. I’ve written a lot of containers for Boost and outside
Boost. Deque is not my favorite container, though ;-)

¿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.



Boost list run by bdawes at, gregod at, cpdaniel at, john at