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

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 pimpl with a std::variant (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 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 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 any_segment_t; //Propagate allocator using a possibly custom construct operation typedef allocator_traits<Allocator>::rebind_traits 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::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 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