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

Subject: Re: [boost] [review] Review of PolyCollection starts today (May 3rd)
From: Thorsten Ottosen (tottosen_at_[hidden])
Date: 2017-05-11 16:18:25

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ó:
>> Hi Joaquín (and Ion),
>>
>> [...]
>>
>> A. OO programming and copyability

> Technically, this is doable and, at first blush, simple, since all
> element copying and
> assignent is centralized in a single wrapper class:
>
>
> Another possibility is to use a copying traits class to let users
> customize this point,
> along the custom RTTI thing proposed by Ion. This looks to me even
> cleaner and
> more powerful.

Yeah, I guess I would need to see how client code looks like to form any 
opinion. Notice that classes in hierarchies often have a non-public 
copy-constructor for use in cloning. Identity management is just not 
like ints, and sometimes having classes that are neither (publicly) 
copyable or movable happens.

> in the end, elements in a base_collection
> must be copyable
> (strictly speaking, moveable) and this will force users to change their
> code

Yes, but it is likely that such types are used outside of the containers 
as well and therefore I think it is important to consider.

> Yes, this is trivial and looks useful. At the risk of bikeshedding,
> c.segment<warrior>()
> might be a better name.

I like it.

>
>> C. I think we talked about an make_overload() function to devirtualize
>> uses of base_collection.  Do we have such a beast in boost already? If
>> not, it might be a worth providing it with this library.
>
> hanna::overload is already here to the rescue:
>
> https://lists.boost.org/Archives/boost/2017/03/233001.php

Awesome!

>> D. Inside the segments you store std::vector. I could easily imagine
>> the need to store something else, say a flat_set or a container
>> suitable for non-movable, non-conpyable types (say a variant of deque).
>> Therefore I would love to have a second defaulted argument set to
>> std::vector. Now this is a template, template parameter which
>> complicate things ... so in a sense a policy with a nested template
>> alias could do the trick.
>
> Of all your proposals this is the one I have most concerns about:
> element contiguity is such
> a key property that basically the whole library implicitly depends on
> it, code- and
> designwise. Policying this aspect away looks to me, in the absence of
> cogent use cases,
> an exercise in overdesign and a lot of work.

I'm just thinking out loud here. So one option would be to require that 
the container is contiguous (flat_set fits this). I was under the 
impression that you rely heavily on having random access iterators on a 
segment, but not on actual contiguity of the elements in a segment. We 
would probably also need some way to get the segment container, say,

   auto& vector = c.segment_container<warrior>();

so why would anyone want to use a flat_set internally. Well, fast 
lookup. The alternative today is to copy the pointers to flat_set/vector 
and use that.

Why would anyone want to use batch_deque 
(http://erenon.hu/double_ended/double_ended/examples.html#double_ended.examples.batch_deque_usage)? 
Well, non-copyable, non-movable types. For example, when I need to load 
a Bayesian network in my work, it maps exactly over to a set of
nodes that each must be loaded once and then kept in memory. Having the 
no-move guarantee ensures that pointers to the nodes can be shared 
freely without any worry that the object reference is not stable.

Anyway, if its a lot of work, I wouldn't put it high on the wish list.

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

>> 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. We are moving a hash_map of std::type_index keys and 
std::unique_ptr<segment> values. Neither of those should throw. And we 
hopefully guarantee reference stability on moving a base_collection 
(that is, we don't move individual elements in the container)? I don't 
think the C++ standard requires a noexcept move for std::unordered, but 
suspect many implementations provide this guarantee
(we are basically swapping a handle). So I'm saying that we can 
guarantee noexcept if the unordered map guarantees it. Perhaps using 
boost::unordered is better than using the standard container.

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

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

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.

>
>> J. why ==,!= but not <,>,>=, <=
>
> Followed the interface of std::unordered_set. As segment order is
> unspecified,
> less-than comparison seems to make no sense.

Right. One would have to copy the std::type_index keys to a local 
buffer, sort it, and use that as the order. But it is hard to imagine a 
use-case.

>> M. using the identifier "concept" may require change in the near future?
>
> Good observation! But, is "concept" not going to be a context-dependent
> keyword
> Ã  la "final"?

Not sure. 
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2015/n4377.pdf 
specifies two keywords.
>
>> 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.

>
>> Q. is there no normal container size()/empty() ? docs say e.g.
>>
>>   cc.size(index)
>>   cc.size<U>()
>>
>>   but then later when we see the full base_collection interface they
>> are mentioned.
>
> There are normal size() and empty() member functions, they're described
> in the
> reference.

Sure, but in the section called Polymorphic collections they sometime 
appear as only segment specific, whereas in the declaration of the 
class, they show all members.
        
>> 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.

kind regards

Thorsten