Boost logo

Boost :

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:


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

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

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


Boost list run by bdawes at, gregod at, cpdaniel at, john at