Re: [boost] [poly_collection] Memory allocation and allocator propagation

Subject: Re: [boost] [poly_collection] Memory allocation and allocator propagation
From: Ion Gaztañaga (igaztanaga_at_[hidden])
Date: 2017-05-15 23:00:07

On 15/05/2017 11:57, Joaquin M López Muñoz wrote:
>> I think the data structure could be optimized to save one indirection.
>> segment_type could directly hold the class derived from
>> segment_backend as packed_segment/split_segment will need the same
>> size and alignment requirements regardless of the ConcreteType they
>> hold (as long as they use std::vector). This could improve insertion
>> times and other operations. This optimization could also make easier
>> to fix the following section (allocator propagation).
>>
>> *Main question 1*: Do you find think PolyCollection should implement
>> this optimization?
>
> How do yo envision this could be done? Replacing the current
> std::unique_ptr<segment_backend> pimpl with a
> std::variant<packed_segment,split_segment> (which would restrict the set
> of implementations of segment_backend to only these two)? Or do you have
> something else in mind?

In theory each Model can specify the alignment and size to hold every 
possible segment type for any ConcreteType. I think any ConcreteType 
will have the same size and alignment requirements (as a vector stores 
pointers so the size or alignment of T does not participate in the size 
or alignment of segment_type).

So the requirement is that there is an upper bound on the  size and 
alignment for segment types holding any ConcreteType. Class segment 
holds aligned storage to hold the any concrete segment_type:

class MyModel
{
   private:
   typedef packed_segment<MyModel, DummyT, DummyTAlloc> any_segment_t;

   private:
   //size of any segment_type usable with this model
   static std::size_t segment_type_size = sizeof(any_segment_t);

   //alignment
   static std::size_t segment_type_alignment = alignof(any_segment_t)

   template<typename Derived,typename Allocator>
   static segment_backend* make_in_place(void *addr, const Allocator& al)
   {
     typedef typename std::allocator_traits<Allocator>::
         template rebind_alloc<Derived> derived_alloc_t;
     typedef packed_segment<MyModel, Derived, derived_alloc_t>
        any_segment_t;

     //Propagate allocator using a possibly custom construct operation
     typedef allocator_traits<Allocator>::rebind_traits
       <any_segment_t> segment_traits_t;
     return segment_traits_t::construct(addr, al);
   }
};

Maybe segment_backend should have a virtual function that does the 
placement destruction using allocator_traits. When "class segment's" 
destructor is run, that virtual function is used to destroy the inplace 
object.

> We have a problem here: your key requirement can be split in two:
>
> A. Allocator is propagated down the data structure for memory allocaion
> B. allocator_traits<allocator_type>::construct/destroy is used for
> construction/destruction
> of the "container's element type".
>
> As for A, in fact the root allocator is copied and used for all dynamic
> memory handling
> from the top std::unordered_map down to the private std::vectors in
> packed_segment/split_segment *except* at the
> std::unique_ptr<segment_backend> pimpl
> part. This could be remedied either by supressing the unique_ptr
> altogether as you
> suggest at the beginning of the post, or providing a custom deleter to
> unique_ptr or
> something.

Right. I noticed that value_holder also does not propagate the allocator 
argument when the concrete type is constructed. value_holder could be 
defined so that uses_allocator_v == true (defining an internal 
allocator_type and having extended constructors. Then it could use 
allocator traits to construct the concrete type and forward the 
allocator if that type supports it.

IMHO, even if the standard seems to say the opposite (as only requires 
allocator_traits::construct for the element_type), I think the allocator 
should be propagated also to the vector holding the index in 
split_segment. The idea is that all memory needed by the container 
should come from the same source.

> Now as for B: This really depends on what the "container's element type"
> is supposed
> to be. A natural posibility would be to equate this with the container's
> value_type, in
> which the case the situation is:

I think the standard is written to support only std containers but not 
generic containers. IMHO requirement B is not applicable to PolyCollection.

> Summing up: I see A (all dyamic memory handled by passed allocator) as
> an useful and
> desireable feature. I don't see the point of doing contortions to
> achieve B (by passing
> allocators to value_holder etc.) just for the sake of compliance, much
> more so when in
> one collection (namely base_collection) it is impossible to comply in a
> literal sense (it is
> derived classes that get constructed/destroyed).

You need to pass the allocator to value_holder so it forwards it to the 
real concrete type, which could be a container. Just use 
allocator_traits each time you need to construct an object in place.

>> - The "emplace" operation uses a placement new to wrapped in a lambda
>> which is type-erased with a captureless lambda. It looks to me that
>> instead of delegating the work into the value_holder, the type erasure
>> arguments should be treated by the segment so that internal vectors
>> propagate the allocator when needed.
>
> I don't see how this could be done: type erasure must happen before
> segment is used, and actual
> args types are then unknown to segment... Care to elaborate?

I haven't thought it carefully and it might not possible at all, but 
maybe the lambda could execute:

    s.emplace_back(forward<Args>(args...));

where s is the concrete segment type that can be obtained via Model (the 
address of the aligned storage inside "class storage" is casted to 
Mode::get_segment_type<T>::type*) because the ConcreteType we are going 
to construct is known at compile time in emplace_back_impl.

I also wonder if insert<T> and other functions should avoid slicing 
detection so that they can also avoid the virtual call overhead. If T is 
assumed to be the same type of the final ConcreteType, you can use 
typeid(T) instead of typeid (x) (which can require to trip through the 
vptr) when searching in the unordered map and obtain a pointer to the 
concrete segment type just casting. Insertion times could be improved, 
specially range insertions could shine (as vector could be resized just 
once). Or am I missing something?

Best,

Ion