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

On 16/05/2017 9:23, Joaquin M López Muñoz wrote:

...

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?

For the emplace function, as the ConcreteType it's always statically known (type T is the type to be constructed, whereas in "insert" T is the type used to construct the concrete type), then I think no and lambda is needed, it could be directly translated to a simple call to the statically known segment type: s.emplace_back(forward<Args>(args...));

Ion, I think you're on to something here. As it happens, poly_collection can statically determine when T is acceptable and dynamically detect the cases where x's subtype is actually T, in which case virtual calls can be omitted altogether --A reference to the internal packed_segment/split_segment can be statically obtained from segment.

Ok, I see it. If typeid(x) == typeid(T), the static path (let's call it statically_known_insert(x)) is taken. Otherwise the virtual function is used. In any case, the runtime slicing detection will slow down ranges, as you'll need to check the typeid of each *it reference in the range. If all the range is assumed to be the same runtime type (or slicing is assumed) then the operation is a simple: s.insert(s.end(), first, last); which will use distance(first, last) for forward iterators, allocate all the storage once and avoid a lot of objet moving/copying. Maybe a new overload for insert taking a range that the user does not care to slice could be a good idea for performance reasons: base_collection.insert<warrior>(warriors_first, warriors_last); For absolute zero overhead (no repeteated typeid, no repeated hash search), a segment handle utility comes to my mind: typedef base_collection<sprite> bc_t; bc_t bc; //register type bc.register_types<warrior>(); //Obtain segment handle (maybe just a struct holding the pointer to //the concrete segment) bc_t::segment_handle<warrior> sh = bc.segment_handle<warrior>(); //Insert directly in the segment (just vector insertion) //and updating bc's member data if any. bc.insert(sh, pos, warrior); Additional comments: 1) I also noticed that bc.size() and bc.empty() are not constant-time. It seems a bit surprising, it might be noticeable when the number of segments grows. This avoids common data in poly_collection but I imagine most users assume these functions are free. 2) The number of additional operations that could take advantage of the "I know your static type" optimization is important, although the speedup will depend on the cost of each operation (eg. size()/ reserve() vs. a virtual function call): template<typename T> void reserve(size_type n); template<typename T> void shrink_to_fit(); template<typename T> size_type capacity() const; template<typename T> size_type max_size() const; template<typename T> size_type size() const; template<typename T> bool empty() const; template<typename T> void clear(); Additional possible "zero cost" calls using the segment handle: template<typename SegmentHandle> void reserve(SegmentHandle sh, size_type n); template<typename SegmentHandle> void shrink_to_fit(SegmentHandle sh); template<typename SegmentHandle> size_type capacity(SegmentHandle sh) const; template<typename SegmentHandle> size_type max_size(SegmentHandle sh) const; template<typename SegmentHandle> size_type size(SegmentHandle sh) const; template<typename SegmentHandle> bool empty(SegmentHandle sh) const; template<typename SegmentHandle> void clear(SegmentHandle sh); Best, Ion

On 16/05/2017 20:28, Joaquin M López Muñoz wrote:

...

In any case, the runtime slicing detection will slow down ranges, as you'll need to check the typeid of each *it reference in the range.

Not in every case, see for instance the two insert overloads at:

https://github.com/joaquintides/poly_collection/blob/master/include/boost/po...

where you can notice than when the type is terminal we don't repeat typeid checking.

Is the iterator's "value_type" a guarantee of the dynamic type of the referenced object? I can imagine ptr_vector or Boost.Intrusive iterators, where value_type is the base class, but the dynamic type of the object is a derived class. If the implementation wants to avoid any slicing and support these "special" iterators then it should check the typeid of every value in the range.

We sort of already have that:

bc.insert(bc.end<warrior>(),warriors_first, warriors_last);

See:

https://github.com/joaquintides/poly_collection/blob/master/include/boost/po...

I was not talking about a range taking local iterators, but a range of iterators of a vector holding warriors. Something like: https://github.com/joaquintides/poly_collection/blob/master/include/boost/po... which also assumes iterator::value_type is the dynamic type of the whole range.

This is efficient typeid-wise, not so with respect to preallocating based on distance. If we go ahead with your proposal of static-fying the interface when the concrete type is known, we can get much better --actually, as fast as possible.

...

For absolute zero overhead (no repeteated typeid, no repeated hash search), a segment handle utility comes to my mind:

[...]

I think this is not needed in light of my previous comment.

As a suggestion, I would include in the insertion benchmarks a vector push_back. At least for packed_segment, vector push_back is the upper_bound of any performance improvement. If the performance difference between the new "staticfied" single value insertion function: while(....) pc.insert(warrior()); and the vector push_back code while(...) warrior_vector.push_back(warrior()); is significant, then maybe a uglier but near-zero overhead alternative (like the segment handle) methods might be a good idea. Specially for power programmers that want to create a bunch of warriors when the new game level starts ;-)

...

1) I also noticed that bc.size() and bc.empty() are not constant-time. It seems a bit surprising, it might be noticeable when the number of segments grows. This avoids common data in poly_collection but I imagine most users assume these functions are free.

Strictly speaking, they're constant time wrt number of elements, assuming (correctly, I'd say) that the number of registered types is bounded and don't increase linearly with size(). I'm very against caching size for consistency reasons and because we are adding a little fat to every operation of the container.

I don't know if anyone will use poly_collection with many different types and few elements per segment. As always users will surprise us ;-) In any case I would recommend documenting this visible somewhere (ideally in the method description as Complexity) with a complexity similar to (I hope I don't get it wrong): O(distance(segment_traversal().begin(), segment_traversal().end())) as typically most programmers would think about those as extremely cheap operations and might call them in a loop.

...

2) The number of additional operations that could take advantage of the "I know your static type" optimization is important, although the speedup will depend on the cost of each operation (eg. size()/ reserve() vs. a virtual function call):

template<typename T> void reserve(size_type n); template<typename T> void shrink_to_fit(); template<typename T> size_type capacity() const; template<typename T> size_type max_size() const; template<typename T> size_type size() const; template<typename T> bool empty() const; template<typename T> void clear();

If/when we staticfy the interface of course we'll go all the way and improve as much as can be improved. The functions you list above, though, are not expected to be a performance problem in any sensible program.

Right. My "the root of all evil" side is also reviewing the library ;-) And hopefully these are my last comments ;-) I think none of them are needed for the acceptance of the library, as they could be added as future improvements. Best, Ion

Den 16-05-2017 kl. 23:59 skrev Joaquin M López Muñoz via Boost:

El 16/05/2017 a las 23:41, Ion Gaztañaga escribió:

...

I don't know if anyone will use poly_collection with many different types and few elements per segment. As always users will surprise us ;-)

I agree with Joaquin that we should not store the size.

...

In any case I would recommend documenting this visible somewhere (ideally in the method description as Complexity) with a complexity similar to (I hope I don't get it wrong):

O(distance(segment_traversal().begin(), segment_traversal().end()))

as typically most programmers would think about those as extremely cheap operations and might call them in a loop.

Noted.

I think if your documentation defines n = # of elements in container, k = # of segments in container, then simply saying Complexity: O(k) or Complexity: linear in k is nicer to read than all the range stuff. kind regards -Thorsten