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-16 21:59:51

El 16/05/2017 a las 23:41, Ion Gaztañaga escribió:
> 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/poly_collection/detail/poly_collection.hpp#L660-L683 
>>
>>
>> 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.

Exactly, this is what it does. At the end of the day, this is about 
convenience vs.
performance. I'd have to find a very convincing argument to give slicing 
prevention
away. Furthermore, you can have the best of both worlds if you keep 
reading below :-)

>> 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/poly_collection/detail/poly_collection.hpp#L694-L705 
>>
>
> 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/poly_collection/detail/poly_collection.hpp#L707-L722 
>
>
> which also assumes iterator::value_type is the dynamic type of the 
> whole range.

I know, and this is what you got:

https://github.com/joaquintides/poly_collection/blob/master/include/boost/poly_collection/detail/poly_collection.hpp#L785-L818

Note that in bc.insert(bc.end<warrior>(),warriors_first, warriors_last) 
it's only
the first arg that's actually a local iterator: warriors_first and 
warriors_last can
be any InputIterator. No typeid checking is done (except on debug mode, see
the BOOST_ASSERT's) and when this is staticfied we can get the preallocation
performance boost etc. In a sense, bc.end<warrior>() is the indication to
Boost.PolyCollection that the inserted range *must* be warriors and not 
something
else.

> [...]
>
> 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 ;-)

Hintless insertion resolves to pushing back to the corresponding 
segment. The difference
in performance would solely consist in the looking up of the segment. 
Again, you can already
have your second version with the existing interface:

while(...)
   pc.insert(bc.end<warrior>(),warrior());

(Insertion at the end is, of course, the same as pushing back).

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

Noted.

> [...]
>
> 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. 

Thank you for your very interesting input. Let's see is some latecomer joins
the party before the review is over.

Joaquín M López Muñoz