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
