On Mon, Sep 25, 2017 at 12:17 PM, Thorsten Ottosen via Boost < boost@lists.boost.org> 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).

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

On Tue, Sep 26, 2017 at 10:59 AM, Thorsten Ottosen via Boost < boost@lists.boost.org> 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 < boost@lists.boost.org> 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).

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

On 26. Sep 2017, at 03:39, Zach Laine via Boost wrote:

On Mon, Sep 25, 2017 at 12:17 PM, Thorsten Ottosen via Boost < boost@lists.boost.org mailto:boost@lists.boost.org> 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

Den 27-09-2017 kl. 04:18 skrev Soul Studios via Boost:

...

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.

Visual studio's implementation is almost brokenly slow compared to others.

I totally agree.

...

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

Not true. Libstdc++'s implementation iterates almost as fast as vector except for large structs (due to a fixed memory-based block size). http://www.plflib.org/benchmarks_haswell_gcc.htm#rawperformance

Nice work, btw. Note I said "can" not "must". FWIW, batch_deque also uses a compile-time block size. kind regards Thorsten

On Mon, Sep 25, 2017 at 2:52 AM, Zach Laine via Boost

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#idp4037601... Thanks, Benedek

On Tue, Sep 26, 2017 at 11:32 AM, Thorsten Ottosen via Boost < boost@lists.boost.org> 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 < boost@lists.boost.org

...

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

________________________________ From: Benedek Thaler [thalerbenedek@gmail.com] Sent: 25 September 2017 22:48 To: boost@lists.boost.org Cc: boost-announce@lists.boost.org; 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" mailto:boost@lists.boost.org> 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

On Tue, Sep 26, 2017 at 1:14 PM, Thorsten Ottosen via Boost wrote:

The missing _emplace functions is surely an oversight.

Fair enough.

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?

The problem is that the new hard/unsafe parts isn't justified by any hard performance numbers. We are talking about adding functions that make it more likely for users to do things wrong, possibly in a manner that's completely well-defined but massively inefficient (inappropriate reserves). The benefit from it is skipping a branch that the predictor probably gets right most of the time. On its face, this doesn't appear to me to be a substantial enough benefit to justify the cost. It is of course quite possible that I'm underestimating the benefit, but if so I'd like to see actual numbers proving it.

...

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.

The same design used in boost::container. You take a tag type that indicates that the elements should be default-initialized rather than value-initialized. For trivially default constructible types, this means that no initialization is actually performed. Of course if the type isn't trivially default constructible, it would still call the constructor. The question is: how often do such cases actually arise?

...

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?

Anything that reallocates, really. Basically, unconditionally move during reallocation instead of move_if_noexcept, and if the move throws you only get basic exception safety.

...

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.

Indeed. I've seen 1.5. I've seen 2. 4, on the other hand, I haven't seen before, so I'm curious if there's anything behind that choice.

On Wed, Sep 27, 2017 at 2:20 PM, Thorsten Ottosen via Boost wrote:

...

...

...

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?

Anything that reallocates, really. Basically, unconditionally move during reallocation instead of move_if_noexcept, and if the move throws you only get basic exception safety.

Does Boost.Container do this? Would it not make generic code harder to reason about?

I haven't checked, but I'd be surprised if boost::container::vector offers less exception safety than std::vector, even if the stronger exception safety is arguably a design error that had to be retained for backward compatibility. There is, however, no standard container named "devector", so there might be some room for change there. Anyway, my main point, which I perhaps didn't express too well, is that "introduce unsafe functions to save a branch" and "have no way to avoid expensive copies if the move constructor can potentially throw" are inconsistent.

On 27/09/2017 20:20, Thorsten Ottosen via Boost wrote:

...

Anything that reallocates, really. Basically, unconditionally move during reallocation instead of move_if_noexcept, and if the move throws you only get basic exception safety.

Does Boost.Container do this? Would it not make generic code harder to reason about?

Yes. See: http://www.boost.org/doc/libs/1_65_1/doc/html/container/Cpp11_conformance.ht... Best, Ion

...

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.

That has pretty much been refuted by third party testing as far as I'm aware. In my personal experience I found no performance difference between fbvector and libstc++'s.

Actually, no need to look at something like FBVector, the VS2017 STL std::vector implementation uses the following growth policy:

capacity += capacity / 2;

I'm not sure how that used to be, on the MSDN blog (not that long ago) it was noted that an overhaul of std::vector was implemented. I think I remember it used to duplicate before (but cannot verify that anymore).

It used to be closer to 1.5 - I'm glad they changed it. https://stackoverflow.com/questions/12271017/initial-capacity-of-vector-in-c...

...

That has pretty much been refuted by third party testing as far as I'm aware. In my personal experience I found no performance difference between fbvector and libstc++'s.

Any source on that?

The first, yes: this is worth reading through, including the links: https://www.reddit.com/r/cpp/comments/2ezwee/stdvector_optimization_by_faceb... The second, just early testing on my part. I didn't publish any of it. But certainly there was no significant difference in my testing.

...

...

Actually, no need to look at something like FBVector, the VS2017 STL std::vector implementation uses the following growth policy:

capacity += capacity / 2;

I'm not sure how that used to be, on the MSDN blog (not that long ago) it was noted that an overhaul of std::vector was implemented. I think I remember it used to duplicate before (but cannot verify that anymore).

It used to be closer to 1.5 - I'm glad they changed it.

Seems like its still 1.5 to me.

Sorry, I misread degski's message-

On Thu, Sep 28, 2017 at 10:12 AM, degski via Boost wrote:

This:

boost::double_ended::devectorstd::uint64_t v ( 16, 123 );

does not work on both Clang/LLVM-6.0 and VS2017 on Windows. One has to explicitely cast 123 to std::uint64_t, i.e.

boost::double_ended::devectorstd::uint64_t v ( 16, ( std::uint64_t ) 123 );

does work.

Noted, thanks. Benedek

On Tue, Sep 26, 2017 at 5:06 PM, Benedek Thaler via Boost wrote:

On Tue, Sep 26, 2017 at 2:43 AM, Tim Song via Boost wrote:

...

[snip]

...

typedef pointer iterator; typedef const_pointer const_iterator;

Why are pointers being used as iterator types directly?

To keep simple things simple. What's wrong with pointers?

Using pointers directly makes it easier to write buggy code. A custom iterator type, even if just a thin wrapper, provides more type safety.

...

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

`pointer` is defined by allocator_traits. Couldn't that be a fancy pointer, if the Allocator defines it so?

allocate/deallocate use (possibly fancy) `pointer`. construct/destroy always use raw pointers, never fancy pointers.

Den 27-09-2017 kl. 01:08 skrev Daniel James via Boost:

On 26 September 2017 at 22:20, Tim Song via Boost wrote:

...

On Tue, Sep 26, 2017 at 5:06 PM, Benedek Thaler via Boost wrote:

...

On Tue, Sep 26, 2017 at 2:43 AM, Tim Song via Boost wrote:;

...

Why are pointers being used as iterator types directly?

To keep simple things simple. What's wrong with pointers?

Using pointers directly makes it easier to write buggy code. A custom iterator type, even if just a thin wrapper, provides more type safety.

That's a pretty slim advantage, I'd value simplicity more. It's very much a judgement call.

I think Boost.Container uses a simple wrapper around T*, but at the same time has a macro that can be defined to turn it into pointers again. I would expect that some code does things differently if they are passed two pointers instead of two iterators. kind regards Thorsten

On 26 September 2017 at 09:33, degski 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

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

AMDG On 09/26/2017 12:33 AM, degski via Boost wrote:

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.

That doesn't make any sense to me. deque = double ended queue devector = double ended vector veque = vector queue? In Christ, Steven Watanabe

On 28 September 2017 at 00:06, Ion Gaztañaga via Boost < boost@lists.boost.org> wrote:

The theoretical limit value for the growth factor to be able to reuse previously allocated memory is roughly 1.61.

That figure smells suspiciously like the Golden Ratio https://en.wikipedia.org/wiki/Golden_ratio: 1.618033988749895 (unsurprisingly even, maybe, if one considers what the GR entails). degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798

On Sep 28, 2017, at 4:49 AM, Thorsten Ottosen via Boost wrote:

Den 27-09-2017 kl. 23:06 skrev Ion Gaztañaga via Boost:

...

On 26/09/2017 22:03, Joaquin M López Muñoz via Boost wrote:

...

4. Same goes for the growing policy. Not even boost::container::vector features a growing policy, which seems an indication that this is not a heavily demanded customization point. True. But is on my todo list I was recently trying to add customization options to Boost.Container containers (I need to offer something different to my fans that the standard containers can't offer ;-).

We do need some general agreement about what a boost library can do and not do. There is a large difference between saying "I'm not going to use this" or "I don't see the benefit" and saying "I want to prohibit legitimate use cases for other people".

...

Usually the choice is usually between a factor of 2 and 1.5. The theoretical limit value for the growth factor to be able to reuse previously allocated memory is roughly 1.61. Howard Hinnant shared with my a nice paper about this more than ten years ago showing how to grow using a factor of 1.6 and the math behind this. I just reviewed that brief paper recently, and since it's not longer online, Howard kindly has given me permission to share it with the Boost community.

Thanks for sharing this.

There is another argument for 1.5 and that is that the casual users ends up with only about 16% wasted space on average compared to 25%.

Reading through the argument, there are a few things I don't get. Is seems that the proof sort of assumes one container instance. And will the heap manager actually coalesce anything?

Good questions, and to put this into perspective: When I wrote the CodeWarrior vector I used this argument to use a growth factor of 1.6. But several years later, when I wrote libc++, I went back to 2. Howard

Den 28-09-2017 kl. 21:35 skrev Ion Gaztañaga via Boost:

On 28/09/2017 10:49, Thorsten Ottosen via Boost wrote:

...

Reading through the argument, there are a few things I don't get. Is seems that the proof sort of assumes one container instance. And will the heap manager actually coalesce anything?

DLMalloc coalesces. Several heap managers coalesce when the allocation is bigger than a limit. Boost.Interprocess allocators coalesce.

I'm not sure what jemalloc and similar allocators do.

Yes, there seem to be many takes on this. Stuff like http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n3536.html seem to suggest that a larger chunk is independent of smaller chunks. The argument says we are looking for \sum_{j=o}^{i-1} S[j] >= S[i+1] so the coalescing is supposed to happen between the i'th and (i+1)'th allocation. Now, if there are two vectors in play, or other data structures that uses memory, surely those leftovers can be coalesced into something that satisfy a larger growth factor. kind regards -Thorsten

On 28 September 2017 at 14:31, Paul A. Bristow via Boost < boost@lists.boost.org> wrote:

Boost has the floating-point constant phi

http://www.boost.org/doc/libs/1_65_1/libs/math/doc/html/ math_toolkit/constants.html

Expressed as a ratio: // The Golden Ratio, the ratio of the 2 largest consecutive Fibonacci numbers // representable in std::intmax_t... #ifdef _WIN64 using golden_ratio = std::ratio<7540113804746346429, 4660046610375530309>; #else using golden_ratio = std::ratio<1836311903, 1134903170>; #endif Which makes the definition of the Golden Ratio independent of the underlying (system defined) representation of reals, but the best possible. degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798

On 9 October 2017 at 12:58, Paul A. Bristow via Boost

wrote:

Boost.Math constants also all provide the best possible representation of reals,

You don't like that definition? Cool, no problem, ignore it... Why *not* use boost if you can? degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798

On 29/09/2017 09:17, Bjorn Reese via Boost wrote:

On 09/27/2017 11:06 PM, Ion Gaztañaga via Boost wrote:

...

Usually the choice is usually between a factor of 2 and 1.5. The theoretical limit value for the growth factor to be able to reuse previously allocated memory is roughly 1.61. Howard Hinnant shared with

There are several factors in play, so we may need a slightly more sophisticated growth policy.

Me personally, my biggest complaint with the STL containers is that you don't get direct control over when they call malloc or free. My great hope remains that for STL2 we get new STL2 containers which never reallocate without being asked to by the programmer. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

Me personally, my biggest complaint with the STL containers is that you don't get direct control over when they call malloc or free.

Which standard library containers are you concerned about doing allocations beyond those allocations where they use the given Allocator instance and invoke its allocate() member function?

My biggest peeve is std::vector. I absolutely hate that it can ever allocate new storage on its own. In my preferred STL2 design, a vector would only ever occupy its capacity which is given to it at the time of construction. It cannot change its capacity at all. You the programmer can, of course, create a new vector of larger capacity and have all the contents from the old vector moved/copied into the new vector. All the remaining STL2 containers are then built in layers atop this STL2 vector, muxed in with Ranges and Views. BTW STL1 containers don't go away. They're still available for when you don't care and just need something quick and dirty. And for legacy code of course. You can see some of my STL2 container ideas in AFIO v2 where memory mapped files are "malloc" and `afio::algorithm::mapped_view<T>` is a typed view of some mapped file storage. I haven't implemented `afio::algorithm::vector<T>` yet, but it's on the plan. One of the super cool things with this design is constant time vector extensions when the type has a trivial move and copy constructor because we simply map the underlying file storage to a new address. No memory copying needed. The other super cool thing is sparse storage, so you can allocate trillion element vectors without issue on any system. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/

AMDG On 09/26/2017 02:03 PM, Joaquin M López Muñoz via Boost wrote:

Also, the reference statement that insertion is "linear in half the size of *this [...]" is currently not true (when the favored side is full insertion takes longer than that).

Technically it is true, since "linear in half the size" is equivalent to "linear in the size."

I'd rather drop this optimization and document that shifting always happen to the direction where the least operations are needed.

In Christ, Steven Watanabe

On 27 September 2017 at 00:43, Joaquin M López Muñoz via Boost < boost@lists.boost.org> wrote:

... but libraries, in my opinion, should start with a minimal and well grounded design and add more stuff as demand proves their need.

This sounds good in theory, but doesn't work like that in practice. Libraries tend to get "stuck" in their inital state. As an example of this: I recently proposed to add variadic move construction for nodes to boost::pool (a trivial change). And even though this has obvious advantages (and would get rid for C++11 capable compilers of the use of M4 to generate the necessary code), this was received with: file a PR, including tests (?) and change to documentation. Enough to put me off, so I just changed it locally. Another example is the VS std::deque, where chunk size is the greater of 16 bytes and the size of one object and makes std::deque have std::list performance for anything other than chars, shorts and ints (luckily there's boost!!! It's the greater of 512 bytes and the size of one object b.t.w.). 4. Same goes for the growing policy. Not even boost::container::vector

features a growing policy, which seems an indication that this is not a heavily demanded customization point.

The fact that it's not there, does not proof anything and might be related to the point I raised in the above. This implementation of a vector https://github.com/aguinet/pector, which shares ideas (and has some other ones) with devector has a growth policy (although not as flexible and neat as devector). That implementation also provides, next to a multiplicative growth strategy, an additive growth strategy. The current devector design makes implementing this a trivial exercise.

5. Defining size_type as unsigned int for the sake of class size seems to me overzealous.

I dis-agree, the above pt::pector goes further in this respect and (can) reduce(s) it's footprint to 16 bytes (64 bits app.) if required (at the cost of a small performance penalty). The use case I referred to above is a DAG with adjacency vectors! i.e. every node (many in my use case) has 2 vectors (in and out), shaving of 8 bytes makes a difference (in improved locality and overall memory use). Why not make this decision a template parameter (as in pt::pector) and be done with it? degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798

On 27 September 2017 at 15:42, Edward Diener via Boost < boost@lists.boost.org> wrote:

The pool library has no official maintainer so it had been added to the CMT libraries. You would probably have gotten more response to your suggestion if pool had an official maintainer.

It's un-fortunately a sad state of affairs. What bugs me the most is (nobody here to blame), that there are (on this list) on a regular basis so many people stating they would like to "contribute" to Boost... and then, there's silence.

I do not think that is much proof that libraries tend to get "stuck" in their initial state, although it happens some of the time.

No proof intended, just examples... For some reason, lack of maintainers, backward (binary) compatibility, things don't progress... And one ends up, like you suggested below, doing ones' own thing.

C++ inheritance often means that you can add functionality to a library via another library or your own one-off class(es).

Reason number one is simple, it's this rule: "Thou shall not inherit from class xxx publicly in the absence of a virtual destructor as it effectively prevents you from polymorphic use of descendants.", and this rule is repeated over and over again. boost::pool does not have a virtual destructor (trivial change, I agree, but that was what I was doing in the first place!).

But I agree that the initial notion that a library should have a well grounded design, although "minimal" is highly subjective, is a good one.

Getting back on the thread we are actually discussing, it seems to me that there is a discrepancy between what Benedek proposes and how this library is being reviewed (by some), that's the source of the subjectiveness you are referring to, IMO. The idea (the way I see it) is not necessarilly that the library will/or should be minimal and do the right thing all the time, but that it should provide maximum control and potentially (when well used) optimal performance. We are looking at control C-style. Yes, one can "shoot ones' leg of". For me, that's understood from the outset. It's most probably not a candidate for standardization, but, on the other hand, might become quite popular with game- or HFT-app-developpers. degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798

I dis-agree, the above pt::pector goes further in this respect and (can) reduce(s) it's footprint to 16 bytes (64 bits app.) if required (at the cost of a small performance penalty). The use case I referred to above is a DAG with adjacency vectors! i.e. every node (many in my use case) has 2 vectors (in and out), shaving of 8 bytes makes a difference (in improved locality and overall memory use).

Why not make this decision a template parameter (as in pt::pector) and be done with it?

There's a couple of problems - main one is that two objects from the same template and with the same T cannot interact (=, ==, swap etc) easily if the size_type is a template parameter. The second is that unless the type being declared in template parameter is being used a -lot-, the reduction in performance cost and memory usage is very low. I think a better alternative is to make the default case as generic as possible, then make it easy for people to modify the code if they have specific cases that require or benefit from doing so- I use a template parameter for the skipfield type in colony, but that's used as much as T so it makes sense.

Den 26-09-2017 kl. 23:43 skrev Joaquin M López Muñoz via Boost: Thanks for the thorough review.

3. The question arises of whether segment access can gain us some speed. I've written a small test to measure the performance of a plain std::for_each loop over a batch_deque vs. an equivalent sequence of segment-level loops (attached, batch_deque_for_each.cpp), and this is what I got for Visual C++ 2015 32-bit (x86) release mode in a Windows 7 64-bit box with an Intel Core i5-2520M @2.5GHz:

  [](int x){return x;}   segment size: 32   n       plain   segmented   10E3    25.5472 23.6305   10E4    24.5778 23.6907   10E5    24.5821 22.8076   10E6    25.5007 23.1037   10E7    27.1452 24.0339   segment size: 512   n       plain   segmented   10E3    23.8384 23.6638   10E4    23.0284 23.8705   10E5    22.8449 22.8187   10E6    23.8485 23.7454   10E7    24.1711 23.5404

  [](int x){return x%4?x:-x;}   segment size: 32   n       plain   segmented   10E3    33.9795 23.6662   10E4    32.4817 24.023   10E5    32.8731 23.3803   10E6    33.5396 22.9298   10E7    33.1034 23.0206   segment size: 512   n       plain   segmented   10E3    25.0623 23.3205   10E4    25.1048 23.5812   10E5    25.3343 21.7686   10E6    25.6961 22.4639   10E7    25.8664 22.9964

For 32-bit release mode on windows 7 64 bit with intel i7-2700K: [](int x){return x;} segment size: 32 n plain segmented 10E3 21.4589 21.8351 10E4 19.9545 20.5133 10E5 19.4889 20.6197 10E6 19.2552 19.6976 10E7 19.2919 19.5425 segment size: 512 n plain segmented 10E3 20.2503 20.6372 10E4 19.0234 19.3367 10E5 18.5394 18.6171 10E6 18.555 18.5816 10E7 19.0918 19.1833 [](int x){return x%4?x:-x;} segment size: 32 n plain segmented 10E3 28.743 19.7501 10E4 26.8371 19.0719 10E5 27.0304 18.7624 10E6 26.9561 18.2357 10E7 27.2985 18.6425 segment size: 512 n plain segmented 10E3 22.1073 20.0347 10E4 20.7825 19.5639 10E5 20.6122 18.0773 10E6 20.6039 18.4895 10E7 21.7964 19.1822 So basically the same as your results. The case for segment size 32 and a non-trivial lambda does show some speedup, doesn't it? For 64-bit release mode on windows 7 64 bit with intel i7-2700K: [](int x){return x;} segment size: 32 n plain segmented 10E3 34.748 21.1357 10E4 32.8879 19.8592 10E5 32.6779 18.955 10E6 32.6255 19.3307 10E7 33.2282 19.3158 segment size: 512 n plain segmented 10E3 28.442 20.0265 10E4 26.5783 18.5851 10E5 26.4857 18.6023 10E6 26.4884 18.6571 10E7 27.0076 19.1338 [](int x){return x%4?x:-x;} segment size: 32 n plain segmented 10E3 43.0149 18.8431 10E4 42.2736 18.5071 10E5 42.4035 18.7087 10E6 42.1964 18.3355 10E7 42.8113 18.7723 segment size: 512 n plain segmented 10E3 40.3695 19.0028 10E4 38.5371 18.2029 10E5 38.2163 17.85 10E6 38.2952 17.9199 10E7 38.7489 18.6342 I don't know why a 64-bit program would be slower, but there seems to be a larger difference here. I'm wondering how the results would be on 32/64 bit ARM. Also, I do expect a benchmark of serialization to be much better. I don't think one do that optimally without access to the segments. Benedek, could you please make a test of the performance of serialization for both devector/batch_deque vs boost::vector/boost::deque (release mode, full speed optimization), perhaps using the same measuring technique as employed by Joaquin. And then post results and code so people can run it on their favorite system. You should use types char, int, and something bigger, e.g. string or array. kind regards Thorsten

Hi, Some more points to consider. I tried comparing push_back/unsafe_push_back a little. I don't see any performance speedup on my system if the loop body is just the push_back. If I make the loop a little more complicated than just a push_back, I get some differences: 32 bit: boost::vector::push_back vs devector::unsafe_push_back 10E3 29.0508 24.8578 10E4 26.9987 22.7853 10E5 26.9468 22.3659 10E6 26.9766 22.3562 10E7 27.1064 22.5215 64 bit: 10E3 28.6106 24.2881 10E4 27.9322 23.6613 10E5 28.0182 23.3318 10E6 28.0493 23.3803 10E7 28.1458 23.5394 32 bit: boost::deque::push_back vs batch_deque::unsafe_push_back 10E3 34.803 45.6774 10E4 36.0686 46.3888 10E5 36.7773 48.6228 10E6 40.7754 49.6144 10E7 43.1134 49.1949 64 bit: 10E3 33.5997 30.0433 10E4 35.5992 32.8985 10E5 34.4685 48.9641 10E6 40.7974 48.6893 10E7 43.2836 48.9001 I'm not 100% sure why batch_deque is so much slower, but looking a little at the assembler, it seems that going from an iterator to a pointer may be expensive because the batch_deque::iterator uses a segment pointer and an index. (normal push_back in batch_deque therefore also appears somewhat slower than in boost::deque). kind regards Thorsten

Den 03-10-2017 kl. 00:02 skrev Benedek Thaler via Boost:

On Mon, Oct 2, 2017 at 7:30 PM, Thorsten Ottosen wrote:

...

Hi,

Some more points to consider. I tried comparing push_back/unsafe_push_back a little. I don't see any performance speedup on my system if the loop body is just the push_back. If I make the loop a little more complicated than just a push_back, I get some differences:

Hi,

My concern with the above benchmark, is that it does not compare the same thing: it calls reserve here but not there (std::deque and boost::container::deque have no reserve).

Well, true. But since the unsafe_push_back on batch_deque needs to be preceded by a reserve, it would not be fair to exclude that.

I tried a similar test, comparing devector/vector/container.vector unsafe_push_back/push_back, using google benchmark. See the code attached. This is how I run it:

what is container.vector? Also, the file you attached uses batch_deque and std::vector, you test mentions 3 types .. kind regards Thorsten

Den 03-10-2017 kl. 00:02 skrev Benedek Thaler via Boost:

Re-run results in very similar results. I think the numbers are convincing in favor of devector::unsafe_push_back.

There is not a huge difference between devector and vector. If I take my test where I try to confuse the branch predictor and alter just 1 flag: "favor small code" instead of "favor fast code", then I get: 32 bit: 10E3 63.8728 42.2238 10E4 62.2564 40.5588 10E5 62.0731 40.2956 10E6 62.2532 40.2451 10E7 62.3553 43.5931 64 bit: 10E3 29.2422 24.6654 10E4 28.3354 24.246 10E5 28.2262 23.7662 10E6 28.2777 23.8788 10E7 28.3777 23.8641 I think that is a good example of how the compiler can play tricks on you. And this is major reason we should always strive after providing abstractions with zero overhead. kind regards Thorsten

Hi Benedek,

Please find the benchmark code and results attached. It compares serialization of devector/batch_deque/std::vector/std::deque. (I couldn't find a ready serializer for Boost.Container). The comparison is not exactly fair, because it seems boost/serialization/vector.hpp also adds version information. Measurement was done as above.

Brief preview of the full set of attached results:

I was a bit surprised that std::vector performed almost as good as devector. Then I realized that you are testing serialization "save" and not serialization "load". Given that, I'm now surprised that devector/batch_deque is faster than std::vector for e.g. std::array! I did not expect that. However, the "load" test should be even more interesting as that is the one that involves potential double initialization. Could you post those numbers too? Thanks in advance Thorsten

On 4 October 2017 at 23:48, Benedek Thaler via Boost wrote:

As expected, both devector and batch_deque highly outperforms std::vector and queue in deserialization.

This sounds (to me) counterintuitive. Why is this the case? degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798

Den 05-10-2017 kl. 10:20 skrev Thorsten Ottosen via Boost:

Den 05-10-2017 kl. 04:19 skrev degski via Boost:

...

On 4 October 2017 at 23:48, Benedek Thaler via Boost wrote:

...

As expected, both devector and batch_deque highly outperforms std::vector and queue in deserialization.

This sounds (to me) counterintuitive. Why is this the case?

Because they can avoid double initialization for some types. When using std::vector, you have to either

A. reserve + load item to local object + push_back B. resize + delegate to bulk operation in Boost.Serialization

The bulk operation is to prefer, but then requires redundant initialization in resize.

I gave this a little thought, and must admit that the numbers cannot be explained by double initialization alone. Looking at the serialization code for DoubleEnded, it think may not be quite in line with the Boost.Serialization approach. For example, it seems to be me that it is not working correctly with e.g. xml archives. Basically, the implementation for trivial types avoids all the Boost.Serialization machinery by calling load_binary/save_binary directly. Now, what I don't understand is how that machinery can be so costly for the binary archive case to get the huge difference we see with std::vector. This is a real mystery (In the same way the save test got much slower when the type became array). Secondly, I think we can see the current numbers as a best case of what is possible with the extra functionality provided by DoubleEnded. There are other serialization libs out there, and they should be able to benefit even if there is no way to specialize for the binary case in Boost.Serialization. kind regards Thorsten

Den 05-10-2017 kl. 18:03 skrev degski via Boost:

On 5 October 2017 at 18:37, Thorsten Ottosen via Boost < boost@lists.boost.org> wrote:

...

Secondly, I think we can see the current numbers as a best case of what is possible with the extra functionality provided by DoubleEnded. There are other serialization libs out there, and they should be able to benefit even if there is no way to specialize for the binary case in Boost.Serialization.

I added devector to cereal, the file is attached and should be placed in the types sub-dir (of cereal). It's just a copy of the std::vector code, with the std::vector<bool> specialisation taken out. Not tested.

Cute. But would one not use std::is_trivially_copyable instead of std::is_arithmetic? And instead of resize, should you not call the version that avoids double initialization? kind regards Thorsten

On Thu, Oct 5, 2017 at 7:25 PM, degski via Boost wrote:

I'll tell the wife!

Has anyone done a search on Google for "DoubleEnded?" To see if there's another library with the same name. Thanks

Den 26-09-2017 kl. 23:43 skrev Joaquin M López Muñoz via Boost:

El 21/09/2017 a las 19:38, Thorsten Ottosen via Boost escribió:

...

Dear users and members of Boost,

[snip]

and mostly utility-level. We already have a bestiary of containers in Boost, namely Boost.Container, so I think both devector and batch_deque are better served if proposed as components of this latter libray. Code in boost::double_ended::detail can go to / merge into boost::container[::detail] --for instance, boost::double_ended::detail::allocator_traits seems to be redundant with boost::containter::allocator_traits.

This makes sense, but it does require that the author of Boost.Container is willing to entertain that idea, doesn't it?

REVIEW FOR DEVECTOR

and violates the "don't pay for what you don't use" principle. I'd remove it.

How does it violate that?

7. Modulo the points discussed above, the interface of devector follows closely that of std::vector (with the obvious additions, e.g. [push|pop_emplace]_front), which is very good. The only interface decisions I'm not fully convinced about is capacity/ resize/reserve/shrink_to_fit without "front" or "back" qualification:

What about generic code that can be used with either a vector or devector?

  - capacity() seems to be (from what I can infer reading the docs only) the sum of   front capacity and back capacity. I can't find any sensible use of this info, and, besides,   the careless reader could assume capacity() works as std::vector::capacity(), which   raises usability concerns. My suggestion is to remove this. FWIW, we had a similar   discussion about capacity() in Boost.PolyCollection, and that member function finally   was dropped.

The capacity from Boost.PolyCollection was quite another beast. Here capacity is just like vector's capacity(), namely the sice of the contiguous chunk of memory.

  - front_free_capacity/back_free_capacity could be more aptly named   front_capacity/back_capacity.

But unlike capacity() in vector, these actually tells you how many push_back/push_front you can do without reallocation. There is no definition of "back capacity" because there is no "middle".

  - reserve as an alias to reserve_back has usability  problems as discussed with capacity.

Again, what about generic code?

  I'd remove them.   - For symmetry, shrink_to_fit could be complemented with [front|back]_shrink_to_fit

Is back_shrink_to_fit then an alias for shink_to_fit or does it actually consider both ends?

be documented officially. I'm assuming that erasure behaves analogously (i.e. space is given back to the side that's closer to the erasure point) --in particular, inserting an element and erasing it immediately after should return front and back capacities to their original values.

Anything else would be very inefficient.

REVIEW FOR BATCH_DEQUE

d.segment_[begin|end](), which allows us to use a range for in:

  for(auto segment:d.segments){     for(auto& element:segment){       // do something with element     }   }

This is a good idea IMO.

2. As with devector, why is serialization code is so complicated and does not simply rely on boost::serialization::stl::collection_load_impl|save_collection?

Let's wait for the performance test.

3. Tests look good.

4. Postconditions on front and back capacity are not documented.

You mean front_free_capacity etc? What condition did you have in mind? The funcions are const. kind regards Thorsten

El 27/09/2017 a las 21:27, Thorsten Ottosen via Boost escribió:

Den 26-09-2017 kl. 23:43 skrev Joaquin M López Muñoz via Boost:

...

REVIEW FOR DEVECTOR

...

and violates the "don't pay for what you don't use" principle. I'd remove it.

How does it violate that?

All the _storage handling is done even if there's the small buffer is 0.

...

7. Modulo the points discussed above, the interface of devector follows closely that of std::vector (with the obvious additions, e.g. [push|pop_emplace]_front), which is very good. The only interface decisions I'm not fully convinced about is capacity/ resize/reserve/shrink_to_fit without "front" or "back" qualification:

What about generic code that can be used with either a vector or devector?

Problem is: suppose d.size()==5, d.capacity()==10,d.back_free_capacity()==2; doing   for(int i=0;i<5;++i)d.push_back(i) will reallocate, unlike std::vector.

[...]

...

   - front_free_capacity/back_free_capacity could be more aptly named    front_capacity/back_capacity.

But unlike capacity() in vector, these actually tells you how many push_back/push_front you can do without reallocation. There is no definition of "back capacity" because there is no "middle".

You're right, my bad. the _free_ infix is very adequate.

...

   - reserve as an alias to reserve_back has usability  problems as discussed with capacity.

Again, what about generic code?

Similar consistency problem with std::vector. d.size()==5, d.capacity()==10, d.back_free_capacity()==2:   d.reserve(d.capacity()) reallocates, whereas it is a no-op for std::vector.

...

   I'd remove them.    - For symmetry, shrink_to_fit could be complemented with [front|back]_shrink_to_fit

Is back_shrink_to_fit then an alias for shink_to_fit or does it actually consider both ends?

The semantics that seems to me the cleanest is   * shrink_to_fit --> front_free_capacity()==0, back_free_capacity()==0   * front_shrink_to_fit --> front_free_capacity()==0, back_free_capacity() untouched   * back_shrink_to_fit --> front_free_capacity() untouched, back_free_capacity()==0 Strictly speaking, standard says shrink_to_fit is an *indication*, so implement all three as no-ops would comply :-)

[...]

...

3. Tests look good.

4. Postconditions on front and back capacity are not documented.

You mean front_free_capacity etc? What condition did you have in mind? The funcions are const.

Sorry, I meant there is no indication of what happens to [front|back]_free_capacity after insertions and erasures. Best Joaquín M López Muñoz

Den 28-09-2017 kl. 15:02 skrev Joaquin M López Muñoz via Boost:

El 27/09/2017 a las 21:27, Thorsten Ottosen via Boost escribió:

...

Den 26-09-2017 kl. 23:43 skrev Joaquin M López Muñoz via Boost:

...

REVIEW FOR DEVECTOR

...

and violates the "don't pay for what you don't use" principle. I'd remove it.

How does it violate that?

All the _storage handling is done even if there's the small buffer is 0.

Is that not optimized away?

...

...

7. Modulo the points discussed above, the interface of devector follows closely that of std::vector (with the obvious additions, e.g. [push|pop_emplace]_front), which is very good. The only interface decisions I'm not fully convinced about is capacity/ resize/reserve/shrink_to_fit without "front" or "back" qualification:

What about generic code that can be used with either a vector or devector?

Problem is: suppose d.size()==5, d.capacity()==10,d.back_free_capacity()==2; doing

  for(int i=0;i<5;++i)d.push_back(i)

will reallocate, unlike std::vector.

Sure, but is that really a problem? The same can happen with two vector instances that have different capacity.

...

...

   - reserve as an alias to reserve_back has usability  problems as discussed with capacity.

Again, what about generic code?

Similar consistency problem with std::vector. d.size()==5, d.capacity()==10, d.back_free_capacity()==2:

  d.reserve(d.capacity())

reallocates, whereas it is a no-op for std::vector.

Who writes code like that? :-) Let me try to understand: your problem is that a generic algorithm may exhibit a different allocation sequence depending on what type that it is given? And you are OK with that happening for the same type?

...

[...]

...

3. Tests look good.

4. Postconditions on front and back capacity are not documented.

You mean front_free_capacity etc? What condition did you have in mind? The funcions are const.

Sorry, I meant there is no indication of what happens to [front|back]_free_capacity after insertions and erasures.

You are right, there seems to be missing some postconditions. Also for push_front/push_back. -Thorsten

On 28 September 2017 at 00:07, Benedek Thaler via Boost < boost@lists.boost.org> wrote:

This is to allow further customization points without an additional policy argument. One issue with the approach above: It isn't clear whether 512 is a number of elements or bytes. de::batch_deque> is conceivable tough.

In a different but related application, I considered the underlying allocator (all Windows here), VirtualAlloc https://msdn.microsoft.com/en-us/library/windows/desktop/aa366887(v=vs.85).a.... Requesting memory from the OS (bar my understanding) results in at least one memory page (4096 Kb) to be allocated (or a multiple of that). Not wanting to let any memory go to waste (it's already allocated anyway), I defined a template parameter that stipulates the *minimum* number of objects to be allocated in one segment. One can then calculate the number of pages required to make up that segment and following that, the number of objects that are actually being reserved in that segment. All this can obviously be static constexpr C++14 member functions. Please comment (anyone), as I might be totally deluded (as I'm still not really sure on this) and don't mind being put straight (preferably). degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798

On 28 September 2017 at 11:16, Thorsten Ottosen via Boost < boost@lists.boost.org> wrote:

Also note that the most general thing would be to allow both

de::batch_deque>

and

de::batch_deque>

One can do better and have: de::segment_policy The policy expressed is: "the greater of bytes and count * sizeof ( value_type )". So boost:container::deque would, as implemented now, have: de::segment_policy<512>; VS's would be: de::segment_policy<16>; degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798

On 28 September 2017 at 13:52, Thorsten Ottosen via Boost < boost@lists.boost.org> wrote:

How is that better? Then I have to look up the documentation to understand how big the segment is...

As, in my mind it's all constexpr, we can have member function segment_size () at zero run-time cost, no need to look things up. It (the policy) also simply generalises what's already current practice. degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798

On 28 September 2017 at 15:02, Thorsten Ottosen via Boost < boost@lists.boost.org> wrote:

I'm talking about reading the actual code and having that code being self-documenting wrt. the size of the segment.

Current practice is, that one is agnostic about what's actually happening (the segment size is an implementation detail). The policy should be defaulted to the current practice. If one wants more control, one *does* need to read the docs and understand what things mean, yes, that's true. No free lunch and such. There are thougher nuts to crack learning (modern) C++, I would think. de::batch_deque> does (due to possible alignment issues) still not give you the number of elements and the other way around de::batch_deque> does not give you the segment size, for the same reason. It could be easily integrated in boost::container::deque without breaking anything. degski -- "*Ihre sogenannte Religion wirkt bloß wie ein Opiat reizend, betäubend, Schmerzen aus Schwäche stillend.*" - Novalis 1798

Den 26-09-2017 kl. 23:43 skrev Joaquin M López Muñoz via Boost:

Hi, this is my review of Boost.DoubleEnded.

[snip]

* The main characteristics of both containers are obscured by many "extras" that feel insufficiently justified to me or even detrimental (I'll discuss in more detail below), so my vote is for this fat to be removed prior to acceptance in Boost. I can see much work and love have gone into adding this many niceties, and the author could understansably resist to simplification, but libraries, in my opinion, should start with a minimal and well grounded design and add more stuff as demand proves their need.

Joaquin & others, Since many of the reviewers have had strong opinions about safety and optimizations, I think we need to establish when it makes sense. As an example, consider this made up story. Assume that boost was around in 1992 and then Stepanov came around and wanted his new STL library to be reviewed by Boost. Boost members anno 1992 would immediately see that his vector had an unsafe operator[](size_t) which did not throw, but had a precondition, when violated, would lead to UB. Why would you want to save one branch or generate slightly smaller code? The reviewers then demanded that operator[](size_t) was removed from vector. So ... have we as a community lost the strive for zero penalty, code that doesn't throw, code that may be well-received in constrained environments? If not, could we at least entertain the idea of secondary class: devector<T> devec; ... devector_access<T> devec_access( devec ); // a non-copyable class that stores reference to devector<T> devec_access.nongrowing_push_back( x ); devec_access.uninitialized_resize( k ); // etc So whenever you have to do something a bit out of the ordinary, you do it via devector_access. That type is then in seperate header and documented under advanced usage.? -Thorsten

Hi Ion, Thanks for the detailed review. Some minor comments follow.

The library presents two containers, devector and batch_deque. I find the first one as a relatively simple but interesting vector extension supporting front insertions. In the future it could maybe take advantage of the backwards memory expansion (taking the previously adjacent free memory segment so that new elements could be added to front without moving the rest of the elements) supported by Boost.Interprocess and the Boost.Container’s modified DLMalloc.

Interesting idea.

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

1) From a design point of view, I would prefer not to include the small buffer optimization with the data structure, although reviewing code, it seems many parts are to be optimized.

Everything should be removed by the optimizer; if not, then that section of code needs to be amended with a constant expression.

It's like just having small_vector without having vector, most libraries have two classes for these two use cases. Different classes also ease that a type erasured base class can be defined independent from the static storage size (Boost.Container calls it small_vector_base, LLVM calls it SmallVectorBase)  I think we should have a devector, and add small_devector and static_devector containers if there is demand.

Can they share some of the implementation, or are we left with a double (or triple) implementation effort?

2) Defaulting size_type to unsigned int is arbitrary and against existing practice.

We didn't do that as an arbitrary decision.

According to the usual STL rules, size_type shall come from the allocator, which knows what type can represent the number of elements that can be allocated.

I have no problems with STL rules, but it as you point out, even Boost.Container deviates from several of those.

3) reserve_only_tag: I would rename it as “reserve_only_t” (similarly to std::allocator_arg_t and Boost.Container’s “default_init_t”). The front and back capacity version should be enough as I think  devector should not show preference for back insertion (if a user wants only a back capacity, then it would use a vector and not a devector).

So you would prefer it to divide the buffer in two approximately equal chucks? Or that one has to specify each chunk size explicitly each time (so full symmetry, and the one-sided constructor gone)?

Strictly speaking, capacity constructors are a bit redundant, but the same could be said about default constructing constructors: //it could be implemented as default constructor + resize explicit vector(size_type n, const Allocator & allocator = Allocator());

Yes, just like push_back is redundant when we have insert( iter, x ) :-)

A reserve-only constructor plus an “unsafe” emplacement could make a container similar to an array, where no redundant checks are done when filling the array. But I don’t expect noticeable performance gains with this reserve-only constructor.

No, it is for convenience.

4) unsafe_uninitialized_tag: I don’t like these non-safe constructors, which are  the cases?. With reserve-only constructors + unsafe emplace back a user can achieve nearly the same performance. For POD types (like the socket example mentioned in the documentation), I would suggest something like Boost.Container’s “default_init_t”. Instead of “unsafe_uninitialized_resize_front” I suggest resize_front(size_type, default_init_t)

I didn't know about these default_init_t when we started in 2015. They have a good design IMO. But unfortunately they don't get rid of double initialization for non-trivial types. So maybe both resize_front( size_type, default_init_t ) resize_front( size_type, uninitialized_t ) would be an idea.

5) reserve() / resize(): I think they have no sensible meaning in the container (capacity() could be useful, depending on the reallocation strategy). We should not treat back insertion as the “default” insertion. IMHO the API of devector should be symmetrical.

Symmetry is good, but what about generic code?

8) Regarding "move_if_noexcept", Boost.Container does not use it as it consider a pessimized design for a situation (throwing moves) that will occur nearly never [snip] devector itself would be copied if small_buffer_size is used, etc.).

only when it stores elements with a non-noexcept move though.

9) Minor comment 2: IMHO I think iterators would be better as classes instead of pointers, a user can always use data() to make sure pointers are returned. Many times unwanted overload resolutions can happen if pointers are used, so I prefer the type safety offered by a class-based iterator. It can also offer checked iterators in the future.

I think you have a way to turn these into pointers again in Boost.Container, By defining some preprocessor symbol, right? Having pointers matters when interfacing with other types, because this is the only case where the iterators are seen as contiguous. I would much rather see that in debug mode the iterator type is a class and in release mode it is a pointer compared to having extra preprocessor symbols.

2) Segment_iterators: Raw pointers are stored in segment iterators. That means that those could not be placed in the memory that the allocator allocates, if the allocator does not defined ::pointer as T*.

There is definitely some work relating to allocators and such.

Also, it seems strange that there is not segment_type/segment_info class. The iterator itself has members that return the address and the size of a segment. I think that’s unexpected, the expected segment iterator would return a reference to a class (e.g. segment_type) that represents the segment,

I think we discussed that design at some point. Benedek, can you remember why we went in the other direction?

3) stable_insert: I can’t see the usefulness of this operation. A batch_deque is a sequence, but the user cares about the insertion point but does not care if additional elements are created somewhere? I fail to see a real use case.

A deque is a sequence, sure, but also a container with reference stability. I'm curious, when you use Boost.Intrusive, where do store the elements?

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

emplace_slow_path: The forced temporary creation should be avoided, it is overkill for containers of containers, devector or containers with sentinel nodes. IMHO supporting references to already included elements is a bad feature of std::vector (a corner case supported in single element insertion, ignored for ranges, etc.) Boost.Container chose not to support it and no one has demanded that feature: http://www.boost.org/doc/libs/1_65_1/doc/html/container/Cpp11_conformance.ht...

Yeah, I remember heated discussion about this in past. I'm not a fan of that feature of the STL containers.

Reallocation strategy: First, I considered this strategyunnatural, but now I am not sure. For a push_front, if no free front capacity is found, but there is free back capacity, then all data is shifted to insert the element. If interleaved front and back insertions are performed, I don’t know if this will lead to too many data movements. When memory is reallocated to make room for a front insertions, the free back capacity is unchanged and all new free capacity goes to front. This means that the last operation (front or back) determines where all the new capacity goes. I find a bit strange that N == front_back_capacity() does not mean that a reallocation will happen if we push_back N times, as repeated data movement will happen if front_free_capacity() is available.

Another strategy is to treat both ends independently: if front insertion has no free space, it could always reallocate and make room at front, so further push_fronts don’t provoke data movement. This would be similar to batch_deque, where memory is allocated if there is no free front capacityregardless of the free back capacity  (no data movement),f and free segment is recycled from back capacity to insert elements at front. Obviously, this approach consumes more memory. Yet another strategy would be distribute any new free capacity (after reallocation) between front and back, indepently from which operation (back or front) has provoked the allocation.

This is tricky. I think the best is to treat both ends independently. If you start moving things around, you can break the O(1) amortized guarantee by interleaving push_front/push_back.

2) The data structure o batch_deque is slightly bigger than the traditional one, just asking if it’s intended or it was developed like this to reuse code. Traditional deque (from SGI) used four elements (map pointer, map size, iterator to begin, iterator to end). Your implementation defines the map as a devector, which stores size and capacity for the map, but this allows you  handle the excess capacity of the map, I’m not sure if it adds performance benefits.

Reuse & simplicity would be the answer. If the iterators are fat, I bet you get the same size as as a batch_deque. Having a secondary ad hoc data structure with amortized O(1) double ended growth doesn't exactly make the code easier to reason about. kind regards Thorsten

Den 04-10-2017 kl. 15:32 skrev Chris Glover via Boost:

...

I think you have a way to turn these into pointers again in Boost.Container, By defining some preprocessor symbol, right? Having pointers matters when interfacing with other types, because this is the only case where the iterators are seen as contiguous.

I would much rather see that in debug mode the iterator type is a class and in release mode it is a pointer compared to having extra preprocessor symbols.

This is a bad idea. Early std library implementations did this and it caused several problems, including code that compiled in release, but not debug, or worse, different overload resolution between debug and release builds.

Sure, the whole point of having a class type in debug mode is to catch things at compile time. And don't you get the same when we start defining BOOST_CONTAINER_ITERATOR_AS_POINTER? -T

Den 04-10-2017 kl. 16:08 skrev Ion Gaztañaga via Boost:

On 04/10/2017 15:38, Thorsten Ottosen via Boost wrote:

...

And don't you get the same when we start defining BOOST_CONTAINER_ITERATOR_AS_POINTER?

Which was recently removed from the develop branch. AFAIK, there was no demand and maintenance and testing for both iterator modes was a cost I preferred to eliminate.

Ok. Given the lack of a contiguous iterator tag, this is not just a switch from pointer to class iterator. The internal code now needs to be careful when it's passed its own iterator type and detect that it actually has a contiguous range. kind regards -Thorsten

Den 04-10-2017 kl. 22:21 skrev Ion Gaztañaga via Boost:

On 04/10/2017 17:23, Thorsten Ottosen via Boost wrote:

...

Given the lack of a contiguous iterator tag, this is not just a switch from pointer to class iterator. The internal code now needs to be careful when it's passed its own iterator type and detect that it actually has a contiguous range.

Right. Internally used algorithms query "are_elements_contiguous<T>" traits which is specialized to true for vector_iterator.

Makes sense. And it works great when applied within one library, say Boost.Container. But then what about all the other container libraries in boost: BiMap CircularBuffer Gil MultiArray MultiIndex Unordered etc. We would have to have a Boost-wide trait for all interactions to be optimal. And then we can't do anything about interactions with the standard library. Anyway, I don't feel strongly about it either way. kind regards Thorsten

Den 04-10-2017 kl. 23:28 skrev Ion Gaztañaga via Boost:

On 04/10/2017 11:45, Thorsten Ottosen via Boost wrote:

...

Can they share some of the implementation, or are we left with a double (or triple) implementation effort?

They can obviously share implementation. That's the case with vector/small_vector/static_vector.

Ok, great.

...

...

According to the usual STL rules, size_type shall come from the allocator, which knows what type can represent the number of elements that can be allocated.

I have no problems with STL rules, but it as you point out, even Boost.Container deviates from several of those.

Yes, but only when they are "clearly bad rules (TM)" ;-)

I don't have any strong position about the size_type but thought it nice to have a small size of the container on 64 system. I do sometimes wonder if breaking the strong guarantee is a smart move. It seems to me that we can end up with non-trivial objects where the invariant is broken. So in principle we can't even reliably destroy them if the destructor relies on the invariant. I guess I really dislike that we are allowed to write move operations that are not noexcept (like swap).

...

...

4) unsafe_uninitialized_tag: I don’t like these non-safe constructors, which are  the cases?. With reserve-only constructors + unsafe emplace back a user can achieve nearly the same performance. For POD types (like the socket example mentioned in the documentation), I would suggest something like Boost.Container’s “default_init_t”. Instead of “unsafe_uninitialized_resize_front” I suggest resize_front(size_type, default_init_t)

I didn't know about these default_init_t when we started in 2015. They have a good design IMO. But unfortunately they don't get rid of double initialization for non-trivial types. So maybe both

resize_front( size_type, default_init_t ) resize_front( size_type, uninitialized_t )

would be an idea.

I understand the idea to avoid zero initialization for buffers, but what's the use case for types with non-trivial constructors? The documentation shows a socket example, and that's covered ith default_init_t.

Well, I don't know if my compiler is wrong, but vc 2017 says: class IntClass { int i; public: IntClass() : i(0) {} IntClass( int i ) : i( i ) {} }; is trivially copyable (hence we can copy arrays of it as fast as arrays of ints). But it will be initialized with zero if I use default_init_t, right? If so, I'm just saying that it may be nice/beneficial to be able to avoid double initialization also for IntClass (perhaps not relevant to sockets, but certainly to serialization). I do agree that reserve + unchecked_emplace_back() should be working well for types that are /not/ trivially copyable (also better in terms of exception-safety). The unitialized_resize idea is probably before we had emplace and so at that time there was no efficient/easy way to construct an object inplace. About the naming of unsafe_emplace_back: I prefer your suggestion with the unchecked_ prefix. Other ideas would be nonreallocating_emplace_back nonallocating_emplace_back nonexpanding_emplace_back nongrowing_emplace_back // seems wrong, since the size does change

...

...

5) reserve() / resize(): I think they have no sensible meaning in the container (capacity() could be useful, depending on the reallocation strategy). We should not treat back insertion as the “default” insertion. IMHO the API of devector should be symmetrical.

Symmetry is good, but what about generic code?

Generic code can't rely on reserve, only vector implements it in the STL. But if reserve() and resize() are unbiased to back insertion maybe they could make sense. reserve() allocates a new buffer if capacity() is not enough and moves existing elements to the middle. Resize could do the same and fill with elements on both ends.

If reserve is not an alias for reserve_back, the I think we must remove it. I was thinking along generic code along the line template< class BacKInsertionContiguousContainer > void foo( BacKInsertionContiguousContainer& cont ) { cont.reserve( source.size() ); for( ... ) cont.push_back( ... ); } why should that not work with both devector and vector?

stable_insert can maintain stability with a middle insertion but there is no equivalent operation for erasures. I just can't imagine a use case that tan take advantage of stable_insert (it needs more or less a positional insertion, but not absolute, instead of front/back insertion) but it will surely exist.

Yeah, I don't have a use case at hand either. Somehow you would want to insert a segments somewhere among the other segments. Then why not allow the segments themselves to be rearranged? (potentially almost trivial to implement). So I guess we could expose a complete container interface to the segments, but it is perhaps premature until we have a good use case.

...

This is tricky. I think the best is to treat both ends independently. If you start moving things around, you can break the O(1) amortized guarantee by interleaving push_front/push_back.

What do you mean by "treat both ends independtly"?

I mean that buffer extensions at either end should never affect each other. That is, a push_back can never remove free capacity from the front, a push_front can never remove free capacity from the back. kind regards Thorsten

Den 05-10-2017 kl. 22:42 skrev Ion Gaztañaga via Boost:

On 05/10/2017 19:02, Thorsten Ottosen via Boost wrote:

...

...

I understand the idea to avoid zero initialization for buffers, but what's the use case for types with non-trivial constructors? The documentation shows a socket example, and that's covered ith default_init_t.

Well, I don't know if my compiler is wrong, but vc 2017 says:

         class IntClass          {              int i;          public:              IntClass() : i(0) {}              IntClass( int i ) : i( i )              {}          };

is trivially copyable (hence we can copy arrays of it as fast as arrays of ints). But it will be initialized with zero if I use default_init_t, right?

Right.

But I agree we don't need two overloads, the existing one just has to work in terms of trivially copyable. We can also put a static assertion in there to lock it down to such types for now.

...

If reserve is not an alias for reserve_back, the I think we must remove it.

reserve() means that a container won't reallocate if size() < capacity(). Where memory is reserved is irrelevant for the user.

...

I was thinking along generic code along the line

template< class BacKInsertionContiguousContainer > void foo( BacKInsertionContiguousContainer& cont ) {     cont.reserve( source.size() );     for( ... )        cont.push_back( ... );

}

why should that not work with both devector and vector?

It would work, but it would not be as efficient as vector.

It may be. But I guess my concern was to make it compile. Sure, if a call to reserve is conditioned on d.capacity() - d.size(), it can behave differently. Reserve maybe easier to do something about. We may need to tweak the definition of reserve_back/reserve_front a little. Let's say we have x x 1 1 x so front_free_capacity is 2, back free capacity is 1 ans size is 2. with d.reserve( d.size() + 3 ); devector uses the expression n = new_capacity - size() so we get n = 5 - 2 = 3 and we get x x 1 1 x x x . A vector 1 1 x does the same. So is your concern that users use capacity to determine what/if to reserve?

...

...

...

This is tricky. I think the best is to treat both ends independently. If you start moving things around, you can break the O(1) amortized guarantee by interleaving push_front/push_back.

What do you mean by "treat both ends independtly"?

I mean that buffer extensions at either end should never affect each other. That is, a push_back can never remove free capacity from the front, a push_front can never remove free capacity from the back.

Ok. I still have no clear idea which allocation strategy would be the "natural" one. I've found this blog with a similar discussion and alternatives:

http://larshagencpp.github.io/blog/2016/05/22/devector

also linked from the blog post:

https://github.com/orlp/devector

Certainly a good analysis.

Moving elements just one step when one side is full and the other side has capacity has bad quadratic behavior while current capacity is being exhausted and we continue inserting in the same side. Moving elements to the middle of the buffer seems a simple operation that reduces this to something closer to O(NlogN). In any case, I will always bad insertion sequence that hurts our strategy, so optimizing the common case seems the way to go.

I'm ok with inserts in the middle to move stuff around since it already has O(n) worst case behavior. For push_back/push_front I don't know. It would have to be really simple to be worth the effort IMO. Say, only when other_size_free_capacity >= size(). The simple thing would be to grow independently, and then the user calls shrink to fit when done if he cares about it. BTW: Before the review some people complained that the container could not work as deque when you repeatedly pop from one end and push another. Something to ponder ... kind regards Thorsten

On 09/10/2017 10:30, Thorsten Ottosen via Boost wrote:

What if we did this:

capacity() -> alias for back_capacity back_capacity() -> return size() + back_free_capacity() front_capacity() -> return size() + front_free_capacity()

?

I think it's very confusing. If we move elements while inserting on one end and the free capacity of that end is zero, then capacity() has sense, it's the limit where memory will be reallocated. Best, Ion

On 10/10/2017 10:08, Thorsten Ottosen via Boost wrote:

If we have - as free space and x as elements, then

 -----xxxxxxxxxxxxx---------

 ^^^^^ front free capacity  ^^^^^^^^^^^^^^^^^^ front capacity       ^^^^^^^^^^^^^ size                    ^^^^^^^^^ back free capacity       ^^^^^^^^^^^^^^^^^^^^^^ back capacity (a.k.a capacity)

Ok, I see it. So capacity() is an alias for back_capacity(). That might work for if a user only calls push_back in generic code but any generic code that checks for capacity() == size() would be broken.

The limit where new memory is acquired for insert can be found easily enough.

Basically we can't both generalize vector behavior and get the segment size in one function. So pick one or none. Two of them allow generic code to compile.

I think the following is coherent, maybe not optimal in moves if only push_back is used: -----xxxxxxxxxxxxx--------- ^^^^^---------------------- front free capacity ^^^^^^^^^^^^^^^^^^--------- front capacity -----^^^^^^^^^^^^^--------- size ------------------^^^^^^^^^ back free capacity -----^^^^^^^^^^^^^^^^^^^^^^ back capacity ^^^^^^^^^^^^^^^^^^^^^^^^^^^ capacity front/back_free_capacity indicates the number of push_front/backs until data movement (and maybe allocation) is needed. front/back_capacity is front/back_free_capacity + size. If size == front/back_capacity, then data movement (and maybe allocation) will happen capacity == size means that any insertion will lead to reallocation.

(*) If push_back/push_front steals memory from the other end, we should be cautious about when this is done (potentially high constant factors as mentioned in the analysis you found). But it is more than that: it may mean that push_back/push_front cannot give the strong exception-safety guarantee. Are you really given that away for Boost.Container's vector? (I hope not).

Sorry about the bad news, push_back has no strong safety in boost::container::vector, as by design, move_if_noexcept is not used. It's mentioned in the documentation. A programmer that can tell the difference with std::vector needs to use throwing moves, catch the exception (if uncatched, the program will terminate and any guarantee is bogus) and do something with it that is based on strong exception safety. And vectors with potentially throwing moves will be really slow. I think vector's strong safety was a consequence from the C++03's copy semantics, and backwards compatibility had to be maintained in C++11 for types that define move constructors and assignments. If designed today, I doubt std::vector would offer strong exception safety for push_back.

Den 10-10-2017 kl. 23:23 skrev Ion Gaztañaga via Boost:

On 10/10/2017 10:08, Thorsten Ottosen via Boost wrote:

...

If we have - as free space and x as elements, then

  -----xxxxxxxxxxxxx---------

  ^^^^^ front free capacity   ^^^^^^^^^^^^^^^^^^ front capacity        ^^^^^^^^^^^^^ size                     ^^^^^^^^^ back free capacity        ^^^^^^^^^^^^^^^^^^^^^^ back capacity (a.k.a capacity)

Ok, I see it. So capacity() is an alias for back_capacity(). That might work for if a user only calls push_back in generic code but any generic code that checks for capacity() == size() would be broken.

why? If the vector is full, capacity() == size(). If the devector's right hand size is full, size() == back_capacity().

...

The limit where new memory is acquired for insert can be found easily enough.

Basically we can't both generalize vector behavior and get the segment size in one function. So pick one or none. Two of them allow generic code to compile.

I think the following is coherent, maybe not optimal in moves if only push_back is used:

  -----xxxxxxxxxxxxx---------

  ^^^^^---------------------- front free capacity   ^^^^^^^^^^^^^^^^^^--------- front capacity   -----^^^^^^^^^^^^^--------- size   ------------------^^^^^^^^^ back free capacity   -----^^^^^^^^^^^^^^^^^^^^^^ back capacity   ^^^^^^^^^^^^^^^^^^^^^^^^^^^ capacity

front/back_free_capacity indicates the number of push_front/backs until data movement (and maybe allocation) is needed.

front/back_capacity is front/back_free_capacity + size. If size == front/back_capacity, then data movement (and maybe allocation) will happen

capacity == size means that any insertion will lead to reallocation.

That's the alternative, but that is the one that breaks generic code, isn't it?. With my scheme above, if you absolutely must know if insertion reallocates, you can use front_free_capacity() + back_free_capacity() == 0. I don't know if that needs a special function though (it could be called full() ).

...

(*) If push_back/push_front steals memory from the other end, we should be cautious about when this is done (potentially high constant factors as mentioned in the analysis you found). But it is more than that: it may mean that push_back/push_front cannot give the strong exception-safety guarantee. Are you really given that away for Boost.Container's vector? (I hope not).

Sorry about the bad news, push_back has no strong safety in boost::container::vector, as by design, move_if_noexcept is not used. It's mentioned in the documentation.

Ah, yes. Only when the type is well-behaved (non-movable, only copyable or no-throw movable) we guarantee that, right? kind regards Thorsten

Den 11-10-2017 kl. 21:00 skrev Ion Gaztañaga via Boost:

On 11/10/2017 13:20, Thorsten Ottosen via Boost wrote:

...

why? If the vector is full, capacity() == size(). If the devector's right hand size is full, size() == back_capacity().

But if capacity() is an alias for back_capacity() and size() == capacity(), an insertion in the middle would not trigger a reallocation. capacity() > size() means to me "is there room for a new insertion without reallocation"?

...

...

capacity == size means that any insertion will lead to reallocation.

That's the alternative, but that is the one that breaks generic code, isn't it?.

Which generic code? I think it's the opposite.

We started with code like (*) if( container.capacity() > container.size() + new_elements ) container.reserve( container.size() + new_elements ); ... for( ... ) container.push_back(...); and we found that this would sometimes not reallocate for devector. So I proposed a design that did. But now ...

For any container with reserve/capacity (vector, string, flat_map, circular_buffer, poly_collection, etc.) if capacity() == size() that means a reallocation will happen for *any* insertion, not just push_back. If you want guarantees for back insertion only, then back_capacity() should give you the answer. Just my 2 cents.

... we broke capacity() == size() means that any insertion will reallocate. What I was trying to convey is that there is no definition of capacity/back_capacity etc that can simultaneously satisfy both. I think the guiding principle should be to support idiomatic code. (*) is not idiomatic: there is absolutely no reason to guard a call to reserve when you can just write: container.reserve( container.size() + new_elements ); That means your design where capacity is the the full buffer length can satisfy both situations. So I agree with you. But it also calls into question the need for anything else than capacity (i.e., there seem to be vanishingly little use for back_capacity/front_capacity and they probably confuse more than they help). I do think reserve is harder to use than it should be. I would have preferred it was called container.anticipate_back( new_elements ); which works regardless of the size of the container. kind regards Thorsten

On Thu, Oct 12, 2017 at 12:17 PM, Ion Gaztañaga via Boost < boost@lists.boost.org> wrote:

On 12/10/2017 10:37, Thorsten Ottosen via Boost wrote:

That means your design where capacity is the the full buffer length can

...

satisfy both situations. So I agree with you. But it also calls into question the need for anything else than capacity (i.e., there seem to be vanishingly little use for back_capacity/front_capacity and they probably confuse more than they help).

I agree. If capacity is the full buffer length, only back/front_capacity make sense.

Normally, my check against capacity() is usually about iterators, pointers and/or references possibly being invalidated more than knowing that an actual allocation will take place. Have we considered capacity() == min(front_capacity(), back_capacity())? Just a thought, Nevin :-) -- Nevin ":-)" Liber > +1-847-691-1404

Den 12-10-2017 kl. 20:34 skrev Nevin Liber via Boost:

Normally, my check against capacity() is usually about iterators, pointers and/or references possibly being invalidated more than knowing that an actual allocation will take place.

What is the difference be an allocation and an invalidation? I assume your context is "what happens when I call push_back?".

Have we considered capacity() == min(front_capacity(), back_capacity())?

Or is your context "what happens when I call either push_back or push_front?" Maybe you can tell us what your program does when it detects that things are invalidated? Do you then recompute the iterators and references? kind regards -Thorsten

On 26/10/2017 20:10, Thorsten Ottosen via Boost wrote:

I'm just rereading all the messages when I came to this one.

That definition seems to satisfy:

A. size() == capacity() implies any insertion /can/ cause reallocation.

B. if( size() + new_elements > capacity ), then reserve() style does not    lead to any invalidation in subsequent push_back (addressing Joaquin's concern).

Ion was using the definition "any insertion /will/ cause reallocation.

This is all very subtle since it depends on the definition of reserve() too.

But I think it's the best definition we have seen.

Yes, not only that. These days I was thinking about a modified capacity() definition. If size() == capacity() an insertion can provoke more than optimal data movement (iterator invalidation) and (optionally) reallocation. That could be implemented if capacity() is defined as: max(size(), min(back_capacity(), front_capacity()); If an insertion is done in the side that has free capacity, no data movement and memory allocation is done, but for the user is similar to a in-place buffer expansion. Capacity has grown to accommodate the insertion without moving anything more that needed. If a user want's to be sure if an insertion in one side will be supported without more than optimal data movement or iterator invalidation, then he/she can check back/front_capacity() against size(). I've haven't thought how reserve() is affected. Best, Ion

On 30/10/2017 19:27, Thorsten Ottosen via Boost wrote:

...

That could be implemented if capacity() is defined as:

max(size(), min(back_capacity(), front_capacity());

Is this not just equivalent to

  min(back_capacity(), front_capacity())

given that back/front_capacity >= size()?

Right. Good catch.

On 12/10/2017 19:17, Ion Gaztañaga via Boost wrote:

On 12/10/2017 10:37, Thorsten Ottosen via Boost wrote:

...

That means your design where capacity is the the full buffer length can satisfy both situations. So I agree with you. But it also calls into question the need for anything else than capacity (i.e., there seem to be vanishingly little use for back_capacity/front_capacity and they probably confuse more than they help).

I agree. If capacity is the full buffer length, only back/front_capacity make sense.

I wanted to say only back/front_FREE-capacity makes sense if capacity is the full buffer length. Ion

On 05/10/2017 9:04, Benedek Thaler via Boost wrote:

...

5) reserve() / resize(): I think they have no sensible meaning in the container (capacity() could be useful, depending on the reallocation strategy). We should not treat back insertion as the “default” insertion. IMHO the API of devector should be symmetrical.

Again, compatibility.

Understood.

s/unsafe/unchecked, agreed. Also, we need the emplace methods as well.

Why both? Isn't emplace enough?

Reallocation strategy: First, I considered this strategyunnatural, but now

...

I am not sure. For a push_front, if no free front capacity is found, but there is free back capacity, then all data is shifted to insert the element. If interleaved front and back insertions are performed, I don’t know if this will lead to too many data movements. [snip]

If it does not shift, it has to reallocate - and then copy/move everything over. I don't see how is that any better.

Yes, this is tricky, as I pointed out in other reply to Thorsten, we could maybe move elements in bigger steps to avoid quadratic behavior with repeated inserts in one end while buffer is being reallocated.

The interest of the community should be put first. If we think adding pieces to Container would improve situations, we should find a way. On the other hand, I wouldn't love to port code to C++03, for two reasons: It is a soul crushing work, and, we should not encourage writing new code using old standards (I know, there's no other option in certain cases.).

Yes. I know will be the last warrior supporting C++03 in Boost ;-) Best, Ion

Den 04-10-2017 kl. 01:30 skrev Ion Gaztañaga via Boost:

-------------------------- batch_deque -------------------------- 1) I like that deque_[const_]iterator is lightweight, I don’t know if iteration/access it’s more efficient than more traditional approaches. boost::container::deque iterators are really fat and should be improved to something similar to batch_deque iterator.

I guess the simplest would be to replace the end iterator with a function that computes it when needed (I think that can be done easily since you now the segment size at compile time). kind regards Thorsten

Den 04-10-2017 kl. 01:30 skrev Ion Gaztañaga via Boost:

and I don’t know if the use cases where devector is supposed to shine needs a whole new library It's hard to guess about all the use-cases. We never had this as a type in our toolbox, so we never gave it any thought. Maybe systems working with RTL and LTR text would be natural.

Given that boost::flat_set/flat_map now has support for a custom container, I can easily see myself plugging in devector in there. Also with a small buffer optimization. And having deque backed by devector allows for example to use the small buffer for, say, one or two of the first segment pointers. So what is the benefit of plugging devector into flat_set/flat_map? Assume a balanced initial capacity (same front free capacity and back free capacity). Then compared with vector when we insert N elements - if all go to the back end, both containers are optimal O(N \lg N) - the worst case for vector is when all go to the front O(N^2), this is O(N \lg N) for devector - unfortunately the average case is O(N^2) for both containers (so we only use it with relatively small sets) /However, the average case for devector uses about half as many moves as vector./ Based on that, I would pick devector as the container in flat_set/flat_map in my code. kind regards Thorsten

Den 10-10-2017 kl. 23:26 skrev Ion Gaztañaga via Boost:

On 10/10/2017 10:50, Thorsten Ottosen via Boost wrote:

...

/However, the average case for devector uses about half as many moves as vector./ Based on that, I would pick devector as the container in flat_set/flat_map in my code.

Interesting points. Anyone willing to do some benchmark? ;-)

I'll try to do one later. But, in theory, if there is sufficient room to maneuver at both ends: - on average, insert takes about half the moves that a vector requires Independently of having space at both ends: - on average, erase takes about half the moves that a vector requires It must be so. Apologies for not realizing this sooner ... kind regards -Thorsten

On 11/10/2017 18:39, Thorsten Ottosen via Boost wrote:

I then plugged in boost::container's code for move-forwards and move-backwards:

32-bit, erase:

10E3    3.39647 4.09578 10E4    2.85362 2.61519 10E5    11.4961 6.07559 10E6    80.8788 27.0292 10E7    913.022 272.85

64-bit erase:

10E3    2.47863 3.61393 10E4    1.75806 2.47981 10E5    4.77791 3.98943 10E6    30.6545 15.9707 10E7    361.743 160.078

Is this awesome or what? :-)

Sure ;-) Differences are not very noticeable for small containers, numbers are better than expected for big containers. I can't deduce why, maybe the initial reserve and index modulo are adding noise to the benchmark. In any case, for flat_xxx family, devector would be a better choice than vector, maintaining contiguous storage, so we already have the use case where devector must shine ;-) Best, Ion

On Wed, Oct 11, 2017 at 6:39 PM, Thorsten Ottosen via Boost < boost@lists.boost.org> wrote:

Den 10-10-2017 kl. 23:26 skrev Ion Gaztañaga via Boost:

...

On 10/10/2017 10:50, Thorsten Ottosen via Boost wrote:

Interesting points. Anyone willing to do some benchmark? ;-)

...

Here is one example comparing boost::vector<int> with devector<int>.

Here are my results of a similar test: Run on (8 X 3500 MHz CPU s) 2017-10-12 22:16:02 ------------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------------- devector_insert/128 3837 ns 3818 ns 176825 devector_insert/512 23179 ns 23168 ns 31408 devector_insert/4096 980113 ns 978796 ns 708 devector_insert/32768 60061674 ns 59983258 ns 11 devector_insert/65536 237795405 ns 237520129 ns 3 cvector_insert/8 853 ns 855 ns 807388 cvector_insert/64 1988 ns 1989 ns 350874 cvector_insert/512 26493 ns 26494 ns 26234 cvector_insert/4096 1752987 ns 1750600 ns 399 cvector_insert/32768 108519299 ns 108385834 ns 6 cvector_insert/65536 436277805 ns 435846258 ns 2 Conditions of the measurement as posted earlier. Thanks, Benedek

On Fri, Oct 13, 2017 at 7:28 PM, Thorsten Ottosen wrote:

Den 12-10-2017 kl. 22:18 skrev Benedek Thaler via Boost:

...

On Wed, Oct 11, 2017 at 6:39 PM, Thorsten Ottosen via Boost <

Here are my results of a similar test:

...

Hi Benedek,

Many thanks!

I'm just curious: why are the N's different for the two classes. For example, devector has 128, but not 8 or 64?

Forgot to change a constant.

There is one final test I would like to see. Instead of relying on shuffled positions, we should keep the container size fixed and insert exactly one time at each position. So instead of

for (std::size_t p : positions) { c.insert(c.begin() + p, p); }

we should before the loop fill the container to 90% capacity. For devector, make sure there is space in both ends. Then do the following:

for( std::size_t p = 0; p < c.size(); ++p ) { state.ResumeTiming(); c.insert( c.begin() + p, p ); state.PauseTiming(); c.erase( c.begin() + p ); }

That would be great to see even for small values 8, 16, 32, 64, 128, etc.

Here you are: Run on (8 X 3500 MHz CPU s) 2017-10-13 19:42:26 ***WARNING*** CPU scaling is enabled, the benchmark real time measurements may be noisy and will incur extra overhead. ------------------------------------------------------------- Benchmark Time CPU Iterations ------------------------------------------------------------- devector_insert/8 6079 ns 6091 ns 114176 devector_insert/64 49051 ns 49162 ns 14195 devector_insert/512 409902 ns 410626 ns 1703 devector_insert/4096 4734707 ns 4740961 ns 147 devector_insert/32768 123148029 ns 123081746 ns 6 devector_insert/65536 442823644 ns 442517234 ns 2 cvector_insert/8 6133 ns 6138 ns 115351 cvector_insert/64 49637 ns 49692 ns 13908 cvector_insert/512 430861 ns 431102 ns 1626 cvector_insert/4096 6275393 ns 6277401 ns 111 cvector_insert/32768 218750948 ns 218571840 ns 3 cvector_insert/65536 825168625 ns 824351333 ns 1 (It'd be great if someone could re-run these tests to verify my results) Thanks, Benedek