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

Subject: Re: [boost] [review] The review of Boost.DoubleEnded starts today: September 21 - September 30
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2017-10-04 21:28:38

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

>> 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?

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

>> 2) Defaulting size_type to unsigned int is arbitrary and against 
>> existing practice.
> 
> We didn't do that as an arbitrary decision.

Yes, sorry, "arbitrary" sounds too strong.

>> 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)" ;-)

>> 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)?

Good questions. Maybe the first, but that would apply also to "reserve".

>> 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.

>> 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.

I somewhat have the idea that in a devector both front and back 
insertions should be common, so a back-biased approach should be 
avoided. Not sure if real usage follows this pattern.

>> 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.

Right.

>> 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.

That could have surprising compilation errors when switching modes. For 
debug iterators, I find interesting the libc++ approach (but I don't 
know how it performs) to maintain binary compatibility between checked 
and non-checked iterators using a global database store containers and 
iterators.

>> 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?

vector if object count or maximum object count is known and all elements 
are going to be destroyed at the same time. Deque if the number of 
elements are not known (but they are destroyed at the same time). If 
elements are destroyed in any order, then you need a pool, a list or 
some kind of free list backed with a deque or similar.

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.

Additional note: stable_insert also constructs a temporary batch_deque 
which is not passed the stored allocator so that objects are created in 
the same memory type of already stored objects. The temporary container 
should be avoided, maybe new segments could be back/front allocated and 
initialized then then just reinserted in their final positions in the map.

> 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"?

Best,

Ion