[boost] [review][DoubleEnded] Review Results

Subject: [boost] [review][DoubleEnded] Review Results
From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2017-10-26 22:00:49

Dear users and members of Boost,

I'm happy to to announce that Benedek Thaler's Boost.DoubleEnded is 
/conditionally/ accepted into Boost provided that it can be integrated 
smoothly with Boost.Container. There are several other conditions, some 
major and some minor which I will outline below.

For now, I would like to thank everyone that participated with reviews 
and comments. We didn't have that many reviews, but the reviewers did 
spend a lot of time both on review and the following discussions.

Special thanks also goes to Benedek for his hard work. It is not too 
often that a GSOC code ends with something of this quality. Two of the 
world's expert C++ container developers used phrases like "solid"
and "everything looks clean and beautiful" about the implementation, 
"tests look very good, corner cases and all", "The reference section is 
very good". Congratulations, Benedek.

==============
A path forward
==============

Ion has most kindly accepted the idea of merging the library into 
Boost.Container. This consists of

A. taking selected elements from batch_deque and adding them to 
boost::container::deque.

B. putting devector into boost.container after changes have been applied
     to code and documentation

C. back-porting the devector code to C++03

(C) does not need to happen immediately, that is, we can have a release 
where devector is available in a C++11 version. Ion has also most kindly 
agreed to help with this process. I will help write a new introduction 
that focuses on the main principles of devector. We also have a number 
of benchmarks which we can gather and use for a small section of on that 
topic. I'll leave it to you and Ion to work out the details.

==========================
Detailed comments devector
==========================

Apart from the merging with Boost.Container, the most heard complaint 
was about the "fat", the non-essential parts if the interface, that 
could be removed. This includes

-- Remove the direct support for small buffer optimization form 
devector. When the time comes, provide small_devector similar to the way 
we have vector/small_vector (there is no requirement that small_devector 
is provided).

-- remove all of the following:
   - all constructors that uses reserve_only_tag,
   - all constructors that uses unsafe_uninitialized_tag,
   - void unsafe_uninitialized_resize_front(size_type);
   - void unsafe_uninitialized_resize_back(size_type);
   - unsafe_push_front(...);
   - unsafe_push_back(...);

-- add instead
   - constructors that uses default_init_t like boost.container
   - resize versions that uses default_init_t
   - T& unchecked_emplace_back(...) noexcept(...)
   - T& unchecked_emplace_front(...) noexcept(...)

At some point, I hope we can upgrade default_init_t to mean no 
construction for all trivially copyable types.

There was a wish for more symmetry in devector and so functions that 
break symmetry or can appear ambiguous should be removed. This means we 
should remove:

-- capacity()

There is no need for front_capacity() and back_capacity().
We could remove reserve(), but then we can't use devector with a 
flat_set. Reserve() should not be an alias for reserve_back() though, 
but controlled by the policy. We could remove resize(), but even deque 
has it where it means resize_back(). I totally agree it would be ideal 
to remove all of reserve(),resize(),capacity(),clear(), but I see no 
easy way we can use devector with flat containers if we remove the first 
and the last. Unless we start deprecating stuff in 
boost::deque/boost::vector and provide new consistent alternatives, we 
will never get a 100% satisfactory solution. At the end of the day, we 
need to be pragmatic, so if deprecation is not on the table, this seems 
the best we can do.

Since we don't want two allocations implied by calling reserve_back() 
and reserve_front(), you can add a mechanism for doing that. That is, 
you can provide

-- reserve( new_capacity );
-- reserve_front( new_front_capacity )
-- reserve_back( new_back_capacity )
-- reserve( new_front_capacity, new_back_capacity )

or, since reserve() is such a weird beast, simply provide

-- reserve( new_capacity ); // for flat containers
-- anticipate_front( new_front_elements )
-- anticipate_back( new_back_elements )
-- anticipate( new_front_elements, new_back_elements )

to get rid of the funky

-- container.reserve_front( container.size() + new_front_elements )

dance.

There were suggestions for shrink_back/front_to_fit, but since we are 
trying to remove fat, I suggest that we wait for a use-case.

There were also suggestions that clear() should be amended. As the 
growth (or resizing policy) mandates what clear does, we need a way to 
escape. The minimal change that allows that is to provide

-- clear( front_free_capacity )

which gives full power to the user. You may provide clear_back() as 
clear(0) and clear_front() as 
clear(c.size()+c.front_free_capacity()+c.back_free_capacity()). Ideally, 
clear() would have been removed entirely like capacity()/resize(), but 
like reserve(), it just seems like impossible when we start using it 
with flat containers.

Other minor comments:

- drop strong exception safety guarantees and do it like boost.container
- prefer to make iterator a type (should be easy with reuse from 
boost::container::vector
- allocator should not be inherted from
- make clear O(1) amortized gurantees depend on growth policy
- consider calling growth policy for resizing policy
- make sure SFINAE works properly with constructors
- make the default growth factor 2 (as we heard from Sean Parent: no 
factor below 2 is empirically good)
- consider renaming front_free_capacity to free_front_capacity. 
Rationale: "front_capacity" is a concept, noun, and "free" is the 
adjective. Ditto for back_free_capacity.
- remove size_type from growth policy and take it from the allocator
- make the allocator template argument the 2nd argument
- fix remaning TODO in code
- documentation should not sell devector as drop-in replacement for 
vector, but rather stress it is not
- the allocator supports needs to be improved. I guess doing it the 
Boost.Container way ensures that (ask Daniel James for help)
- exception-safety issues pointed out by Ion
- postconditions of insert/erase needs to specify behavior to 
front_free_capacity/back_free_capcity
- use of local containers should be avoided
- rotate should be avoided
- delegate range move operations to those defined in Boost.Container
- make sure all functions excepting non-overlapping range uses memcpy 
(not just memmove). This includes:
   - range constructor
   - copy-constructor
   - copy-assignment
   - range-assignment
   - range insert
- destructor should used std::has_trivial_destructor to avoid loop in 
that case to make sure all compilers optimize it away (similar for erase).

There is one final puzzle and that is the growth policy. I hope we can 
finalize that by testing Joaquin's and Ion's suggestions over the coming 
weeks.

=============================
Detailed comments batch_deque
=============================

For deque, the comments were similar, although there was far less to 
discuss than for devector. All agreed that one should be able to control
the segment size.

- stable_insert was not needed.

- segment iteration was good, but should be usable with range-based for 
loop. The segment iterator should return a segment type if possible, and 
the segment should have begin(),end(),size() members.

- since boost::deque already has a resize with default_init_t, that 
should be sufficient to provide fast serialization load for trivial 
types. No need for

   - resize_front
   - resize_back
   - unsafe_uninitialized_resize_front
   - unsafe_uninitialized_resize_back
   - reserve
   - shrink_to_fit()
   - capacity()

The following are still needed for optimal code
(or code that can be known not to reallocate,
or for better locality in deserialization, avoiding double initialization)

   - free_front_capacity;
   - free_back_capacity;
   - reserve_front
   - reserve_back
   - unchecked_emplace_front
   - unchecked_emplace_back

Boost.Container's unit-tests should be extended with those from 
batch_deque where it makes sense.

Since segmented iteration was somewhat faster, it should be use 
internally where it makes sense. In particular

- copy-constructor
- copy-assignment
- destructor

As for devector, all constructor/functions that iterate over 
non-overlapping ranges should use memcpy. destructor should
use is_trivially_destructible to ensure it is optimized away
(similar for erase).

======================
Serialization comments
======================

I suggest that the default versions just do what Boost.Serialization 
does, perhaps just replacing resize with resize with default_init_t.
That ensures it works correctly for all archive types. It also needs
to use make_nvp() so the output is identical to std::vector. We will 
then talk to Robert about how we can take advantage of the binary 
archive in a correct fashion.

======================

kind regards

Thorsten, review manager