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

From: David Maisonave (dmaisonave_at_[hidden])
Date: 2006-01-05 10:44:09

"Sam Partington" <sam.partington_at_[hidden]> wrote in message
news:<546fdb840601050424v61fae4f4n952293c6451203ae_at_[hidden]>...
> (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?)

Sorry Sam, but that's incorrect.
As I posted in one of my previous examples, the noncopyable method does
not work on pointer idioms.  Noncopyable is for preventing slicing via
concrete types.
Noncopyable does not help for cloning.
Since using the clone function method requires adding additional code
for each new type, this increases the chances of slicing.
And therefore (IMHO) it's easier to introduce bugs using this method.

> 
> 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());

The above code can be prevented if the T type is an abstract type.

Both methods can prevent most slicing by using an abstract type.
Both methods can still get slice via a derived-derived type.
And in both methods, using noncopyable does not prevent slicing.

However, (IMO), it's easier for a user to accidentally introduce slicing
using the clone-function method, then it 

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

It took me a while to get most of these containers working, and I was
only able to get ptr_set and ptr_map working with Thorsten's help.
I also like the ptr_map::iterator better, and I which the std::map had
use that interface instead.
But since std::map didn't, I don't think ptr_map should deviate from
it's counter part.
It's too bad both methods can't be some how incorparated.

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

That's not true.  The copy container test shows cow_ptr being a clear
winner.
On my test, it show a very significant difference, and as I previously
posted, the difference would be even more significant if we used a more
complex type who's constructor takes more CPU time.

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

That would *not* be an accurate test, since you're not taking advantage
of the cow_ptr's feature.
That's more of a worse case scenario test.
Just as sorting algorithms have best case scenario and worse case
scenario, depending on the data, so does cow_ptr and boost pointer
containers.
You can't use one type of data and say that would be an accurate test
for all sorting algorithms.

The cow_ptr will be most beneficial when copying a container or copying
part of a container, and when the copy is not access via non-constant
pointer.
The std::string is an example where this logic works well.

When you copy a class that has an std::string member, the copy is
performed efficiently if the std::string implementation is using COW
logic.
Most of the time you won't even access all the data members of a class,
which means the COW method helps to prevent copying data that doesn't
need to be copy.

I don't think ptr_vector should change to copy on write.  I think it
should have the option, via policy class, to use either COW or
deep-copy-always.
That way, the user can decide which is right for their particular
requirements.

You mention that you felt the discussion is actually three orthogonal.
However, none of the three items you listed included what I consider to
be the main issue.
To me the main issue, is should a separate set of container classes be
used as a main method for pointer of container logic.
Or should we use the existing well tested, well known, portable STL
containers, with a good clone smart pointer.

I favor using the existing STL containers, which is easier for a C++
programmer to learn.