Simple reference counting.

[aaronfude]

Hi,

Please consider the following class (it's not really my class, but it's
a good example for my question):

class Vector {
int myN;
double *myX;
Vector(int n) : myN(n), myX(new double[n]) { }
double &operator()(int i) { return myX; }
// Some other typical methods;

~Vector() { delete[] myX }
};

This class needs reference counting so that the following would work:

Vector a(5);
Vector b = a;

And I know of a way to do it by defining a class that houses "double
*myX" and counts references and then have "class Vector" contain a
pointer to that ref counting class. That's ok, but I'm concerned that
having an extra pointer to resolve will slow down the access of
elements. (My program has very few Vectors but uses them a lot.)

Two questions:
1. Are my concerns about access time founded?
2. If yes, is there a simpler way to do ref counting e.g. somehow let
Vector count references?

Very many thanks in advance!

Aaron Fude

 

[Kai-Uwe Bux]

Hi,

Please consider the following class (it's not really my class, but it's
a good example for my question):

class Vector {
int myN;
double *myX;
Vector(int n) : myN(n), myX(new double[n]) { }
double &operator()(int i) { return myX; }
// Some other typical methods;

~Vector() { delete[] myX }
};

This class needs reference counting so that the following would work:

Vector a(5);
Vector b = a;

And I know of a way to do it by defining a class that houses "double
*myX" and counts references and then have "class Vector" contain a
pointer to that ref counting class. That's ok, but I'm concerned that
having an extra pointer to resolve will slow down the access of
elements. (My program has very few Vectors but uses them a lot.)

Two questions:
1. Are my concerns about access time founded?

I would not think so. However, just try it.

2. If yes, is there a simpler way to do ref counting e.g. somehow let
Vector count references?

I don't know if it is simpler, but you can do something like this, I think
(beware, the following is untested code):


#include <algorithm>
#include <memory>

class Vector {

double* data;
unsigned length;
unsigned* ref_count;

public:

Vector ( unsigned l )
{
length = l;
std::auto_ptr< unsigned > ref_count_dummy ( new unsigned );
data = new double [ length ];
ref_count = ref_count_dummy.release();
*ref_count = 1;
}

Vector ( Vector const & other )
: data ( other.data )
, length ( other.length )
, ref_count ( other.ref_count )
{
++ *ref_count;
}

Vector& operator= ( Vector const & other ) {
Vector dummy ( other );
this->do_swap( dummy );
return ( *this );
}

void do_swap ( Vector & other ) {
std::swap( data, other.data );
std::swap( length, other.length );
std::swap( ref_count, other.ref_count );
}

~Vector ( void ) {
-- *ref_count;
if ( *ref_count == 0 ) {
delete [] data;
delete ref_count;
}
}

};

This should speed up access to the vector elements at the cost of making
assignments a little more expensive.

Some comments:

(a) the auto_ptr yadda yadda in the constructor is needed since

data = new double [ length ];

might throw. As there is no auto_array, this also determines the order of
assignments in this constructor.

(b) the swap idiom in the assignment operator is not just to make a strong
exception safety guarantee, it is also the easiest way to get the reference
counting right: the only places that deal with counting are the
constructors and the destructor. That keeps things simple.

(c) You may want to measure whether all this is actually needed. After all,
there is std::vector. Also note that the class above will fail you in a
multithreaded environment. Reference counting is notoriously hard to get
right in the presence of multiple threads.


Best

Kai-Uwe Bux

 

[Luke Meyers]

class Vector {
int myN;
double *myX;
Vector(int n) : myN(n), myX(new double[n]) { }
double &operator()(int i) { return myX; }
// Some other typical methods;

~Vector() { delete[] myX }
};

This class needs reference counting so that the following would work:

Vector a(5);
Vector b = a;

Your class could easily do that without ref counts. What you mean is
that you assume your class needs ref counting in order to do the above
with acceptable performance.

And I know of a way to do it by defining a class that houses "double
*myX" and counts references and then have "class Vector" contain a
pointer to that ref counting class.

Or, y'know, use a general smart pointer like tr1::shared_ptr.

That's ok, but I'm concerned that
having an extra pointer to resolve will slow down the access of
elements.

What do your performance tests tell you?

(My program has very few Vectors but uses them a lot.)

The rule is, make the common case fast. If you aren't creating many
vectors, why are you so concerned with avoiding copying them? Don't
introduce ANY "clever optimizations" until you do performance tests and
discover a need, and even then be sure to check that the "optimization"
actually helped.

1. Are my concerns about access time founded?

Not until your profiler tells you so. Yes, really.

2. If yes, is there a simpler way to do ref counting e.g. somehow let
Vector count references?
tr1::shared_ptr.

Very many thanks in advance!

HTH,
Luke

 

[Earl Purple]

tr1::shared_ptr.

If you mean shared_ptr< vector<T> > then that will work to reference
count the vector. Of course the vector will need to be created
initially with new.

If you mean vector< shared_ptr < T > > that is different, of course.
That is used to avoid copying the T objects, and when you copy the
vector you'll get a vector to the same T instances as before.

Or do you mean shared_ptr< T, array_deleter<T>() > where array_deleter
is a deleter that calls delete[], in which case he is not using vector
at all (Is shared_array part of tr1 by the way?)

 

[Ben Pope]

Hi,

Please consider the following class (it's not really my class, but it's
a good example for my question):

class Vector {
int myN;
double *myX;
Vector(int n) : myN(n), myX(new double[n]) { }
double &operator()(int i) { return myX; }
// Some other typical methods;

~Vector() { delete[] myX }
};

This class needs reference counting so that the following would work:

Vector a(5);
Vector b = a;

Yes, you'd need a copy constructor and assignment operator (since you
manage resources)

And I know of a way to do it by defining a class that houses "double
*myX" and counts references and then have "class Vector" contain a
pointer to that ref counting class.

So what you're saying is that by copying the Vector, you actually want
reference semantics to the data? That Vector itself has reference
semantics? That modifications to b, also modify a?

Or do you want the copy to be quick (shallow), but when the data is
first modified it must be copied (Copy On Write, COW)?

> That's ok, but I'm concerned that
having an extra pointer to resolve will slow down the access of
elements. (My program has very few Vectors but uses them a lot.)

Looks like you're going the wrong way then. You're trading speed of
access to increase speed of copying.

Two questions:
1. Are my concerns about access time founded?
Unlikely.

2. If yes, is there a simpler way to do ref counting e.g. somehow let
Vector count references?

In addition to boost::shared_ptr, you could also use
boost::intrusive_ptr, which has a little less space overhead, but
requires you to inherit from it and store the count yourself.

I'm lazy so I created a base class to do this for me.

You can also use a COW pointer, but that depends on the semantics you
require.

If you really want reference semantics, it's often better to make that
explicit to the user with:


#include <boost/shared_ptr.hpp>

class Vector {};

typedef boost::shared_ptr<Vector> Vector_ptr;

int main()
{
Vector_ptr a(new Vector);
Vector_ptr b(a);
Vector_ptr c = a;

}


Ben Pope