[review][DoubleEnded] Review Results

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
11 messages Options
Reply | Threaded
Open this post in threaded view
|

[review][DoubleEnded] Review Results

Boost - Dev mailing list
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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost-announce] [review][DoubleEnded] Review Results

Boost - Dev mailing list
On Thu, Oct 26, 2017 at 6:09 PM, Glen Fernandes wrote:

> On Thu, Oct 26, 2017 at 6:00 PM, Thorsten Ottosen wrote:
>> 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.
>
> Hi Thorsten,
>
> Could you please also summarize (a list) who voted for acceptance and
> who voted for rejection?
>
>> provided that it can be integrated smoothly with Boost.Container
>
> Does this mean become part of Boost.Container (instead of a separate library)?
>
> Glen

Also, congratulations to Benedek - and thank you to you for managing
the review. :)

Glen

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost-announce] [review][DoubleEnded] Review Results

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 27-10-2017 kl. 00:09 skrev Glen Fernandes via Boost-users:
> On Thu, Oct 26, 2017 at 6:00 PM, Thorsten Ottosen wrote:
>> 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.
>
> Hi Thorsten,
>
> Could you please also summarize (a list) who voted for acceptance and
> who voted for rejection?

Sure.

Zach Laine (reject)
Louis Dionne (reject)
Joaquin  López Muñoz (conditionally accept)
Ion Gaztañaga (conditionally accept)
Me (conditionally accept)

>> provided that it can be integrated smoothly with Boost.Container
>
> Does this mean become part of Boost.Container (instead of a separate library)?

Yes.

kind regards

Thorsten


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost-announce] [review][DoubleEnded] Review Results

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list


> -----Original Message-----
> From: Boost [mailto:[hidden email]] On Behalf Of Glen Fernandes via Boost
> Sent: 26 October 2017 23:12
> To: Thorsten Ottosen
> Subject: Re: [boost] [Boost-announce] [review][DoubleEnded] Review Results
>
> > On Thu, Oct 26, 2017 at 6:00 PM, Thorsten Ottosen wrote:
> >> 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.

> Also, congratulations to Benedek - and thank you to you for managing
> the review. :)

+1

(And especially to Benedek for the high quality of the documentation).

Paul

---
Paul A. Bristow
Prizet Farmhouse
Kendal UK LA8 8AB
+44 (0) 1539 561830




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [review][DoubleEnded] Review Results

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Fri, Oct 27, 2017 at 5:58 AM, Ion Gaztañaga via Boost
<[hidden email]> wrote:
> I think devector and batch_deque
> additions will be useful for Boost.Container users.

Apologies if this was already answered but how exactly will Benedek
participate in the Boost.Container GitHub repository? Added with write
access with an understanding to limit changes only to his files?

Thanks

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [review][DoubleEnded] Review Results

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Fri, Oct 27, 2017 at 12:00 AM, Thorsten Ottosen <[hidden email]>
wrote:

> 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.
>
>
Thank you for the enormous effort put into mentoring, reviewing and review
managing. It was a disciplined journey, and a really high quality summary
of conditions at the end - which seems not to be the end, after all.

Thanks,
Benedek

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost-announce] [review][DoubleEnded] Review Results

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Boost - Dev mailing list wrote

> Den 27-10-2017 kl. 00:09 skrev Glen Fernandes via Boost-users:
>> On Thu, Oct 26, 2017 at 6:00 PM, Thorsten Ottosen wrote:
>>> 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.
>>
>> Hi Thorsten,
>>
>> Could you please also summarize (a list) who voted for acceptance and
>> who voted for rejection?
>
> Sure.
>
> Zach Laine (reject)
> Louis Dionne (reject)
> Joaquin  López Muñoz (conditionally accept)
> Ion Gaztañaga (conditionally accept)
> Me (conditionally accept)
>
> [...]

Note that my "reject" vote can also be seen as a conditional acceptance with
the conditions already outlined. Not that it matters, but as one of those
that said "reject", I think the current outcome is optimal and I am happy
with it. Also, if there's interest for it, I'd be happy to help review PRs
to Boost.Container when they are ready if that's how things proceed.

Thanks Thorsten for the very detailed review summary, and thanks and
congratulations to Benedek for the library!

Louis




--
Sent from: http://boost.2283326.n4.nabble.com/Boost-Dev-f2600599.html

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [review][DoubleEnded] Review Results

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
El 27/10/2017 a las 0:00, Thorsten Ottosen via Boost escribió:
> 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.
>
> [...]

Congrats to Benedek and thank you Thorsten for the huge effort you've
put into
this very lively (and difficult) review process. I am very much looking
forward to
your upcoming results with respect to the different resizing policies
discussed
--it's been a very exciting theoretical discussion but now the time's
come to see
how the various proposals hold water.

This may sound like an overstatement, but I think there's a possibility that
devector will compete with std::vector for the title of "default
container of
choice" the latter holds in the C++ community: during the review I've
come to
appreciate devector's potential for flexibility and improved performance.
Results and time will say.

Joaquín M López Muñoz



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [Boost-announce] [review][DoubleEnded] Review Results

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 28-10-2017 kl. 10:58 skrev Louis Dionne via Boost:
> Boost - Dev mailing list wrote

> Note that my "reject" vote can also be seen as a conditional acceptance with
> the conditions already outlined. Not that it matters, but as one of those
> that said "reject", I think the current outcome is optimal and I am happy
> with it.

It's good to hear, nevertheless. Thanks :-)

> Also, if there's interest for it, I'd be happy to help review PRs
> to Boost.Container when they are ready if that's how things proceed.

I'm sure there is.

kind regards

Thorsten

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [review][DoubleEnded] Review Results

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 27-10-2017 kl. 18:36 skrev Vinnie Falco via Boost:
> On Fri, Oct 27, 2017 at 5:58 AM, Ion Gaztañaga via Boost
> <[hidden email]> wrote:
>> I think devector and batch_deque
>> additions will be useful for Boost.Container users.
>
> Apologies if this was already answered but how exactly will Benedek
> participate in the Boost.Container GitHub repository? Added with write
> access with an understanding to limit changes only to his files?

Maybe Ion & Benedek can resolve that?

kind regards

Thorsten

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|

Re: [review][DoubleEnded] Review Results

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 28-10-2017 kl. 11:42 skrev Joaquin M López Muñoz via Boost:

> I am very much looking
> forward to
> your upcoming results with respect to the different resizing policies
> discussed
> --it's been a very exciting theoretical discussion but now the time's
> come to see
> how the various proposals hold water.
>
> This may sound like an overstatement, but I think there's a possibility
> that
> devector will compete with std::vector for the title of "default
> container of
> choice" the latter holds in the C++ community: during the review I've
> come to
> appreciate devector's potential for flexibility and improved performance.
> Results and time will say.

Indeed. I hope to do some work in this this week.

kind regards

Thorsten

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost