operator+ ohne Kopie?



  • 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.



  • 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;
    		}
    


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



  • 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...



  • 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.


  • Mod

    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.



  • 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.


  • Mod

    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.



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


  • Mod

    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).



  • 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;
    		}
    	}
    


  • Hmm... Diese interessante Diskussion habe ich erst jetzt gesehen. Ich möchte da auch noch mal meinen Senf dazugeben:

    Die Berechnung des Matrixprodukts (mit einer neuen Matrix statt eines Proxies als Ergebnis) würde ich auslagern in eine Funktion der Art

    void multiply(matrix const& a, matrix const& b, matrix & result);
    

    Ich wüsste jetzt auch nicht wie man ein Produkt "in-place" berechnen kann. Von daher würde ich lieber so eine Funktion wie oben statt *= in den restlichen Operatoren verwenden. Diese lässt sich dann auch beim Potenzieren per square-and-multiply verwenden. Ich denke mal, dass, wenn man das Matrix-Potenzieren per *= implementiert, viele temporäre Matrizen anfallen. Und das ewige Speicherreservieren/freigeben kostet Zeit.

    Move Semantics (C++2011)
    Wenn man es sich einfach machen möchte und trotzdem möglichst wenig überflüssige Kopierorgien durchführen will, geht das meiner Meinung in C++2011 mit Move Semantics am besten. Dazu benötigt die matrix-Klasse einen Move-Ctor und einen Move-Assignmeht-Operator.

    inline matrix operator*(matrix const& a, matrix const& b)
    { matrix result; multiply(a,b,result); return result; }
    

    Ich zweifle hier jedoch daran, ob eine Überladung für && (rvalues) sinvoll ist. da ich spontan nicht wüsste, wie man ein Produkt "in-place" berechnen soll. Aber für + und - geht das natürlich:

    inline matrix operator+(matrix const& a, matrix const& b)
    { matrix result (     a ); result += b; return result; }
    inline matrix operator+(matrix && a, matrix const& b)
    { matrix result (move(a)); result += b; return result; }
    inline matrix operator+(matrix && a, matrix && b)
    { matrix result (move(a)); result += b; return result; }
    inline matrix operator+(matrix const& a, matrix && b)
    { matrix result (move(b)); result += a; return result; }
    

    (Hier nehme ich an, dass matrix dynamischen Speicher verwendet, so dass sich move semantics lohnt)

    Ich gebe hier absichtlich nicht constante Matrix-Objekte zurück. Wer sich hier auf Scott Meyers' Regel beruft, dem sei gesagt, dass er sein "Effective C++" vor der Einführung von Move Semantics aufgestellt hat und bereits öffentlich zugegeben hat, dass diese Daumenregel damit nicht mehr zeitgemäß ist, da sie move semantics unnötig verhindern könnte.

    non-const Rückgabewerte
    Ich gebe auch absichtlich keine Referenzen zurück, da zu gefährlich und da es nichts bringen würde.

    Wer so Sachen wie a+b=c immer noch verhindern will, darf, wenn die Compiler das dann endlich mal unterstützen, eine Ref-Qualifier verwenden:

    matrix& operator=(matrix m) [b]&[/b]
      { swap(*this,m); return *this; }
    

    Swaptimization
    Steht einem "move semantics" nicht zur Verfügung, darf man "Swaptimization" verwenden. Nexus hat dazu einen netten Link parat gehabt. Hier würde das dann so aussehen:

    // absichtlich keine const-ref bei a !
    matrix operator+(matrix a, matrix const& b)
    {
      matrix result;   // <-- billig
      swap(result,a);  // <-- billig
      result += b;
      return result;   // <-- NRVO (guter Compiler tut das)
    }
    

    double --> vector<double>**
    Von double** würde ich abraten. Lieber std::vector<double> verwenden und dann alle Matrix-Elemente hintereinander packen (row-major oder column-major storage).

    Expression Templates und Proxies
    Dann gibt es natürlich noch Expression Templates oder so Ansätze wie Proxy-Objekte. Damit kann man auch temporäre Objekte sparen. Sowas ist aber ein relativ großer Implementierungsaufwand und nicht ganz unproblematisch, was die Lebensdauer von referenzierten Matrizen angeht. Auch in Zeiten von "auto" wo man mal gerne schreibt:

    auto x = a*b + c*d;
    

    sind Expression Templates (ET) mit großer Vorsicht zu genießen. Deswegen bin ich auch eher dagegen, Expression Templates "implizit" einzusetzen. Unter "explizitem ET-Einsatz" verstehe ich folgendes:

    matrix ergeb = xpr(a)*b + xpr(c)*d;
    auto z = eval( xpr(a)*b + xpr(c)*d );
    

    Man sieht hier sofort, dass man mit Expression-Objekten arbeitet und kann auch sehen, ob man ein eval() hinter dem auto vergessen hat. Ein xpr-Aufruf würde ein Expression-Objekt erzeugen (ähnlich wie bei Boost.Lambda) und mit eval() würde es explizit ausgewertet. Eine implizite Konvertierung eines Matrix-Expression-Objekts zu einer Matrix ist sinnvoll. Dann kann man auch viele Operatoren einfach so implementieren:

    inline matrix operator*(matrix const& a, matrix const& b)
    { return xpr(a)*b; }
    

    wenn man ohne ETs rechnen will.

    Die Lebenszeitproblematik von referenzierten Objekten bei ET-Nutzung kann man etwas entschärfen, indem man mit C++2011-Mitteln beispielsweise nach lvalues und rvalues unterscheidet. lvalues leben hoffentlich lang genug, dass man Referenzen darauf im expression-objekt speichern darf. rvalues kann man dank move semantics effizient in das expression-objekt umziehen lassen. Dann sollte man expression-Objekte aber auch nicht leichtfertig kopieren sondern auch ggf "moven". Das endet womöglich in vielen vielen const&/&& Überladeungen, was auch einiges an Schreibarbeit ist. 😞

    Alternativ wird auch wieder COW (copy-on-write) wieder interessant, finde ich. So habe ich letztes Jahr angefangen, eine Bibliothek für spezielle Optimierungsprobleme zu schreiben, bei der auch Expression Templates zum Einsatz kamen. Hier habe ich auf COW gesetzt. Vektoren werden in das Expression-Objekt kopiert -- ob lvalue oder rvalue. Aber das Kopieren ist billig dank COW und die Expression-Objekte werden damit auch nie ungültig. Für COW hatte mich mir ein Klassentemplate für eine Wrapper-Klasse geschrieben. Diese kann man dann auch noch move-optimieren. Das bringt sogar bei COW etwas, weil man damit die Referenzzähler schön niedrig halten kann und sich das Kopieren vor einer Modifikation ggf sparen kann.

    kk
    (hatte zuletzt implizite ETs verwendet, die sich über COW mit "containern" die resourcen teilen).


  • Mod

    Wie gesagt: Auslagern in eine eigene Funktion dürfte helfen. Wenn es ein Operator sein muss, ist ^, wie schon gesagt wurde eine schlechte Wahl, weil es in C++ ein zu niedrige Priorität hat. Eine schöne Alternative könnte ->* sein. ^ ist auch nur ein verkappter noch oben gerichter Zeiger, in ->* ist dafür der Zusammenhang mit * gegeben. Jedenfalls hat ->* genau die richtige Priorität.

    Abgesehen davon ist NRVO hier gar nicht das Problem: streng genommen willst du das gar nicht: eine Kopie ist nämlich gänzlich unvermeidlich, da eine in-place Matrix-Multiplikation nicht möglich ist. Es wird immer eine (temporäre) Kopie benötigt. Anstatt also die Kopie beim return zu vermeiden, solltest du daran arbeiten, bei jeder Multiplikation die Zuweisung loszuwerden:

    // Ich nehme an es gibt eine Funktion void mul(Matrix& res, const Matrix& a, const Matrix& b)
    // die davon ausgehen darf, dass kein Aliasing zwischen res und a sowie res und b besteht
    // dann kann das Kopieren vermieden werden
    Matrix operator->*(Matrix const &A, unsigned int c)
    {
        return A.m == A.n ? c < 2 ? c == 0 ? identity(A.m) : A : pow(A, c) : throw std::invalid_argument("Matrix muss quadratisch sein.");
    }
    
    Matrix pow(const Matrix& A, unsigned c)
    {
        using std::swap;
        assert( A.m == A.n && c >= 2 );
        Matrix res;
        if ( c == 2 )
            mul(res, A, A);
        else
        {
           Matrix B, C;
           mul(B, A, A);
           Matrix* x = B;
           Matrix* y = C;
           for ( unsigned i = highest_power_of_2(c) >> 1;; )
           {
               if ( c & i != 0 )
               {
                   mul(*y, *x, A);
                   swap(x, y);
               }
               if ( i == 2 )
                   break;
               mul(*y, *x, *x);
               swap(x, y);
            }
            if ( c & 1 != 0 )
            {
                mul(*y, *x, *x);
                mul(res, *y, A);
            }
            else
                mul(res, *x, *x);
         }
         return res;             // NRVO
    }
    

Anmelden zum Antworten