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

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