Le 05/05/2017 à 22:10, Ion Gaztañaga via Boost a écrit :

I know a lot of boosters are willing to write a review of this great library, so please don't be shy! I've started to rad the documentation. The library is so good (as usual from JMLM) that I've not yet added a single issue to my possible review. This kind of boring ;-)

Hope I will have/take the time to send a review soon. Best, Vicente

El 06/05/2017 a las 5:53, Edward Diener via Boost escribió:

On 5/2/2017 7:46 PM, Ion Gaztañaga via Boost wrote:

...

Hi everyone,

The formal review of Joaquín M. López Muñoz's PolyCollection library starts today. [...]

* boost::function_collection

I could not understand from the documentation what it is I am supposed to be inserting into a function_collection. The tutorial did not explain this to me and the reference's technical explanation on this eluded me.

You can insert into a boost::function_collection<Signature> any entity that a std::function<Signature> object could be constructed from. For instance, boost::function_collection holds callable entities that can be invoked with a (convertible to) int argument and return a (convertible to) double result: double f(int n){return (double)n;} struct g { double operator()(int n)const{return (double)2*n;} }; boost::function_collection c; c.insert(&f); c.insert(g{}); double factor=3; c.insert([=](int n){return factor*n;}); for(const auto& x:c)std::cout<http://tinyurl.com/kddv9nz . Didn't you find this section sufficiently explanatory? Joaquín M López Muñoz

El 06/05/2017 a las 16:49, Edward Diener via Boost escribió:

The explanation you cite with the link above is a tutorial, not an explanation. Furthermore, perhaps for the sake of syntactical brevity, you cite an example in which a lambda function returns another lambda function !!! This may be exceedingly clever but it can hardly be a mainstream explanation of your functionality which most programmers would easily understand as how a function collection "works". Your examples above are a much better and more mainstream example of how the function_collection works, and even the short explanation you have given me should have been in the documentation.

Will think about how to make the intro part more accessible along the lines you suggest.

It is also hard to understand what the advantage of a poly collection of these objects entail over a more normal C++ collection ( vector, array etc. ) of std::function<Signature> objects, since the latter object type already represents a generalized callable construct in C++. Some of your performance tests suggest there is little or no advantage, so a discussion of this would have been welcome in the documentation.

Performance is actually the *only* reason for using Boost.PolyCollection as opposed to say std:.vector. Perfomance tests are not very conclusive about insertion times (VS favors Boost.PolyCollection, GCC and Clang std:.vector>), but processing times, which are the crux of the matter, definitely show the point of the library. Admittedly this section should be added a comments section where the results are discussed --otherwise they might be hard to interpret. Joaquín M López Muñoz

El 08/05/2017 a las 15:48, Adam Wulkiewicz via Boost escribió:

Ion Gaztañaga Via Boost wrote:

...

The formal review of Joaquín M. López Muñoz's PolyCollection library starts today. [...] The library looks very well and I think it'd be a valuable contribution to Boost.

Thank you!

But I'm wondering, would it make sense to expand the scope of the library? Besides storing polymorphic data of the same type based on run-time info to improve caching there are situations when data might be divided into hot and cold data based on compile-time info. E.g. a "vector" of tuples could internally store tuple of vectors and provide interface allowing to access tuples more or less transparently. Storing hot and cold data in different but contigeous parts of memory would also improve caching. Since the principle is similar, would it have sense to have both types of collections in one library? Not necessarily now, but if this was a good idea then the name of the library would have to be changed into something more general.

IMHO this is an entirely different beast that happens to share the same underlying data structure as Boost.PolyCollection, but the apropriate interface would look different: no type registration, no type restitution, typed local_iterator's should have to go, etc. I think this would be best served by another, unrelated library.

I noticed that in the documentation a word "container" is used WRT poly collections. AFAIU this is not correct because poly_collection doesn't meet the requirements of C++ container as defined in the standard, i.e. allocator_traits::construct should be called only for the element type (23.2.1.3) but poly_collection contains std::unordered_map and packed_segment contains std::vector which constructs objects of their own value types. Also Models call operator new in make function. If that's correct and I'm not missing anything then I suggest using the word "collection" consistently in the docs.

Throughout the docs the word "container" is used in a non-standardese sense, as you correctly point out. On the reference, however, the concept PolymorphicCollection is defined as a refinement of PolymorphicContainer (http://tinyurl.com/m9yh3hq ), which is explicitly defined as resembling, but not the same as a standard Container. The part about 23.2.1.3 is not listed among the differences, and I should include it as well (thanks!). BTW, the standard itself is rather lousy with respect to the Container concept. For instance, [forwardlist.overview]/1 says "A forward_list is a container that supports forward iterators..." only to state in the next parapragh that "A forward_list satisfies all of the requirements of a container (Table 96), except that the size() member function is not provided and operator== has linear complexity." So, in the end, forward_list is *not* a container :-) Joaquín M López Muñoz

Gavin Lambert Via Boost wrote:

On 9/05/2017 01:48, Adam Wulkiewicz wrote:

...

I noticed that in the documentation a word "container" is used WRT poly collections. AFAIU this is not correct because poly_collection doesn't meet the requirements of C++ container as defined in the standard, i.e. allocator_traits::construct should be called only for the element type (23.2.1.3)

On that note, do you know of a more-comprehensible-than-standardese guide on how allocator_traits is supposed to be used for node-based custom container types? I've tried to figure it out a couple times but I'm sure I'm missing important points.

No, sorry, I'm not aware of any literature regarding it, though it doesn't mean it doesn't exist. I don't consider myself an expert in this area. I'd suggest to check out several STL implementations and Boost.Container's code for hints. Adam

On 13/05/2017 12:50, Glen Fernandes wrote:

What do you want to know?

1. The storage for the node should be allocated with the Allocator's 'allocate()', for an allocator instance 'a' whose value_type is the containers node type (i.e. 'a' can be achieved by rebinding an existing allocator instance in the normal way).

2. The node object itself would be constructed in the normal way - e.g. placement new to construct the node object.

3. The containers' value_type object within the node must be constructed by allocator_traits<U>::construct(u, p, args...) where u of type U is a rebound copy of the allocator such that the allocator's value_type is the container's value_type.

4. Similar to 3, for destruction of the container's value_type object should be destroyed by allocator_traits<U>::destroy(u, p)

5. Similar to 2, the node object is destroyed in the normal way - e.g. invoking the destructor of the node type.

Yeah, that's what it sounded like it said. But those rules seem very peculiar to me. Why wouldn't you use allocator_traits<node>::construct to construct the node type as well instead of using placement new directly? That way you only ever need one allocator instance, that for the node type. Why is it sensible to call allocate with a different type than construct, if the reason to not call construct is to avoid leaking the node type externally? In particular, these rules seem to basically require that the node type be trivially-constructible, because you can't legally call the node constructor and then call the value constructor where the value is a field of the node; you'd have to construct the node, destroy the value, then re-construct the value, which seems well over the line into crazypants territory. It all seems very arbitrary to me.

On 15/05/2017 11:12, Glen Fernandes wrote:

On Sun, May 14, 2017 at 7:02 PM, Gavin Lambert wrote:

...

In particular, these rules seem to basically require that the node type be trivially-constructible, because you can't legally call the node constructor and then call the value constructor where the value is a field of the node; you'd have to construct the node, destroy the value, then re-construct the value, which seems well over the line into crazypants territory.

It all seems very arbitrary to me.

No. You could also design the node type to contain a std::aligned_storage_t object (instead of containing a value_type object).

That way after you construct the Node type with ::new(x) Node(args...); you an use std::allocator_traits<U>::construct(u, address, args...) with the address of that aligned storage.

Apologies for the delayed response, but I was distracted by other things. If the node actually contains aligned_storage rather than T, doesn't that then require reinterpret_casting everywhere (since everything will expect a T*, not an aligned_storage_t<>*)? Isn't that usually considered a bad thing? It also seems really error-prone, since allocator_traits::construct/destroy accept pointers of all types, not just their parameterised type, and then act based on the received type. So given: struct node { node* next; std::aligned_storage_t storage; }; using alloc_traits = std::allocator_traits<T>; using node_traits = typename alloc_traits:: template rebind_traits<node>; alloc_traits::allocator_type m_alloc; node_traits::allocator_type m_node_alloc; // m_node_alloc(m_alloc) This code looks correct at a glance, but is horribly horribly wrong: node* n = node_traits::allocate(m_node_alloc, 1); ::new(n) node({ nullptr }); // not allowed to call construct? alloc_traits::construct(m_alloc, std::addressof(n->storage)); // ... alloc_traits::destroy(m_alloc, std::addressof(n->storage)); n->~node(); // not allowed to call destroy? node_traits::destroy(m_node_alloc, n, 1); (The double-construction of storage isn't the wrong part -- we're relying on it being a trivially-constructible type.) This compiles, and it default-constructs and then destroys a T inside node, right? No, since storage is the wrong type it ends up calling the storage-POD constructor and destructor, not T's. Despite alloc_traits supposedly being the traits for T. Why is the allocator even templated on this type when it doesn't actually use it? To make that code actually behave as expected, you need to reinterpret_cast(n->storage). And you need to remember to do that everywhere, and the compiler won't help you because it will happily compile with the wrong behaviour if you forget. (Only the allocator parameter is type-checked, not the address parameter.) Am I missing something? This seems a bit broken. Granted it's easy enough to make this safe once you're aware of it, but it seems like a way-too-easy trap to fall into. eg. this would be a "safe" node: struct node { explicit node(node* n = nullptr) : next(n) {} node* next; T& value() { return reinterpret_cast(storage); } private: std::aligned_storage_t storage; }; But of course now it's not a POD. One other thing that the lax type-checking does allow is this: node* n = node_traits::allocate(m_node_alloc, 1); ::new(n) node(); // not allowed to call construct? node_traits::construct(m_node_alloc, std::addressof(n->value())); // ... node_traits::destroy(m_node_alloc, std::addressof(n->value())); n->~node(); // not allowed to call destroy? node_traits::destroy(m_node_alloc, n, 1); (Specifically not actually using m_alloc or alloc_traits any more.) Which seems like it should be illegal (despite being convenient, since it means storing only one allocator), although a StackOverflow thread claims that it's intended behaviour.

On Thu, Jun 15, 2017 at 4:17 AM, Gavin Lambert via Boost wrote:

If the node actually contains aligned_storage rather than T, doesn't that then require reinterpret_casting everywhere (since everything will expect a T*, not an aligned_storage_t<>*)? Isn't that usually considered a bad thing?

Yes., and...

It also seems really error-prone,

Yes. :) i.e. It is easy to make the mistake you mentioned, among others. The model isn't nice (but it is what we have, until someone designs a less terrible one). Glen

El 10/05/2017 a las 17:56, Hans Dembinski via Boost escribió:

Hi,

I am not a Boost author, but I think I am able to give a review of PolyCollection, so here it goes.

Thanks for your review!

[...]

...

- What is your evaluation of the documentation? [...]

boost::function_collection was not so clear to me. It is nice to keep the narrative of game development going, but like someone said before, I think it would help to give a simpler example. I felt that the benefit of using boost::function_collection was not so clearly presented as for boost::base_collection. The function pointers are all the same size, so how exactly does the optimisation enter? I assume it is not about memory allocation here, but about sorting equal function signatures into homogeneous blocks to improve branch prediction and locality, but I am not sure.

I have to think over the boost::function_collection given that it does't look as clear as I expected... As you correctly guess my aim was to have a single narrative, but seems like that's not working so well. Regarding the benefits of boost::function_collection<Signature> with respect to std::vector, memory allocation improves as well: except where small object optimization applies, each std::function object stores a pointer to a heap-allocated copy of the wrapped callable entity passed by the user; boost::base_collection, on the contrary, stores same-type callable entities contiguously. (If you are really curious, a segment of a boost::function_collection is composed of *two* vectors, one for the callable entities proper and another storing std::function-like objects pointing to the former. Think of it as a std::vector constructed with such a smart memory allocator that (same-type) wrapped callable entities all happen to lie sequentially in memory.)

[...]

...

- Did you try to use the library? With what compiler? Did you have any problems? I tried to compile the tests on a Mac with Apple-clang 8.0.0. It worked after I manually specified "cxxflags=-std=c++11" in the b2 call. By the way, it would be great if b2 used the highest standard that is available by default.

It's weird because the Jamfile does have this flag already: https://github.com/joaquintides/poly_collection/blob/master/test/Jamfile.v2 I guess the snapshot provided from the Incubator might be oldish and not include that... I can't check right now because blincubator.com is not responding :-(

[...]

...

- Do you think the library should be accepted as a Boost library? Yes.

Thank you! Joaquín M López Muñoz

El 11/05/2017 a las 9:46, Hans Dembinski escribió:

I tried to compile the tests on a Mac with Apple-clang 8.0.0. It worked after I manually specified "cxxflags=-std=c++11" in the b2 call. By the way, it would be great if b2 used the highest standard that is available by default.

...

It's weird because the Jamfile does have this flag already:

https://github.com/joaquintides/poly_collection/blob/master/test/Jamfile.v2

I guess the snapshot provided from the Incubator might be oldish and not include that... I can't check right now because blincubator.com is not responding :-( It seems I got the right version, I checked out from github, not the incubator. My version of the Jamfile has these lines

project : requirements <toolset>gcc:<cxxflags>-std=c++11 <toolset>clang:<cxxflags>-std=c++11 ;

I am not a Boost.Build expert, but that looks ok to me. Nevertheless, when I run just ./b2 in the "tests" folder, it tries to compile but fails. When I run ./b2 cxxflags=-std=c++11, the tests compile fine.

I'm no Boost.Build expert either. A shot in the dark: maybe Apple-clang has a different toolset than "regular" clang? Joaquín M López Muñoz

El 10/05/2017 a las 22:33, Thorsten Ottosen via Boost escribió:

Hi Joaquín (and Ion),

[...]

A. OO programming and copyability of classes is not something that everybody is going to like. The normal thing is to derive from boost::noncopyable to get rid of a bunch of undesired behaviors. Would it be possible for the library to pick up a private or protected copy-constructor when needed, possible via a friend declaration? I think many uses of this library will also store pointers to the objects in other collections, e.g. vector, and as members so being able to have your hierarchy non-copyable while allowing copyability within the container is important IMO.

Technically, this is doable and, at first blush, simple, since all element copying and assignent is centralized in a single wrapper class: https://github.com/joaquintides/poly_collection/blob/master/include/boost/po... 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. I have no strong objection against including ths feature in whatever form, but don't particularly like it either --in the end, elements in a base_collection must be copyable (strictly speaking, moveable) and this will force users to change their code by writing the necessary ctors, so requiring an extra layer of boilerplate (declaring friends etc.) is just more hassle.

B. I miss range versions of the various iteration patterns so I can use them directly with a range-based for. E.g. instead of

for( auto i = c.begin<warrior>(); i != c.end<warrior>(); ++ i )

I should be able to say

for( auto& : c.range<warrior>() );

Yes, this is trivial and looks useful. At the risk of bikeshedding, c.segment<warrior>() might be a better name. Unfortunately there's no std naming practice here to follow on, unless someone proves me wrong.

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

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.

[...]

...

- Do you think the library should be accepted as a Boost library?

Yes.

Thank you!

*Specific comments*

A. why is subaddress() returning void* instead of T* ?

Because only void* is needed: subaddress() is used in poly_collection/detail/segment.hpp as a client of the type-erased virtual interface defined in https://github.com/joaquintides/poly_collection/blob/master/include/boost/po...

B. is the void* stuff like this

virtual range emplace( const_base_iterator p,void (*emplf)(void*,void*),void* arg) { return range_from(s.emplace(iterator_from(p),emplf,arg)); }

needed ? That is, is there no way to use real ans specific types?

This is connected to A, and in fact gives me the opportunity to comment on one of the more beautiful (IMHO) pieces of the lib :-) The implementation of a typical emplace(args...) function just forwards the args to the corresponding allocator construction call. The problem with Boost.PolyCollection is that this construction happens inside a class implementing a virtual interface (the one mentioned before), and this interface can't have a member function template able to accept(args...). We have a type erasure wall, if you wish. So the workaround is to define a type-erased callback (the emplf bit) that is invoked from the virtual class implementation and provided by the frontend of poly_collection, where the types of (args...) haven't been erased. Take a look at https://github.com/joaquintides/poly_collection/blob/master/include/boost/po...

C. Does value_holder<T>::data() need to return void*

It could return T*, but that's not needed, as data() is used for placement new.

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.

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.

F. I understand the layout to be roughly std::unordered_map ... this does not quite match diagram on page 2 of documentation, that is, you are missing an indirection.

You're right, but the diagram is merely explanatory and I wouldn't want to complicate it to no avail. In fact, the segments are pointed to from what looks like a small vector of three elements (light blue), which is also not a correct depiction of a std::unordered_map internal structure. In the end, all these indirections don't affect performance in any significant way (workload is in the segments proper).

G. tutorial: consider using override where appropriate

Noted, will do.

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

I. why emplace_pos/hint but not insert_hint/pos ?

This is insert(it,x). As for the naming, we have emplace(args...) emplace_hint(it,args...) emplace_pos(local_it,args...) insert(x) insert(it,x) insert(local_it,x) which follows std conventions except for "emplace_pos". I had to made that name up because, in the standard, fixed position emplace only happens in sequence containers where the name is simply "emplace", but I can't use "emplace" as emplace(it,args...) would collide with emplace(args...) (which sequence containers don't have).

J. why ==,!= but not <,>,>=, <=

Followed the interface of std::unordered_set. As segment order is unspecified, less-than comparison seems to make no sense.

K. clarify that

boost::poly_collection::for_each ( //restituted types c.begin(),c.end(),[&](const auto& x)

loops over all elements or only the specific.

Loops over all elements, doing type restitution on those marked. Noted, will clarify.

L. It could be good to have a performance test of erase in the middle/front.

I can do that. Interpretation is going to be tricky, as the compared data structures differ wildly wrt erasure.

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

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?

P. clarify test are without use of reserve

Noted, will do.

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.

R. dumb question: is there any thing in your code that requires std::is_polymorphic_v<Base> for base_collection ? If not, then perhaps one should be able to avoid that and work completely with type restitution ? In some sense, you could create a hierarchy where classes a memcopyable and without a single virtual function.

Actually, std::is_polymorphic_v is enforced on the reference but not anywhere in the code. I guess I preferred to be conservative here. As for working with type restitution alone, I think this scenario would be best served by a potential variant_collection, which was discussed at https://lists.boost.org/Archives/boost/2017/03/233001.php

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?

That's it. Great work :-).

What a thorough review! Thank you, Joaquín M López Muñoz

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

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

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

El 15/05/2017 a las 16:13, Thorsten Ottosen via Boost escribió:

...

...

...

...

D. Implementation of equality: do we need to be set like semantics

My bad. Your code does what the docs say. You have this

// TODO: can we do better than two passes?

By that, do you mean that the first pass is the size() comparison?

OK, now I get it. Yes. the size() comparison does a first pass of both containers' internal std::unordered_maps, and I wondered whether we can come up with something smarter that avoids that.

...

...

...

...

E. should the test check (perhaps via static_assert) the conditions under which move-construction and move-assignment is noexcept? (sorry

...

...

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.

I guess some vendors wanted freedom, and then gave users the near impossible task of tracking no-except/except impacts through their code bases. Now, you use =default for all the move operations, so I think they are required to be deduced to be noexcept exactly when they can be. Though a static assertion in the tests can track any fault in that logic.

If one ever puts base_collection's into a container, you are in for a huge penalty when the container operation falls back on copying.

Fallback copying cannot occur to the best of my knowledge: [container.requirements.general]/Notes: "Those entries marked “(Note A)” or “(Note B)” have linear complexity for array and have constant complexity for all other standard containers." As for noexcept in std unordered associative containers, I don't have a clue why move construction is not marked conditionally noexcept the way move assignement is... given this messy state I'd prefer to rely on =default before committing to any noexcept guarantees.

...

...

...

...

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. [...] So take the processing test. You already compare against a shuffled ptr_vector<T>. So far so good. Now take a base_collection<T> as is also done. Then take the address of every element in the base

collection and put them into a vector<T*>. Now shuffle this vector<T*>'s content like you did for ptr_vector. Then compare the processing time over a ptr_vector with the processing over the vector<T*>.

I claim this is a slightly more realistic test because one often wants to impose an order of some or all of the elements in the base_collection<T> before processing/iterating them somehow. So you won't always access the items in the order induced by the base_collection<T>. That's why I said that the current test is a best-case scenario, and there is no need to change that test. But I think it would be useful to see how much better your library is when access is not segment-sequential even though storage is.

I did that with this testing shuffled_base_collection class template: template<typename Base> struct shuffled_base_collection { template<typename T> void insert(const T& x) { bc.insert(x); } template<typename F> void for_each(F f) { std::for_each(v.begin(),v.end(),[&](Base* x){f(*x);}); } void prepare_for_for_each() { std::for_each(bc.begin(),bc.end(),[&](Base& x){v.push_back(&x);}); std::shuffle(v.begin(),v.end(),std::mt19937(1)); } private: boost::base_collection<Base> bc; std::vector v; }; (Complete performance program attached for your experimentation). Results for Visual C++ 2015 in 32-bit (x86) release mode, Windows 7 64-bit, Intel Core i5-2520M @2.5GHz, shuffled_base_collection is the fourth column: for_each: n;ptr_vector;sorted ptr_vector;shuffled ptr_vector;shuffled base_collection;base_collection;base_collection (poly::for_each);base_collection (restituted poly::for_each) 1000;68.6908;28.0432;86.3083;94.0958;37.7935;30.107;29.0816 2000;66.4786;27.1926;91.2408;96.0413;35.2004;27.8589;26.583 3100;65.5093;26.8698;89.2557;93.8447;34.4803;27.2731;26.1223 4310;64.4793;27.1499;89.499;98.0149;35.1578;28.2978;26.5429 5640;64.266;26.9044;91.033;98.202;34.2633;27.501;25.8809 7105;64.0913;26.8572;91.0014;97.3875;33.7854;27.4859;26.5453 8715;63.7974;27.3087;91.9985;98.399;34.2015;27.2596;25.599 10485;65.3485;26.5905;94.7418;97.5851;33.7521;27.6211;26.5611 12430;64.7723;27.3904;96.0209;99.1571;34.043;27.2985;26.1444 14575;64.2452;27.1067;96.5124;97.7042;34.5654;27.4023;25.8673 16930;65.1636;27.3421;98.1957;98.6361;34.0196;27.3581;25.9065 19520;64.7248;27.515;99.7822;99.5556;33.8953;27.5236;26.1173 22370;65.5374;27.8343;101.01;98.5953;33.8068;27.7628;27.0117 25505;65.0315;27.0511;103.225;101.638;34.2136;27.0208;26.2058 28955;64.1178;27.5933;103.772;105.797;33.9232;27.4988;26.231 32745;64.029;28.1792;103.421;106.625;33.8092;27.3831;25.794 36915;64.8421;28.1159;104.303;107.454;34.0542;27.405;25.7482 41505;65.1041;28.1572;105.835;108.924;34.07;27.1529;25.7295 46550;65.1797;27.8241;107.201;111.251;34.6232;27.6993;25.7345 52100;64.4235;28.0879;106.881;111.354;33.8314;27.0135;25.7227 58205;64.6465;27.9511;107.758;110.244;34.211;27.1424;25.8198 64920;65.1627;27.8584;110.97;111.413;34.7061;27.5941;26.0383 72305;65.5236;28.4969;111.552;112.634;34.0255;27.8747;25.7921 80430;66.1873;28.6039;115.026;114.442;34.3514;28.2707;25.6547 89365;66.3345;29.7042;119.888;114.368;33.976;27.5066;26.405 99195;67.5842;29.8768;132.691;118.178;33.8057;27.5137;26.3577 110005;67.502;33.2295;137.329;119.368;33.9743;28.261;25.8561 121900;67.8779;32.8886;144.397;119.939;34.0421;27.5768;26.1762 134980;73.2615;35.4748;215.428;150.062;35.1048;27.9387;26.3445 149370;69.5914;39.4097;166.049;132.759;35.3813;28.1609;26.5035 165195;70.0795;36.9757;176.128;125.824;35.4784;28.0991;27.1848 182605;70.678;39.4236;184.899;132.561;34.7531;27.9232;26.7449 201755;69.804;41.916;189.486;147.688;34.5916;28.4368;26.4968 222815;70.9049;43.3167;197.706;151.125;35.4652;28.6605;27.8671 245985;70.03;53.1854;201.855;164.847;35.7549;28.4426;27.1877 271470;69.6931;46.2775;209.332;179.249;36.2631;29.0661;28.4608 299505;70.9044;47.3569;212.374;194.289;36.024;29.2358;27.8824 330340;70.5898;47.0813;211.55;198.904;37.2955;29.1048;28.3034 364260;69.3568;48.0286;216.136;213.392;36.4719;29.6492;28.947 401570;70.0784;55.6783;217.553;216.374;36.6151;29.8494;28.6781 442610;70.2452;55.8915;222.709;222.249;36.4878;29.7408;28.192 487755;70.0358;48.7904;222.94;229.27;36.3237;30.3672;28.6129 537415;70.3103;50.0021;221.074;231.909;37.1915;30.0791;28.471 592040;70.1439;55.2571;223.077;234.858;37.6925;29.8299;28.4722 652125;70.8862;51.2554;230.277;239.505;37.3451;30.2505;28.1771 718220;70.4251;49.5872;233.219;239.863;36.5727;30.2672;28.6706 790920;69.7149;55.3772;230.926;242.922;37.2833;30.2138;28.9888 870895;69.4214;51.0372;235.172;251.45;36.9112;30.0106;29.2397 958865;70.4314;51.3184;235.628;252.243;37.3236;30.2469;28.4398 1055630;70.0297;52.1747;240.768;253.405;36.8073;30.0849;28.7678 1162075;71.0985;50.314;247.533;259.274;37.3846;30.3551;28.422 1279160;71.061;55.4783;243.327;257.581;37.0938;29.5389;29.1207 1407955;70.1601;50.6091;247.387;264.074;37.0902;29.8258;28.5657 1549630;70.4848;50.497;246.17;264.641;36.97;30.0207;28.4441 1705470;69.8107;50.983;247.042;261.625;36.5883;30.2686;28.5624 1876895;69.9785;51.5235;252.602;266.711;36.9832;29.9705;29.0799 2065465;69.4235;51.4422;256.153;265.141;37.3256;29.9859;29.0338 2272885;69.8385;51.4589;250.552;266.472;37.3823;30.3282;28.4389 2501050;69.9755;55.2984;255.818;272.43;36.9822;29.7997;28.9513 2752030;69.9469;54.2768;256.759;266.995;37.3053;30.2714;28.5217 3028110;70.3192;50.6052;261.753;272.133;37.5515;30.1139;28.9316 3331795;70.5005;49.9084;266.412;277.529;37.3315;30.3557;29.0938 3665850;70.0603;56.1319;271.833;276.466;37.199;29.6312;29.383 4033310;70.3551;51.7834;270.162;276.077;37.2656;29.772;28.5666 4437515;70.1824;50.7757;278.203;278.845;36.9247;29.4452;28.7805 4882140;70.5786;49.2731;281.148;283.854;37.1183;30.1079;28.9781 5371225;70.0242;49.7885;285.602;287.699;37.0402;30.4146;28.411 5909220;69.9687;51.3314;284.474;282.396;36.4418;29.6589;28.3406 6501010;70.3126;55.6867;297.482;284.977;36.9394;30.0999;28.9472 7151985;69.8237;50.2656;295.983;286.696;36.7772;29.8695;28.7694 7868050;69.6268;55.6824;303.074;291.302;37.4062;30.572;29.7347 8655725;69.5738;50.8151;310.437;300.738;37.2501;30.0555;28.7516 9522170;69.8031;56.4064;317.517;301.382;36.8001;30.8586;28.9918 10475255;69.6152;50.142;331.536;302.847;37.3644;30.9883;29.0113 So, shuffled ptr_vector and shuffled base_collection seem to perform equally bad; I can't see any significant pattern here, which leads me to conclude shuffling destroys any cache friendliness elements might have due to the fact they come from a boost::base_collection. Joaquín M López Muñoz

El 15/05/2017 a las 19:46, Thorsten Ottosen via Boost escribió:

Den 15-05-2017 kl. 19:01 skrev Joaquin M López Muñoz via Boost:

...

El 15/05/2017 a las 16:13, Thorsten Ottosen via Boost escribió:

...

...

...

...

> D. Implementation of equality: do we need to be set like semantics [...] OK, now I get it. Yes. the size() comparison does a first pass of both containers' internal std::unordered_maps, and I wondered whether we can come up with something smarter that avoids that.

Hm. Yeah, I guess we have at least three options:

a) current version

b) omit check to "global" size() and let segment comparison deal with that

c) store the size in poly_collection

I think c) is not that attractive due to all the code to provide consistency. Whether a) is better than b) I guess will depend on the on the actual runtime data. I speculate that your current version is the best.

I think this variation of a) might perform better (code untested): template bool operator==( const poly_collection& x, const poly_collection& y) { typename poly_collection::size_type s=0; const auto &mapx=x.map,&mapy=y.map; for(const auto& p:mapx){ s+=p.second.size(); auto it=mapy.find(p.first); if(it==mapy.end()?!p.second.empty():p.second!=it->second)return false; } if(s!=mapy.size())return false; return true; }

[...]

...

So, shuffled ptr_vector and shuffled base_collection seem to perform equally bad; I can't see any significant pattern here, which leads me to conclude shuffling destroys any cache friendliness elements might have due to the fact they come from a boost::base_collection.

Thanks for quick update. It wasn't clear to me if your time includes the time to insert and prepare_for_for_each. If so, it would be fair to call v.reserve( bc.size() ); in prepare_for_for_each.

Timing does not include insert() or prepare_for_for_each().

Anyway, it is a bit surprising. Perhaps modern allocators are good at allocating same size objects closely and without much overhead ...

I think the similarity in performance between shuffled ptr_vector and shuffled base_collectin goes the other way around: once sequentiality is destroyed, it doesn't matter much whether elements lie relativley close to each other in main memory. Joaquín M López Muñoz

El 16/05/2017 a las 11:11, Thorsten Ottosen via Boost escribió:

Den 15-05-2017 kl. 21:21 skrev Joaquin M López Muñoz via Boost:

...

I think the similarity in performance between shuffled ptr_vector and shuffled base_collectin goes the other way around: once sequentiality is destroyed, it doesn't matter much whether elements lie relativley close to each other in main memory.

Ok. I guess (and there is no hurry) it will also be interesting to see for 0-1000 elements.

In my todo list.

I know its nice to have a graph that grows as a function of n, but I think the best thing would be make each data point be based on the same number of iterations. So I would use an exponential growth for n, n = 8, 16, 32 ... max_n and then run each loop x times, x being max_n / n.

Not sure why this is better than having homogeneous units all across the plot (namely nanoseconds/element). In any case the testing utilities sort of do the loop repetition the way you suggest, at least for small values of n: measure_start=high_resolution_clock::now(); do{ res=f(); ++runs; t2=high_resolution_clock::now(); }while(t2-measure_start(t2-measure_start).count()/runs; This runs the loop as many times as needed to at least occupy a min_time_per_trial slot (200 ms) so as to avoid measuring individual executions that are too small for the high_resolution_clock granularity. Then, of course, resulting times are normalized back to ns/element. Joaquín M López Muñoz

El 16/05/2017 a las 16:20, Thorsten Ottosen via Boost escribió:

Den 15-05-2017 kl. 21:21 skrev Joaquin M López Muñoz via Boost:

...

I think this variation of a) might perform better (code untested):

template bool operator==( const poly_collection& x, const poly_collection& y) { typename poly_collection::size_type s=0; const auto &mapx=x.map,&mapy=y.map; for(const auto& p:mapx){ s+=p.second.size(); auto it=mapy.find(p.first); if(it==mapy.end()?!p.second.empty():p.second!=it->second)return false; } if(s!=mapy.size())return false; return true; }

I not sure about this version. mapy.size() should be y.size() ?!?

My typo, it should read as you say: template bool operator==( const poly_collection& x, const poly_collection& y) { typename poly_collection::size_type s=0; const auto &mapx=x.map,&mapy=y.map; for(const auto& p:mapx){ s+=p.second.size(); auto it=mapy.find(p.first); if(it==mapy.end()?!p.second.empty():p.second!=it->second)return false; } if(s!=y.size())return false; return true; }

Or do you need sx and sy? But also, once all the segments have been compared in the loop, you know the x.size() == y.size() ...

Not so: consider the case where y has a segment (let's call it seg) which is not present in x; in this case the for loop would pass succesfully and seg wouldn't have been hit, and we'd thus erroneously return true. That's why we need the extra check on size. In other words, we can't determine equality by only going through x's segments. Joaquín M López Muñoz

On 15/05/2017 19:46, Thorsten Ottosen via Boost wrote:

...

As for noexcept in std unordered associative containers, I don't have a clue why move construction is not marked conditionally noexcept the way move assignement is... given this messy state I'd prefer to rely on =default before committing to any noexcept guarantees.

Sounds reasonable. As I stated, it appears to me that you will take advantage of noexcept if it exists in the standard container.

It might be related to sentinel nodes. They are used in lists and ordered associative containers from Dikum STL from early versions. Sentinel nodes can't be transferred if source container invariants must be preserved. Reviewing Dinkum STL code it seems that std::unordered_xxx uses std::list internally, so sentinel nodes are allocated when move constructing an unordered_xxx and thus move constructor can't be noexcept. Ion

On 5/10/17 2:46 PM, Edward Diener via Boost wrote: algorithms.cpp

...

algorithms.cpp(12): fatal error C1083: Cannot open include file: 'boost/poly_collection/algorithm.hpp': No such file or directory

1) Clone beneath the 'your_boost_tree_root/libs' directory 2) run 'b2 headers' from 'your_boost_tree_root' after you clone

...

Did I mention I am using Microsoft Visual Studio on Windows?

Full disclosure, I have had this problem twice before when trying to review libraries. In the past I have simply given up. But I want to contribute something back since my own library will be reviewed soon.

This is a common situation. The boost directory structure doesn't play nice with new libraries which are not already part of boost. When I put the safe numerics library into the incubator, I used path names for includes so that one would not have to do the above procedure for the new library. This permitted one to build and run the tests and examples, but of course created consternation of another sort. Robert Ramey

On Wed, May 10, 2017 at 2:46 PM, Edward Diener via Boost wrote:

1) Clone beneath the 'your_boost_tree_root/libs' directory 2) run 'b2 headers' from 'your_boost_tree_root' after you clone

Okay, this worked and I was off to the races! - What is your evaluation of the design? It seems pretty straightforward. Given an explanation of the problem the design of the collection feels natural and right. Most of the container interface is standard boilerplate and so was immediately familiar. - What is your evaluation of the implementation? I have not looked at the implementation, only the public interfaces. - What is your evaluation of the documentation? I was able to find everything I looked for. The diagrams look great and really helped me understand the nature of the problem and how the library solves it. The author makes container performance claims which are then backed up with benchmarks across a variety of compilers and systems. My preference is for the style of documentation where exposition precedes each member declaration (e.g. http://www.boost.org/doc/libs/1_64_0/doc/html/boost_asio/reference/io_servic...) but the presented style is also workable. - What is your evaluation of the potential usefulness of the library? These containers look quite useful, and I can think of at least a couple of instances where I have rolled my own inferior solutions to accomplish the same result. - Did you try to use the library? With what compiler? Did you have any problems? I had some trouble getting going using the Microsoft Visual C++ toolchain on Windows, but this had to do more with how the repository needs to be cloned into a subtree of a boost library installation rather than the proposed library itself. I built the example using the compiler version 14.10.25017. Then I added my own code to one of the example sources to get a feel for how the library worked. I had no trouble at all writing correct code. My attempts to abuse the library APIs were met with resistance from the compiler in the form of compilation errors. - How much effort did you put into your evaluation? A glance? A quick reading? In-depth study? I spent about an hour on it. I exercised mostly the boost::base_collection container in my own program. I expect the containers to work similarly. I have not used boost::any so I can't comment on the any_collection. I focused on the "interesting" member functions, the ones which operate differently from their standard container counterparts. I assume the non-interesting functions act with predictable results. - Are you knowledgeable about the problem domain? Yes. I have implemented many containers with conforming allocator support of all varieties. I have used Boost.Intrusive heavily to create complex containers and I have dabbled with some Boost.MultiIndex. - Do you think the library should be accepted as a Boost library? This library is tightly focused on solving a specific, worthwhile problem and does so in a way that feels natural and "boosty." So YES. - Questions Iterators returned by begin<T>() cannot be compared to iterators returned by end(typeid(T)). Is this an oversight or a consequence of the design? It seems to me they should be comparable. - Other comments: Iterators returned by begin<T>() produce a long, ugly compile error when compared against iterators returned by begin<U>() or end<U>(). I think the library could do better by producing a static_assert with a helpful message. Its not a showstopper but a suggestion. I echo the comments from other reviewers, a range<T>() function to allow range-for iteration of a segment should be added at the earliest convenience. I wouldn't hold up acceptance for it. Thank you to the author for putting together a polished library!

On May 17, 2017, at 12:12 PM, Joaquin M López Muñoz via Boost wrote:

Thanks for noticing this, will fix in the corresponding Jamvile.v2. By the way, algorithms.cpp need C++14 not because of make_unique (which is not used there) but for generic lambdas such as:

https://github.com/joaquintides/poly_collection/blob/master/example/algorith...

Yes, I forgot the details at the time, but this reminds me that generic lambdas were exactly the problem.

FWIW, algorithms is already marked as needing C++14:

https://github.com/joaquintides/poly_collection/blob/master/example/Jamfile....

so I guess you didn't use b2 for building for went directly with the compiler command line, right?

Yes, that is correct. I personally, don’t use b2 for building anything except boost itself. It seems too far afield from “normal” build environments to be useful in my own work. I was not really pointing this out as a problem with the library, but rather that I thought there was some mention of it being a c++11 library and then I found I need to use c++14 at some points. I suppose that is entirely due to the example code, though, and not the library itself. Perhaps a mention of the need for c++14 in some examples? None of this is a big deal, though. The bottom line is it seems to be a great piece of work. Cheers, Brook

On 23/05/2017 05:21, Joaquin M López Muñoz wrote:

...

"interspersedly" This word sounds a bit awkward to me.

Any less awkward synonim? For other readers' convenience, the statement in which the word appears is:

"This mechanism is rendered mostly useless when derived1, derived2 and derived3 elements are traversed interspersedly without a definite pattern."

"interleaved", perhaps?

...

"to explicitly forbid" split infinitive

At the risk of starting a style war, it is my understanding that split infinitives are okay when used wth caution. Here, the alternative:

"to forbid explicitly copying at"

seems (to me) less clear as it might be parsed as referring to some sort of explicit copying...

FWIW, as a native English (or dialect thereof) speaker, the original version sounds better to me, and not just because of the ambiguity of the alternative. As far as I am aware, objecting to split infinitives is out of fashion, and was never all that popular to begin with.