[gelöst] Vector ist wesentlich langsamer als Array?

[ComputerCarl]

wow... Danke!
Ich muss mich da erstmal reinlesen. Diesen "erfahrenen"
Programmierstil bin ich noch nicht gewöhnt. Aber ich
glaube zu sehen was gemeint ist. Werde einfach meinen
Code überarbeiten (angelehnt an das gepostete).

Vielen Dank an alle die Tipps gegeben haben. Ich
werde jetzt einfach mal das Thema als gelöst markieren.

[cooky451]

zeusosc schrieb:

Hauerdrinn?

jetzt bin ich neugierig,... auslernen will ich ja auch nicht,...

Keine Sorge, "Auslernen" wirst du so schnell sicher nicht.

- Die sehr hässlichen _ am Anfang wurden ja schon erwähnt.
- Ein komisches selbst gebasteltes malloc statt new[]?
- Cast nach void*?
- Cast von 0 nach T*?
- Das ständige this-> irritiert total.
- Nicht richtig eingerückt.
- Komische und unnötige ; hinter if() und hinter Funktionen, die den Lesefluss total behindern.
- Index von operator [] nicht unsigned.

Und wo bitte ist bei dir überhaupt der Vorteil zu std::vector? Im Speicher liegt doch immer noch alles kreuz und quer, oder habe ich in dem WirrWarr jetzt den Super-Trick übersehen?

[cooky451]

@ComputerCarl

Was du noch machen kannst, wenn die Dimensionen zwar fest aber erst zur Laufzeit bekannt sind, ist, dir eine Klasse zu bauen, die Größenangaben zu den Dimensionen im Konstruktor nimmt, und dann Zugriff über operator () mit drei Indexvariablen auf einmal gibt. (Intern nutzt du einfach einen std::vector und reservierst sx * sy * sz Elemente am Stück).

int main()
{
  unsigned sx, sy, sz; // Werte einlesen
  DeineKlasse<float> mat(sx, sy, sz);
  mat(5, 7, 3) = 77; // Zugriff
}

Ob das viel schneller ist weiß ich nicht, da du den Index halt auch zur Laufzeit ausrechnen musst. (Das sind halt Multiplikationen, wie man die Dimensionen runterrechnet weißt du?)
Aber ich denke mal einen Versuch ist es wert.

[SeppJ]

cooky451 schrieb:

Ob das viel schneller ist weiß ich nicht, da du den Index halt auch zur Laufzeit ausrechnen musst. (Das sind halt Multiplikationen, wie man die Dimensionen runterrechnet weißt du?)
Aber ich denke mal einen Versuch ist es wert.

Glaub mir, das ist VIEL schneller.

Was ist denn Arraydereferenzierung? Additionen und Multiplikationen. Es ist daher so schnell wie ein zusammenhängendes Array mit dem Komfort eines Containers.

[cooky451]

SeppJ schrieb:

Was ist denn Arraydereferenzierung? Additionen und Multiplikationen. Es ist daher so schnell wie ein zusammenhängendes Array mit dem Komfort eines Containers.

Äh ja, stimmt, der Index muss ja auch bei statischen Arrays errechnet werden, irgendwie hatte ich da einen Denkfehler. Super, dann dürfte das ja die Lösung sein.

[arghonaut]

zeusosc schrieb:

soweit ich weiss folgt bei mir auf den Unterstrich aber ein
kleiner Buchstabe bzw. eine Zahl.

17.6.4.3.2: Global names, zweiter Punkt:

Each name that begins with an underscore is reserved to the implementation for use as a name in the global namespace.

Deine Klasse liegt im global namespace, deshalb ist ALLES was mit einem einzigen Unterstrich beginnt, ebenso der Implementierung vorbehalten und sollte vom User nicht verwendet werden.

[zeusosc]

cooky451 schrieb:

zeusosc schrieb:

Hauerdrinn?

jetzt bin ich neugierig,... auslernen will ich ja auch nicht,...

Keine Sorge, "Auslernen" wirst du so schnell sicher nicht.

- Die sehr hässlichen _ am Anfang wurden ja schon erwähnt.
- Ein komisches selbst gebasteltes malloc statt new[]?
- Cast nach void*?
- Cast von 0 nach T*?
- Das ständige this-> irritiert total.
- Nicht richtig eingerückt.
- Komische und unnötige ; hinter if() und hinter Funktionen, die den Lesefluss total behindern.
- Index von operator [] nicht unsigned.

Und wo bitte ist bei dir überhaupt der Vorteil zu std::vector? Im Speicher liegt doch immer noch alles kreuz und quer, oder habe ich in dem WirrWarr jetzt den Super-Trick übersehen?

Also, trick ist da keiner.
Die Anforderung war (so wie ich das sah):
Schreibe ein zur initialisierungszeit dynamisches Array auf
das man mit [][][] zugreifen kann, und recht fix ist.

STL vectoren springen häufig durch verschiedene Unterfunktionen,
die die Länge prüfen, ob der Zeiger richtig ist und und und,..
hier wird alloziiert und über maximal zwei ptrs beim zugriff
dereferenziert (und auf das dritte dan referenziert)...
sollte also relativ flink laufen,..

Jetzt mal vom underscore abgesehen:

* Zum new: ich vermeide es wo ich kann! (hier nutze ich es exakt 1x)
Wird der new operator nicht über den source definiert, so findet
eine (Compiler spezifische) Ersetzung statt, die ich erst zur Laufzeit
sehe. Das will ich nicht!

* Cast von 0 nach T* : 0 ist kein Typ.
Sind verschiedene konvertierungsvorschrifften vorhanden,
wird die erste passende vom Compiler genommen. (Meistens basistypen).
Ich will das der Compiler "explizit" 0 als T* behandelt.

* Cast nach void*: sehe ich jetzt nicht,.. wo?

* Index operator [] nicht unsigned: Ja,.. kann man so und so sehen,
"ist übergebene uint > size dann gib referenz" wäre hier wohl
bessere wahl gewesen, da hast du recht...

* this-> bleibt definitiv !!! es ist ein unterschied ob ich eine
Methode der Instanz aufrufe oder eine gleichnamige Funktion aus
dem gleichen Namensraum, geschweige denn Member.
Da der Compiler das so oder so die addy's der Member aus der
Referenzierung des this holt (in asm schön sichtbar), dann
kann ich es auch gleich richtig machen. Ausserdem ist dann
IMMER klar, WANN ich eine Methode oder Member innerhalb einer
Methode aufrufe,...
(Macht sich besonders bemerkbar wenn intellisense spinnt)

* Einrückung: hä? wie was? wo?
Es gibt ja mal wohl mehrere Varianten von einrückungen...

* ";" ?? Meines wissens hat nach jeder abgeschlossenen Anweisung ein ";"
zu folgen. Auch wenn manchen Compilern das wurscht ist....

Also bis auf die underscores und dem uint (danke, ja da haste ja recht)
sehe ich jetzt nicht viele hauerdrinn,...

@Cookie457:
Ja, hatte ich auch zuerst überlegt,... dann dachte ich, bevor er sich
mit "suchen und ersetzen" menüpunkt anlegt um die [i][j][k] durch
(i,j,k) zu ersetzen, gleich n template mit variabler dim anzahl
basteln. Er nutzt ja mehrere 1d 2d und 3d arrays.,...

grüße

[SeppJ]

zeusosc schrieb:

STL vectoren springen häufig durch verschiedene Unterfunktionen,
die die Länge prüfen, ob der Zeiger richtig ist und und und,..

Wenn du mit "häufig" meinst "im Debugmodus", dann kann man das so stehen lassen.

[cooky451]

zeusosc schrieb:

STL vectoren springen häufig durch verschiedene Unterfunktionen,
die die Länge prüfen, ob der Zeiger richtig ist und und und,..
hier wird alloziiert und über maximal zwei ptrs beim zugriff
dereferenziert (und auf das dritte dan referenziert)...
sollte also relativ flink laufen,..

Ein std::vector macht genau das gleiche. (Im Releasemodus). Nein, warte, er ist viel schneller als deine Version, weil er den Index nicht testet.

zeusosc schrieb:

* Zum new: ich vermeide es wo ich kann! (hier nutze ich es exakt 1x)
Wird der new operator nicht über den source definiert, so findet
eine (Compiler spezifische) Ersetzung statt, die ich erst zur Laufzeit
sehe. Das will ich nicht!

Bitte was?

zeusosc schrieb:

* Cast von 0 nach T* : 0 ist kein Typ.
Sind verschiedene konvertierungsvorschrifften vorhanden,
wird die erste passende vom Compiler genommen. (Meistens basistypen).
Ich will das der Compiler "explizit" 0 als T* behandelt.

Ja.. dann nimm nullptr.

zeusosc schrieb:

* Cast nach void*: sehe ich jetzt nicht,.. wo?

In Zeile 58.

zeusosc schrieb:

* Index operator [] nicht unsigned: Ja,.. kann man so und so sehen,
"ist übergebene uint > size dann gib referenz" wäre hier wohl
bessere wahl gewesen, da hast du recht...

Nein, die bessere Wahl wäre gewesen, den Test einfach nicht zu machen.

zeusosc schrieb:

* this-> bleibt definitiv !!! es ist ein unterschied ob ich eine
Methode der Instanz aufrufe oder eine gleichnamige Funktion aus
dem gleichen Namensraum, geschweige denn Member.
Da der Compiler das so oder so die addy's der Member aus der
Referenzierung des this holt (in asm schön sichtbar), dann
kann ich es auch gleich richtig machen.

Was heißt hier "richtig", es macht halt keinen Unterschied, aber das this wegzulassen ist übersichtlicher.

zeusosc schrieb:

Ausserdem ist dann
IMMER klar, WANN ich eine Methode oder Member innerhalb einer
Methode aufrufe,...
(Macht sich besonders bemerkbar wenn intellisense spinnt)

Das ist auch so klar. Mehr noch, this-> impliziert, dass diese explizite Schreibweise nötig ist, weil sonst etwas Anderes gemeint wäre. Daher sollte man es meiden, wenn dem nicht so ist.

zeusosc schrieb:

* Einrückung: hä? wie was? wo?
Es gibt ja mal wohl mehrere Varianten von einrückungen...

Das hat nichts mehr mit Stil zu tun, das ist einfach falsch bzw. teilweise gar nicht eingerückt.

zeusosc schrieb:

* ";" ?? Meines wissens hat nach jeder abgeschlossenen Anweisung ein ";"
zu folgen. Auch wenn manchen Compilern das wurscht ist....

Nein, keinem Compiler ist das egal. Aber leere ; sind jedem Compiler egal, deswegen kompiliert der Code überhaupt. Auf einen Scope muss kein ; folgen. (Und sollte dadurch auch nicht.)

zeusosc schrieb:

nicht viele hauerdrinn,...

Doch, das malloc Gefrickel ist eines der übelsten Sachen die ich seit Langem gesehen habe. Und wenn der Index nicht mehr gültig ist gibt man einfach einen *new T() zurück der nie mehr freigegeben wird?

zeusosc schrieb:

gleich n template mit variabler dim anzahl
basteln. Er nutzt ja mehrere 1d 2d und 3d arrays.,...

Das funktioniert nicht. Die Dimensionen sind erst zur Laufzeit bekannt, wären sie zur Compilezeit bekannt, könnte man auch einen std::vector<std::array<...>> nehmen. Daher fällt jegliches Templategezauber weg.

[otze]

Ich hoffe, du schaust nochmal in den Thread rein, auch wenn du das als (warum auch immer) gelöst markiert hast.

Ich habe mal ein wenig Code aus meinem aktuellen Projekt extrahiert und soweit vereinfacht, dass du es mit deinem Kenntnisstand verstehen müsstest. Das ist natürlich so minimal wie möglich, aber es sollte dir schon mal einen deutlichen Speedup geben. Aber du musst noch eine Menge Code hinzufügen, damit das für dein neuronales Netz passt.

Syntaxfehler könnten drin sein, und eventuell hab ich beim Umbauen auch igendwelche variablen vertauscht. Aber diese Fehler dienen dann nur dazu, dass du versuchst, den Code zu verstehen (jaja, ich bin gerade zu faul zum testen)

//stores a matrix in row major format.
//as minimal as possible, so it offers only element access via op():
//matrix(i,j)= 10;
//and a constructor which takes the dimensionality and a method which returns
//the internal block of memory
class Matrix{
private:
    std::vector<float> data;
    std::size_t rows;
    std::size_t columns;
public:
    Matrix(std::size_t nRows,std::size_t nColumns)
   :data(rows*columns),rows(nRows),columns(nColumns){}

   float& operator()(std::size_t row, std::size_t col){
       return data[row*columns+col];
   }
   float operator()(std::size_t row, std::size_t col)const{
       return data[row*columns+col];
   }
   std::size_t numRows()const{
       return rows;
   }
   std::size_t numColumns()const{
       return columns;
   }
   float const* storage()const{
       return &data[0];
   }
};

//prod(A,b,c) computes c+=A*b
//where b,c are vectors and A is a matrix 
void prod(
    Matrix const & matA,
    std::vector<float> const& vecB,
    std::vector<float& vecC,
){

    std::size_t n = matA.numRows();
    std::size_t k = matA.numColumns();

    //calculate 4 rows at the same time until the remaining number of columns is lower than 4. This saves memory accesses by a factor of 4.
    std::size_t maxRow=(n/4)*4;
    std::size_t row=0;
    while(row!= maxRow){
        float* A0 = matA.storage()+row*k;
        float* A1 = A0+k;
        float* A2 = A1+k;
        float* A3 = A2+k;
        float c0=0;
        float c1=0;
        float c2=0;
        float c3=0;
        for(std::size_t i = 0; i != k; ++i){
            c0+=A0[i]*vecB[i];
            c1+=A1[i]*vecB[i];
            c2+=A2[i]*vecB[i];
            c3+=A3[i]*vecB[i];
        }
        vecC[row]+=c0;
        vecC[row+1]+=c1;
        vecC[row+2]+=c2;
        vecC[row+3]+=c3;
        row+=4;
    }
    //calculate the remaining rows of the result
    for(;row!=n; ++row){
        float* A = matA.storage()+row*k;
        float c0=0;
        for(std::size_t i = 0; i != k; ++i){
            c0+=A[i]*vecB[i];
        }
        vecC[row]+=c0;
    }
}

//benutzung:

Matrix m(20,10);
std::vector<float> argument(10);
std::vector<float> result(20);
//some initialization skipped here
prod(m,argument,result);

hat bei mir im Test mit 512er quadratischen Matrizen ATLAS geschlagen. Aber ich gebe zu, dass ein Datenpunkt alleine da nicht wirklich ausschlaggebend ist

[zeusosc]

@Otze:
Für Matrixprodukt gibt es doch auch ne SSE2 Variante!??

@cooky451:
Hi, danke erst einmal das du Dich, auch wenn es etwas Threadfremd ist,
damit beschäftigts... sieh bitte meine antworten nicht als lernunwillig,
sondern als debattenbeitrag...

cooky451 schrieb:

zeusosc schrieb:

STL vectoren springen häufig durch verschiedene Unterfunktionen,
die die Länge prüfen, ob der Zeiger richtig ist und und und,..
hier wird alloziiert und über maximal zwei ptrs beim zugriff
dereferenziert (und auf das dritte dan referenziert)...
sollte also relativ flink laufen,..

Ein std::vector macht genau das gleiche. (Im Releasemodus). Nein, warte, er ist viel schneller als deine Version, weil er den Index nicht testet.

echt? is natürlich doof (für mich). Ich werde das nachher mal testen...

cooky451 schrieb:

zeusosc schrieb:

* Zum new: ich vermeide es wo ich kann! (hier nutze ich es exakt 1x)
Wird der new operator nicht über den source definiert, so findet
eine (Compiler spezifische) Ersetzung statt, die ich erst zur Laufzeit
sehe. Das will ich nicht!

Bitte was?

Ja, new ist ein operator den man gerne überladen kann. Wird im Fall x
kein new operator gefunden, z.b. bei einem Basistyp, nimmt der Compiler
"seine" variante. Das sieht man im trivialsten Fall auch bei
Zuweisungsoperatoren. Die definition solcher sind im sinne eigentlich
überladungen....

cooky451 schrieb:

zeusosc schrieb:

* Cast von 0 nach T* : 0 ist kein Typ.
Sind verschiedene konvertierungsvorschrifften vorhanden,
wird die erste passende vom Compiler genommen. (Meistens basistypen).
Ich will das der Compiler "explizit" 0 als T* behandelt.

Ja.. dann nimm nullptr.

hmm ja

cooky451 schrieb:

zeusosc schrieb:

* Cast nach void*: sehe ich jetzt nicht,.. wo?

In Zeile 58.

//siehe
void free ( void * ptr );

cooky451 schrieb:

zeusosc schrieb:

* Index operator [] nicht unsigned: Ja,.. kann man so und so sehen,
"ist übergebene uint > size dann gib referenz" wäre hier wohl
bessere wahl gewesen, da hast du recht...

Nein, die bessere Wahl wäre gewesen, den Test einfach nicht zu machen.

gut,.. wenn es dem aufrufer obligt diesen test zu machen um eine access
exception zu umgehen...

cooky451 schrieb:

zeusosc schrieb:

* this-> bleibt definitiv !!! es ist ein unterschied ob ich eine
Methode der Instanz aufrufe oder eine gleichnamige Funktion aus
dem gleichen Namensraum, geschweige denn Member.
Da der Compiler das so oder so die addy's der Member aus der
Referenzierung des this holt (in asm schön sichtbar), dann
kann ich es auch gleich richtig machen.

Was heißt hier "richtig", es macht halt keinen Unterschied, aber das this wegzulassen ist übersichtlicher.

zeusosc schrieb:

Ausserdem ist dann
IMMER klar, WANN ich eine Methode oder Member innerhalb einer
Methode aufrufe,...
(Macht sich besonders bemerkbar wenn intellisense spinnt)

Das ist auch so klar. Mehr noch, this-> impliziert, dass diese explizite Schreibweise nötig ist, weil sonst etwas Anderes gemeint wäre. Daher sollte man es meiden, wenn dem nicht so ist.

Also letzendlich wäre das also nur eine Stilfrage? Du sagst: Nutze wenn muss,
lasse wenn kann wegen leserlichkeit...

cooky451 schrieb:

zeusosc schrieb:

* Einrückung: hä? wie was? wo?
Es gibt ja mal wohl mehrere Varianten von einrückungen...

Das hat nichts mehr mit Stil zu tun, das ist einfach falsch bzw. teilweise gar nicht eingerückt.

sry, aber pro tiefe ein tab,.. für mich ist das eine entsprechende einrückung..

cooky451 schrieb:

zeusosc schrieb:

* ";" ?? Meines wissens hat nach jeder abgeschlossenen Anweisung ein ";"
zu folgen. Auch wenn manchen Compilern das wurscht ist....

Nein, keinem Compiler ist das egal. Aber leere ; sind jedem Compiler egal, deswegen kompiliert der Code überhaupt. Auf einen Scope muss kein ; folgen. (Und sollte dadurch auch nicht.)

Da kann ich Dir gerade nicht folgen... Hast Du einen entsprechenden Link?

cooky451 schrieb:

zeusosc schrieb:

nicht viele hauerdrinn,...

Doch, das malloc Gefrickel ist eines der übelsten Sachen die ich seit Langem gesehen habe. Und wenn der Index nicht mehr gültig ist gibt man einfach einen *new T() zurück der nie mehr freigegeben wird?

Da muss ich Dir wiedersprechen:

{
T& foo(void)
{
   return *(new T());
};

void blub(void)
{
    T t;
    t=foo();
}

Was passiert denn am ende der fkt blub? Det Dtor wird aufgerufen und das Objekt
zerstört,...
Das malloc "gefrickel" ist, wie oben erwähnt, die folge das ich kaum ein new benutze,..

cooky451 schrieb:

zeusosc schrieb:

gleich n template mit variabler dim anzahl
basteln. Er nutzt ja mehrere 1d 2d und 3d arrays.,...

Das funktioniert nicht. Die Dimensionen sind erst zur Laufzeit bekannt, wären sie zur Compilezeit bekannt, könnte man auch einen std::vector<std::array<...>> nehmen. Daher fällt jegliches Templategezauber weg.

[/quote]
Die Dimensionen sind maximal 3-> Schicht, Neuron, gewichte,.. Dynamisch sind
die Anzahl der Schichten, Neuronen und entsprechend Gewichte,...

Fazit: ich werde mal n geschwindigkeitsvergleich machen, Vector vs meine Implementation..

grüße

[cooky451]

zeusosc schrieb:

sieh bitte meine antworten nicht als lernunwillig,
sondern als debattenbeitrag...

Ich versuche es, auch wenn es mir schwer fällt.

zeusosc schrieb:

Ja, new ist ein operator den man gerne überladen kann. Wird im Fall x
kein new operator gefunden, z.b. bei einem Basistyp, nimmt der Compiler
"seine" variante. Das sieht man im trivialsten Fall auch bei
Zuweisungsoperatoren. Die definition solcher sind im sinne eigentlich
überladungen....

??? Ja, operator new kann man überladen. Das ist ja das tolle. Warum sollte das ein Argument sein new nicht zu benutzen? oO

zeusosc schrieb:

//siehe
void free ( void * ptr );

Sag ich ja.
Sei T* ein Zeiger auf ein Objekt. (Keine Funktion), dann ist
T* -> void* implizit, benötigt also keinen Cast. (Du nutzt reinterpret_cast.)
void* -> T* ein Fall für static_cast. (Auch hier verwendest du reinterpret_cast.)
Man sollte aber immer den "schwächsten" Cast nutzen, für den das Verhalten noch garantiert ist.
(Weil sich sonst natürlich jeder fragt, warum nutzt der jetzt reinterpret_cast, habe ich was übersehen?)
(Und weil man sonst den eigentlichen Sinn der C++ Casts unterdrückt, nämlich die Absicht mit der Art des Casts zu verbinden, um so viele Fehler wie möglich zur Compilezeit zu bekommen.)

zeusosc schrieb:

gut,.. wenn es dem aufrufer obligt diesen test zu machen um eine access
exception zu umgehen...

Du hast grundätzlich zwei Möglichkeiten bei einem Operator, oder einer Funktion die einen Fehler nicht durch den Rückgabewert ausdrückt, so etwas zu behandeln:
- Ignorieren und es halt drauf ankommen lassen
- Test und std::out_of_range werfen.
Siehe std::vector operator[] und .at().
Aber einfach ein neues Element zurückzugeben ist völliger Quatsch.

zeusosc schrieb:

Also letzendlich wäre das also nur eine Stilfrage? Du sagst: Nutze wenn muss,
lasse wenn kann wegen leserlichkeit...

Ja, eine Stilfrage. Aber keine besonders Kontroverse.

zeusosc schrieb:

sry, aber pro tiefe ein tab,.. für mich ist das eine entsprechende einrückung..

Wo ist bei den Zeilen 46, 50-67 bitte pro Ebene ein Tab? oO

zeusosc schrieb:

Da kann ich Dir gerade nicht folgen... Hast Du einen entsprechenden Link?

Die ; in den Zeilen 39, 47, 56, 62, 67, 74, 81, 87, 95, 101, 107, 116, 138, 147 und 158 sind sinnlos und damit sehr hässlich.

zeusosc schrieb:

Da muss ich Dir wiedersprechen:
[...]
Was passiert denn am ende der fkt blub? Det Dtor wird aufgerufen und das Objekt
zerstört,...

Argh, du hast das mit der dynamischen Speicherverwaltung (oder dem Destruktor) völlig falsch verstanden. Zähl mal wie viele Objekte erstellt und wie viele zerstört werden: http://ideone.com/5YiqF

zeusosc schrieb:

Die Dimensionen sind maximal 3-> Schicht, Neuron, gewichte,.. Dynamisch sind
die Anzahl der Schichten, Neuronen und entsprechend Gewichte,...

Die Größe der Dimensionen ist zur Compilezeit nicht bekannt. Vielleicht kannst du ein Template basteln, das immerhin für die Zahl der Dimensionen einen Parameter bereitstellt, der ist ja bekannt. Aber wie willst du dann den Zugriff gestallten? Du bräuchtest also so viele (normale) Argumente, wie Dimensionen. Das wäre also nur mit <cstdarg> möglich - sehr hässlich. Leider. (Oder aber mit variadic Templates. Da könnte was laufen. Aber mein Compiler mag die nicht :(, daher werde ich da jetzt nichts versuchen.)

[otze]

zeusosc schrieb:

@Otze:
Für Matrixprodukt gibt es doch auch ne SSE2 Variante!??

Ja. und eine parallele Variante und eine GPU Variante und eine Clustervariante und... Was ist der Punkt? Das Code, den ich auf ein für einen Anfänger verständliches Niveau runter gebrochen hab, nicht das absolute Performanceoptimum darstellt?

In der Tat wird jeder momentan übliche Compiler wenn man Optimierungen anschaltet den Code vektorisieren und SSE2-code erzeugen. Natürlich kann man besser als das werden. Viel besser. Aber das ist dann kein Code, den man hier im Forum posten könnte. Das fängt damit an, dass man dafür sorgen muss, dass der Speicher an 16 Byte Grenzen ausgerichtet sein muss und hört dann bei sicherlich 100 Zeilen unverständlichen SSE-Intrinsics auf.

Natürlich geht es schneller. Und ich würde jedem mit ein wenig Erfahrung empfehlen, sich mal eine explizite Vektorisierung anzutun. Aber SSE macht aus schlechtem Code keine Rakete. Und wie man hier im Thread - und auch bei dir - sieht, würden die Flaschenhälse bei den meisten Leuten einfach ganz woanders liegen. Das fängt schon mal damit an, dass du zum Beispiel die Laufzeit von tanh völlig überschätzt. 1 tanh kannst du auf double Präzision in weniger als 150 Takten berechnen. Das sind ganz schön viele tanh pro Sekunde. Und mal so nebenbei: wenn es eine so einfache Möglichkeit gäbe, tanh bei ähnlicher Präzision erheblich schneller zu berechnen, dann würden die Hersteller der Laufzeitbibliotheken diese mitliefern. Ähnliches gilt für std::vector (Bemerkenswerte Ausnahme ist std::complex, das kann nach den Vorgaben des Standards gar nicht schnell sein).

Wie du siehst, kann man da gar nicht so viel falsch machen, außer std::vector falsch zu verwenden, natürlich. Aber bei der linearen Algebra. Da kannst du richtig viel verlieren.
Es ist mal wieder Zeit für meinen liebsten Benchmark.
http://eigen.tuxfamily.org/index.php?title=Benchmark

Da kommt der Faktor 10 her.

[ComputerCarl]

otze schrieb:

Ich hoffe, du schaust nochmal in den Thread rein, auch wenn du das als (warum auch immer) gelöst markiert hast.

Ich habe mal ein wenig Code aus meinem aktuellen Projekt extrahiert und soweit vereinfacht, dass du es mit deinem Kenntnisstand verstehen müsstest.

Ja klar schau ich hier immer mal rein. Na ja und ich hab ihn als gelöst markiert, da ja recht einstimmig gesagt wurde, dass vectoren nicht allzu oft verschachtelt werden sollten. Ich habe mich deshalb einfach nur rangesetzt um meinen Code so wie die vorgeschlagene Matrix-Sache zu verbessern. Solche spezifischen Details wie sie jetzt zum Schluss besprochen worden, scheinen ja nicht mehr direkt meine Frage bezüglich der Geschwindigkeit zu beantworten.
Danke für den Code! Er ist wirklich mal gut zu verstehen und macht es mir als Nicht-Profi-Programmierer relativ leicht ihn umzusetzten.

[Gast]

... reicht mir zumindest nicht. Wo ist denn der Beleg, dass das Verschachteln von vector<> langsamer ist als ein C-Stil Feld? Erst messen, dann entscheiden.

Habe mir ein Testprogramm geschrieben mit folgenden Ergebnissen:
StdMatrix ist vector<vector<T>>
StdArray ist array<array<T, N>, M>
Flat ist T* mit new alloziert

C:\work\learning\matrixPerformance\x64\Release>matrixPerformance.exe

Measuring Matrix performance in different implementations

StdMatrix  = 0.0014709030 s
StdArray   = 0.0014882258 s
FlatMatrix = 0.0021665119 s

Speedups:
          -->   | StdMatrix     StdArray        FlatMatrix
----------------+------------------------------------------------------
Std::Matrix     |1.0000000000   1.0117770217    1.4729128500
Std::Array      |0.9883600621   1.0000000000    1.4557682359
c_Matrix        |0.6789267946   0.6869225302    1.0000000000

Benchmarking matrix multiplication...
Time Flat = 81.0635421623s // "triviale Implementierung"
Time Opt  = 5.0158342457s  // optimierte und parallelisierte Implementierung (auf mobile i5)
Speedup   = 16.1615273137

Benchmarking cache performance in transpose...
Transpose time Flat = 0.0335489836s // transponieren der Matrix "triviale Implementierung"
Transpose time Opt  = 0.0005909019s // tranponieren auf cache optimiert und parallelisiert 
Speedup   = 56.7758957655

Habe im output noch ein paar Kommentare hinzu gefügt. vector und array sind nahezu gleich schnell, die C-Stil matrix ist in jedem Fall langsamer.

Zeitmessungen habe ich, der höheren Genauigkeit wegen, mit QueryPerformanceCounter (Win32) durchgeführt.

EDIT: Für unterschiedliche Datentypen variieren bei mir die Zeiten durchaus, aber nicht in Bereichen jenseits 30% (auf meinem Rechner)

[Gast]

Hier ist noch der Code zu meinem vorherigen Post:

#include <stdlib.h> // rand()

#include <iostream>
#include <iomanip>
#include <vector>
#include <array>
#include <algorithm>
#include <numeric>
#include <limits>

#include "PerformanceCounterWin32.h"

extern void MatrixMultiplication(void);

#ifdef max 
#undef max
#endif

using namespace std;

const unsigned int rows     = 1201;
const unsigned int columns  = 1201;

typedef short elemType;

elemType makeElem(void)
{
    return static_cast<elemType>((double)rand()/(double)RAND_MAX*numeric_limits<elemType>::max());
}

void initializeData(vector<vector<elemType>>& matrix)
{
    matrix.resize(rows);

    for (auto it = matrix.begin(); it != matrix.end(); ++it)
    {
        (*it).resize(columns);    
        generate((*it).begin(), (*it).end(), makeElem);
    }
}

void initializeData(array<array<elemType, columns>, rows>& matrix)
{
    // just for demonstration purposes, that stl based matrices
    // can be syntactically addressed like vanilla arrays
	// the loops can also be replaced by the same code like in 
	// the initialization function for the vector<vector<>> code
    for (unsigned int y = 0; y<matrix.size(); ++y)
    {
        for (unsigned int x = 0; x<matrix[y].size(); ++x)
        {
            matrix[y][x] = makeElem();
        }
    }
}

void initializeData(elemType* data, elemType**& rat)
{
    for(unsigned int i = 0; i<rows*columns; ++i)
    {
        data[i] = makeElem();
    }
    // the row address table provides [][] addressing
    // syntax
    for(unsigned int i = 0; i<rows; ++i)
    {
        rat[i] = &data[i*columns];
    }
}

__declspec(noinline) elemType benchStdMatrix(vector<vector<elemType>>& matrix)
{
    volatile elemType  sum = 0;
    for( unsigned int i = 0; i<matrix.size(); ++i)
    {
        // accumulate is the fastest approach for vector
        sum = accumulate(matrix[i].begin(), matrix[i].end(), elemType(0)); 
    }

	return sum;
}

__declspec(noinline) elemType benchStdArray(array<array<elemType, columns>, rows>& matrix)
{
    volatile elemType sum = 0;
    for(unsigned int i = 0; i<rows; ++i)
    {
        // accumulate is the fastest approach for array
        sum += accumulate(matrix[i].begin(), matrix[i].end(), elemType(0));
    }

	return sum;
}

__declspec(noinline) elemType benchFlatMatrix(elemType**& rat)
{
    volatile elemType sum = 0;

    // This is the fastest version using flat model
	// difficult to read and with pointer arithmetics
    elemType* line = rat[0];
    unsigned int counter = rows*columns;
    do
    {
        sum = *line++;
    }while (counter--);

    //for( unsigned int i = 0; i<rows; ++i)
    //{
    //    for( unsigned int j = 0; j<columns; ++j)
    //    {
    //        sum += rat[i][j];
    //    }
    //}
	return sum;
}

void printResults(	PerformanceCounterWin32& perfCounter, const elemType& sum0, const elemType& sum1, const elemType& sum2)
{
    double timeStdMatrix  = perfCounter.getDeltaInSeconds(0, 1);
    double timeStdArray   = perfCounter.getDeltaInSeconds(1, 2);
    double timeFlatMatrix = perfCounter.getDeltaInSeconds(2, 3);

    cout << setprecision(10) << setfill(' ');
    cout.setf(ios_base::fixed|ios_base::showpoint);

    cout << "StdMatrix  = " << timeStdMatrix << " s" << endl;
    cout << "StdArray   = " << timeStdArray << " s" << endl;
    cout << "FlatMatrix = " << timeFlatMatrix << " s" << endl << endl;

    cout << "Speedups: " << endl;
    cout << "\t  -->\t| StdMatrix\tStdArray\tFlatMatrix" << endl;
    cout << "----------------+------------------------------------------------------" << endl;
    cout << "Std::Matrix     |" << setw(8) << timeStdMatrix/timeStdMatrix  << "\t" << setw(8) << timeStdArray/timeStdMatrix  << "\t" << setw(8) << timeFlatMatrix/timeStdMatrix << endl;
    cout << "Std::Array      |" << setw(8) << timeStdMatrix/timeStdArray   << "\t" << setw(8) << timeStdArray/timeStdArray   << "\t" << setw(8) << timeFlatMatrix/timeStdArray << endl;
    cout << "c_Matrix        |" << setw(8) << timeStdMatrix/timeFlatMatrix << "\t" << setw(8) << timeStdArray/timeFlatMatrix << "\t" << setw(8) << timeFlatMatrix/timeFlatMatrix << endl;

	cout << endl << endl;

	cout << "Sum0 = " << sum0 << endl;
	cout << "Sum1 = " << sum1 << endl;
	cout << "Sum2 = " << sum2 << endl;
}

int main(void)
{
    vector<vector<elemType>> stdMatrix;
    array<array<elemType, columns>, rows>* stdArray = new array<array<elemType, columns>, rows>();
    elemType* flatMatrix = new elemType[rows*columns];
    elemType** flatMatrixRAT = new elemType*[rows];
	elemType sum0 = static_cast<elemType>(0);
	elemType sum1 = static_cast<elemType>(0);
	elemType sum2 = static_cast<elemType>(0);

	PerformanceCounterWin32 perfCounter;

    initializeData(stdMatrix);
    initializeData(*stdArray);
    initializeData(flatMatrix, flatMatrixRAT);

    cout << endl << "Measuring Matrix performance in different implementations" << endl << endl;

    perfCounter.startMeasurement();
	sum0 = benchStdMatrix(stdMatrix);
	perfCounter.queryCounter();
	sum1 = benchStdArray(*stdArray);
	perfCounter.queryCounter();
	sum2 = benchFlatMatrix(flatMatrixRAT);
    perfCounter.queryCounter();
	printResults(perfCounter, sum0, sum1, sum2);

	// MatrixMultiplication();
}

MatrixMultiplication habe ich erst mal außen vor gelassen um den Thread nicht zuzumüllen. Kann ich bei Bedarf gerne auch bereit stellen.

Sollten in obigem Code Fehler sein, bin ich für Korrekturen dankbar.

[realoaded]

vector<vector<elemType>> stdMatrix;
    array<array<elemType, columns>, rows>* stdArray = new array<array<elemType, columns>, rows>();
    elemType* flatMatrix = new elemType[rows*columns];
    elemType** flatMatrixRAT = new elemType*[rows];

- std::array ist hier völlig fehl am Platz, weil die Grösse erst zur Laufzeit bekannt ist. Ausserdem ist es immer sinnlos, es mit new zu allozieren.
- flatMatrix wäre richtig (im Gegensatz zu flatMatrixRAT), aber das diese testest du nie
- warum ein einfacher (nicht geschachtelter) std::vector<> langsamer sein sollte als ein dynamisches Array ist mir auch nicht klar. Warum es schneller sein sollte auch nicht.
- zeusosc hat einen Mist programmiert, den kannst du ignorieren. Aber schau auf den Code von otze, der benutzt auch std::vector. Stört dich nur der Threadtitel?

[Gast]

- std::array ist hier völlig fehl am Platz, weil die Grösse erst zur Laufzeit bekannt ist. Ausserdem ist es immer sinnlos, es mit new zu allozieren.

Das ist richtig. Ist nur der Vergleichbarkeit wegen drin, da array im Thread vorher schon mal erwähnt worden ist.

- flatMatrix wäre richtig (im Gegensatz zu flatMatrixRAT), aber das diese testest du nie

Doch, das wird getestet in benchFlatMatrix(), den Code mit der Row Adress Table habe ich auskommentiert, weil er in meiner Umgebung langsamer war, als das direkte Berechnen des Indexes. vector und array lösen das intern ja genau so.

- warum ein einfacher (nicht geschachtelter) std::vector<> langsamer sein sollte als ein dynamisches Array ist mir auch nicht klar. Warum es schneller sein sollte auch nicht.

Ich verstehe das auch nicht, insbesondere, wenn man in die Implementierung von vector rein schaut. Die Unterschiede liegen ja auch nur im Bereich zwischen 10% und 30%, je nach gewähltem elemType, wobei alleine die Messungenauigkeit bei verschiedenen Durchläufen schon bei 10% liegt.

Mein Fazit ist ja, dass die Laufzeitunterschiede nicht daher kommen, dass vector<> verwendet wird.

[cooky451]

ogni42 schrieb:

Mein Fazit ist ja, dass die Laufzeitunterschiede nicht daher kommen, dass vector<> verwendet wird.

Du hast es nicht verstanden. vector<vector<vector<double>>> ist natürlich wesentlich langsamer, als vector<array<array<double, N>, N>>. Dieser Effekt wird stärker, je mehr du im Speicher herumspringst. Sprobier mal so eine Schleife:

for (int i = 0; i != sx; ++i)
    for (int j = 0; j != sy; ++j)
      for (int k = 0; k != sz; ++k)
        v[i][j][k] = v[k][j][i] = v[j][i][k] = std::rand();

Hier bekommst du eine ~50%ige Laufzeitbeschleunigung für Speicher der Am Stück liegt. Wenn du öfter so zugreifst, dass die Elemente nebeneinander liegen, erhöht sich der Effekt noch.

Keine Ahnung was du da mit deinem C Zeugs beweisen willst, dass ein vector<double> nicht langsamer ist als manuelle Verwaltung sollte wohl jedem klar sein.

[Gast]

cooky451 schrieb:

Du hast es nicht verstanden.

Das ist möglich, aber nicht sehr wahrscheinlich

cooky451 schrieb:

vector<vector<vector<double>>> ist natürlich wesentlich langsamer, als vector<array<array<double, N>, N>>. Dieser Effekt wird stärker, je mehr du im Speicher herumspringst.

Nein, das stimmt so nicht. Du setzt nämlich voraus, dass bei vector der Speicher "natürlich" nicht zusammenhängend im Speicher liegt. Das ist aber z.B. bei der Standard Lib, die ich hier habe der Fall. Die Standard-Bibliothek verlangt das aber nicht von std::vector<> wohingegen std::array<> das zusichert.