operator+ ohne Kopie?

[yYy]

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.

[yYy]

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?

[bmario]

DocShoe schrieb:

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.

Dann aber MatrixProxy lieber einen Funktor übergeben

z.B.:

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

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

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

[DocShoe]

@bmario:

Warum? Damit schaffst du nur eine unnötige weitere Zwischenschicht. Außerdem verlierst du den nötigen Kontext, z.B. bei der Multiplikation zweier Matrizen, wo die beiden Elemente der Matrizen allein nicht mehr ausreichen.
Du hast zwar nur noch einen Proxytyp, aber dafür musst du die einzelnen Funktoren noch implementieren. Wenn die beiden Elemente ausreichend wären könnte man tatsächlich std::plus etc. nehmen, aber das reicht eben nicht.

[bmario]

Coderedundanz ist mir schon ein ausreichendes Argument

Außerdem könnte man dem Funktor statt den beiden Elementen auch Referenzen auf die Matrizen, sowie die Spalten- und Zeilenangabe mitgeben. Durch inlining sollte diese Zwischenschicht dann auch nichtmehr auf die Performance gehen.

Aber nicht ganz unrecht hast du auch... das werd ich gleich mal testen.

[volkard]

DocShoe schrieb:

@bmario:
Warum?

Weil es geht. Wer den Template-Dungeon erforscht, muß halt erstmal jede Truhe öffnen und jede Tür aufmachen.

[volkard]

bmario schrieb:

Außerdem könnte man dem Funktor statt den beiden Elementen auch Referenzen auf die Matrizen, sowie die Spalten- und Zeilenangabe mitgeben. Durch inlining sollte diese Zwischenschicht dann auch nichtmehr auf die Performance gehen.

Nur um + und - zu optimieren.
Denk dran, daß E=(A+B)*(C+D) gerne vielleicht X=A+B,Y=C+D,E=X+Y sein würde. Also kein Proxy mehr, ätschebätsch, weil man nicht 2n^3 mal zweimal + machen mag, sondern nur 2n^2 mal zweimal +. Das kannste wieder mit Metaprogrammierung rausfischen, was der Funktor machen muß, wenn links und rechts welche Funktoren waren. Dabei brauchen die Funktoren noch Zusatzinfos, was sie machen.
Aber das waren doch gerade DocShoes Proxies. Die sind zu füttern und schlau zu machen. Soo viele verschiedene Rechenoperatoren wird's dann schon nicht geben, daß man totgeht, wenn ein bißchen Code mehrfach ist. Das ist eh fast schon Write-Only-Code.
Ich hätte gerne, daß A+-B zu A-B vereinfacht wird. Da mußte der Vereinfacher des Plusproxys schauen, ob der rechte Teil ein UnärerMinusProxy ist und ein MinusProxy zurückgeben mit dem selben linken Teil und rechts nur dem Inhalt des UnärenMinusproxies. Das macht bestimmt viel mehr Freude, wenn diese zusätzliche Abstraktion noch nicht dabei ist.
Zumal wohl doch noch eine Ebene hinzukommen muß, nämlich denke ich, man muß AdditionProxy und AdditionAusdruck schon trennen, wobei AdditionAusdruck::eval() einen AdditionProxy zurückgibt, oder vermutlich besser ein Ausdruck<Addition<Matrix,Matrix>> gibt einen Proxy<Addition<Matrix,Matrix>> zurück, da spart man sich viel SFINAE mit, weil man im Prototyp auf Ausdruck<T> matchen kann und im Inneren dann T genüßlich zerlegen.

[camper]

yYy schrieb:

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

Optimierung ist nicht gleich Optimierung.

Wenn der Compiler "Optimierung" sagt, meint er "as-if" im Sinne des Standards (1.9/1), d.h. besseren Code zu erzeugen, der das Gleiche tut.

RVO und NRVO sind "Optimierungen" im Sinne des Standards, d.h. Transformationen, die das erzeugte Progamm und dessen Verhalten ändern, man könnte sagen, dass es sich um Sprachvarianten handelt. Es wäre eher kontraprofuktiv das eine vom anderen abhängig zu machen. Führt der Compiler nämlich (N)RVO nur durch, wenn im Optimierung im Allgemeinen erlaubt ist, dann ist es nicht mehr möglich, die (RVO)-optimierte Version vernünftig zu debuggen.

[bmario]

Ich hab grade mal probiert, wie das für + und * Funktoren und einem einheitlichen MatrixProxy gehen könnte und musste feststellen, dass man dann in die Funktoren zu viel Logik packen müsste. Etwa dadurch, dass sich die Dimension der resultierenden Matrix bei der + und der * Operation unterschiedlich verhält.

[yYy]

Hallo noch mal,

ich habe den Operator^ als Potenzierungsoperator überladen. Wenn ich diesen aufrufe, wird wieder keine (N)RVO angewendet. Ich habe auch versucht, ihn als freien Operator zu implementieren, wie schon mal geraten (und geholfen), aber das bringt nichts. Habe ich jetzt wider irgendwas falsch gemacht, oder muss man bei unterschiedlichen Operatoren unterschiedliches beachten?

Matrix operator^(unsigned int const &c) const
		{
			if (m != n)
			{
				//...
			}
			if (c == 0)
			{
				Matrix tmp = identity(m);
				return tmp;
			}
			Matrix M = *this;
			unsigned int potenz = 1;
			for (; potenz <= c/2; potenz *= 2)
				M *= M;
			for (; potenz < c; potenz++)
				M *= *this;
			return M;
		}

[314159265358979]

Benutz doch fürs Potenzieren die Funktion pow() aus dem Header <cmath>. Evtl wäre es auch nützlich, Wurzelziehen über Exponenten zuzulassen?

[yYy]

314159265358979 schrieb:

Benutz doch fürs Potenzieren die Funktion pow() aus dem Header <cmath>. Evtl wäre es auch nützlich, Wurzelziehen über Exponenten zuzulassen?

Und pow kann meine Matrizen potenzieren?
Wie du aus einer Matrix eine Wurzel ziehen willst, will ich sehen...

[Nexus]

yYy schrieb:

ich habe den Operator^ als Potenzierungsoperator überladen.

Schlechte Idee. Erstens assoziiert kein C++-Programmierer den operator^ mit Potenz, zweitens hast du eine unglückliche Operatorpriorität. Schreib eine benannte Funktion dafür.

yYy schrieb:

Wenn ich diesen aufrufe, wird wieder keine (N)RVO angewendet.

NRVO wird nicht immer angewandt. In deinem Fall hast du mehrere unterschiedliche Objekte, die zurückgegeben werden. Der Compiler nimmt dann wahrscheinlich an, dass er ohnehin kopieren muss.

Schau dir mal Exploiting Copy Elisions und Want Speed? Pass by Value inklusive der Kommentare an.

yYy schrieb:

unsigned int const &c

Nimm unsigned int , die Referenz auf const bringt hier nichts.

[camper]

yYy schrieb:

Hallo noch mal,

ich habe den Operator^ als Potenzierungsoperator überladen. Wenn ich diesen aufrufe, wird wieder keine (N)RVO angewendet. Ich habe auch versucht, ihn als freien Operator zu implementieren, wie schon mal geraten (und geholfen), aber das bringt nichts. Habe ich jetzt wider irgendwas falsch gemacht, oder muss man bei unterschiedlichen Operatoren unterschiedliches beachten?

Matrix operator^(unsigned int const &c) const
		{
			if (m != n)
			{
				//...
			}
			if (c == 0)
			{
				Matrix tmp = identity(m);
				return tmp;
			}
			Matrix M = *this;
			unsigned int potenz = 1;
			for (; potenz <= c/2; potenz *= 2)
				M *= M;
			for (; potenz < c; potenz++)
				M *= *this;
			return M;
		}

Operatorfunktionen sind ganz normale Funktionen die lediglich einen speziellen "Namen" haben. Es gelten also keine besonderen Regeln. Ansonsten spricht in dem gezeigten Code nichts prinzipiell gegen die Anwendung von NRVO bei den returns; andererseits verhalten sich Compiler manchmal seltsam. Das erste was du veruschen könntest (und das würde ich sowieso aus anderen Gründen empfehlen), ist, die Funktion in kleinere Teile zu zerlegen.

Matrix operator^(unsigned int const &c) const
{
    return m == n ? c == 0 ? identity(m) : pow_square(*this,c) : pow_non_square(*this,c);
}

mit den entsprechrechenden privaten Funktionen. RVO bezogen auf den Operator ist dann trivial - und wenn der Compiler das nicht schafft, gibt es wenig was du noch tun könntest - und die Einzelfunktionen sind dann erheblich simpler. Übrigens ist dein Algorithmus nicht ganz optimal: x^32 ist schnell, x^31 dagegen nicht.

[ipsec]

Jetzt mal eine Verständnissache. Nach meiner Auffassung ist (N)RVO, dass die Funktion das Returnobjekt nicht auf ihrem Bereich des Stacks anlegt, sondern direkt in den Stackbereich des Aufrufers konstruiert. Das impliziert, dass nur ein Rückgabewert optimiert werden kann - wenn die Funktion an unterschiedlichen Stellen bzw. mit unterschiedlichen Werten verlassen wird, muss der Compiler sich aussuchen, welche Rückgabe er optimiert. Ergo ist campers Beispiel gerade nicht trivial, weil der Compiler überhaupt keinen Ansatz hat, bei welchen der möglichen Werte sich eine Optimierung lohnt.

Auf der sicheren Seite bist du auf jeden Fall, wenn du deine Matrix movable machst. Dann hast du auch in dem Fall, dass keine (N)RVO angewendet wird, nur geringen Overhead.

[camper]

ipsec schrieb:

Jetzt mal eine Verständnissache. Nach meiner Auffassung ist (N)RVO, dass die Funktion das Returnobjekt nicht auf ihrem Bereich des Stacks anlegt, sondern direkt in den Stackbereich des Aufrufers konstruiert.

Das ist der Trick, um NRVO zu implementieren.

Das impliziert, dass nur ein Rückgabewert optimiert werden kann - wenn die Funktion an unterschiedlichen Stellen bzw. mit unterschiedlichen Werten verlassen wird, muss der Compiler sich aussuchen, welche Rückgabe er optimiert.

Nicht ganz, problematisch ist es nur, wenn zu irgendeinem Zeitpunkt zwei Objekte gleichzeitig existieren, die potentiell als Rückgabewerte in Frage kommen

Ergo ist campers Beispiel gerade nicht trivial, weil der Compiler überhaupt keinen Ansatz hat, bei welchen der möglichen Werte sich eine Optimierung lohnt.

was hier nicht der Fall ist. Die potentiellen Scopes überschneiden sich nämlich nicht.

[ipsec]

Gut, kleiner Denkfehler, das ergbt natürlich Sinn.

[camper]

ipsec schrieb:

Gut, kleiner Denkfehler, das ergbt natürlich Sinn.

Es ist aber möglicherweise tatsächlich ein praktischer Grund für den Compiler.
Nämlich dann, wenn dieser - als nichtstandardkonforme Erweiterung - Sprünge zwischen in Scopes von non-POD Objekten zulässt (was mit goto ja nicht geht, aber man könnte z.B. an longjmp & co. denken).

[yYy]

Ich habe überlegt, ob ich dem Compiler ein wenig auf die Sprünge helfen kann.
Mit folgendem Code wird immerhin schon beim Aufruf von A^0 die Optimierung durchgeführt. (Zumindest bekomme ich nur eine Konstruktor und eine Destuktor-Ausgabe.)

Matrix operator^(Matrix const &A, unsigned int c)
	{
		if (A.m != A.n)
		{
			throw std::invalid_argument("Matrix muss quadratisch sein.");
		}
		else if (c == 0)
		{
			return identity(A.m);
		}
		else
		{
			Matrix M = A;
			unsigned int potenz = 1;
			for (; potenz <= c/2; potenz *= 2)
				M *= M;
			for (; potenz < c; potenz++)
				M *= A;
			return M;
		}
	}