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

Subject: Re: [boost] [poly_collection] Memory allocation and allocator propagation
From: Joaquin M López Muñoz (joaquinlopezmunoz_at_[hidden])
Date: 2017-05-15 09:57:41

El 14/05/2017 a las 17:01, Ion Gaztañaga escribió:
> Hi Joaquín,
>
> Some additional comments about the design:
>
> /////////////////////////
> //  Memory indirections
> /////////////////////////
>
> If I understand code correctly, the internal structure of a poly 
> collection is approximately:
>
> 1) poly_collection stores an unordered_map<type_index, segment_type>
>
> 2) segment_type stores a unique_ptr<segment_backend> and 
> segment_backend_is an abstract class, so roughly equivalent to 
> unique_ptr<packed_segment/split_segment> (both 
> packed_segment/split_segment derive from segment_backend.
>
> 3) packed_segment/split_segment stores a vector of concrete types.
>
> So we need 3 memory hops to navigate between the "this" pointer of a 
> PolyCollection to a pointer to a concrete type: poly_collection -> 
> unordered node -> segment in unique_ptr -> vector value.
>
> 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 principle if the optimization is reasonably implemented I'd say it'd 
be welcome. I don't
think this is going to show in performance, though, but profiling could 
tell us.

> /////////////////////////
> //  Allocator propagation
> /////////////////////////
>
> As mentioned in Adam Wulkiewicz's review PolyCollection currently does 
> not propagate the allocator from the constructor argument of 
> poly_collection to the concrete type. From a practical point of view, 
> the key requirement is that all intermediate memory until the concrete 
> type must be allocated using the same root allocator passed when a 
> poly_collection was constructed, and that allocator must be propagated 
> also to the concrete type.

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.

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:

* base_collection<Base> does *not* use 
allocator_traits<allocator_type>::construct/destroy
for construction of its value_type (=Base). What gets into the internal 
vector is a
value_holder<Derived>, which constructs/destroys the contained Derived 
values through
placement new and direct call to Derived::~Derived, respectively 
Strictly speaking, it is
impossible to use allocator_traits<allocator_type>::construct/destroy 
for *Base*, as it
is *Derived* objects that get constructed/destroyed.
* function_collection and any_collection *do* use 
allocator_traits<allocator_type>::construct/destroy
for construction/destruction of their value_type objects 
(function_collection_value_type and
any_collection_value_type); take a look at

https://github.com/joaquintides/poly_collection/blob/master/include/boost/poly_collection/detail/split_segment.hpp#L54-L57

Now, if by "container's element type" we understand the various concrete 
types that
get stored in the polymorphic collections, the the situation is like in 
base_collection
before: none of these concrete objects is cosntructed/destroyed through 
an allocator
but directly with placement new / Concrete::~Concrete inside value_holder.

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

> [...]
>
> I think that a unique memory source for all internal structures and 
> the correct propagation of the allocator using allocator_traits is a 
> very interesting feature for PolyCollection.

Hopefully answered above.

> [...]
>
> *Main question 2*: Do you think PolyCollection should support stateful 
> allocator using the scoped allocator model?

Now, the scoped allocator model is an even stronger requirement than we 
have discussed
so far. I don't have the necessary expertise in this, but I fail to see 
the applicability to
PolyCollection from a cursory glance at N2554.

> Some specific notes that might show places where the scoped allocator 
> model has problems.:
>
> [...]
>
> - 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?

Joaquín M López Muñoz