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/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.
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/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.
I know, and this is what you got: https://github.com/joaquintides/poly_collection/blob/master/include/boost/po... 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