Re: [boost] Performance comparison between ptr_vector and vector<cow_ptr<Shape> >, vector<copy_ptr<Shape> >
"Thorsten Ottosen" <tottosen@dezide.com> wrote in message news:<dph810$l4b$1@sea.gmane.org>...
David Maisonave wrote:
"Thorsten Ottosen" <tottosen@dezide.com> wrote in message news:<dpgu8s$e6k$1@sea.gmane.org>...
This gave:
Test performance for initializing and copying container of pointers.
vector<copy_ptr<Shape> > 1.42 s
boost::ptr_vector<Shape> 0.81 s
vector<cow_ptr<Shape> > 0.13 s
But this test is a bit unfair: we create copies of the vector, but we never mutate that copy. A fair test would mutate all the elements.
The cow_ptr is like a clone pointer and a shared pointer put together.
right.
It shares the pointer, until an attempt is made to access it via non-constant operator-> or operator*. If non-constant access is made, then it checks to see if it's reference counter is larger then
one. If so, it then performs the deep-copy, and releases the reference count.
This is very efficient, because there's a good chance that the using
code will never access all or any of the container objects in a non-constant manner.
well, if no objects are being mutated, we don't have to make a copy.
In practice I don't have a good estimate of how much data is touched, but imgaine that it can easily be it all. In that case I expect ptr_vector to win again (like it did in the other three categories).
The difference in efficiency will show up even more, when you have a
more complex type that takes more time to construct.
right, the above results has another string data member of size 100.
The test code uses a simple Shape class, which doesn't have much to it, but if you added more data members, and made the construction more complex, then the above test will be drastically different and it would show cow_ptr having a very high performance ratio.
it would also increase the likelihood that we would mutate the objects.
By the way, I believe you could add this type of COW logic to the existing boost pointer containers, and increase their efficiency.
It depends somewhat of the situation at hand AFAICT.
But there is an overhead to this logic,
right. ptr_vector uses vector<void*> internally to minimize binary size too. and runtime-space-wise, its optimal. whether that matters depends on the situation.
and you might have notice that some of the test show copy_ptr out performming cow_ptr. You could consider adding a policy option to the boost pointer containers, that would allow choosing between COW method and Clone-Always method.
perhaps, but I do fear such a thing would greatly complicate the implementation.
I also have some concerns on performance of COW in multi-threaded environments.
As for cow_ptr requiring copy-semantics, then I think that is a very poor idea. It must be possible to call new_clone() or similar.
I don't see anything wrong with requiring copy-semantics, and I don't like the idea of forcing the user to implement new_clone, because it makes using the smart pointer less generic. The built-in types have copy constructors, and so does most of the STL objects. To quote Scott Meyers [Effective C++]: ************************************************************************ ***************************************************** "If it's good enough for int's, it's good enough for me and my classes. It should be good enough for you and yours, too. Why introduce gratuitous incompatibilities with the conventions followed by the build-in types?" ************************************************************************ ***************************************************** A container of cow_ptr is more generic then boost pointer containers, because it doesn't require the type to have a clone method, or extra clone logic. If you want to use cow_ptr with legacy code, you can do so, with out having to break the interface. Imagine having legacy code, in which you already have an interface for an abstract type. If you want to create a container of pointers using boost pointer containers, you would have to make a lot of changes to existing legacy code, that could, or more then likely would introduce new bugs to the code. It's far safer to have a container that requires little - to no modification of existing code, and cow_ptr can do that as-is.
(Incidentally David you can disable the ADL warning in the project, or on the command line and they go away, quite why they don't with #pragma I don't know :-) ) It seems to me that this discussion is actually three orthogonal discussions. 1. How should cloning be implemented. Current implementation : A clone function which defaults to copy constructor (if accessible) for the static type of the container. Overridable using ADL. Alternative implementation: Use the copy constructor for the static type of the pointer passed in (which may be a more derived type than the static type of the container). It seems to me that the first has the disadvantage of making it relatively easy to provide an incorrect cloner that allows slicing. However this is relatively easy to avoid by making your hierarchy noncopyable, (Perhaps a way around this is to remove the default implementation of new_clone?) The second makes this harder. The default it gives you is more sensible but implementing this requires a cloner type to be stored along side each and every element in the container. Also if you do have a problem with slicing, there is no way of overriding the default behaviour. For example, this will slice with no fix possible. T* CreateT(); // return something derived from T cow_ptr<T> p(CreateT()); 2. Should ptr_ containers differ in interface from std containers. I've only just recently had a proper look at the ptr containers, and I do find the differences somewhat disconcerting. The map iterator dereferencing for example, is not what one is used to STL containers would expect. I think it will cause most people to stumble when they first start to use it. I can see the temptation to 'fix' interface problems in the std containers, but that comes at a cost of a learning curve and strange inconsitencies for the user. i->first and i->second isn't pretty, but we're used to it now, and I can't see the std containers changing. pop_back also is somewhat surprising, I haven't really thought this through, but could an innocent user in generic code write something like this and get unexpected results. (assume an exception free environment) typename Container::value_type v = container.back(); container.pop_back(); return v; ? 3. Should ptr_vector support copy on write semantics. Or could boost use a cow smart pointer? All of the performance comparisons shown so far that aren't affected by cow show nearly identical results. This is understandable since they are all implemented with the same container underneath. To test the copy on write behaviour more accurately, I changed the copy test so it mutated all of the objects. And I added shared_ptr to the types tested. Adding shared_ptr tests how a multithreaded cow ptr would behave if no mutations were to occur - some marshalling has to be done, some ref count twiddling, but no copying. Which makes it a better comparison against the ptr_vector which obviously copies all its objects. container populate copy operator[] iterator* std::vector<copy_ptr<Shape> > 2.52 s 2.53 s 1.06 s 1.08 s boost::ptr_vector<Shape> 0.64 s 2.61 s 1.09 s 1.08 s std::vector<cow_ptr<Shape> > 1.20 s 4.75 s 1.13 s 1.14 s std::vector<boost::shared_ptr<Shape> > 1.38 s 0.17 s 1.09 s 1.09 s The results are pretty much what you'd expect. shared_ptr performs well on the copy test, cow_ptr performs very poorly. I think you can read this as best/worst case scenario for COW. Best case copy on write performs 90% quicker. Worst case copy on write performs 100% slower. Like all situations like this you have to pick and choose the tool based on your needs. Sam PS I don't find the docs terribly easy to follow. Finding what a member means navigating each concept and base class until you find what you want. And working out the class hierarchy is not always that straight forward. For example, I wanted to find out the exact type of ptr_map::value_type. So I went to the ptr_map page, which has no members. And not even an obvious link to tell me which of the 4 "See also" pages is the next in the chain. Since ptr_map_adaptor is the base class I selected that. ptr_map_adaptor has no base class, so I assume that of the 4 "see also" links I probably want associative_ptr_container, as it sounds like it ought to be the next in line. When I get there I still don't have a value_type, but now I can see I probably want to look on the reversible_ptr_container page, where sure enough I find it. That would have been a lot easier if each class page listed the hierarchy and its place in it, rather than just listing them in a "See also" section. Even better than that would be if ptr_map and etc. listed ALL its members. This could presumably be automated?
Sam Partington wrote:
(Incidentally David you can disable the ADL warning in the project, or on the command line and they go away, quite why they don't with #pragma I don't know :-) )
It seems to me that this discussion is actually three orthogonal discussions.
1. How should cloning be implemented. Current implementation : A clone function which defaults to copy constructor (if accessible) for the static type of the container. Overridable using ADL.
Alternative implementation: Use the copy constructor for the static type of the pointer passed in (which may be a more derived type than the static type of the container).
It seems to me that the first has the disadvantage of making it relatively easy to provide an incorrect cloner that allows slicing. However this is relatively easy to avoid by making your hierarchy noncopyable, (Perhaps a way around this is to remove the default implementation of new_clone?)
It's not very sensible to make the hierarchy copyable, because you can run into slicing in other places then. As for the default, then I've been thinking about this too. It still won't catch that one missed a clone() function longer down the hiararchy.
2. Should ptr_ containers differ in interface from std containers.
I've only just recently had a proper look at the ptr containers, and I do find the differences somewhat disconcerting. The map iterator dereferencing for example, is not what one is used to STL containers would expect. I think it will cause most people to stumble when they first start to use it. I can see the temptation to 'fix' interface problems in the std containers, but that comes at a cost of a learning curve and strange inconsitencies for the user. i->first and i->second isn't pretty, but we're used to it now, and I can't see the std containers changing.
This is not to fix the interface, but to hide direct write-access to the pointer.
pop_back also is somewhat surprising, I haven't really thought this through, but could an innocent user in generic code write something like this and get unexpected results. (assume an exception free environment)
typename Container::value_type v = container.back(); container.pop_back(); return v;
?
I don't think so. The first statement won't compile. Secondly, your types should not be copyable.
3. Should ptr_vector support copy on write semantics. Or could boost use a cow smart pointer?
All of the performance comparisons shown so far that aren't affected by cow show nearly identical results. This is understandable since they are all implemented with the same container underneath.
To test the copy on write behaviour more accurately, I changed the copy test so it mutated all of the objects. And I added shared_ptr to the types tested.
Adding shared_ptr tests how a multithreaded cow ptr would behave if no mutations were to occur - some marshalling has to be done, some ref count twiddling, but no copying. Which makes it a better comparison against the ptr_vector which obviously copies all its objects.
container populate copy operator[] iterator* std::vector<copy_ptr<Shape> > 2.52 s 2.53 s 1.06 s 1.08 s boost::ptr_vector<Shape> 0.64 s 2.61 s 1.09 s 1.08 s std::vector<cow_ptr<Shape> > 1.20 s 4.75 s 1.13 s 1.14 s std::vector<boost::shared_ptr<Shape> > 1.38 s 0.17 s 1.09 s 1.09 s
The results are pretty much what you'd expect. shared_ptr performs well on the copy test, cow_ptr performs very poorly. I think you can read this as best/worst case scenario for COW.
right. I'm a bit surprised that the worst case is so bad.
Best case copy on write performs 90% quicker. Worst case copy on write performs 100% slower.
well, almost I guess it would make sense to repeat the test with different sizes of the containers. This is only for one size.
Like all situations like this you have to pick and choose the tool based on your needs.
Sam
PS I don't find the docs terribly easy to follow. Finding what a member means navigating each concept and base class until you find what you want. And working out the class hierarchy is not always that straight forward.
For example, I wanted to find out the exact type of ptr_map::value_type. So I went to the ptr_map page, which has no members. And not even an obvious link to tell me which of the 4 "See also" pages is the next in the chain.
Since ptr_map_adaptor is the base class I selected that. ptr_map_adaptor has no base class, so I assume that of the 4 "see also" links I probably want associative_ptr_container, as it sounds like it ought to be the next in line. When I get there I still don't have a value_type, but now I can see I probably want to look on the reversible_ptr_container page, where sure enough I find it.
That would have been a lot easier if each class page listed the hierarchy and its place in it, rather than just listing them in a "See also" section.
not a bad idea. I couldn't figure out what the type is either. I can figure out what you want with that type either; AFAICT, it has no use (so maybe it is not that serious it is not there).
Even better than that would be if ptr_map and etc. listed ALL its members. This could presumably be automated?
How? -Thorsten
Thorsten Ottosen wrote:
Sam Partington wrote:
It seems to me that the first has the disadvantage of making it relatively easy to provide an incorrect cloner that allows slicing. However this is relatively easy to avoid by making your hierarchy noncopyable, (Perhaps a way around this is to remove the default implementation of new_clone?)
It's not very sensible to make the hierarchy copyable, because you can run into slicing in other places then.
As for the default, then I've been thinking about this too. It still won't catch that one missed a clone() function longer down the hiararchy.
Hm...I just came to think that a little assertion might help us out here: inline base* new_clone( const base& b ) { base* res = b.clone(); assert( typeid(*res) == typeid(b) ); return res; } That should catch any problems. I can even put this inside the clone-allocator, so the user don't have to specify this. -Thorsten
It seems to me that the first has the disadvantage of making it relatively easy to provide an incorrect cloner that allows slicing. However this is relatively easy to avoid by making your hierarchy noncopyable, (Perhaps a way around this is to remove the default implementation of new_clone?)
It's not very sensible to make the hierarchy copyable, because you can run into slicing in other places then.
Agreed, so why do we encourage copyable types by providing a default new_clone that uses the copy constructor. It almost gives the impression that that its a recommended way to do it. The only time the default would be useful is when you are using the ptr_ containers to store non-polymorphic types, probably for efficiency problems. Its not so much of a burden to require the user to write new_clone in those situations.
As for the default, then I've been thinking about this too. It still won't catch that one missed a clone() function longer down the hiararchy.
No, but we can only help you so far. And like you say in a later post a typeid based assert could help to avoid that when RTTI is enabled.
curve and strange inconsitencies for the user. i->first and i->second isn't pretty, but we're used to it now, and I can't see the std containers changing.
This is not to fix the interface, but to hide direct write-access to the pointer.
How so? Could you not emulate it with a proxy? Or would the overhead be too high? Perhaps this could go in the docs FAQ / rationale.
typename Container::value_type v = container.back(); container.pop_back(); return v;
?
I don't think so. The first statement won't compile. Secondly, your types should not be copyable.
I see, but is value_type not T*, so I'm guessing then that back returns a reference? Oh, it has to doesn't it, to match the indirection semantics of the ptr_ containers. Fair enough. This does compile : template<class Container> typename Container::value_type f(const Container& container) { typename Container::value_type v = &container.back(); container.pop_back(); return v; } But that wouldn't compile for a std container, and its quite apparent that the code is taking the address of something and then popping it - so I agree pop_back should stay as it is. It would be nice to have something in the FAQ / rationale about why pop_back returns the popped element.
The results are pretty much what you'd expect. shared_ptr performs well on the copy test, cow_ptr performs very poorly. I think you can read this as best/worst case scenario for COW.
right. I'm a bit surprised that the worst case is so bad. (snip) I guess it would make sense to repeat the test with different sizes of the containers. This is only for one size.
I was surprised too - I was expecting the cost of copying the object to overshadow the overhead of the copy on write logic. Size of container, and the object being stored, and the amount of mutating done changes all this greatly. (BTW I meant 100%-ish :-) I didn't see much point in working it out exactly since the numbers depend entirely on the problem domain)
I couldn't figure out what the type is either. I can figure out what you want with that type either; AFAICT, it has no use (so maybe it is not that serious it is not there).
I wanted to know the type to figure out whether the code fragment I gave before would compile. If value_type had been a reference, or back had returned a pointer then it would have compiled and would return either a reference or a pointer to a deleted object.
Even better than that would be if ptr_map and etc. listed ALL its members. This could presumably be automated?
How?
Not easily, and I don't think the boost build process has the ability to do things like this, but I was thinking along the lines of some kind of embedded directives, parsed by a python/perl script. For example the ptr_map might contain a directive like this, below its own members : <?inherit from="ptr_map_adapter"?> Which would pull out all of the members documented in ptr_map_adapter.html headed with "Inherited from ptr_map_adaptor". This in turn would pull in any inherited things from associative_ptr_container.html with a similar declaration. I'd be happy to write a suitable script. The alternative would be to copy+paste it all, but making changes to base class documentation would be a maintainance nightmare. Of course you may feel that its all too much effort and the user should follow the hierarchy to find the member they want. Which would be fair enough :-). Sam
Sam Partington wrote:
It seems to me that the first has the disadvantage of making it relatively easy to provide an incorrect cloner that allows slicing. However this is relatively easy to avoid by making your hierarchy noncopyable, (Perhaps a way around this is to remove the default implementation of new_clone?)
It's not very sensible to make the hierarchy copyable, because you can run into slicing in other places then.
Agreed, so why do we encourage copyable types by providing a default new_clone that uses the copy constructor. It almost gives the impression that that its a recommended way to do it. The only time the default would be useful is when you are using the ptr_ containers to store non-polymorphic types, probably for efficiency problems. Its not so much of a burden to require the user to write new_clone in those situations.
I guess not.
curve and strange inconsitencies for the user. i->first and i->second isn't pretty, but we're used to it now, and I can't see the std containers changing.
This is not to fix the interface, but to hide direct write-access to the pointer.
How so? Could you not emulate it with a proxy? Or would the overhead be too high? Perhaps this could go in the docs FAQ / rationale.
So you mean i->second gives back a reference? That is not a bad idea :-)
typename Container::value_type v = container.back(); container.pop_back(); return v;
?
I don't think so. The first statement won't compile. Secondly, your types should not be copyable.
I see, but is value_type not T*, so I'm guessing then that back returns a reference? Oh, it has to doesn't it, to match the indirection semantics of the ptr_ containers. Fair enough. This does compile :
template<class Container> typename Container::value_type f(const Container& container) { typename Container::value_type v = &container.back(); container.pop_back(); return v; }
But that wouldn't compile for a std container, and its quite apparent that the code is taking the address of something and then popping it - so I agree pop_back should stay as it is. It would be nice to have something in the FAQ / rationale about why pop_back returns the popped element.
right. It works that way because its exception-safe to do so.
I couldn't figure out what the type is either. I can figure out what you want with that type either; AFAICT, it has no use (so maybe it is not that serious it is not there).
I wanted to know the type to figure out whether the code fragment I gave before would compile. If value_type had been a reference, or back had returned a pointer then it would have compiled and would return either a reference or a pointer to a deleted object.
right, the typedefs could be better eplained for map/set.
Of course you may feel that its all too much effort and the user should follow the hierarchy to find the member they want. Which would be fair enough :-).
Right. You asked for a more logical way to navigate. What about splitting the *see also* bullet into *see also* and *hierachy* (or something). The latter would only show links to the "virtual" base and derived classes, always showinf the same list, with the current page being a "link" you can't follow.? -Thorsten
On 1/6/06, Thorsten Ottosen <tottosen@dezide.com> wrote:
So you mean i->second gives back a reference?
That is not a bad idea :-)
Yep, see the attached file. Just to show the outline - its missing out most of the usual iterator stuff you need.
Right. You asked for a more logical way to navigate. What about splitting the *see also* bullet into *see also* and *hierachy* (or something). The latter would only show links to the "virtual" base and derived classes, always showinf the same list, with the current page being a "link" you can't follow.?
That sounds perfect. Sam :-)
Doh, attachment! Sam On 1/6/06, Sam Partington <sam.partington@gmail.com> wrote:
On 1/6/06, Thorsten Ottosen <tottosen@dezide.com> wrote:
So you mean i->second gives back a reference?
That is not a bad idea :-)
Yep, see the attached file. Just to show the outline - its missing out most of the usual iterator stuff you need.
Right. You asked for a more logical way to navigate. What about splitting the *see also* bullet into *see also* and *hierachy* (or something). The latter would only show links to the "virtual" base and derived classes, always showinf the same list, with the current page being a "link" you can't follow.?
That sounds perfect.
Sam :-)
participants (3)
-
David Maisonave -
Sam Partington -
Thorsten Ottosen