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

----------
devector
--------

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, 
default_init_t)

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): 
“unchecked_emplace_back/front(Args&&….)”.

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 
Boost.Container.

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.

----------
Batch_deque
--------
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 lafstern.org/matt/segmented.pdf, 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.

--------------------------
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/Cpp11_conformance.html#container.Cpp11_conformance.container_const_reference_parameters

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.

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.

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

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

Best,

Ion