[review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
162 messages Options
1234 ... 9
Reply | Threaded
Open this post in threaded view
|

[review] The review of Boost.DoubleEnded starts today: September 21 - September 30

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

The library may be downloaded from

https://github.com/erenon/double_ended

and the documentation may be found here:

http://erenon.hu/double_ended/

Anyone is welcome to post a review and/or take part in subsequent
discussions (see below for review guidelines).

Introduction
------------

This is a container library that provides two containers:

A. boost::devector

B. boost::batch_deque

Both containers provides efficient push_front and push_back operations,
hence the name DoubleEnded.

The boost::devector class can be seen as an extension of std::vector
with efficient support for push_front (so boost::devector provides
contiguous storage). In addition, it provides a customizable small
buffer optimization like boost::small_vector(*).
It furthermore allows for customization of the growth factor such that
the user can decide if a reallocation should allocate 1.5 or 2 or
whatever more memory. And finally it provides new functionality that
does not exist in normal vector implementations -- this functionality
allow the class to excel in performance in certain situations like
serialization or transfer of data from sources that require a
preallocated buffer.

The boost::batch_deque is similar to std::deque, but with two important
twists. Like std::deque, it provides reference stability when calling
push_front/push_back. Reference stability is crucial for programs that
uses intrusive containers e.g. using Boost.Intrusive (**).
boost::batch_deque has the following main advantages:

1. It allows the user to specify the segment size

2. It allows for external iteration over the segments

Taken together, they provide a very efficient and flexible basis for
intrusive containers. Access to the segments also increases performance
for tasks such as serialization. Finally, boost::batch_deque may be seen
as an efficient alternative to std::vector if you want to replace
a percent-wise memory overhead with a constant memory overhead and have
no need for contiguous storage.


Review guidelines
-----------------

Please provide in your review whatever information you think is
valuable to understand your final choice of ACCEPT or REJECT including
Fit as a Boost library. Please be explicit about your decision.

Some other questions you might want to consider answering:

   - What is your evaluation of the design?
   - What is your evaluation of the implementation?
   - What is your evaluation of the documentation?
   - What is your evaluation of the potential usefulness of the library?
   - Did you try to use the library? With which compiler(s)? Did you
     have any problems?
   - How much effort did you put into your evaluation? A glance? A quick
     reading? In-depth study?
   - Are you knowledgeable about the problem domain?

More information about the Boost Formal Review Process can be found
here: http://www.boost.org/community/reviews.html


Kind regards

Thorsten, Review manager



(*) boost::small_vector: https://tinyurl.com/ycslp4ot

(**) http://www.boost.org/doc/libs/1_64_0/doc/html/intrusive.html

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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Boost - Dev mailing list
On Thu, Sep 21, 2017 at 12:38 PM, Thorsten Ottosen via Boost <
[hidden email]> 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.


[snip]


> Please provide in your review whatever information you think is
> valuable to understand your final choice of ACCEPT or REJECT including
> Fit as a Boost library. Please be explicit about your decision.
>

I think you mean Boost.DoubleEnded, not Fit :).

I vote to reject Boost.DoubleEnded.


> Some other questions you might want to consider answering:
>
>   - What is your evaluation of the design?
>

I don't think it is up to Boost's standards.

My first concern is that this library is centered around runtime
performance,
yet there appears to be no measurement done to determine what -- or even
whether -- optimization occurs when using this library instead of the
standard
containers.

My second concern is that the containers in this library are difficult to
reason about.

You'll find these two issues reinforced multiple times in the details of
the review below.

Here's the first snippet of code from the examples in the
online docs:

de::devector<int, de::small_buffer_size<16>> small_devector;

BOOST_ASSERT(small_devector.capacity() == 16); // but no dynamic memory was
allocated

small_devector.push_back(2);
small_devector.push_back(3);
small_devector.push_back(4);

small_devector.push_front(1); // allocates

There are no standard containers for which capacity() == 16 implies that
when there are three elements, an allocation will occur when I add a
fourth.  That's substantially odd.  It means that as a user I must know
about extrinsic state information (how many pushes were to the front or
back) in order to predict memory usage and the number of allocations even
roughly.

The next example is this:

de::devector<int> reserved_devector(32, 16, de::reserve_only_tag{});

for (int i = 0; i < 32; ++i) {
  reserved_devector.push_front(i);
}

for (int i = 0; i < 16; ++i) {
  reserved_devector.push_back(i);
}

That's not a compelling use case to me.  Why can't I just do this:

std::vector<int> reserved_vector;
vector.reserve(48);

// Fill in the values, etc.

Why must there be an implicit zero-point, such that front-pushes allocate
before the capacity is reached, and back-pushes allocate before the
capacity is reached (but after a different number of pushes)?  This is all
pretty wonky.  If I only care about growth in one direction, I just use a
vector, and don't worry about the push-front case, because I have reverse
iterators.  Otherwise, I'm inclined just to use deque, because I don't have
to consider these wonky semantics with that, and I have no measurements to
recommend the use of this library instead.

(
BTW, please create an object of your tag type:

de::devector<int> reserved_devector(32, 16, de::reserve_only_tag{});
->
de::devector<int> reserved_devector(32, 16, de::reserve_only);
)

For that matter, is the performance of devector better than std::deque when
I
don't know the relative frequency of front- and back-pushes?  It seems in
many
cases that it would be quite a bit worse.

But it seems that no one knows -- not me, not the author -- because no one
has measured it.  If I'm wrong about this, please share the measurements!

A custom growth policy must have an integral growth factor, but a commonly
used growth factor is 3/2.

I don't understand why should_shrink() is part of GrowthPolicy.  If I'm
growing the container, why am I worried about shrinking it?

Another example from the docs:

de::devector<std::string> reversed_lines;
reversed_lines.reserve_front(24);

std::string line;

while (std::getline(std::cin, line))
{
  reversed_lines.push_front(line);
}

std::cout << "Reversed lines:\n";
for (auto&& line : reversed_lines)
{
  std::cout << line << "\n";
}

How is this better than doing:

std::deque<std::string> reversed_lines;

std::string line;
while (std::getline(std::cin, line))
{
  reversed_lines.push_front(line);
}

std::cout << "Reversed lines:\n";
for (auto it = reversed_lined.begin(), end = reversed_lines.rend());
     it != end; ++it)
{
  std::cout << line << "\n";
}

?  If it's just to avoid the verbose for-loop, that's not enough for me.  If
it's an efficiency claim, I have no numbers to back that up, and the use of
IO
in the example makes it moot anyway.

I need a justification for unsafe_push_front() besides "avoiding a check,
thus
sparing a few instructions".  My intuition is that it does not matter, since
branch prediction is quite good these days, and a single allocation will
swallow all the gains if there are any.  However, *measurement* is the only
thing that can make this justification, pro or con.

Again, from the example docs:

// int sockfd = socket(...); connect(...);
de::devector<char> buffer(256, de::unsafe_uninitialized_tag{});
long recvSize = recv(sockfd, buffer.data(), buffer.size(), 0);

if (recvSize >= 0)
{
  buffer.unsafe_uninitialized_resize_back(recvSize);
  // process contents of buffer
}
else { /* handle error */ }

The unsafe resize does nothing in this case, since char has a trivial
dtor.  For
nontrivially destructed types, we get RAII violations.  I don't know how to
use a type that does that.


>   - What is your evaluation of the implementation?
>

I did not look.


>   - What is your evaluation of the documentation?
>

There are a lot of aspects of the docs I found to be unclear.

The Benchmarks section contains no benchmarks.

There is this:

"
Reference stability is an important feature of the batch_deque. Inserting
elements to the front or to the back of the sequence never invalidates any
references. Moreover, a special insert operation is provided, stable_insert,
which takes an iterator, as a hint, and inserts a sequence of elements (not
necessary directly) before the element pointed by the hint, in a way that
it doesn't invalidate references.
"

I find that very difficult to understand.  It seems to be saying that
stable_insert() does not always insert where you wanted in the sequence,
because the insertion point is just a hint.  I think what is intended is
that the insertion will not necessarily be contiguous (or at least I hope
that's what is intended).

These are other examples like this, but until the high-level design issues
are resolved, I don't want to take the time to get into all the specifics.


>   - What is your evaluation of the potential usefulness of the library?
>

It does not seem useful to me, except that the ability to specify the
block-size for a deque would sometimes come in handy.


>   - Did you try to use the library? With which compiler(s)? Did you
>     have any problems?
>

I did not.


>   - How much effort did you put into your evaluation? A glance? A quick
>     reading? In-depth study?
>

I spent 4-5 hours.

  - Are you knowledgeable about the problem domain?
>

Yes.

Zach

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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Boost - Dev mailing list
Hi Zach,

Thanks for spending a lot of time thinking about the library. Some minor
points for discussion follow.

> My first concern is that this library is centered around runtime
> performance,
> yet there appears to be no measurement done to determine what -- or even
> whether -- optimization occurs when using this library instead of the
> standard
> containers.

For devector:
-------------

Is it it not obvious that an O(1) push_front performs better than an
O(n) vec.insert( vec.begin(), x ) ?

Is it not obvious that having a small buffer optimization can be useful?
boost::small_vector does it. Nearly all std::string does it.
stlsoft::auto_buffer has done it for a decade, described in detail in
Matthew Wilson's book. Chandler Carruth had the following presentation
last year

https://www.youtube.com/watch?v=vElZc6zSIXM

about small buffer optimizations use in Clang data structures.

For batch_deque:
----------------

With std::deque you cannot control the segment size, and implementations
differ widely. Is it not obvious that having a block size of 1 or 2 (as
e.g. visual c++ does) is very fast.

That iteration over a deque can be slow has been known for two decades,
Matt Austern wrote an article about it.

> My second concern is that the containers in this library are difficult to
> reason about.

Look at it this way: devector is like vector with O(1) front insertion;
batch_deque is like deque with custom control over the segment size.

Are you opposed to such containers or is it "all the extra" stuff (which
you don't have to use btw) that makes you uneasy?

Serialization:
--------------

std types are over encapsulated which means that they can't avoid double
initialization, nor process elements in batches. Is it not obvious that
double initialization is more expensive than single initialization?

> For that matter, is the performance of devector better than std::deque when
> I
> don't know the relative frequency of front- and back-pushes?  It seems in
> many
> cases that it would be quite a bit worse.

You are comparing apples and oranges. push_back on vector may be worse
than on deque (just try to store array<T,1024>).

It will depend on the situation, how expensive move operations are, how
expensive allocation is etc. But if you need or want a contiguous
layout, you can't use deque.

> Another example from the docs:
>
> de::devector<std::string> reversed_lines;
> reversed_lines.reserve_front(24);

[snip]

> ?  If it's just to avoid the verbose for-loop, that's not enough for me.  If
> it's an efficiency claim, I have no numbers to back that up, and the use of
> IO in the example makes it moot anyway.

It's not about rewriting a loop. It about having a different layout for
your container's sequence because that layout is either more natural or
convenient or simply needed.

The first use case for devector is actually in the implementation of
batch_deque. One could use some deque implementation, but that would not
be optimal for performance. Being able to use devector there has made
the code so much simpler.

> I need a justification for unsafe_push_front() besides "avoiding a check,
> thus sparing a few instructions".  My intuition is that it does not matter, since
> branch prediction is quite good these days, and a single allocation will
> swallow all the gains if there are any.  However, *measurement* is the only
> thing that can make this justification, pro or con.

Yes, and what do you do when you actually measure and find out push_back
is the bottleneck?

vector has both operator[] and at(), and I'm pretty sure people would go
mad if they were forced to use an operator[] that did what at() does. So
why is push_back any different? You have basically the same situation:
two functions that differ only slightly in their precondition.

>
> Again, from the example docs:
>
> // int sockfd = socket(...); connect(...);
> de::devector<char> buffer(256, de::unsafe_uninitialized_tag{});
> long recvSize = recv(sockfd, buffer.data(), buffer.size(), 0);
>
> if (recvSize >= 0)
> {
>    buffer.unsafe_uninitialized_resize_back(recvSize);
>    // process contents of buffer
> }
> else { /* handle error */ }
>
> The unsafe resize does nothing in this case, since char has a trivial
> dtor.

It changes the size of the container so you can't read uninitialized values.

kind regards

-Thorsten

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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Mon, Sep 25, 2017 at 2:52 AM, Zach Laine via Boost <[hidden email]
> wrote:

>
>
> I vote to reject Boost.DoubleEnded.
>
>
Thanks for your review, I really appreciate your time.


> My first concern is that this library is centered around runtime
> performance,
> yet there appears to be no measurement done to determine what -- or even
> whether -- optimization occurs when using this library instead of the
> standard
> containers.
>

I'm sure you've seen the `benchmark` documentation page, and the linked ML
thread:
https://lists.boost.org/Archives/boost/2016/02/227743.php

I wasn't able to create a convincing micro-benchmark for this container: It
is really hard for the general case. (esp. comparing to vector, which
offers only a subset of devectors features)

On the other hand, a macro-benchmark would require a use-case, which makes
it subjective again. I don't think there's a point in comparing performance
of a small vector vs standard vector, given that the developer got the
`small` size right.


> There are no standard containers for which capacity() == 16 implies that
> when there are three elements, an allocation will occur when I add a
> fourth.  That's substantially odd.  It means that as a user I must know
> about extrinsic state information (how many pushes were to the front or
> back) in order to predict memory usage and the number of allocations even
> roughly.
>

No need for extrinsic state info, there are the front_free_capacity() and
back_free_capacity() members.


> de::devector<int> reserved_devector(32, 16, de::reserve_only_tag{});
>
> [snip]
>
> That's not a compelling use case to me.  Why can't I just do this:
>
> std::vector<int> reserved_vector;
> vector.reserve(48);
>

The reserve_only_tag is a convenient shorthand I tend to miss.


> For that matter, is the performance of devector better than std::deque when
> I
> don't know the relative frequency of front- and back-pushes?  It seems in
> many
> cases that it would be quite a bit worse.
>

I do agree. If you have no clue, use a deque - except, in cases when you
are not supposed to use anything more complicated (see: the internal map of
segments of batch_deque is a devector), or contiguous storage is required.


> A custom growth policy must have an integral growth factor, but a commonly
> used growth factor is 3/2.
>

The growth policy takes the old capacity, and returns the new. new =
uint(3/2*old) is a possible implementation. I don't think float capacity
makes sense.


> I don't understand why should_shrink() is part of GrowthPolicy.  If I'm
> growing the container, why am I worried about shrinking it?
>

Because next time you can avoid growing it.


> Again, from the example docs:
>
> // int sockfd = socket(...); connect(...);
> de::devector<char> buffer(256, de::unsafe_uninitialized_tag{});
> long recvSize = recv(sockfd, buffer.data(), buffer.size(), 0);
>
> if (recvSize >= 0)
> {
>   buffer.unsafe_uninitialized_resize_back(recvSize);
>   // process contents of buffer
> }
> else { /* handle error */ }
>
> The unsafe resize does nothing in this case, since char has a trivial
> dtor.  For
> nontrivially destructed types, we get RAII violations.  I don't know how to
> use a type that does that.
>

One must explicitly call unsafe_uninitialized_resize_back again, after the
exact size is known, avoiding the UB.


>
> >   - What is your evaluation of the implementation?
> >
>
> I did not look.
>
>
> >   - What is your evaluation of the documentation?
> >
>
> There are a lot of aspects of the docs I found to be unclear.
>
> The Benchmarks section contains no benchmarks.
>
> There is this:
>
> "
> Reference stability is an important feature of the batch_deque. Inserting
> elements to the front or to the back of the sequence never invalidates any
> references. Moreover, a special insert operation is provided,
> stable_insert,
> which takes an iterator, as a hint, and inserts a sequence of elements (not
> necessary directly) before the element pointed by the hint, in a way that
> it doesn't invalidate references.
> "
>
> I find that very difficult to understand.  It seems to be saying that
> stable_insert() does not always insert where you wanted in the sequence,
> because the insertion point is just a hint.  I think what is intended is
> that the insertion will not necessarily be contiguous (or at least I hope
> that's what is intended).
>

Perhaps the reference helps?
http://erenon.hu/double_ended/boost/double_ended/batch_deque.html#idp40376016-bb

Thanks,
Benedek

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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

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

Thorsten

I am starting to look at a review of Double Ended.

I have succeeded to build the devector example using Clang 3.6 and 4.0 with their corresponding libc++.

When I run the example I get only one line of output:

Reversed lines:

This does not tell me much at all and I have not found out what it is expected to do.  It seems to read a file, which is not supplied or described.  I have not found anything in the documentation.

On another topic, I have not seen in the documentation any discussion of models for what is going on.  I am aware of Chris Okasaki's book "Purely Function Data Structures" (1998) and a lot of subsequent literature.  Does this work relate at all to previous work?

Answers will help me to put together a review.

Best wishes

John Fletcher




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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Boost - Dev mailing list
On Sep 25, 2017 11:26 PM, "Fletcher, John P via Boost" <
[hidden email]> wrote:



When I run the example I get only one line of output:

Reversed lines:

This does not tell me much at all and I have not found out what it is
expected to do.  It seems to read a file, which is not supplied or
described.  I have not found anything in the documentation.


Hi,
It reads the standard input. Try piping in some lines.

HTH,
Benedek

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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Just some comments on devector for now, based on a quick read of the
documentation and implementation.

Design:

I don't find the unsafe functions sufficiently motivated. Introducing
footguns should require a compelling performance justification, but
there are no actual benchmarks. The unsafe_push_* functions encourage
heavy uses of reserve(), which, if done incorrectly, can easily
prevent the growth policy from working.  Moreover, the design is
inconsistent. Why unsafe_push_* but not unsafe_emplace_*?

What's the motivating use case for the unsafe_uninitialized functions
that can't handled by a non-invariant-violating design like
default_init? The sole example in the documentation is a
devector<char> whose content will be filled by recv later, which can
be handled equally well. Also, assuming that this container meets the
allocator-aware container requirements, the user would have to
construct and destroy the elements via
allocator_traits<>::construct/destroy, not just placement new.
Otherwise, your container's destructor would be asking its allocator
to destroy something it didn't construct.

I'm somewhat surprised that dropping the move_if_noexcept/strong
exception safety dance doesn't seem to have been considered for a
container that's supposed to be performance-oriented.

> typedef pointer iterator;
> typedef const_pointer const_iterator;

Why are pointers being used as iterator types directly?

Implementation:

> class devector
>    : Allocator

Even private derivation can interfere with overload resolution in
unexpected and undesirable ways. You have enough data members around
to leverage EBO without having to make devector itself derive from the
allocator.

https://github.com/erenon/double_ended/blob/master/include/boost/double_ended/devector.hpp#L403
incorrectly calls push_back rather than emplace_back.

Insofar as I can determine, your clear() doesn't deallocate storage,
so https://github.com/erenon/double_ended/blob/master/include/boost/double_ended/devector.hpp#L570
just overwrites the only allocator capable of deallocating the storage
you are currently holding - without deallocating it first.

More generally, implementation of allocator support requires
substantial improvement. An allocator that doesn't propagate on X is
not required to support X at all, but there's no handling for that in
your code.  Another example: construct takes raw pointers, not
possibly fancy `pointer` like what you did here:
https://github.com/erenon/double_ended/blob/master/include/boost/double_ended/devector.hpp#L2086

The fast path for range-insert-at-front
(https://github.com/erenon/double_ended/blob/master/include/boost/double_ended/devector.hpp#L2496)
is broken based on a cursory inspection:

vector<int> x = {1, 2, 3};
devector<int> y = {4, 5, 6};
y.reserve_front(10);
y.insert(y.begin(), x.begin(), x.end()); // {3, 2, 1, 4, 5, 6} (!)

Documentation:

Does your push_back etc. really have "amortized linear" complexity?
And doesn't that depend on the growth policy?

How can clear() have the postcondition "empty() &&
front_free_capacity() == 0 && back_free_capacity() == small buffer
size" yet not deallocate memory?

The default growth policy is:

> static size_type new_capacity(size_type capacity);
> Returns: 4 times the old capacity or 16 if it's 0.

Why those numbers? Were they arbitrarily chosen or based on some sort
of benchmark? If so, what?

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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Mon, Sep 25, 2017 at 12:17 PM, Thorsten Ottosen via Boost <
[hidden email]> wrote:

> Hi Zach,
>
> Thanks for spending a lot of time thinking about the library. Some minor
> points for discussion follow.
>
> My first concern is that this library is centered around runtime
>> performance,
>> yet there appears to be no measurement done to determine what -- or even
>> whether -- optimization occurs when using this library instead of the
>> standard
>> containers.
>>
>
> For devector:
> -------------
>
> Is it it not obvious that an O(1) push_front performs better than an O(n)
> vec.insert( vec.begin(), x ) ?
>

I find the use of the word "obvious" when applied to optimization to be a
little suspect.  Also, that statement is not quite true.  push_front() is
*amortized* O(1), not O(1).  A particular call to push_front() is actually
O(N).  But the larger point to me is that I can use vector when I care
about amortized O(1) growth in either direction.  I only care about
devector or deque when I need amortized O(1) growth in *both* directions.
Then, it is a question of whether the relative performance recommends
devector or deque.  As of this writing, I have to write benchmarks or do a
lot of custom profiling to figure out which works better.

My strong preference would be that the author provide sufficient
measurements of a few use cases of both of these data structures at various
values of N, so that I can make a reasonable educated guess when first
selecting the data structure to use.  It won't allow me to elide profiling
altogether, but it will get me going in the right direction more often,
with less effort for me as a user.


> Is it not obvious that having a small buffer optimization can be useful?
> boost::small_vector does it. Nearly all std::string does it.
> stlsoft::auto_buffer has done it for a decade, described in detail in
> Matthew Wilson's book. Chandler Carruth had the following presentation last
> year
>
> https://www.youtube.com/watch?v=vElZc6zSIXM
>
> about small buffer optimizations use in Clang data structures.
>

You don't need to justify SBO to me; I'm all for it.  We already have
boost::small_vector though, as you point out.  Furthermore, that particular
optimization only pays off when N is small.  When N is small, amortization
doesn't really pay off.  So, again, since I would only use devector/deque
when I know I need growth in *both* directions, I would want to see the
relative strengths and weaknesses of deque vs. devector to make an informed
decision.


> For batch_deque:
> ----------------
>
> With std::deque you cannot control the segment size, and implementations
> differ widely. Is it not obvious that having a block size of 1 or 2 (as
> e.g. visual c++ does) is very fast.
>

Right.  Control of the segment size is the one thing I called out in my
review as an unambiguous positive.


> That iteration over a deque can be slow has been known for two decades,
> Matt Austern wrote an article about it.


... and this should have been the other.  I'm aware of that work, and I'd
like to see a deque that features configurable segment size and segmented
iteration support.  As an aside, my experiments with segmented iteration
have been of mixed utility.  The standard algorithms useful on segments is
limited, since they cannot see across segment boundaries.  For instance,
adjacent_difference() does not work without some gymnastics.


> My second concern is that the containers in this library are difficult to
>> reason about.
>>
>
> Look at it this way: devector is like vector with O(1) front insertion;
> batch_deque is like deque with custom control over the segment size.
>
> Are you opposed to such containers or is it "all the extra" stuff (which
> you don't have to use btw) that makes you uneasy?
>

Up until now, in this post all my objections have been related to runtime
efficiency.  But now you've brought back up a major complaint that I have,
which is the unsafety of the interface.  To say that I don't have to use it
is a bit disingenuous to me.  Adding an unsafe API weakens the invariants
of the type, making it more difficult to reason about and use.  The idea
that I can add elements that will be manually destructed but that are not
yet constructed is a serious defect in my opinion.  Any throwing operation
I do between the creation of such elements and their construction is now
unsafe.


> Serialization:
> --------------
>
> std types are over encapsulated which means that they can't avoid double
> initialization, nor process elements in batches. Is it not obvious that
> double initialization is more expensive than single initialization?


In the abstract, of course you cannot argue with that.  I don't find it to
be a useful question, though.  The questions I have are:

1) In my specific case, do I care (that is, is it measurable)?  In many
cases, a type will be expensive to copy or non-default-construct, but
trivial to default construct.
2) If the answer to #1 is yes, is reserve() not sufficient?

I would expect the answer to one of those two questions to be "no" in
almost all cases.  It's not that you'd *never* answer "yes" to both, it's
just that this represents a low-frequency corner.

>
> For that matter, is the performance of devector better than std::deque when
>> I
>> don't know the relative frequency of front- and back-pushes?  It seems in
>> many
>> cases that it would be quite a bit worse.
>>
>
> You are comparing apples and oranges. push_back on vector may be worse
> than on deque (just try to store array<T,1024>).
>

Re-reading that. I think I didn't state my point very clearly.   What I was
trying to say is that the zero-point implied in having separate front and
back capacities means that I need to guess the relative frequency of front
and back pushes if I want the benefits of reserving space.  When you
combine that with the fact that growing a devector requires copying every
element, it may be a pessimization to use one over a deque.  To me, that's
not an apples/oranges comparison, because my use of the entire library
boils down to the case where I know I need growth in *both* directions, and
now I must determine whether devector or deque is a better fit.

It will depend on the situation, how expensive move operations are, how

> expensive allocation is etc. But if you need or want a contiguous layout,
> you can't use deque.
>
> Another example from the docs:
>>
>> de::devector<std::string> reversed_lines;
>> reversed_lines.reserve_front(24);
>>
>
> [snip]
>
> ?  If it's just to avoid the verbose for-loop, that's not enough for me.
>> If
>> it's an efficiency claim, I have no numbers to back that up, and the use
>> of
>> IO in the example makes it moot anyway.
>>
>
> It's not about rewriting a loop. It about having a different layout for
> your container's sequence because that layout is either more natural or
> convenient or simply needed.
>

Fair enough.  Sometimes contiguity is very important.


> The first use case for devector is actually in the implementation of
> batch_deque. One could use some deque implementation, but that would not be
> optimal for performance.


For small objects or large?  For what values of N?  For what pattern of
calls?  Only for double-ended growth, or for single-ended growth as well?
I don't necessarily doubt your claim, I just don't have the relative
superiority of devector quantified in any way that I can use.


> Being able to use devector there has made the code so much simpler.


It's not obvious to me why.  Could you elaborate?


> I need a justification for unsafe_push_front() besides "avoiding a check,
>> thus sparing a few instructions".  My intuition is that it does not
>> matter, since
>> branch prediction is quite good these days, and a single allocation will
>> swallow all the gains if there are any.  However, *measurement* is the
>> only
>> thing that can make this justification, pro or con.
>>
>
> Yes, and what do you do when you actually measure and find out push_back
> is the bottleneck?
>
> vector has both operator[] and at(), and I'm pretty sure people would go
> mad if they were forced to use an operator[] that did what at() does. So
> why is push_back any different? You have basically the same situation: two
> functions that differ only slightly in their precondition.


First, please demonstrate that I should care about those few instructions.
Second, I agree that the difference is slight, but I disagree that it's ok
to make that slight change.  One of the chief invariants of a standard
container is that it manages its storage.  This breaks that.  Dangerous
interfaces are not necessarily evil, but they certainly need to be
justified.  I would need significant use cases with significant performance
benefits (not night-and-day, but significant) to tolerate this unsafety.


>
>> Again, from the example docs:
>>
>> // int sockfd = socket(...); connect(...);
>> de::devector<char> buffer(256, de::unsafe_uninitialized_tag{});
>> long recvSize = recv(sockfd, buffer.data(), buffer.size(), 0);
>>
>> if (recvSize >= 0)
>> {
>>    buffer.unsafe_uninitialized_resize_back(recvSize);
>>    // process contents of buffer
>> }
>> else { /* handle error */ }
>>
>> The unsafe resize does nothing in this case, since char has a trivial
>> dtor.
>>
>
> It changes the size of the container so you can't read uninitialized
> values.
>

That's true, though some sort of span would accomplish the same thing with
no loss of safety.  In the case that the unsafe uninitialized resize grows
the container, leaving storage around that is not yet constructed, but that
the dtor will destruct, is very dangerous.

If I distill all my objections down it comes to these three points, I think:

1) This library seems to cover small corner cases.
2) The API is unsafe.
3) I don't have any reason to expect that the efficiency gains in the
corner cases are substantial enough to justify the unsafety, or even that
there are positive gains in my particular corner case.

Zach

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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Playing around with devector, I find the default growth strategy (x4)
rather (too) agressive. It also has some in my view un-intended effects.
Starting from let's say initial front and back capacities of each 4, now
adding 5 elements in front and 5 elements in the back (so 10), now gives me
a devector with capacity 128 (wow, why bothr with SBO at all).

Then looking how the free_capacity is split between front and back we get
95 and 23 (or the other way around, depending on whether we first push_back
or first push_front, even when front- and back-pushes are interleaved). As
we are multiplying by 4, this will become more and more skewed.

I think capacity() should go, and replaced by (next to the free versions)
front_capacity() and back_capacity().

I think the template allocator parameter should be second, not last.

Some bikeshedding (tm). I don't like any of the names much. The batch_deque
*is* a deque, it should be called that way. devector is a hybrid
vector/deque, I think veque would capture that. Then as to double_ended, I
think it's too long and describes badly what we are talking about. I
haven't got any (much) better proposal, but was thinking of Boost.Que, nice
and short.

i.e. boost::que::veque and boost::que::deque.

degski

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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Boost - Dev mailing list
On 26 September 2017 at 09:33, degski <[hidden email]> wrote:

> Then looking how the free_capacity is split between front and back we get
> 95 and 23 (or the other way around, depending on whether we first push_back
> or first push_front, even when front- and back-pushes are interleaved).
>

Maybe a rebalance ( size_type hint ) member function could address this
issue and relocate the "zero-point" to the hinted at position (possible
safe and unsafe). A clear ( size_type hint ) could do the same on clearing.

degski
--
"*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend,
Schmerzen aus Schwäche stillend.*" - Novalis 1798

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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 26-09-2017 kl. 03:39 skrev Zach Laine via Boost:
> On Mon, Sep 25, 2017 at 12:17 PM, Thorsten Ottosen via Boost <
> [hidden email]> wrote:
>

>> Is it it not obvious that an O(1) push_front performs better than an O(n)
>> vec.insert( vec.begin(), x ) ?
>>
>
> I find the use of the word "obvious" when applied to optimization to be a
> little suspect.

[snip]

>  But the larger point to me is that I can use vector when I care
> about amortized O(1) growth in either direction.  I only care about
> devector or deque when I need amortized O(1) growth in *both* directions.

Can you explain how that works for vector when growing the front?

> Then, it is a question of whether the relative performance recommends
> devector or deque.  As of this writing, I have to write benchmarks or do a
> lot of custom profiling to figure out which works better.
>
> My strong preference would be that the author provide sufficient
> measurements of a few use cases of both of these data structures at various
> values of N, so that I can make a reasonable educated guess when first
> selecting the data structure to use.  It won't allow me to elide profiling
> altogether, but it will get me going in the right direction more often,
> with less effort for me as a user.

I agree that is not a bad thing to add to the documentation.

>  As an aside, my experiments with segmented iteration
> have been of mixed utility.  The standard algorithms useful on segments is
> limited, since they cannot see across segment boundaries.  For instance,
> adjacent_difference() does not work without some gymnastics.

We recently got Boost.PolyCollection. It has specialized algorithms:

   https://tinyurl.com/yaffvebf

I'm wondering if its possible to make these more general. Basically, a
poly-collection stores a vector for each dynamic type, and this is a bit
like a segment (although segment size may differ).

>> Are you opposed to such containers or is it "all the extra" stuff (which
>> you don't have to use btw) that makes you uneasy?
>>
>
> Up until now, in this post all my objections have been related to runtime
> efficiency.  But now you've brought back up a major complaint that I have,
> which is the unsafety of the interface.  To say that I don't have to use it
> is a bit disingenuous to me.  Adding an unsafe API weakens the invariants
> of the type, making it more difficult to reason about and use.  The idea
> that I can add elements that will be manually destructed but that are not
> yet constructed is a serious defect in my opinion.  Any throwing operation
> I do between the creation of such elements and their construction is now
> unsafe.

For the record, I'm not trying to be disingeneous. Let me explain.

The invariant of the container remains the same no matter you do.

I dislike the word "unsafe" used in the naming of such functions, but
that is what Benedek has chosen. For example, I don't think a function
should be labeled unsafe just because it has one extra precondition
compared to a similar function. If we did that, quite a few "unsafe"
labels would appear in a normal high-level C++ program.

Now, the functions that allow you to avoid double initialization can be
misused. They have a strict contract if you will. Does that mean no
library can ever contain such functionality? My personal view is that
if containers over-encapsulate in order to be "safe" (or "safer"), but
sacrifice near-optimal performance, some users will chose not to use
them. And what they fall back on is going to be so much worse than using
a container that is built to help them (worse in terms of
exception-safety, abstraction, low-levelness of code). So what has been
added to devector is the minimal thing needed to accomplish the goal of
giving the user the choice of getting rid of double initialization.

So if we chose not to add such functionality, it will make the container
less useful to some (not all) people. And that is perhaps why I don't
understand your argument. Yes, some of the function are more difficult
to use, but only if actually use them. And those very few who do need to
use them will find them much easier to use than the alternatives.

>
>> Serialization:
>> --------------
>>
>> std types are over encapsulated which means that they can't avoid double
>> initialization, nor process elements in batches. Is it not obvious that
>> double initialization is more expensive than single initialization?
>
>
> In the abstract, of course you cannot argue with that.  I don't find it to
> be a useful question, though.  The questions I have are:
>
> 1) In my specific case, do I care (that is, is it measurable)?  In many
> cases, a type will be expensive to copy or non-default-construct, but
> trivial to default construct.
> 2) If the answer to #1 is yes, is reserve() not sufficient?
>
> I would expect the answer to one of those two questions to be "no" in
> almost all cases.  It's not that you'd *never* answer "yes" to both, it's
> just that this represents a low-frequency corner.

No matter how we program, I think it's safe to say that container<int>
or container<char> is not going away any time soon. So the answer to
your question is that "it depends". If you high-level objects are build
upon low-level things, making those low-level things faster can
certainly impact the high-level things.

>>
>> For that matter, is the performance of devector better than std::deque when
>>> I
>>> don't know the relative frequency of front- and back-pushes?  It seems in
>>> many
>>> cases that it would be quite a bit worse.
>>>
>>
>> You are comparing apples and oranges. push_back on vector may be worse
>> than on deque (just try to store array<T,1024>).
>>
>
> Re-reading that. I think I didn't state my point very clearly.   What I was
> trying to say is that the zero-point implied in having separate front and
> back capacities means that I need to guess the relative frequency of front
> and back pushes if I want the benefits of reserving space.

Well, there is nothing that requires you to use
reserve_front/reserve_back. Just like there is no one that requires you
to use reserve in vector.

> When you
> combine that with the fact that growing a devector requires copying every
> element, it may be a pessimization to use one over a deque.  To me, that's
> not an apples/oranges comparison, because my use of the entire library
> boils down to the case where I know I need growth in *both* directions, and
> now I must determine whether devector or deque is a better fit.

We are not in disagreement here. But std::deque may be faster than
std::vector for push_back. So I don't see how that can be a criticism of
devector. It's not better than vector in this respect.

And I agree some form of performance tests to give a rough idea of how
the containers compare would be good.

>> The first use case for devector is actually in the implementation of
>> batch_deque. One could use some deque implementation, but that would not be
>> optimal for performance.
>
>
> For small objects or large?  For what values of N?  For what pattern of
> calls?  Only for double-ended growth, or for single-ended growth as well?
> I don't necessarily doubt your claim, I just don't have the relative
> superiority of devector quantified in any way that I can use.

If you write a deque like container, you need some data-structure to
hold the segments. For some reason, implementations of deque tends to
call this a map. Anyway, this "map" needs to support amortized O(1)
growth at both ends in order for the deque class to guarantee amortized
O(1) growth at both ends. What all the implementations I know of do is
then to create this map as an internal data-structure. This clutters the
code considerably compared to what Benedek has done.

The reason that you don't want to use deque as a building block for
batch_deque is that it destroys "map" locality.


>> I need a justification for unsafe_push_front() besides "avoiding a check,
>>> thus sparing a few instructions".  My intuition is that it does not
>>> matter, since
>>> branch prediction is quite good these days, and a single allocation will
>>> swallow all the gains if there are any.  

[snip]

> First, please demonstrate that I should care about those few instructions.
> Second, I agree that the difference is slight, but I disagree that it's ok
> to make that slight change.  One of the chief invariants of a standard
> container is that it manages its storage.  This breaks that.

It's not an invariant of vector that push_back allocates memory.
unsafe_push_back does not change anything wrt. what the container manages.

> Dangerous
> interfaces are not necessarily evil, but they certainly need to be
> justified.  I would need significant use cases with significant performance
> benefits (not night-and-day, but significant) to tolerate this unsafety.

It might be hard to make you personally care. But even if you don't
personally care, rest assured that some people will care.
And I do think the documentation should be improved. But the simplicity
(or not) of a function affects a lot of things:

- exception specification: unsafe_push_back can be made conditionally
noexcept, push_back cannot (it is not right now, but it should be).
- inlineability: the simpler the function, the higher the chance it
get's inlined
- register allocation: the simpler the function, the better for the
optimizer
- branch prediction: on some platforms this works well, on other not so
much

which may depending on situation/platform be a big deal.

But seriously, we should not call functions with one extra precondition
"dangerous" or "unsafe". It's still much better than the alternative,
and as I explained above, we should strive to make the inherently
low-level and unsafe code obsolete. And the only way to do that is to
present an alternative that is just as per formant (or better) yet
offers a superior high-level approach. We don't want people to
use local arrays and manage the size of it manually.

>>>     buffer.unsafe_uninitialized_resize_back(recvSize);

>> It changes the size of the container so you can't read uninitialized
>> values.
>>
>
> That's true, though some sort of span would accomplish the same thing with
> no loss of safety.

But then you just postponed the double initialization to when the span
needs to be copied into a proper container!

The whole point is that we don't want to forego the great benefit of a
container just because we are interfacing with a low-level API.

kind regards

Thorsten

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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

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

> On 26. Sep 2017, at 03:39, Zach Laine via Boost <[hidden email]> wrote:
>
> On Mon, Sep 25, 2017 at 12:17 PM, Thorsten Ottosen via Boost <
> [hidden email] <mailto:[hidden email]>> wrote:
>
>> For devector:
>> -------------
>>
>> Is it it not obvious that an O(1) push_front performs better than an O(n)
>> vec.insert( vec.begin(), x ) ?
>>
>
> I find the use of the word "obvious" when applied to optimization to be a
> little suspect.

I wanted to say the same. I got my fair share of surprises when I benchmarked code that I expected to run faster than some other code. I can recommend Google Benchmark for micro-benchmarks, it is quite neat.

https://github.com/google/benchmark

Best regards,
Hans

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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 25-09-2017 kl. 23:13 skrev Benedek Thaler via Boost:
> On Mon, Sep 25, 2017 at 2:52 AM, Zach Laine via Boost <[hidden email]
>> wrote:

>> There are no standard containers for which capacity() == 16 implies that
>> when there are three elements, an allocation will occur when I add a
>> fourth.  That's substantially odd.  It means that as a user I must know
>> about extrinsic state information (how many pushes were to the front or
>> back) in order to predict memory usage and the number of allocations even
>> roughly.
>>
>
> No need for extrinsic state info, there are the front_free_capacity() and
> back_free_capacity() members.

1. vector's capacity says nothing about whether the next push_back will
allocate

2. there are containers that allocate on every push_back/push_front, so
why is this odd?

3. we have different options here. I don't suppose you object to the
fact when a small buffer is specified, then the small buffer size is
also the initial capacity?

So the choices we have is where to distribute the capacity between
front_free_capacity and back_free_capacity:

A. divide it as evenly as possible
B. maximize front_free_capacity
C. maximize back_free_capacity

Currently, devector does (C) and provide means for the user to choose
the capacity at both ends. What would you prefer instead?

>> I don't understand why should_shrink() is part of GrowthPolicy.  If I'm
>> growing the container, why am I worried about shrinking it?
>>
>
> Because next time you can avoid growing it.

To add to that: shrinking involves allocating a new buffer and copying
or moving elements to the new buffer, which may be very expensive.

Say you feel this is not worth doing if the amount of reclaimed memory
is less than 5 percent (i.e. the vector is at +95% capacity).

kind regards

-Thorsten

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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Hi Tim,

> Just some comments on devector for now, based on a quick read of the
> documentation and implementation.
>
> Design:
>
> I don't find the unsafe functions sufficiently motivated. Introducing
> footguns should require a compelling performance justification, but
> there are no actual benchmarks. The unsafe_push_* functions encourage
> heavy uses of reserve(), which, if done incorrectly, can easily
> prevent the growth policy from working.  Moreover, the design is
> inconsistent. Why unsafe_push_* but not unsafe_emplace_*?

The missing _emplace functions is surely an oversight.

I the thread with Zach's review I tried to view this from a more
philosophical viewpoint. What is safe and unsafe is highly subjective
(and as I wrote in the other thread, it is a mistake to use the word
"unsafe" in the function name").
But C++ is not memory safe like Java or C#, and there are tons of
preconditions in C++ code that are only checked with debug assertions.
Yet I don't think in general that C++ programs have more bugs than Java
or C# programs. Take a look at various Boost libraries and they offer
plenty of opportunity to shoot yourself in the foot. But we use them
anyway because they offer functionality and performance that cannot be
found in any other way. Said differently: all the alternatives are
worse. As just one example: I can use Boost.Intrusive and it is surely
harder to use than normal containers, but the performance is awesome and
compared with all the hand-rolled, ad hoc alternatives, it's vastly
superior.

So it's easy to say something is hard and unsafe to use. But what about
the alternative?

I have personally been optimizing stuff that fell back on vector's
push_back was not inlined. So I had to rewrite the code, effectively
making an ad hoc container just so I could add elements to it
efficiently in the loop that controlled the general performance of the
program.

> What's the motivating use case for the unsafe_uninitialized functions
> that can't handled by a non-invariant-violating design like
> default_init? The sole example in the documentation is a
> devector<char> whose content will be filled by recv later, which can
> be handled equally well.

Can you elaborate on what this design is exactly? Thanks.

> Also, assuming that this container meets the
> allocator-aware container requirements, the user would have to
> construct and destroy the elements via
> allocator_traits<>::construct/destroy, not just placement new.
> Otherwise, your container's destructor would be asking its allocator
> to destroy something it didn't construct.

Indeed. If the documentation doesn't say so, it needs to be updated.

> I'm somewhat surprised that dropping the move_if_noexcept/strong
> exception safety dance doesn't seem to have been considered for a
> container that's supposed to be performance-oriented.

For which container operation are you thinking about?

> The default growth policy is:
>
>> static size_type new_capacity(size_type capacity);
>> Returns: 4 times the old capacity or 16 if it's 0.
>
> Why those numbers? Were they arbitrarily chosen or based on some sort
> of benchmark? If so, what?

In this connection,

https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md

may be relevant. It argues for a 1.5 growth factor.

kind regards

Thorsten

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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Tue, Sep 26, 2017 at 10:59 AM, Thorsten Ottosen via Boost <
[hidden email]> wrote:

> Den 26-09-2017 kl. 03:39 skrev Zach Laine via Boost:
>
>> On Mon, Sep 25, 2017 at 12:17 PM, Thorsten Ottosen via Boost <
>> [hidden email]> wrote:
>>
>
[snip]


>  But the larger point to me is that I can use vector when I care
>> about amortized O(1) growth in either direction.  I only care about
>> devector or deque when I need amortized O(1) growth in *both* directions.
>>
>
> Can you explain how that works for vector when growing the front?


Sure:

std::vector<int> v;

v.push_back(1);
v.push_back(2);
v.push_back(3);

for (auto it = v.rbegin(), end = rend(); it != end; ++it) {
    // whatever
}

Just as you don't care whether your stack grow up or down, you don't care
whether you're pushing to the "front" or "back" if you only push/pop to one
side -- because you can always view the resulting sequence in reverse.

 As an aside, my experiments with segmented iteration

>> have been of mixed utility.  The standard algorithms useful on segments is
>> limited, since they cannot see across segment boundaries.  For instance,
>> adjacent_difference() does not work without some gymnastics.
>>
>
> We recently got Boost.PolyCollection. It has specialized algorithms:
>
>   https://tinyurl.com/yaffvebf
>
> I'm wondering if its possible to make these more general.


I think that would be interesting work, perhaps something we could even
standardize.


> Are you opposed to such containers or is it "all the extra" stuff (which
>>> you don't have to use btw) that makes you uneasy?
>>>
>>>
>> Up until now, in this post all my objections have been related to runtime
>> efficiency.  But now you've brought back up a major complaint that I have,
>> which is the unsafety of the interface.  To say that I don't have to use
>> it
>> is a bit disingenuous to me.  Adding an unsafe API weakens the invariants
>> of the type, making it more difficult to reason about and use.  The idea
>> that I can add elements that will be manually destructed but that are not
>> yet constructed is a serious defect in my opinion.  Any throwing operation
>> I do between the creation of such elements and their construction is now
>> unsafe.
>>
>
> For the record, I'm not trying to be disingeneous. Let me explain.
>
> The invariant of the container remains the same no matter you do.
>

They do not.  The most basic container invariant is RAII.  That is,
elements that have been constructed in the container will be destructed
properly when the container is destructed, and -- importantly -- nothing
else. I should not have to worry about destruction of not-yet-constructed
elements for which there is storage allocated (as with
unsafe_uninitialized* APIs).  It does not matter that I do not use these
APIs.  If they exist, then later under maintenance I or a coworker may add
use of them.  I therefore have to write code that operates under the
invariants of the type, not my particular use of it.

But again, don't get me wrong -- I'm not opposed to doing these kinds of
low-level hacks to get performance.  For instance, move operations are
unsafe in a similar fashion (though not as unsafe, IMO), and I use them all
the time.

The issue to me is that these are high-level container types, and yet they
have invariants that are less safe than std::array.  I feel they are not
sufficiently justified in such a container.

By the way, there are other ways to get similar performance gains without
sacrificing safety:

template <typename T>
struct devector_guts
{
    // low level unsafe stuff goes here, "here be dragons", etc.

    T * elements_;
    size_t size_;
    size_t capacity_;
};

template <typename T>
struct devector
{
    // only safe operations here

    devector_guts steal_guts () &&; // returns guts; empties *this

private:
    devector_guts guts_;
};

[snip]

For that matter, is the performance of devector better than std::deque when

>>>
>>>> I
>>>> don't know the relative frequency of front- and back-pushes?  It seems
>>>> in
>>>> many
>>>> cases that it would be quite a bit worse.
>>>>
>>>>
>>> You are comparing apples and oranges. push_back on vector may be worse
>>> than on deque (just try to store array<T,1024>).
>>>
>>>
>> Re-reading that. I think I didn't state my point very clearly.   What I
>> was
>> trying to say is that the zero-point implied in having separate front and
>> back capacities means that I need to guess the relative frequency of front
>> and back pushes if I want the benefits of reserving space.
>>
>
> Well, there is nothing that requires you to use
> reserve_front/reserve_back. Just like there is no one that requires you to
> use reserve in vector.


Sure.  I'm trying to point out that when I *do* want to use it, the current
separate-and-fixed scheme is hard to use, because you must guess something
close to the relative ratio of front and back pushes.


> When you
>> combine that with the fact that growing a devector requires copying every
>> element, it may be a pessimization to use one over a deque.  To me, that's
>> not an apples/oranges comparison, because my use of the entire library
>> boils down to the case where I know I need growth in *both* directions,
>> and
>> now I must determine whether devector or deque is a better fit.
>>
>
> We are not in disagreement here. But std::deque may be faster than
> std::vector for push_back. So I don't see how that can be a criticism of
> devector. It's not better than vector in this respect.
>

It's not a criticism of devector at all.  It's an open question for which I
have no answer, meaning I have to 1) do a lot of homework (profiling, etc.)
before knowing if I should even consider devector, and 2) weigh any
possible gains in performance against loss of ability to reason about my
code.

It is, however, a criticism of the library, which should do this profiling
homework and proper encapsulation for me.


> And I agree some form of performance tests to give a rough idea of how the
> containers compare would be good.
>
> The first use case for devector is actually in the implementation of
>>> batch_deque. One could use some deque implementation, but that would not
>>> be
>>> optimal for performance.
>>>
>>
>>
>> For small objects or large?  For what values of N?  For what pattern of
>> calls?  Only for double-ended growth, or for single-ended growth as well?
>> I don't necessarily doubt your claim, I just don't have the relative
>> superiority of devector quantified in any way that I can use.
>>
>
> If you write a deque like container, you need some data-structure to hold
> the segments. For some reason, implementations of deque tends to call this
> a map. Anyway, this "map" needs to support amortized O(1) growth at both
> ends in order for the deque class to guarantee amortized O(1) growth at
> both ends. What all the implementations I know of do is then to create this
> map as an internal data-structure. This clutters the code considerably
> compared to what Benedek has done.
>
> The reason that you don't want to use deque as a building block for
> batch_deque is that it destroys "map" locality.


Thanks for the explanation.  That makes sense.


> I need a justification for unsafe_push_front() besides "avoiding a check,
>>>
>>>> thus sparing a few instructions".  My intuition is that it does not
>>>> matter, since
>>>> branch prediction is quite good these days, and a single allocation will
>>>> swallow all the gains if there are any.
>>>>
>>>
> [snip]
>
> First, please demonstrate that I should care about those few instructions.
>> Second, I agree that the difference is slight, but I disagree that it's ok
>> to make that slight change.  One of the chief invariants of a standard
>> container is that it manages its storage.  This breaks that.
>>
>
> It's not an invariant of vector that push_back allocates memory.


Sure it is. 26.3.11.5/1 says:
template reference emplace_back(Args&&... args);
template iterator emplace(const_iterator position, Args&&... args);
void push_back(const T& x);
void push_back(T&& x);
Remarks: Causes reallocation if the new size is greater than the old
capacity. Reallocation invalidates all the references...


> Dangerous
>> interfaces are not necessarily evil, but they certainly need to be
>> justified.  I would need significant use cases with significant
>> performance
>> benefits (not night-and-day, but significant) to tolerate this unsafety.
>>
>
> It might be hard to make you personally care. But even if you don't
> personally care, rest assured that some people will care.
>

I *do* care about maximizing efficiency.  I just want any unsafe code I
have to write to be encapsulated so that I can unit-test it, and not care
about the unsafe details.  To the extent that the unsafe details leak out
of the interface, I need *justification for* -- not complete absence of --
the unsafe bits.


> And I do think the documentation should be improved. But the simplicity
> (or not) of a function affects a lot of things:
>
> - exception specification: unsafe_push_back can be made conditionally
> noexcept, push_back cannot (it is not right now, but it should be).
>

If it can be, we should do it in Boost.  If nothing else, that will serve
as an existence proof of successful industrial use of that approach, making
it a lot easier to sell to the committee.


> - inlineability: the simpler the function, the higher the chance it get's
> inlined
> - register allocation: the simpler the function, the better for the
> optimizer
> - branch prediction: on some platforms this works well, on other not so
> much
>
> which may depending on situation/platform be a big deal.
>

I agree with all that.


> But seriously, we should not call functions with one extra precondition
> "dangerous" or "unsafe". It's still much better than the alternative, and
> as I explained above, we should strive to make the inherently low-level and
> unsafe code obsolete. And the only way to do that is to present an
> alternative that is just as per formant (or better) yet offers a superior
> high-level approach. We don't want people to
> use local arrays and manage the size of it manually.
>

I think that the unsafety comes from changing the invariants in such a way
that I can no longer reason about lifetimes, etc.  And going straight to
handwritten code over arrays is IMO a red herring.  A second unsafe tier
can be provided with the desired operations, that everyone knows is unsafe,
is truly opt0in, etc.


>     buffer.unsafe_uninitialized_resize_back(recvSize);
>>>>
>>>
> It changes the size of the container so you can't read uninitialized
>>> values.
>>>
>>>
>> That's true, though some sort of span would accomplish the same thing with
>> no loss of safety.
>>
>
> But then you just postponed the double initialization to when the span
> needs to be copied into a proper container!
>

Well, in the limited case where I copy it, sure.  But that's also true if I
copy buffer after calling

buffer.unsafe_uninitialized_resize_back(recvSize);

above.  The point is you want to use the [0, recvSize) subsequence of
buffer, and you don't need to have a unsafe_uninitialized_resize_back()
member to do that.


> The whole point is that we don't want to forego the great benefit of a
> container just because we are interfacing with a low-level API.
>

I think we can actually have both.

Zach

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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
On Tue, Sep 26, 2017 at 11:32 AM, Thorsten Ottosen via Boost <
[hidden email]> wrote:

> Den 25-09-2017 kl. 23:13 skrev Benedek Thaler via Boost:
>
>> On Mon, Sep 25, 2017 at 2:52 AM, Zach Laine via Boost <
>> [hidden email]
>>
>>> wrote:
>>>
>>
> There are no standard containers for which capacity() == 16 implies that
>>> when there are three elements, an allocation will occur when I add a
>>> fourth.  That's substantially odd.  It means that as a user I must know
>>> about extrinsic state information (how many pushes were to the front or
>>> back) in order to predict memory usage and the number of allocations even
>>> roughly.
>>>
>>>
>> No need for extrinsic state info, there are the front_free_capacity() and
>> back_free_capacity() members.
>>
>
> 1. vector's capacity says nothing about whether the next push_back will
> allocate
>

That's exactly what capacity says.  See my earlier post, plus 26.3.11.3/1:

size_type capacity() const noexcept;
Returns: The total number of elements that the vector can hold without
requiring reallocation.


> 2. there are containers that allocate on every push_back/push_front, so
> why is this odd?
>

Because capacity() indicates that it does not do this, in relation to the
current value of size(), when I call push_back().  Removing capacity() and
not calling devector a container would alleviate this particular concern.


> 3. we have different options here. I don't suppose you object to the fact
> when a small buffer is specified, then the small buffer size is also the
> initial capacity?
>

No.


> So the choices we have is where to distribute the capacity between
> front_free_capacity and back_free_capacity:
>
> A. divide it as evenly as possible
> B. maximize front_free_capacity
> C. maximize back_free_capacity
>
> Currently, devector does (C) and provide means for the user to choose the
> capacity at both ends. What would you prefer instead?


I don't have a better alternative.  I do find the current choice clunky.


> I don't understand why should_shrink() is part of GrowthPolicy.  If I'm
>>> growing the container, why am I worried about shrinking it?
>>>
>>>
>> Because next time you can avoid growing it.
>>
>
> To add to that: shrinking involves allocating a new buffer and copying or
> moving elements to the new buffer, which may be very expensive.
>
> Say you feel this is not worth doing if the amount of reclaimed memory is
> less than 5 percent (i.e. the vector is at +95% capacity).
>

Ah, thanks.  That makes sense.

Zach

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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Hi Degski,

Thanks for your time.

> Playing around with devector, I find the default growth strategy (x4) >
> rather (too) agressive. It also has some in my view un-intended effects.
> Starting from let's say initial front and back capacities of each 4, now
> adding 5 elements in front and 5 elements in the back (so 10), now gives me
> a devector with capacity 128 (wow, why bothr with SBO at all).

There is room for improvement here.

https://github.com/facebook/folly/blob/master/folly/docs/FBVector.md

recommends 1.5. But if I used it as a local buffer, a bigger value might
be warranted (so at least the user can choose).

> Then looking how the free_capacity is split between front and back we get
> 95 and 23 (or the other way around, depending on whether we first push_back
> or first push_front, even when front- and back-pushes are interleaved). As
> we are multiplying by 4, this will become more and more skewed.

Yeah, but would it not become more and more skewed no matter what number
 >1 we multiply with?

Is there any way to avoid that? Is it desirable to avoid that? The
analog for vector is that it has (with a growth factor of 2) on average
25% unused objects. As the container grows, so does the wasted space in
absolute terms.

> Some bikeshedding (tm). I don't like any of the names much. The batch_deque
> *is* a deque, it should be called that way. devector is a hybrid
> vector/deque, I think veque would capture that. Then as to double_ended, I
> think it's too long and describes badly what we are talking about. I
> haven't got any (much) better proposal, but was thinking of Boost.Que, nice
> and short.
>
> i.e. boost::que::veque and boost::que::deque.

I think it's great to do some bikeshedding. Keep doing 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] The review of Boost.DoubleEnded starts today: September 21 - September 30

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
> 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.

This week is the CppCon conference, and many C++ minded individuals that may
have wanted to participate to the review (including myself) will be
absolutely
incapable of doing so. In fact, they may even miss the fact that a review is
ongoing (such as what happened to me until now).

I would like to request that the review be extended for some time after the
conference ends to give others the chance of participating if they want to.

Does that seem reasonable?

Thanks,
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] The review of Boost.DoubleEnded starts today: September 21 - September 30

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

________________________________
From: Benedek Thaler [[hidden email]]
Sent: 25 September 2017 22:48
To: [hidden email]
Cc: [hidden email]; Thorsten Ottosen; Fletcher, John P
Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30



On Sep 25, 2017 11:26 PM, "Fletcher, John P via Boost" <[hidden email]<mailto:[hidden email]>> wrote:


When I run the example I get only one line of output:

Reversed lines:

This does not tell me much at all and I have not found out what it is expected to do.  It seems to read a file, which is not supplied or described.  I have not found anything in the documentation.

> Hi,
> It reads the standard input. Try piping in some lines.

> HTH,
> Benedek

Benedek

Would you give me an example of what you mean?  I have tried various things none of which make any sense.  You are supposed to supply clear information.  A review is not supposed to be a guessing game.

It would help if the examples had clear information about expected outcomes.

John


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

Re: [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

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

________________________________________
From: Thorsten Ottosen [[hidden email]]
Sent: 26 September 2017 08:28
To: Fletcher, John P
Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30

>> Hi Fletcher,
>>
>> On another topic, I have not seen in the documentation any discussion of models for what is going on.  I am aware of Chris Okasaki's book "Purely Function Data Structures" (1998) and a lot of subsequent literature.  Does this work relate at all to previous work?
>I'm not familiar with that book. You should think of standard C++
>containers like std::vector and std::deque which models a sequence concept:

 I should have given a reference.  Here is one.

http://okasaki.blogspot.co.uk/2008/02/ten-years-of-purely-functional-data.html 

This is the authors comments on 10 years from publication.

If you put the title into google you will get lots of information.

My point is that there is a strong theoretical basis in this area and one of the issues for me is how far this has been taken into account in this new work.

I was not until recently familiar with the work.  It has helped me a lot understand the underlying problems in this area and I want to know whether the author of the library has looked at it.  There is nothing in the documentation that I have seen about the wider issues.

John Fletcher


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