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

From: Sam Partington (sam.partington_at_[hidden])
Date: 2006-01-06 05:05:02

On 1/5/06, David Maisonave <dmaisonave_at_[hidden]> 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?)
>
> 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.

I don't agree with that.  The clone concept is a well established
idiom for polymorphic types.  Sure missing out a clone _does_ lead to
slicing, but that is understood, and as Thorsten says we can help
check for that with an assert.  We  can only help the user to get it
write, we can't do it all for them.

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

I disasgree - with cloning if the class hierarchy has implemented
clone correctly then all code using the hierarchy will work correctly
- you just have to get it right in one place.

Using the copy constructor it is down to the code passing around the
pointers that has to be correct.  In _every_ place that you pass
around a pointer.

Yes if all of the concrete types are leaf nodes of the hierarchy then
there is no problem, and in an ideal world all concrete types would be
leaf nodes, but in my experience that utopia is very short lived in
any large code base.

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

Yep, agreed :-)  The differences should be as minimal as possible.

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

No it is true.  I said "that aren't affected by cow".  Of course copy
is affected by cow, thats precisely what it tries to optimise.

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

I said precisely that it showed a worst case scenario.  And I compared
it against vector<shared_ptr> for a best case scenario (ie a situation
where all copies are optimised away).  Somewhere in the middle,
depending on the use case is the typical scenario.

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

I think yes it could add that as a policy.  But I don't think it needs
to, policies can make nice interfaces really ugly sometimes.  I think
boost would benefit more from a cow pointer, and when you need cow
semantics, you use vector<cow_ptr>.

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

Why does it have to be either/or? Can they not co-exist? 
ptr-containers are just another tool to the developers toolbox.  You
weigh up the benefits of each and choose the one most suitable for the
job at hand.