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

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
53 messages Options
123
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
El 11/05/2017 a las 4:46, Vinnie Falco via Boost escribió:
> [...]
> - 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.

Thank you!

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

You need to do an explicit cast (either direction) first, so it follows
comparison
can't be done directly. I preferred to require expilcit conversion
between the two
types of local iterator as it seemed to me safer from the user's code
point of view.

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

Will study the issue. I'm not sure I can improve the dagnostics but will
take a look.

Thank you for your review,

Joaquín M López Muñoz

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
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




_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
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<allocator_type>::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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
Gavin Lambert wrote:
> 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.

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.

Glen

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Gavin Lambert wrote:
> 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.

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.

6. Similar to 1, the storage for the node is deallocated with the
Allocator's deallocate() (for an allocator instance whose value_type
is the container's node type).

Glen

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
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.
>
> I'd like to encourage your participation as the proposed library is
> small and focused, and reviewers don't need to be domain experts to
> appreciate the potential usefulness of the library and propose
> improvements.
>
> PolyCollection implements fast containers of polymorphic objects.
> Typically, polymorphic objects cannot be stored directly in regular
> containers and need be accessed through an indirection pointer, which
> introduces performance problems related to CPU caching and branch
> prediction. Boost.PolyCollection implements a novel data structure that
> is able to contiguously store polymorphic objects without such
> indirection, thus providing a value-semantics user interface and better
> performance. Three polymorphic collections are provided:
>
> * boost::base_collection
> * boost::function_collection
> * boost::any_collection
>
> dealing respectively with classic base/derived or OOP polymorphism,
> function wrapping in the spirit of std::function and so-called duck
> typing as implemented by Boost.TypeErasure.
>
> The library can be found here:
>
>   Incubator:
>    http://blincubator.com/bi_library/polycollection/?gform_post_id=1643
>
>   Github:
>    https://github.com/joaquintides/poly_collection
>
> and the documentation here:
>
> http://rawgit.com/joaquintides/poly_collection/website/doc/html/index.html
>
> Please post your comments and review to the boost mailing list
> (preferably), the Boost Library Incubator. or privately to the Review
> Manager (to me ;-). Here are some questions you might want to answer in
> your review:

This is my review of PolyCollection,

>
> - What is your evaluation of the design?

I have no problem with the design as it succinctly covers the three
areas to which poly collections apply. These areas should be enough for
using any types with polycollections.

>
> - What is your evaluation of the implementation?

I did not look at it.

>
> - What is your evaluation of the documentation?

I have mentioned previously that I think the documentation should be
more specific about the types being used for the
boost::function_collection. While an example is good, as in the case of
the tutorial, and while a reference is good, as in the case of the
documentation for the insert member function, I found the former to be
too singular and special an example while I found the latter to be
highly technical and therefore hard to understand in general terms. A
better addition is simply to document in an explanation of ideas and
concepts exactly what types the boost::function_collection entails. I
assume it is any type which can be passed to std::function, but I do not
know if it can be a std::function object itself. Saying it is "Function
wrapping in the spirit of std::function" does not explain it adequately
to me. Also since std::function ( or boost::function if you will )
represents any callable it would be nice to understand why the
programmer would want to use boost::function_collection versus a
collection of std::function objects.

>
> - What is your evaluation of the potential usefulness of the library?

I see the library as being useful as an optimization over present
techniques in both speed and size terms. In effect it offers a choice
for end-users over normal C++ collections.

>
> - Did you try to use the library? With what compiler? Did you have any
> problems?

I tried it with gcc-7.1 in c++11 mode and it worked well.

>
> - How much effort did you put into your evaluation? A glance? A quick
> reading? In-depth study?

Mostly a slow reading and an attempt to understand why the library
should be used and how to use it.

>
> - Are you knowledgeable about the problem domain?

Somewhat knowledgeable, but not an expert in the type of optimizations
which polycollection use.

>
> And most importantly:
>
> - Do you think the library should be accepted as a Boost library?

I think the library should be accepted based on the fact that it offers
an alternative to normal collections which can prove valuable to
end-users, and that it is a polished library with few surprises. With
that said I think the library should document better the advantages and
practical situations that make polycollection superior to normal C++
collections, else an end-user will be puzzled about for what situations
it will be useful.

>
> For more information about Boost Formal Review Process, see:
> http://www.boost.org/community/reviews.html
>
> Waiting your reviews!
>
> Ion


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
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.



_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
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<sizeof(value_type), alignof(value_type)>
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.

Glen

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
El 14/05/2017 a las 22:33, 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.
>> [...]
>
> This is my review of PolyCollection,

Thank you for your contribution!

> [...]
>
>> - What is your evaluation of the documentation?
>
> I have mentioned previously that I think the documentation should be
> more specific about the types being used for the
> boost::function_collection. While an example is good, as in the case
> of the tutorial, and while a reference is good, as in the case of the
> documentation for the insert member function, I found the former to be
> too singular and special an example while I found the latter to be
> highly technical and therefore hard to understand in general terms. A
> better addition is simply to document in an explanation of ideas and
> concepts exactly what types the boost::function_collection entails. I
> assume it is any type which can be passed to std::function, but I do
> not know if it can be a std::function object itself. Saying it is
> "Function wrapping in the spirit of std::function" does not explain it
> adequately to me. Also since std::function ( or boost::function if you
> will ) represents any callable it would be nice to understand why the
> programmer would want to use boost::function_collection versus a
> collection of std::function objects.

Points taken, as we have already discussed them in the past days. I'll
try to improve docs
so as to make these aspects clearer.

(When you insert a std::function<Signature> object x, into a
function_collection<Signature>,
it is x that gets copied/stored rather than its underlying callable
entity. This is so because
std::function lacks functionalty to recover the wrapped callable entity
without statically
knowing its type, observe std::function::target does not type erase:
http://en.cppreference.com/w/cpp/utility/functional/function/target .
Incidentally, this
is the main reason why function_collection<Signature>::value type is *not*
a std::function, but an internall lookalike with the required extra
functionality.)

> [...]
>
>>
>> And most importantly:
>>
>> - Do you think the library should be accepted as a Boost library?
>
> I think the library should be accepted based on the fact that it
> offers an alternative to normal collections which can prove valuable
> to end-users, and that it is a polished library with few surprises.
> With that said I think the library should document better the
> advantages and practical situations that make polycollection superior
> to normal C++ collections, else an end-user will be puzzled about for
> what situations it will be useful.

Thank you,

Joaquín M López Muñoz

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 15-05-2017 kl. 00:14 skrev Joaquin M López Muñoz via Boost:
> 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
[snip]
>
> Sorry, I'm not getting you. The current implementation enforces exact
> segment match.
> Could you maybe elaborate/reword your question?

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?


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

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

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.

kind regards

Thorsten

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
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<base*>, 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<Base*>           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


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost

perf_thorsten.cpp (20K) Download Attachment
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
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
>>
>> 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.

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.


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


That is true, but as soon you hit code that calls std::move_if_noexcept,

http://en.cppreference.com/w/cpp/utility/move_if_noexcept

those move operations that are not marked/deduced noexcept will not be
in effect.

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


>
> 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<Base*>           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:

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

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

-Thorsten

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
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<typename Model,typename Allocator>
   bool operator==(
     const poly_collection<Model,Allocator>& x,
     const poly_collection<Model,Allocator>& y)
   {
     typename poly_collection<Model,Allocator>::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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 15-05-2017 kl. 21:21 skrev Joaquin M López Muñoz via Boost:
> El 15/05/2017 a las 19:46, Thorsten Ottosen via Boost escribió:

>
> I think this variation of a) might perform better (code untested):
>
>    template<typename Model,typename Allocator>
>    bool operator==(
>      const poly_collection<Model,Allocator>& x,
>      const poly_collection<Model,Allocator>& y)
>    {
>      typename poly_collection<Model,Allocator>::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;
>    }
>

Yeah, could be.

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

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

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.

kind regards

Thorsten


_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
Den 15-05-2017 kl. 21:29 skrev Ion Gaztañaga via Boost:

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

yikes

-T

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
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<typename Model,typename Allocator>
>    bool operator==(
>      const poly_collection<Model,Allocator>& x,
>      const poly_collection<Model,Allocator>& y)
>    {
>      typename poly_collection<Model,Allocator>::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() ?!?
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() ...

-Thorsten

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

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

Boost - Dev mailing list
In reply to this post by Boost - Dev mailing list
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<min_time_per_trial);
trials[i]=duration_cast<duration<double>>(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

_______________________________________________
Unsubscribe & other changes: http://lists.boost.org/mailman/listinfo.cgi/boost
123
Loading...