Dilemma: Geschwindigkeit contra Design

Liebe Experten,

ich habe eine Klasse für Matrizen (zweidimensionale Arrays) geschrieben, die als Member-Variablen die Anzahl Zeilen, die Anzahl Spalten und einen Zeiger auf einen Speicherbereich beinhaltet. Der Speicher für die Array-Elemente werden dynamisch alloziiert.

Wenn ich jetzt Methoden schreibe (z.B. eine Inverse), dann könnte ich die schnelle Variante verwenden, also:

Ergebnismatrix.inv(Eingabematrix);

Dies ist natürlich nicht, was man von objektorientiertem Design gewöhnt ist. Bei richtigem Design, müßte der Aufruf wie folgt aussehen:

Ergebnismatrix = Eingabematrix.inv();

Das Dumme ist nur, daß dann zusätzlich mit dem überladenen Zuweisungs-Operator (=) eine zusätzliche Kopie der Matrix erzeugt wird, was das Ganze bei großen Matrizen enorm verlangsamt.

Was gibt es für Auswege aus diesem Dilemma?

Danke schon mal im Vorraus,

Daniel.

Hi,
du koenntest zwei Methoden exportieren: eine Matrix inverse(), die das Inverse liefert und eine void invert(), die das aktuelle Objekt invertiert.
Um das effizient zu gestalten kannst du intern die gleiche Funktion benutzen. inverse() kopiert die Matrix, laesst den Algorithmus drueber laufen und gibt eine Referenz auf die Kopie zurueck.
invert() arbeitet direkt auf dem Original-Array.
Die Methoden kann man auch eindeutiger benennen :wink:
Gruesse,
Moritz

Hallo Moritz,

danke für deine rasche Antwort. Das Problem mit deinem Vorschlag ist, daß ich dann zwar eine Kopie mit dem richtigen Ergebnis erzeugt habe, aber diese ja nur eine temporäre Variable ist, die nur innerhalb des Funktionsrumpfes gilt. Und wenn ich die Referenz darauf zurückgebe, dann wird nach dem Verlassen der Funktion der Destruktor aufgerufen und die Referenz zeigt ins Leere (der Compiler warnt sogar davor).

Hier kurz ein idealisiertes Beispiel dazu:

Matrix& inverse()
{
 Matrix Ergebnis;
  Ergebnis.kopiere(this);
  Ergebnis.invertiere();
  return(Ergebnis);
}

Schöne Grüße,

Daniel.

Matrix& inverse()

Du darfst natürlich hier keine Referenz zurückgeben sondern nur den Typ „Matrix“…

Hi,
dann erzeuge doch einfach per new eine Matrix auf dem Heap und gebe die zurueck.
Grüße,
Moritz

Hallo Moritz,

danke für die erneute Antwort. Ja, das habe ich schon versucht, allerdings mit der Inverse-Routine selbst, z.B.

Matrix inverse()
{
 Matrix pErgebnis = new Matrix;
 ...
 pErgebnis-\>element(i,j) = element(i,k) \* element(j,k);
 ...
 return(pErgebnis);
}

Das Dumme ist nur, daß die Zeigeroperation „->“ das ganze enorm verlangsamt. Ich könnte aber eine Kombination aus deinem Vorschlag und dieser Lösung versuchen:

Matrix inverse()
{
 Matrix pErgebnis = new Matrix;
 ...
 pErgebnis-\>invertiere(); // Aufruf der "internen" Routine
 ...
 return(pErgebnis);
}

Dann wird nämlich der Zeigeroperator „->“ nur einmal aufgerufen. Ich werde das nächste Woche mal ausprobieren.

Vielen Dank und schöne Grüße,

Daniel.

Hallo Nicos,

danke für deine Antwort. Ja, du hast recht, das ist genau das Problem. Wenn ich aber keine Referenz, sondern das Objekt selbst zurückgebe, dann wird automatisch der =-Operator aufgerufen, der die komplette Matrix kopiert, was das ganze enorm verlangsamt.

Ich werde am Montag mal den neuen Vorschlag ausprobieren.

Schöne Grüße,

Daniel.

Hallo,

> Matrix inverse()  
> {  
> Matrix pErgebnis = new Matrix;


das wird schon mal nicht kompilieren; du Mustt pErgebnis als Zeiger deklarieren:
 Matrix\* pErgebnis = new Matrix;



> ...  
> pErgebnis-\>element(i,j) = element(i,k) \* element(j,k);  
> ...  
> return(pErgebnis);  
> }

Das Dumme ist nur, daß die Zeigeroperation „->“ das ganze
enorm verlangsamt.

sicher? mit einem guten Kompiler und guten Betriebssystem sollte die Matrix, wenn sie nicht zu gross ist, im Cache des Prozessors bleiben, dann duerfte man kaum einen Unterschied merken…

Ich könnte aber eine Kombination aus deinem

Vorschlag und dieser Lösung versuchen:

Matrix inverse()
{
Matrix pErgebnis = new Matrix;

pErgebnis->invertiere(); // Aufruf der „internen“ Routine

return(pErgebnis);
}

Das war eigentlich das woran ich gedacht hab - sorry dass ich mich nicht so klar ausgedrueckt hab…

Grüße,
Moritz

Hallo Daniel,
weisst du denn ob das Kopieren tatsächlich zu so deutlicher Verlangsamung führt? Immerhin braucht die Berechnung des Inversen O(n^3) Schritte waehrend das kopieren in linearer Zeit klappt, die meisten Chipsätze kopieren Speicherblöcke auch recht schnell.
Kann es sein dass du dir unnötige Sorgen über die Performance machst oder hast du praktische Erfahrung (mit Profiler) damit?
Grüße,
Moritz

[Bei dieser Antwort wurde das Vollzitat nachträglich automatisiert entfernt]

Hallo Daniel,

ich habe eine Klasse für Matrizen (zweidimensionale Arrays)
geschrieben, die als Member-Variablen die Anzahl Zeilen, die
Anzahl Spalten und einen Zeiger auf einen Speicherbereich
beinhaltet. Der Speicher für die Array-Elemente werden
dynamisch alloziiert.

ok.

Wenn ich jetzt Methoden schreibe (z.B. eine Inverse), dann
könnte ich die schnelle Variante verwenden, also:
Ergebnismatrix.inv(Eingabematrix);

Mit „schnelle Variante“ meinst Du hier wahrscheinlich
eine Variante „ohne automatische Erzeugung eines
temporären Arrays“.

Dies ist natürlich nicht, was man von objektorientiertem
Design gewöhnt ist. Bei richtigem Design, müßte der Aufruf wie
folgt aussehen:
Ergebnismatrix = Eingabematrix.inv();

Würde ich nicht sagen, da Du ja *nicht* Eingabematrix
selbst invertieren möchtest, sondern Du möchtest eine
an Ergebnismatrix zugewiesene Kopie von
Eingabematrix invertieren.

Du suchst imho: EI = ER ^ -1 im Sinne von (EI = ER) ^ -1

Das Dumme ist nur, daß dann zusätzlich mit dem überladenen
Zuweisungs-Operator (=) eine zusätzliche Kopie der Matrix
erzeugt wird, was das Ganze bei großen Matrizen enorm
verlangsamt.

Diese Verlangsamung tritt afaik nur bei simplen
Matrixoperationen wie z.B. ADDMUL auf. Eine Invertierung
ist selbst geschwindigkeitsbestimmend, wie in den anderen
Postings hier schon zu lesen war.

Was gibt es für Auswege aus diesem Dilemma?

Eigentlich ist das gar kein Dilemma. Die Grundregel
des absoluten C+±Gurus ist zu beherzigen: "keep ist
simple and stupid
"

Daher wäre die Lösung, die man auch nach Jahren beim
Durchsehen des Quelltextes noch versteht, vielleicht diese:

 Ergebnismatrix = Eingabematrix;
 Ergebnismatrix.inv();

Allerdings müsste man die Matrix ‚in place‘
invertieren können, sonst klappt das nicht.

Wenn Du es schicker haben willst, kannst Du
auch einen Objekt-Operator ^= definieren

 Ergebnismatrix ^= Eingabematrix; 

was aber nicht sehr eingängig ist.
Oder mit einer Kombination der beiden Objekt-
Operatoren „operator=(const Matrix&amp:wink:“ und
„operator^(int oper)“ zuschlagen.
Und das einmal *mit* temporärer Kopie:

Ergebnismatrix = Eingabematrix ^ -1;

und einmal *ohne*

(Ergebnismatrix = Eingabematrix) ^ -1;

Ein Problem tritt auf, wenn Du, wie oben angemerkt, auf
beide Matrizen zur selben Zeit Zugriff brauchst
(z.B. weil eine ‚in place‘ Operation nicht geht), aber
trotzdem keine unnötige temporäre Kopie haben willst.
Dann *musst* Du imho eine Variante im Sinne von

Ergebnismatrix.inv(Eingabematrix);

verwenden, ohne zu härteren Bandagen (z.B.
verstecktes klasseneiges statisches temp-Array,
das du dann im Hintergrund über Zeiger mit dem
Ergebis austauschst) greifen zu müssen.

Also: entweder mit Kopie oder mit Deiner
„schnellen Variante“ :wink:

Grüße

CMБ

Hallo Daniel,:Also: entweder mit Kopie oder mit Deiner
„schnellen Variante“ :wink:

Beide Varianten lassen sich miteinander kombinieren, indem du eine Klasse als reinen Container implementierst, und eine andere Klasse die Darstellung einer Matrix übernimmt. Das hörst sich im ersten Moment ein wenig konfus an, macht aber durchaus Sinn. Bestes Beispiel ist die Implementierung der Klasse std::string, viele Compilerhersteller nehmen hier auch so eine Trennung vor (der C++ Standard weisst im übrigen explizit auf dieses Model hin) und beschleunigen die Implementierung mit COW Algorithmen.

Beispiel:

std::string t1(„hello world“);

legt ein übliche Zeichenkette an, nichts besonderes.

std::string t2( t1 );

Auf den ersten Blick wird die Zeichenkette t1 kopiert, bei genauerem hinsehen in die Quelltexte offenbart sich aber, hier wird nur zum schein kopiert. Der Trick besteht darin, dass ein std::string immer die gleiche größe hat, unabhängig davon, wieviele Zeichen im std::string stecken. std::string verweist stattdessen auf eine Instanz einer anderen Klasse, die die Speicherung von Zeichen übernimmt. Der Kopiervorgang sieht dann so aus, das t1 und t2 abschließend auf den gleichen Inhalt verweisen. Anders als ein strcpy werden also nicht ganze Speicherbereiche umkopiert, sondern nur Pointer.

Damit ergibt sich ein weiteres Problem, was passiert wenn t1 seinen Inhalt ändert, t2 darf dann nicht verändert werden. Die Lösung hierzu heisst COW = Copy On Write. In der Literatur und auch in google wirst du einiges zu diesem Thema finden. Im Prinzip geht es darum, das ein einzlenes Objekt geSHAREd wird, du sparst dir die Kosten für n gleiche Kopien. Im gleichen Zug werden Referenzen gezählt, der interne std::string weiss, wieviele std::string Objekte es referenzieren.

Muss ein interner std::string schreiben, also non-const, zugegriffen werden, so erzeugt das entsprechende std::string objekt eine Kopie und verwendet diese stattdessen.

Bezogen auf die Matrix sähe das in etwa wie folgt aus:

class Matrix{
MatrixImpl* pImpl;
};

class MatrixImpl {
int references; // wieviele Matrix-Objekte verweisen ?
};

Ein weiter Schritt besteht darin, die Matrix-Implementierung auf mehere spezialisierte Klassen aufzuteilen. Sicherlich benötigt ein Matrix Container eine sinnvolle standard-initialisierung, aber muss dafür jedesmal wertvoller Speicher allokiert werden?

class MatrixImpl; // eine rein abstracte Klasse

class UninitializedMatrix : public MatrixImpl …

Kannst du als Singleton realisieren, jede Methode wirft nur eine Exception. Spezielle, häufig verwendete Matrizen, werden ebenfalls mit einer eigenen Klasse bedacht.
Stell dir als analogie die Datentypen float, short und int vor, nimm an, sie werden durch eine Klasse implementiert. Du weisst, das Ergebnis durch die Addition von zwei short in jedem Fall in den Datentype int passt:

class Short {
Int operator+( const Short& ) const;
// ist der zweite Operand ein Float, sieht das schon anders aus
Float operator+(const Float& ) const;
};

Du schafft für deine speziellen Klassen angepasste Operatoren. Die Klassen Short, Int und Float sind eng miteinander verwand. Es handelt sich hier um einen Design Pattern, der in der Literatur auch als Family Pattern bekannt ist.

Ich hoffe so ein wenig neue Anregung gegeben zu haben.

Gruß Markus

1 Like

Liebe Experten,

nach einigem Probieren habe ich eine eingermaßen befriedigende Lösung gefunden.

Die Erzeugung der Matrix auf dem Heap war problematisch, da ich den Speicher nicht mehr frei bekommen habe. Dadurch passiert es, daß wenn die Routine ein paar tausend Mal in einer Schleife aufgerufen wird, auf die Platte geswappt wird und sich eine enorme Verlangsamung ergibt. Nicht zu reden von den Speicherlöchern.

Ich favorisiere jetzt folgende Variante mit zwei überladenen Methoden:

// "schnelle" Methode: referenz auf Ergebnisobjekt wird übergeben.
// ähnlich wie bei strcpy.
Matrix inv(Matrix& RES)
{
 ...
 RES(i,j) = ....
 ...
 return(RES);
}

// langsamere aber "elegante" methode (ruft schnelle Methode auf)
Matrix inv()
{
 Matrix RES;
 return(inv(RES));
}

Bei einer einzigen Invertierung einer großen Matrix ist die zweite Methode 20-50% langsamer. In einer Schleife etwa doppelt so langsam. Intern verwende ich natürlich die schnelle Variante, stelle aber beide Varianten den Benutzer der Bibliothek zur Verfügung.

Danke für die vielen Tips und Ratschläge,

Daniel.