Sign in to follow this  

Copy-on-Write - How?? [subject name changed]

This topic is 4101 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hey all, I need a sugestion or two. Say I had a matrix class, Mat. It is an arbitrary-size 2D matrix, using a std::vector<float> as its internal representation. These objects will be of very large size, so I'd like to avoid any unnecessary construction / destruction, while keeping their use simple. Now, here is the syntax of what I would like to do:
Mat A, B, C;
A = fft( B );
// or
A = B = fft( C );
// or
A = fft( fft(B) );


Very simple. I am getting stuck in the details however. Should fft() return by value? If so, there are unnecessary copies going on. Should it allocate on the heap and return a pointer? If so, the syntax gets a bit uglier (unless Mat::operator=( Mat* ) is defined, but then the user must save the pointer, and handle deleteing). Should there be a global vector<Mat*> to keep track of all Mat's? Should I pass around handles as a level of indirection in this case? The real problem seems to be fft( Mat ), I'm not sure how to allocate the result-of-the-fft's memory. Would inlining the fft() function get rid of the return-by-value copying cost? Thanks for tips. [Edited by - discman1028 on September 17, 2006 4:59:29 PM]

Share this post


Link to post
Share on other sites
Compiler optimisation may or may not take care of it, depending on the compiler.


#include <stdio.h> // don't have stl port for one of the compilers I tested

class a
{
public:
a(int v) : value(v) { printf("constructor\n"); }
a(const a &v) : value(v.value) { printf("copy\n"); }

int value;
};

a func(int x)
{
a ret(x); return ret;
}

int main()
{
a x=func(10);
}



If the above code is compiled with Borland BCC55, it outputs:

constructor
copy

If the same code is compiled with DigitalMars DMC, it just outputs:

constructor

To be fair to Borland, there is probably an option to turn on optimising that would take care of this, but my point is you shouldn't be relying on optimisations like this.

A method that is sometimes used with string classes to address the issues you describe is to have the string class contain a pointer to a private implementation class. The implementation class holds a reference count of all the string objects that are pointing to it and when a string is copied, the implementation is just pointed to by another string class. Only when the string class actually tries to modify its data is a check made to see if the reference count of the implemetation pointed to is greater than one and, if so, the modifying string first creates its own copy of the data before modifying that.

Stroustrup describes such a string in The C++ Programming Language. I don't know if this approach would be useful in the situation you describe.

Share this post


Link to post
Share on other sites
Quote:
Original post by EasilyConfused
To be fair to Borland, there is probably an option to turn on optimising that would take care of this, but my point is you shouldn't be relying on optimisations like this.


Good advice..

Quote:
Original post by EasilyConfused
A method that is sometimes used with string classes to address the issues you describe is to have the string class contain a pointer to a private implementation class. The implementation class holds a reference count of all the string objects that are pointing to it and when a string is copied, the implementation is just pointed to by another string class. Only when the string class actually tries to modify its data is a check made to see if the reference count of the implemetation pointed to is greater than one and, if so, the modifying string first creates its own copy of the data before modifying that.


This does sound good. So the fft() would return a Mat by value, which is a tiny copy. I'll get back to you with any more questions I have (probably on how to decide when a Mat's about to be modified), but this sounds good, thanks. Other comments welcome.

Share this post


Link to post
Share on other sites
Quote:
Original post by discman1028
I'll get back to you with any more questions I have (probably on how to decide when a Mat's about to be modified)


That certainly is the tricky bit [smile]. In the example Stroustrup uses for a copy-on-write string, obviously operator= and operator+= and so on are quite straightforward, but he does some very clever stuff with operator[] (accessing characters) whereby on the non-const operator[], a class wrapping a char but binded with a reference to the owning string is returned.

If memory serves, this class then overloads all the operators for modification and can then defer any modifications to an individual character back to the string, which can then check to see if it needs its own copy first before modifying.

Been a while since I read that book though. Googling "copy-on-write c++" seems to return quite a lot of results.

Share this post


Link to post
Share on other sites
In my case, I think it will be an acceptable assumption to assume that non-const functions will modify the data, and as such, a copy is okay to do. As a detail, I will only be using Mat::operator(...), probably not Mat::operator[].

And thanks, "copy-on-write", very cool, a new thing to learn. ;)

Share this post


Link to post
Share on other sites
Quote:
Original post by discman1028
In my case, I think it will be an acceptable assumption to assume that non-const functions will modify the data, and as such, a copy is okay to do.


Only problem with that is that if you have a const and non-const accessor, say, then even if you are using the accessor in a non-modifying context, if the object is non-const, the non-const accessor will be called anyway.

Maybe this daft little snippet will explain what I mean better:


class a
{
private:
int val;

public:
a(int v) : val(v) { }

int &value(){ return val; }
int value() const { return val; }
};

int main()
{
a x(10);

int z=x.value();
}







That could be a typical example of where your accessor returns a reference for the non-const, and by value for the const.

The trouble comes in the last line, where x.value() is assigned to z so the accessor is used in the non-modifying sense. Because x is a non-const object the non-const member is still the one selected.

I don't know if this will present problems in the context you plan to use your class but I thought I'd mention it anyway.

Share this post


Link to post
Share on other sites
Yeh, it will, and it's a good point -- I hadn't thought it through that well yet. I am looking at boost::shared_ptr currently. I guess I will look into some "copy-on-write" then, first.

EDIT: Well, actually, considering my simple case:


Mat A, B, C;
A = fft( B );
// or
A = B = fft( C );
// or
A = fft( fft(B) );



The following two functions should suffice (I don't need to check for a modify, I know which mat's will need to be modified):

Mat& Mat::operator= (Mat const& mat) <== no copy, just change pointer
Mat& Mat::operator= (Mat mat) <== no copy, just change pointer
Mat fft( Mat const& mat ) <== new Mat, return by value

Again, I havent thought this through completely.

Share this post


Link to post
Share on other sites
I wouldn't bother with both those operator='s. The first will suffice. Since it is a const reference it will happily take temporaries as well as properly addressable objects.

You also want a copy constructor:

Mat::Mat(const Mat &Copy){ /* ... */ }

That has to take a const reference otherwise you get an infinte recursion.

By the way, I should probably also suggest that you first write all your code forgetting all this copy-on-write complexity and just copy everything by value. If profiling then reveals that this is actually causing a problem, this copy-on-write stuff is an optimisation that is better performed then.

Unless you are writing Mat for a library and you can't forsee all its possible future uses, anyway.

Share this post


Link to post
Share on other sites
Quote:
Original post by EasilyConfused
I wouldn't bother with both those operator='s. The first will suffice. Since it is a const reference it will happily take temporaries as well as properly addressable objects.


Oops, brain fart.

Quote:
Original post by EasilyConfused
Unless you are writing Mat for a library and you can't forsee all its possible future uses, anyway.


Yeh, that's actually the case - it is to be designed for large problems. Thanks, and I'll post some code when I have it!

Share this post


Link to post
Share on other sites
Okay, I have a test program made. I have a Mat class, a MatImplementation class, and a templated cow_ptr (copy-on-write) class which uses boost::shared_ptr for ref-counting.

I decided to make fft() a member function of Mat for now, as it makes it easier to understand.

Here is main.cpp:


#include <cstdlib>
#include <vector>
#include <iostream>
#include "cow_ptr.h"
using namespace std;


/// The actual fft.
void thefftimplementation( vector<float>& rData )
{
// just do something dumb like multiply by 2.0f for now
for( int i = 0; i < rData.size(); i++ )
{
rData[i] *= 2.0f;
}
}


class MatImplementation
{
public:
/// Constructors.
MatImplementation( int nRows, int nCols )
{
m_data.resize( nRows*nCols );
for( int i = 0; i < nRows*nCols; i++ )
{ // Fill with random data for now
m_data[ i ] = 1.0f*rand();
}
}
MatImplementation( MatImplementation const& m ) : m_data( m.m_data ) {}

/// = operator.
MatImplementation& operator=( MatImplementation const& m )
{
m_data = m.m_data;
return *this;
}

/// Destructor.
~MatImplementation() {}

/// Honest-to-goodness matrix data.
vector<float> m_data;
};


class Mat
{
public:
/// Constructors.
Mat( int nRows, int nCols ) : pMatrixData( 0 )
{
pMatrixData = new MatImplementation(nRows, nCols);
}
Mat( Mat const& m ) : pMatrixData( m.pMatrixData ) {}

/// = operator.
Mat& operator=( Mat const& m )
{
pMatrixData = m.pMatrixData;
return *this;
}

/// FFT operation.
Mat fft()
{
Mat returnMat( *this );
thefftimplementation( returnMat.pMatrixData->m_data );
return returnMat;
}

/// Destructor.
virtual ~Mat() {}

protected:
/// Copy-on-write matrix.
cow_ptr<MatImplementation> pMatrixData;
};


int main(int argc, char* argv[])
{
Mat a( 10, 10 );
Mat b( 10, 10 );

a = b.fft();





return 0;
}






And here is cow_ptr.h, adapted from an online example.


#ifndef _COW_PTR_H_
#define _COW_PTR_H_

#include <boost/shared_ptr.hpp>

template <typename DataType>
class cow_ptr
{
public:
/// Constrcutors.
cow_ptr() {}
cow_ptr( DataType* ptr ) : m_pPtr(ptr) {}

/// = operator.
cow_ptr& operator=( cow_ptr const& rPtr )
{
m_pPtr = rPtr.m_pPtr;
return *this;
}

/// Destructor.
virtual ~cow_ptr() {}

/// Const ops.
DataType const* get() const { return m_pPtr.get(); }
DataType const* operator->() const { return m_pPtr.get(); }
DataType const& operator*() const { return *m_pPtr; }

/// Non-const ops.
DataType* get() { MakeCopy(); return m_pPtr.get(); }
DataType* operator->() { MakeCopy(); return m_pPtr.get(); }
DataType& operator*() { MakeCopy(); return *m_pPtr; }

protected:
/// Make a new copy on the heap of the data currently pointed to.
void MakeCopy()
{
// If we are pointing to unique data, there is no need to copy. Else, copy.
if( !m_pPtr.unique() )
{
m_pPtr.reset( new DataType( *m_pPtr ) );
}
}

/// The ref-counted pointer.
boost::shared_ptr<DataType> m_pPtr;
};

#endif






PLEASE, comments! Soon, the matrix data type will be templated as well, as well as some other functionality, so abstracting this COW as best as possible is important!

EasilyConfused, I believe your comment about the non-const function always being called still holds here, but perhaps the const version of get() can be forced to be called by passing const references into a matrix get function, and just a reference into a set function.

Thanks.

Share this post


Link to post
Share on other sites

Quote:
Original post by EasilyConfused
In the example Stroustrup uses for a copy-on-write string, obviously operator= and operator+= and so on are quite straightforward, but he does some very clever stuff with operator[] (accessing characters) whereby on the non-const operator[], a class wrapping a char but binded with a reference to the owning string is returned.

If memory serves, this class then overloads all the operators for modification and can then defer any modifications to an individual character back to the string, which can then check to see if it needs its own copy first before modifying.


I want to avoid doing this for every operator I need.. which may only be '()', but I am not certain.

Share this post


Link to post
Share on other sites
Maybe someone else can suggest something, but I can't see a way to force the const functions to be called. In my daft example above, the problem is that if you do:

int z=x.value();

it is not the call itself, but where the result is placed that determines whether you want the const or non-const method called and I don't personally know of a way in C++ to enforce this. I'm fairly sure someone else here will have a bright idea that I'm missing.

Another option would be to not worry about it. In your example of:

Mat a=fft(fft(b));

you would not be calling your () operator. Perhaps a simpler solution would be to make () call GetOwnCopy (or whatever) but also have a const version of () that doesn't (I'm not too sure what () is going to do so don't know if that is feasible).

You could then rely on the user of the library to enforce it like this:


void f(const Mat &M)
{
cout << M(4) << endl; // guessing about the use of () here
}

void g(Mat &M)
{
M(2)=2.4f;
}

int main()
{
Mat b;
Mat a=fft(fft(b)); // GetOwnCopy not called yet

f(a); // GetOwnCopy still not called

g(a); // GetOwnCopy called inside g
}




I appreciate this is not ideal, but it is a solution. Perhaps if you could describe what you want the () function to actually do, people will be able to suggest cleaner solutions.

There could equally be a far better overall solution to your original problem than copy-on-write as well of course. It just seemed appropriate to me.

HTH

Share this post


Link to post
Share on other sites
I actually wanted the operator for accessing one element of a matrix:



float& Mat::operator()( int x, int y )
{
return data[ x*m_numRows + y ];
}

float Mat::operator()( int x, int y ) const
{
return data[ x*m_numRows + y ];
}



Share this post


Link to post
Share on other sites
This is a suggestion I have thrown together quickly and not thoroughly tested but it seems to work:


#include <iostream>
#include <vector>

using namespace std;

class Matrix
{
private:

class Imp
{
public:
Imp(int w,int h) : r(0),wt(w),ht(h) { v.resize(w*h); cout << "imp\n"; }
~Imp(){ cout << "free\n"; }

vector<float> v; int r,wt,ht;
};

class MFloat
{
public:
MFloat(Matrix *M,float *v,int fx,int fy) : Mp(M),Fv(v),x(fx),y(fy) { }

operator float() const { return *Fv; }
operator float&()
{
if(Mp->Im->r>1) Mp->GetOwnCopy();

Fv=&(Mp->Im->v[(y*Mp->Im->wt)+x]);

return *Fv;
}

Matrix *Mp; float *Fv; int x,y;
};

Imp *Im;

friend class MFloat;
void GetOwnCopy();

public:
Matrix(int w,int h){ Im=new Imp(w,h); Im->r=1; }
Matrix(const Matrix &M){ Im=M.Im; ++Im->r; }
~Matrix(){ --(Im->r); if(Im->r==0) delete Im; }

const Matrix &operator=(const Matrix &M)
{ --Im->r; if(Im->r==0) delete Im; Im=M.Im; ++Im->r; return *this; }

float operator()(int x,int y) const { return Im->v[(y*Im->wt)+x]; }

MFloat operator()(int x,int y)
{ return MFloat(this,&(Im->v[(y*Im->wt)+x]),x,y); }
};

void Matrix::GetOwnCopy()
{
Imp *I=Im; Im=new Imp(I->wt,I->ht); Im->v=I->v; Im->r=1;
--(I->r); if(I->r==0) delete I;
}

int main()
{
Matrix M(5,5),N=M;
M(2,2)=23.0f;

cout << M(2,2) << endl;
}





It relys on the fact that when a non-const Matrix has its () operator called, it returns the MFloat class, which is private to Matrix. MFloat has operator float and operator float& functions and it would appear that the correct one gets called depending on whether you are asking for an lvalue or not.

In the int main() as above, the GetOwnCopy is called before the assignment. If you take the M(2,2)=23.0f line out, it isn't called since the operator float is used to get the value for the cout statement rather than the operator float&.

I have no idea whether this would work if developed or not, or whether there is a well-defined precedence for calling the non-reference operator float function over the reference version depending on if an lvalue is being used or not, so I make no apology if this program is relying on undefined behaviour or non-standard aspects of the compiler I tested this on. It is just an idea that I hope might provoke some discussion.

Share this post


Link to post
Share on other sites
Thanks for the reply. I am very much interested in this problem, but have decided that I will deal with its complexity later, as I do not have forever to spend on the problem. I will return by value for now from the fft function.

EDIT: I agree, in that I don't know if the technique you mention could be trusted / extended, I'm interested to hear what others do! I found a link of a cow_ptr implementer that used the string [] technique you mentioned earlier here, and is pretty similar to what you tried -- differentiate an operator() by the return type.

Thanks EasilyConfused!

Share this post


Link to post
Share on other sites
I think that sounds like a wise idea.

This was an interesting topic for me because I've never tried to implement copy-on-write for anything before.

To be honest though, I tend to pass stuff I don't want copied around as const whatever &, and I'd have just made ttf take a non-const reference to the value it is modifying rather than return a value.

Not a solution if you're writing classes for other people to use though.

Share this post


Link to post
Share on other sites
Quote:
Original post by EasilyConfused
To be honest though, I tend to pass stuff I don't want copied around as const whatever &, and I'd have just made ttf take a non-const reference to the value it is modifying rather than return a value.

Not a solution if you're writing classes for other people to use though.


Exactly my reasoning.

I have no problem making fft() a non-member function, and passing non-const ref as you say, but the real problem is the return value.

Share this post


Link to post
Share on other sites
I also realize that I may have been going over the top for my needs. Though that auto-copying would be nice, all I really needed was a reference-counting ptr to the matrix implementation, and I can decide myself when to copy it (e.g., in fft()):


#include <cstdlib>
#include <vector>
#include <iostream>
#include <boost/shared_ptr.hpp>
using namespace std;


/// The actual fft.
void thefftimplementation( vector<float>& rData )
{
// just do something dumb like multiply by 2.0f for now
for( int i = 0; i < rData.size(); i++ )
{
rData[i] *= 2.0f;
}
}


class MatImplementation
{
public:
/// Constructors.
MatImplementation( int nRows, int nCols )
{
m_data.resize( nRows*nCols );
for( int i = 0; i < nRows*nCols; i++ )
{ // Fill with random data for now
m_data[ i ] = 1.0f*rand();
}
}
MatImplementation( MatImplementation const& m ) : m_data( m.m_data ) {}

/// = operator.
MatImplementation& operator=( MatImplementation const& m )
{
m_data = m.m_data;
return *this;
}

/// Destructor.
~MatImplementation() {}

/// Honest-to-goodness matrix data.
vector<float> m_data;
};


class Mat
{
public:
/// Constructors.
Mat( int nRows, int nCols )
{
pMatrixData.reset( new MatImplementation(nRows, nCols) );
}
Mat( Mat const& m ) : pMatrixData( m.pMatrixData ) {}

/// = operator.
Mat& operator=( Mat const& m )
{
pMatrixData = m.pMatrixData;
return *this;
}

/// FFT operation.
Mat fft()
{
// Make a copy of the current Mat (copies a ptr only).
Mat returnMat( *this );

// Explicitly ask for a ptr to a new copy of the data.
returnMat.pMatrixData.reset( new MatImplementation( *pMatrixData ) );

// Perform an fft on the data.
thefftimplementation( returnMat.pMatrixData->m_data );

// Return a (small) copy of the Mat class.
return returnMat;
}

/// Destructor.
virtual ~Mat() {}

protected:
/// Shared pointer to a heap-allocated matrix.
boost::shared_ptr<MatImplementation> pMatrixData;

/// Constructor (hidden).
Mat();
};


int main(int argc, char* argv[])
{
Mat a( 10, 10 );
Mat b( 10, 10 );

a = b.fft();





return 0;
}





This seems ideal, for now.

Share this post


Link to post
Share on other sites
Quote:
Original post by discman1028
Hey all, I need a sugestion or two.

Say I had a matrix class, Mat. It is an arbitrary-size 2D matrix, using a std::vector<float> as its internal representation. These objects will be of very large size, so I'd like to avoid any unnecessary construction / destruction, while keeping their use simple.

Now, here is the syntax of what I would like to do:

*** Source Snippet Removed ***

Very simple. I am getting stuck in the details however. Should fft() return by value? If so, there are unnecessary copies going on. Should it allocate on the heap and return a pointer? If so, the syntax gets a bit uglier (unless Mat::operator=( Mat* ) is defined, but then the user must save the pointer, and handle deleteing). Should there be a global vector<Mat*> to keep track of all Mat's? Should I pass around handles as a level of indirection in this case?

The real problem seems to be fft( Mat ), I'm not sure how to allocate the result-of-the-fft's memory. Would inlining the fft() function get rid of the return-by-value copying cost?


Thanks for tips.


Copy-On-Write is nice, but for your problem it looks like you could just pass in a reference to the object to write to:


Mat A, B, C;
B.fft( A );
// or
C.fft( A );
A = B;
// or
Mat temp;
B.fft( temp );
temp.fft( temp ); // does fft have dependancies that would disallow this?
temp.( A );


I don't know anything about FFT, but if you're unable to write to the object being read you'd simply use another temp Mat. It makes the syntax a little ugly but, if it's speed you want, passing in references to memory should be more effecient than reference counting and Copy-On-Write logic.

Hope that helps.

Share this post


Link to post
Share on other sites
I did end up passing in references to store the solution, for now. It would be neat to develop a general copy-on-write templated type, if not available. I'll put it on the list of things to look into. :)

Share this post


Link to post
Share on other sites
Personally, I would avoid COW unless you first determined it necessary. (That is, you've profile your code, and have determined the copy constructor for your class is too slow or using too much memory for identical copies.) Even so, I might try alternatives...

COW may be a premature optimization, one you don't really need, especially since memory allocators, caches, RAM sizes, etc are not as pathetic as they once were. COW can be tricky to get right, especially if you're doing anything threaded.

Not to say it should never be used... But I wouldn't bother unless you've identified it as the best solution to an existing problem.

Share this post


Link to post
Share on other sites
Quote:
Original post by mossmoss
Personally, I would avoid COW unless you first determined it necessary. (That is, you've profile your code, and have determined the copy constructor for your class is too slow or using too much memory for identical copies.) Even so, I might try alternatives...

COW may be a premature optimization, one you don't really need, especially since memory allocators, caches, RAM sizes, etc are not as pathetic as they once were. COW can be tricky to get right, especially if you're doing anything threaded.

Not to say it should never be used... But I wouldn't bother unless you've identified it as the best solution to an existing problem.


Well, in this case I know it is needed, up front. The data sets will be distributed over ethernet for processing elsewhere to speed up computations. Any allocation more than necessary will result in seconds of extra time.

Share this post


Link to post
Share on other sites
May I also suggest an alternative to COW?

Well, sort of...

Have two related objects.

Matrix
WriteMatrix

Both have a reference counted pointer to the actual data.

Have a method that can turn any Matrix into a WriteMatrix and vice versa. Going from a Matrix to a WriteMatrix should not be implicit, but it should be allowed.

WriteMatrix has non-const methods, and possibly implements COW[1].

Matrix has purely const methods.

Your Matrix class is now "data like" -- it behaves like an int.

The WriteMatrix is for modifying a matrix. Modifying a matrix can be an expensive operation -- by placing the modification functions in it's own class, you restrict such modifications to points where the user knows they are doing something expensive.

Functions return Matrixs. This simply involves add/remove ref -- so passing Matrixs around becomes dirt cheap.

Share this post


Link to post
Share on other sites
Quote:
Original post by discman1028
Quote:
Original post by mossmoss
Personally, I would avoid COW unless you first determined it necessary. (That is, you've profile your code, and have determined the copy constructor for your class is too slow or using too much memory for identical copies.) Even so, I might try alternatives...

COW may be a premature optimization, one you don't really need, especially since memory allocators, caches, RAM sizes, etc are not as pathetic as they once were. COW can be tricky to get right, especially if you're doing anything threaded.

Not to say it should never be used... But I wouldn't bother unless you've identified it as the best solution to an existing problem.


Well, in this case I know it is needed, up front. The data sets will be distributed over ethernet for processing elsewhere to speed up computations. Any allocation more than necessary will result in seconds of extra time.


Seconds of extra time out of how much time?

Share this post


Link to post
Share on other sites

This topic is 4101 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this