Boost logo

Boost :

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

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
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
for construction/destruction of their value_type objects
(function_collection_value_type and
any_collection_value_type); take a look at

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at