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

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.exampl... 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/po...

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, 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 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 + shuffle to perform somewhat better than ptr_vector + shuffle, but it would be interesting to see. kind regards Thorsten