Re: [boost] [review] Review of PolyCollection starts today (May 3rd)

Subject: Re: [boost] [review] Review of PolyCollection starts today (May 3rd)
From: Joaquin M López Muñoz (joaquinlopezmunoz_at_[hidden])
Date: 2017-05-14 22:14:36

El 11/05/2017 a las 18:18, Thorsten Ottosen escribió:

 > Den 11-05-2017 kl. 09:53 skrev Joaquin M López Muñoz via Boost:
 >>
 >> El 10/05/2017 a las 22:33, Thorsten Ottosen via Boost escribió:
 >>>
 >>> D. Implementation of equality: do we need to be set like semantics
 >>> (two-pass)? Why don't you just delegate to the segments after checking
 >>> the size? I don't think the documentation specifies what the
 >>> implementation does.
 >>
 >> We can't blindly delegate to the segments (if I'm getting your question
 >> right) because
 >> the order and associated types of the segments in x and y can differ: we
 >> need to first
 >> match them up, hence the two passes.
 >
 > Well, the documentation states:
 >
 > "a==b evaluates to true iff for each non-empty segment of subojects of
 > type U in a there is a segment of U in b with the same size and equal
 > elements in the same order, and viceversa."
 >          ^^^^^^^^^^^^^^^^^^
 >
 > So the question is we want the current O(n^2) == or if it should do as
 > the docs say. Since we don't have set semantics anyway, I would prefer
 > segments to match exactly.
 >

Sorry, I'm not getting you. The current implementation enforces exact
segment match.
Could you maybe elaborate/reword your question?

 >>> E. should the test check (perhaps via static_assert) the conditions
 >>> under which move-construction and move-assignment is noexcept? (sorry
 >>> if this is already done). Specifically, if std::unordered_map has
 >>> noexcept for these, then you can guarantee the same for
 >>> base_collection etc.
 >>
 >> I can't guarantee noexcept because whether an exception is thrown or not
 >> depends
 >> on the nature of the actual types in the container, which is runtime
 >> info.
 >
 > I don't get it. [...]

My bad, I misread your question. Of course move construction and move
assignment do not throw or copy elements etc., but I didn't mark them as
noexcept following the no-noexcept signature of std unordered associative
containers. I don't know why the std has not made those noexcept.

 >
 > This reminds me, it would be good with a small note of reference
 > stability guarantees.
 > AFAICT, it's swap/move/changing an unrelated segment.

This is implicitly guaranteed by [container.requirements.general]/9, as a
polymorphic collection is a quasi-model of Container, as stated in the
reference.

 >
 >>>
 >>> H. local iterator and undefined behavior?: does the code have an
 >>> assertion at least? Can we not get rid of undefined behavior of
 >>>
 >>>   c.insert(c.begin(typeid(warrior)),juggernaut{11});
 >>>
 >>> ? That would surely be nice.
 >>
 >> There's an assertion: take a look at
 >>
 >> 
https://github.com/joaquintides/poly_collection/blob/master/include/boost/poly_collection/detail/poly_collection.hpp#L645-L658
 >>
 >
 > Ok. Hm. So maybe I don't quite get we have
 >
 > c.insert(c.begin<juggernaut>(),juggernaut{10}); // compile time error
 > c.insert(c.begin(typeid(warrior)),juggernaut{11}); // undefined behavior

The difference is that in the former, the type of the iterator is 
associated to
warrior (I assume you meant "c.begin<warrior>()") at compile time, whereas
in the former this info is dynamic and an assertion is the best we can get.

 > presumably because we may not know the type, so we say
 >
 > c.insert( c.begin(typeid( obj )), std::move(obj) );
 >
 > ? Does it need to be an iterator? Perhaps
 >
 > c.insert( segment_position{0}, std::move(obj) );
 >
 > could work, guaranteeing that no undefined behavior can happen.
 > Otherwise, we should seriously consider throwing instead.

I don't think throwing is the right approach here, as we are penalizing
users who do the right thing and don't mix values with iterators
improperly.

 >>> O. I wouldn't mind seeing separate graphs for 0-300 elements.
 >>
 >> I can extend the graphs to cover that part, but I don't see the point of
 >> using
 >> this library for a handful of elements,don't you think?
 >
 > Why not? The elements may be relatively few, but fat. This fits
 > exactly my use case.

Noted. Will extend the plots, then.

 >>> S. The test are testing best possible scenario; a more realistic test
 >>> would be to copy pointers to an std::vector<base*>, shuffle it and run
 >>> update on that.
 >>
 >> Sorry if I am not getting your question, but is this not the line
 >> labeled "shuffled_ptr_vector"
 >> in the plot?
 >
 > Yes, sort of, but I'm saying that very often one wants to copy
 > pointers from objects in base_collection into std::vector<base*> to
 > rearrange the elements somehow (say, your game entities need to be
 > sorted wrt to distance from the avatar). I still expects
 > base_collection + std::vector<base*> + shuffle to perform somewhat
 > better than ptr_vector + shuffle, but it would be interesting to see.

Sorry again but I don't get it yet. I don't quite understand which 
particular
data structure you'd like me to compare base_collection against.

Joaquín M López Muñoz