[boost] linked_ptr update (long)

From: Borgerding, Mark A. (MarkAB_at_[hidden])
Date: 2000-02-04 19:03:46

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Let me apologize in advance for the length of this email.  I was
going to just send a quick note and post my latest code, but it
became pretty long.  I talk about the functionality that's been
added, the performance vs. shared_ptr, and the future of shared_ptr
and linked_ptr.  

Well, I did some work on linked_ptr.
I cleaned up the code a lot.  It is (hopefully) more readable. I
moved the ptr member into the subclass, which got rid of the nasty
static_cast<T*> operator.

*********Functional Enhancements:

***  release()
I added a release() function that allows the user to delete a pointer
instead of the chain of linked_ptrs.  The "released" message is
passed on to the "left" neighbor when a node leaves the list. This
maintains the O(1) complexity.

I tried to keep the behavior as close to the std::auto_ptr::release()
as possible.  The caller is responsible for deletion of the return
value of release(), and get() will thereafter return 0. 

Since linked_ptr is a reference counted ptr, the behavior is a bit
more complex than auto_ptr.  In some cases there may be linked_ptrs
that still point to the object.  This leaves dangling linked_ptrs,
which would cause an access violaton if a user dereferenced them. 
This danger gave me reservations about putting the functionality in,
but I finally decided that linked_ptr would be much more useful with
it.  Perhaps this feature should be made part of a conditional
compile.

This functionality required adding a bool to the base class. This may
increase the sizeof(linked_ptr), an exception is the case where
struct alignment is 64 bits and a pointer is 32, as is MSVC's
default.  I imagine this is a fairly common condition.  I don't have
access to my linux box right now, or I would see what gcc defaults
to.

*** threading issues
I added thread safety for WIN32 (critical section).  It requires the
definition of BOOST_MULTI_THREAD in config.hpp.  Of course, using
this is not free, but if you need it, you need it.  Hopefully someone
with more experience in 'nix than myself will add some p-style
synchronization.

*** dynamic_cast supported
I added a template function "dynamic_cast_from" that can do safe
downcasts while keeping the reference chain intact.
You don't pay for this unless you use it :)

********* Performance Enchancements:

I made the list circular (Gavin, I gave you credit for the idea in
the revision history, let me know if you don't want your name in
there) and did a bunch of tiny code changes that made my test program
(attached as main.cpp) run faster.  

Then I added the Functional Enhancements above, which pretty much ate
up the time saved by the optimization.  So the performance is about
the same as before, but with more functionality.

My timing results, condensed:
For assignments, shared ptr is 51% faster.
For copy constructors, shared ptr is 260% faster.
For default & dumb-ptr constructions, linked_ptr is 2300% faster.
(Test setup = P2 450, MSVC6)

********* Arguments for linked_ptr:

There are still some operations (op= and copy c'tor) where shared_ptr
is faster, but linked_ptr's performance is more predictable since all
of its operations are constant time, and fairly neglible.  I think it
will be easier to write efficient code with linked_ptr, since you
don't have to think about whether or not a reference count is being
allocated.
For example, the two code snippets
        shared_ptr<float*> sp; // allocates a reference count
        sp = new float;// allocates float and a reference count, deallocates
first reference count
        myList.add(sp);
and 
        shared_ptr<float*> sp(new float);// allocates float and a reference
count
        myList.add(sp);
have basically the same functionally, but the first one will take
considerably longer. If the above code used linked_ptr instead of
shared_ptr, both snippets would take almost exactly the same time,
much like they would with regular pointers.  The performance
scalability makes linked_ptr act more like regular pointers.  There
are relatively few hidden costs.
For those systems where even a slight performance difference is
crucial, an intrusive reference count would probably be better suited
than either linked_ptr or shared_ptr.

In some situations the size of the smart pointer object itself may be
important.  The current linked_ptr holds 3 pointers and a bool,
weighs in at 13 bytes + struct padding, kinda hefty compared to
shared_ptr's 8 bytes (This is assuming a 32 bit word) .  Many (most?)
users won't see any difference if their compiler aligns struct on a
16 byte boundary.  For applications that demand a small footprint, a
better approach is to hold a single pointer to struct that contains
the  reference count as well as the pointer.  This reduces the size
of the smart pointer to the size of 1 pointer.

I am curious to hear what the group has to say about what role
linked_ptr should take.  As the author of linked_ptr ( with a great
deal of suggestions and help from the group, most notably Gavin
Collings), I am somewhat biased, so I leave it to the rest of the
group to decide. 

- -> Should linked_ptr replace shared_ptr altogther? 
        I don't want to ruffle any feathers or deny anyone credit where
credit is due.  I would suggest integrating the copyright and revison
history of both files.  In some ways, linked_ptr *is* a revision of
shared_ptr, the interface is backward compatible except for
use_count, which is omitted from linked_ptr because it's O(n).

- -> Should linked_ptr coexist alongside shared_ptr? In the same file,
in another file?
        Would the added benefit of having choice between two such classes be
worth having to choose between them?  There would be an added
learning curve required on the part of the user to make the decision
between two basically identical interfaces.  It is easy to choose
between shared_ptr and scoped_ptr, the difference between shared_ptr
and linked_ptr is less obvious -- they are functionally the same,
aside from the minutia.

- -> Should there be additional classes put into <smart_ptr.hpp>? 
        Perhaps a small_shared_ptr class whose size is a single pointer (see
struct approach above)?  Possibly a smart pointer designed to handle
the inc/decrementing of the reference count in intrusively counted
objects?

P.S. I took out the linked_array class for now.  I will put it back
in when the non-array version is no longer a moving target.

Mark Borgerding 
markab (at) xetron . com
Software Engineer
Xetron Corporation

-----BEGIN PGP SIGNATURE-----
Version: PGPfreeware 6.5.2 for non-commercial use <http://www.pgp.com>

iQA/AwUBOJto5P9Ej8AEXMygEQIHsACg8iBJPLjx2MI8H0Mr5t9OiAD+cwsAmwXV
1EQE1p/UREhqSYfD0d2SZs4o
=gFIL
-----END PGP SIGNATURE-----