operator+ ohne Kopie?

DocShoe

Du könntest sowas wie´n Proxy bauen, allerdings setzt der voraus, dass die beiden Matrizen A und B mindestens genauso lange leben wie der Proxy:

class MatrixAdditionProxy
{
   const Matrix& M1_;
   const Matrix& M2_;

public:
   MatrixAdditionProxy( const Matrix& M1, const Matrix& M2 ) : M1_( M1 ), M2_( M2 )
   {
   }      

   double operator()( unsigned int Row, unsigned int Col ) const
   {
      return M1_( Row, Col ) + M2_( Row, Col );
   }
};

MatrixAdditionProxy operator+( const Matrix& m1, const Matrix& m2 )
{
   return MatrixAdditionProxy ( m1, m2 );
}

Damit kommst du sogar ganz ohne Kopien aus, hab mir jetzt aber keine Gedanken darüber gemacht, wie man das transparent umsetzen kann. Vermutlich braucht die Matrixklasse irgendwo einen Zuweisungsoperator, der das alles wieder auflöst. Ob das nur für Rechenoperationen taugt, weil man hinterher ja doch wieder eine Matrix (also ein vollwertiges Matrixobjekt) haben möchte. So Sachen wie

Matrix D = A + B + C * D;

gingen jedoch deutlich flotter und ohne Kopien.

volkard

DocShoe schrieb:

So Sachen wie
Matrix D = A + B + C * D;
gingen jedoch deutlich flotter und ohne Kopien.

Sicher auch mit Cache-Effekten?
Bei E=(A+B)*(C+D) hätte ich aber schon zu viel Angst.

megaweber

Hier eine Lösung mit ein wenig template Vodoo:

www.uop.edu.jo/download/PdfCourses/Cplus/sanderson_templates_lecture_uqcomp7305.pdf

Michael E.

yYy schrieb:

const Matrix operator+(Matrix const &B) const
		{
			return Matrix(*this) += B;
		}

Schreib das mal um zu

const Matrix operator+(Matrix const &A, Matrix const &B)
{
	Matrix tmp(A);
	tmp += B;
	return tmp;
}

Dann sollte auch Visual Studio die Optimierung durchführen.

Nexus

Und lass das const beim Rückgabetyp weg.

Michael E.

Nexus schrieb:

Und lass das const beim Rückgabetyp weg.

Warum?

m + m = m;

volkard

Michael E. schrieb:

Nexus schrieb:

Und lass das const beim Rückgabetyp weg.

Warum?
m + m = m;

Und was soll daran verboten sein? Es ist wirklich keine Gefahr. Erinnere Dich, wie oft Du a+b=c; getippt hast und c=a+b; meintest.

Das const macht Dir nur Optimierungen kaputt.

DocShoe

megaweber schrieb:

Hier eine Lösung mit ein wenig template Vodoo:

www.uop.edu.jo/download/PdfCourses/Cplus/sanderson_templates_lecture_uqcomp7305.pdf

Hihi,

habe gerade sowas Ähnliches hingefrickelt. Schön isses zwar nicht, aber es zeigt, dass es funktioniert.

#include <memory>

class Matrix
{
	double values_[4][4];

public:
	Matrix()
	{
   	std::memset( &values_, 0, sizeof( values_ ) );
	}

	template<typename T>
	Matrix( const T& op )
	{
		for( unsigned int r = 0; r < 4; ++r )
			for( unsigned int c = 0; c < 4; ++c )
				values_[r][c] = op( r,c );
	}

	double operator()( unsigned int Row, unsigned int Col ) const
	{
		return values_[Row][Col];
	}

	double& operator()( unsigned int Row, unsigned int Col ) 
	{
		return values_[Row][Col];
	}

	template<typename T>
	Matrix& operator=( const T& op )
	{
		for( unsigned int r = 0; r < 4; ++r )
			for( unsigned int c = 0; c < 4; ++c )
				values_[r][c] = op( r,c );
		return *this;
	}
};

template<typename T, typename U>
class MatrixAdditionProxy
{
	const T& M1_;
	const U& M2_;

public:
	MatrixAdditionProxy( const T& M1, const U& M2 ) : M1_( M1 ), M2_( M2 )
	{
	}

	double operator()( unsigned int Row, unsigned int Col ) const
	{
		return M1_( Row, Col ) + M2_( Row, Col );
	}
};

template<typename T, typename U>
MatrixAdditionProxy<T,U> operator+( const T& M1, const U& M2 )
{
	return MatrixAdditionProxy<T,U>( M1, M2 );
}

template<typename T, typename U>
class MatrixSubtractionProxy
{
	const T& M1_;
	const U& M2_;

public:
	MatrixSubtractionProxy( const T& M1, const U& M2 ) : M1_( M1 ), M2_( M2 )
	{
	}

	double operator()( unsigned int Row, unsigned int Col ) const
	{
		return M1_( Row, Col ) - M2_( Row, Col );
	}
};

template<typename T, typename U>
MatrixSubtractionProxy<T,U> operator-( const T& M1, const U& M2 )
{
	return MatrixSubtractionProxy<T,U>( M1, M2 );
}

int main()
{
	Matrix m1, m2, m3, m4;

	m1( 0,0 ) = 1;
	m2( 0,0 ) = 2;
	m3( 0,0 ) = 3;
	m4( 0,0 ) = 11;

	Matrix m5 = m1 + m2 - (m3 - m4);

	double r = m5( 0,0 );
}

volkard schrieb:

DocShoe schrieb:
So Sachen wie
Matrix D = A + B + C * D;
gingen jedoch deutlich flotter und ohne Kopien.
Sicher auch mit Cache-Effekten?
Bei E=(A+B)*(C+D) hätte ich aber schon zu viel Angst.

Blitz++ setzt diese oder ähnliche Techniken ein und erreicht dabei Geschwindigkeiten von Fortran, scheint also zu gehen.

volkard

DocShoe schrieb:

Blitz++ setzt diese oder ähnliche Techniken ein und erreicht dabei Geschwindigkeiten von Fortran, scheint also zu gehen.

Die Proxies allein versagen.
"oder ähnliche Techniken" bräuchte man wohl.
Auf expression templates wies ich um 09:47 bereits hin, wohl zu leise.

Michael E.

volkard schrieb:

Das const macht Dir nur Optimierungen kaputt.

Welche genau?

volkard

Michael E. schrieb:

volkard schrieb:

Das const macht Dir nur Optimierungen kaputt.

Welche genau?

Das zerstörende Auslutschen von r-values.

Nexus

Michael E. schrieb:

Welche genau?

Die Move-Zuweisung, die hier möglich wäre.

a = b + c;

Diese const -Rückgabe ist ohnehin nur ein verzweifelter Versuch, Klassen-RValues wie skalare RValues zu behandeln (die nicht zugewiesen werden können, obwohl sie nicht const -qualifiziert sind). Wirkliche Fehler vermeidet man nicht.

Michael E. schrieb:

Schreib das mal um zu
const Matrix operator+(Matrix const &A, Matrix const &B)
{
	Matrix tmp(A);
	tmp += B;
	return tmp;
}
Dann sollte auch Visual Studio die Optimierung durchführen.

Ich mag diese Art der Notation nicht wirklich, weil sie dann nicht mehr zu der Klasse gehört.
Aber das klappt, danke. Kommen andere Compiler damit auch zurecht?

BTW: Was tut eigentlich das const am Anfang?

Nexus

yYy schrieb:

Ich mag diese Art der Notation nicht wirklich, weil sie dann nicht mehr zu der Klasse gehört.

Wer sagt, dass der operator+ zur Klasse gehören muss? Viel sinnvoller ist es, ihn als freie Funktion zu implementieren, da er sich so symmetrisch im Bezug auf die Operanden verhält.

yYy schrieb:

Aber das klappt, danke. Kommen andere Compiler damit auch zurecht?

Ja, sofern sie nicht hoffnungslos veraltet sind

yYy schrieb:

BTW: Was tut eigentlich das const am Anfang?

Es soll verhindern, das zurückgegebene temporäre Objekt zu ändern. Aber wie gesagt ist das const in dieser Situation mehr schädlich als nützlich, gewöhn es dir nicht an.

DocShoe

volkard schrieb:

DocShoe schrieb:

Blitz++ setzt diese oder ähnliche Techniken ein und erreicht dabei Geschwindigkeiten von Fortran, scheint also zu gehen.

Die Proxies allein versagen.
"oder ähnliche Techniken" bräuchte man wohl.
Auf expression templates wies ich um 09:47 bereits hin, wohl zu leise.

Naja, wobei die Proxies den Expression Templates schon recht nahe kommen. Wie gesagt, ich hab´s schnell runtergeschrieben und da steckt nicht viel Hirnschmalz dahinter. Das Expression Template Beispiel in C++ Templates - The Complete Guide von Vandevoorde und Josuttis, S. 321ff unterscheidet sich prinzipiell nicht von meinem Ansatz. Auch da werden temporäre Kopien vermieden und der Zugriff erfolgt über Proxy Objekte, nur hat man da etwas mehr Mühe investiert.

Ich habe jetzt auch einen *Operator innerhalb der Klasse implementiert. Hier bekomme ich auch in Debugmodus nur einen Konstruktoraufruf. Wieso?

Matrix operator*(Matrix const &B) const
		{
			if (n != B.m)
				//...
			unsigned int newM = m;
			unsigned int newN = B.n;
			T **c = new T*[newM];
			//...
			return Matrix(newM, newN, c, true);
		}

Nexus

yYy schrieb:

Ich habe jetzt auch einen *Operator innerhalb der Klasse implementiert.

Mach den auch global. Innerhalb der Klasse kannst du *= implementieren, und von aussen darauf zugreifen (da du dynamische Dimensionen hast, ändert sich der Typ der Matrix bei der Multiplikation nicht).

yYy schrieb:

Hier bekomme ich auch in Debugmodus nur einen Konstruktoraufruf. Wieso?

Weil nur ein Objekt konstruiert wird?

Übrigens würde ich die manuelle Speicherverwaltung und Zeiger-Auf-Zeiger-Frickelei irgendwie wegkapseln. Ist unnötig, dass du dich bei jeder neuen Operation darum kümmern musst.

Nexus schrieb:

Mach den auch global. Innerhalb der Klasse kannst du *= implementieren, und von aussen darauf zugreifen (da du dynamische Dimensionen hast, ändert sich der Typ der Matrix bei der Multiplikation nicht).

Ja, weiß ich, hab ich auch vor, ich hatte es nur gerade so und hab mich gewundert.

Nexus schrieb:

Weil nur ein Objekt konstruiert wird?

Wär ich nie drauf gekommen...
Jetzt mal ernsthaft: Wo ist der Unterschied zum +Operator? Da erzeuge ich auch ein Objekt, und C++ erzeugt ne Kopie, die zurückgegeben wird. Warum wird hier keine Kopie erzeugt?

Nexus

yYy schrieb:

Wär ich nie drauf gekommen...

Stell deine Fragen präziser.

Im Beispiel mit operator* wird RVO (Return Value Optimization) angewandt, weil es sich beim return -Ausdruck um ein temporäres Objekt handelt. Bei benannten Objekten kann unter Umständen NRVO (Named Return Value Optimization) angewandt werden, was aber vom Compiler und vor allem vom Code abhängt.

Nexus schrieb:

Im Beispiel mit operator* wird RVO (Return Value Optimization) angewandt, weil es sich beim return -Ausdruck um ein temporäres Objekt handelt. Bei benannten Objekten kann unter Umständen NRVO (Named Return Value Optimization) angewandt werden, was aber vom Compiler und vor allem vom Code abhängt.

Naja, ich habe aber im Debug-Modus gestartet und die Optimierung ausgeschaltet. Deswegen wundert es mich. Wird es also trotzdem optimiert?