Re: [boost] Performance comparison between ptr_vector and vector<cow_ptr<Shape> >, vector<copy_ptr<Shape> >

From: Sam Partington (sam.partington_at_[hidden])
Date: 2006-01-05 07:24:17

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