Referenz vs. lokale Kopie
-
MahlZeit!
Ich sitze momentan an einem C++ Software Projekt und habe eine grundlegende Frage, die hoffentlich von einem erfahrenen Programmierer schnell beantwortet werden kann.
Es geht um die Frage was schneller ist, einer Funktion eine Referenz zu uebergeben und mit dieser zu arbeiten oder eine lokale Kopie zu erstellen und am Ende der Referenz den Inhalt zuzuweisen.Durch folgenden Code wurde das ausprobiert und im grossen Umfang getestet. multiply ist eine Member-Funktion von MontgRep. Der Datentyp "MontgRep" besteht aus einem plus- und einem minus-Teil, die jeweils Datentyp vec_ZZ_p ( Vektoren ) sind.
void multiply(MontgRep &a, const int &A_temp) { vec_ZZ_p thevecp,thevecm; // das sind spezielle Vektoren thevecp.SetLength(plus.length()); thevecm.SetLength(plus.length()); for (int i=plus.length()-1; i>=0; i--) { thevecp[i] = a.plus[i]*A_temp; thevecm[i] = a.minus[i]*A_temp; } plus=thevecp; minus=thevecm; }Im Gegensatz zu
void multiply(MontgRep &a, const int &B_temp) { //Folgender Code geht auch ist aber langsamer!!!!! for (int i=plus.length()-1; i>=0; i--) { plus[i] = a.plus[i] * B_temp; minus[i] = a.minus[i] * B_temp; } }Eigentlich dachte ich, dass es fuer solch grundlegende Sachen zu viel Aufwand ist, noch zusaetzlich lokale Objekte zu erstellen ( auch wenn sie nicht so gross sind ), wenn man schon Speicher fuer das referenzierte Objekt zur Verfuegung hat, welchen man doch auch nutzen kann ( mir wurde sogar mal geraten, dass man den auch nutzen sollte ).
Aber es hat sich herausgestellt, dass das Arbeiten mit einer erstellten einer Kopie und abschliessendem Zuweisen der Werte auf das referenzierte Objekt schneller geht!?Dieses wurde dann versucht auf andere Funktionen anzuwenden, jedoch mit unterschiedlichem Erfolg, sprich es wurde an anderer Stelle mit voellig aequivalenter Herangehensweise langsamer.
Das richt in meiner Nase nach einer speziellen Benutzung von Referenzen. Da diese mir einfach noch nicht bekannt ist, hoffe auf diesem Wege einen Rat zu bekommen.
Hinweise auf Buecher, die das gut umschreiben, werden natuerlich auch dankend angemommen, falls jemand damit dienen kann ... !
Ueber Reaktionen waere ich natuerlich sehr dankbar!
MfG
#50
-
Raute50 schrieb:
Dieses wurde dann versucht auf andere Funktionen anzuwenden, jedoch mit unterschiedlichem Erfolg, sprich es wurde an anderer Stelle mit voellig aequivalenter Herangehensweise langsamer.
jo, ist klar, ne.
referenz macht ne indirektion mehr bei jedem zugriff. wenn du dann damit eine hypergeometrische matrizeninversion machst, bei der für hundert matrixelemente 100^4 zugriffe (indirektionen) passieren, aber sonst nix wesentliches, wäre ne lokale kopie besser. nur einmal kopieren und dann 100000000 indirektionen sparen.
machste aber nur ne observation, ob es ne einheitsmatix ist, guckste mal eben durch die indirektion die matrix an und returnst dein ergebnis, statt erst 100 elemente zu kopieren und dann nur 10 anzugucken.
als faustregel sollte gelten, daß referenz schneller ist als kopie.
eine alternative ist sicherlich auch, sich ne referenz zu ziehen und nen zeiger auf die interne repräsentation lokal anzulegen und auf dem den teuren algo auszuführen.
-
volkard schrieb:
Raute50 schrieb:
Dieses wurde dann versucht auf andere Funktionen anzuwenden, jedoch mit unterschiedlichem Erfolg, sprich es wurde an anderer Stelle mit voellig aequivalenter Herangehensweise langsamer.
jo, ist klar, ne.
Was soll mir klar sein ? Das es mal klappt und mal nicht ?!
volkard schrieb:
referenz macht ne indirektion mehr bei jedem zugriff. wenn du dann damit eine hypergeometrische matrizeninversion machst, bei der für hundert matrixelemente 100^4 zugriffe (indirektionen) passieren, aber sonst nix wesentliches, wäre ne lokale kopie besser. nur einmal kopieren und dann 100000000 indirektionen sparen.
machste aber nur ne observation, ob es ne einheitsmatix ist, guckste mal eben durch die indirektion die matrix an und returnst dein ergebnis, statt erst 100 elemente zu kopieren und dann nur 10 anzugucken.
als faustregel sollte gelten, daß referenz schneller ist als kopie.
eine alternative ist sicherlich auch, sich ne referenz zu ziehen und nen zeiger auf die interne repräsentation lokal anzulegen und auf dem den teuren algo auszuführen.
Wir benutzen die referenzierten Objekte schon ... Die Sache ist nur die, dass wir manchmal ein lokales Objekt erstellen dem die Ergebnisse ( in dem obigen Beispiel ein einfaches Produkt ) zugewiesen werden und das schneller ist, als einfach dem referenzierten Objekt gleich die Werte zuzuweisen ...
Aber das ist von Fall zu Fall unterschiedlich und fuer uns nicht ersichtlich woran das liegen mag ...
MfG
#50
-
Es gibt verschiedene Möglichkeiten. Abhängig vom Zielsystem könnte der registersatz zu klein sein, um alle temporären Ergebnisse aufzunehmen (dann entsteht das von volkard angesprochene problem mit der permanenten indirektion - nebenbei ist es kein vorteil, A bzw. B_temp als referenz zu übergeben). die variante ohne lokale vektoren leidet außerdem möglicherweise unter einem aliasing-problem. des weiteren ist anzumerken, dass die schleife mit dekrementierendem index arbeitet - das ist i.allg. keine gute idee, wenn hardware-prefetching im spiel ist. es könnte aus demselben grund auch sinnvoll sein, den plus- und minus-teil in getrennten schleifen zu verarbeiten. probier mal folgende varianten (annahme ist, dass vec_ZZ_p die daten in einem array speichert):
(restrict als #define auf __restrict__ o.ä. falls dein compiler das unterstützt, sonst leer)void multiply(MontgRep &a, int A_temp) { vec_ZZ_p thevecp,thevecm; thevecp.SetLength(plus.length()); thevecm.SetLength(plus.length()); ptrdiff_t i = -plus.length(); int* restrict s = &a.plus[0] - i; int* restrict t = &thevecp[0] - i; do t[i]=s[i]*a while (++i); i = -plus.length(); s = &a.minus[0] - i; t = &thevecm[0] - i; do t[i]=s[i]*a while (++i); plus=thevecp; minus=thevecm; }vs.
void multiply(MontgRep &a, int B_temp) { ptrdiff_t i = -plus.length(); int* s = &a.plus[0] - i; int* t = &plus[0] - i; do t[i]=s[i]*a while (++i); i = -plus.length(); s = &a.minus[0] - i; t = minus[0] - i; do t[i]=s[i]*a while (++i); }
-
camper schrieb:
Es gibt verschiedene Möglichkeiten. Abhängig vom Zielsystem könnte der registersatz zu klein sein, um alle temporären Ergebnisse aufzunehmen (dann entsteht das von volkard angesprochene problem mit der permanenten indirektion - **(1)**nebenbei ist es kein vorteil, A bzw. B_temp als referenz zu übergeben). die variante ohne lokale vektoren leidet außerdem möglicherweise unter einem **(2)**aliasing-problem. (3)des weiteren ist anzumerken, dass die schleife mit dekrementierendem index arbeitet - das ist i.allg. keine gute idee, wenn hardware-prefetching im spiel ist. (4)es könnte aus demselben grund auch sinnvoll sein, den plus- und minus-teil in getrennten schleifen zu verarbeiten. probier mal folgende varianten (annahme ist, dass vec_ZZ_p die daten in einem array speichert)
zu (1) :
also was wir bis dato gefunden haben ist der Bezug zwischen Objektgröße und Sinn des Referenzierens ...
Also es ist fast gratis eine Kopie von int abzuschreiben, dagegen macht es bei sehr großen Objekten mehr Sinn eine konstante Referenz zu übergeben ...
Das ist das was wir gefunden haben
zu (2) :
Variante ohne Lokale Vektoren führen zu waaaaaas ??zu (3) :
Warum das noch mal ?
Ich sehe ein, dass wenn man bei einem Vektor in der Regel um einen konstanten Faktor im Speicher geht, dass man das irgendwie cleverer machen kann ...
Aber bei vielen Aufrufen der Multiply und bei jedem Durchlauf häufigen Aufrufen von .length() dachten wir, da es syntaktisch eh egal ist, in welcher Reihenfolge da multipliziert wird, dass nur 1x ein Aufruf von .length() wesentlich günstiger wäre ... ????
Was hat das nun noch mal mit hardware prefetching zu tun ????zu (4) :
Haben wir ausprobiert ... ergab keinen Vorteil...Dann mal DANKE!
Haben unser Problem relativ gut gelöst ... besteht also nicht mehr ...
#50