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

ComputerCarl

Hallo,

Ich sitzte gerade daran ein neuronales Netz zu implementieren und habe dafür Vectoren verwendet. Die Laufzeit ist aber absolut unrealistisch hoch. Ich habe viel gegoogelt und auch hier im Forum gesucht, aber nichts scheint mein Problem genau zu beschreiben.

Ein genaues Verständnis für ein Neuronales Netz (NN) ist weiter nicht
Notwendig. Ich habe den Schwerpunkt auf einen minimal kleinen Aspekt reduziert.
In meiner Klasse NN befinden sich folgende Attribute:
vector< vector<double> > M;
//M[i][j] -> verweist auf das j-te Neuron in Schicht i

vector< vector< vector<double> > > w;
//w[i][j][k] -> verweist auf das Gewicht für den Übergang von
dem Neuron j in Schicht i auf das Neuron k in Schicht i+1

Um nun die Ausgabe für ein bestimmten Eingabevector zu generieren:

void activate(vector<double> tmp) {
   this->M[0] = tmp;
   for(int l = 1; l < this->M.size(); l++) {
        for(int i = 1; i < this->M[l].size(); i++) {
              double wTx = 0;
              for(int j = 0; j < this->M[l-1].size(); j++)
              { wTx += this->M[l-1][j] * this->w[l-1][j][i];}
              this->M[l][i] = tanh(wTx);
              }
        }       
    }
}

Diese 3 verschachtelten Schleifen dauern für eine bestimmte Instanz 22 Sekunden.
Die Implementierung meines Übungsleiters brauch insgesamt nur 3 Sekunden und dort wird noch der andere Teil des Netzwerkes abgearbeitet.
Mir ist einfach nicht klar, was die ganze Zeit produziert. Dort werden nur elementare Operationen durchgeführt, nichts gelöscht und nichts kopiert. Wo liegt der Fehler?

vielen Dank.

*Q* 1

Ist das absicht, dass du den vektor per value übergibst?

icarus2

Bitte poste deinen Code mit cpp Codetags. Sonst kann das keiner lesen.

In dem wirren Zeug ist mir nur gerade

void activate(vector<double> tmp)

aufgefallen. Wenn die Funktion oft aufgeruft wird, so muss immer der ganze vector kopiert werden. Das kann das Programm sehr stark verlangsamen. Du solltest den dann besser by reference uebergeben, also so:

void activate(vector<double> & tmp)

ComputerCarl

Na ja die Übergabe des Eingabe-Vectors tmp ist mir eigentlich gleich.
Die hat mit den 22 Sekunden Laufzeit auch nichts zu tun. Hier habe ich
in unterschiedlichen Konstellationen gemessen (auch mit Arrays) und nur
der Aufruf der elemtar Operationen auf die Vectoren produziert die angegebene
Laufzeit.

(Verzeihung wegen dem nicht eingerückten Code!!! Habe es vergessen anzupassen...)

*Q* 1

Du kannst die cpp tags noch per edit hinzufügen.

Wie groß sind die vektoren denn jeweils?

Und bist du sicher das wirklich nur einmal activate aufgerufen wird?

Hast du einen Profiler benutzt? Hast du vielleicht im Debug mode gestartet?

Firefighter

ComputerCarl schrieb:

Na ja die Übergabe des Eingabe-Vectors tmp ist mir eigentlich gleich.
Die hat mit den 22 Sekunden Laufzeit auch nichts zu tun. Hier habe ich
in unterschiedlichen Konstellationen gemessen (auch mit Arrays) und nur
der Aufruf der elemtar Operationen auf die Vectoren produziert die angegebene
Laufzeit.

(Verzeihung wegen dem nicht eingerückten Code!!! Habe es vergessen anzupassen...)

Und wie das einen Unterschied macht ob du das per Value oder per Referenz uebergibst. Arrays werden ja sowieso als Zeiger an eine Funktion uebergeben.

ComputerCarl

Also activate() wird 1600-mal aufgerufen.
Vector M besteht aus 4 Schichten mit (vereinfacht) jeweils 4 Neuronen
(-> 4 X 4 Matrix) Die Gewichte w also aus 3 * 4X4-Matrizen. Der Eingabe-vector
tmp besteht aus eigentlich 2-Dimensionen. (Durch die Vereinfachung oben steht das natürlich im Wiederspruch...)
Also alles in allem sehr kleine Eingaben...

Profiler sagt mir leider nichts... Also die Antwort: Nein.

Ein Profiler zeigt dir, wieviel Zeit das Program in seinen jeweiligen Funktionen verbringt. Für Tests wie diese, besser geeignet, als einfach die Gesamtzeit von einer Stopuhr oder ähnlichem abzulesen. Zumal du direkt ersichtlich ist, wo dein Program hinterher hinkt. Ein quelloffener Profiler ist z.B. GNU gprof.

hustbaer

ComputerCarl schrieb:

In meiner Klasse NN befinden sich folgende Attribute:
vector< vector<double> > M;
//M[i][j] -> verweist auf das j-te Neuron in Schicht i

vector< vector< vector<double> > > w;
//w[i][j][k] -> verweist auf das Gewicht für den Übergang von
dem Neuron j in Schicht i auf das Neuron k in Schicht i+1

Verschachtelte Vektoren sind selten eine gute Idee. Der Dereferenzierungs-Overhead wird dadurch deutlich höher, und für den Cache ist es die komplette Katastrophe.

Ich nehme an dass deine Daten "konstante" Dimensionen haben. Also dass alle Vektoren einer Dimension immer gleich gross sind.

In dem Fall pack das ganze einfach in ein einziges grosses Array.

Angenommen du hast drei Dimensionen, X, Y und Z, dann macht du genau einen vector<double> der SizeX*SizeY*SizeZ Elemente hat.
Und greifst dann mit Index x + y * SizeX + z * SizeX * SizeY zu.
Da SizeX * SizeY konstant ist, packst du das noch in eine Membervariable, dann fällt noch eine Multiplikation weg.

Dadurch sollte dein Programm deutlich schneller werden.

ComputerCarl

Also erstmal vielen Dank für die vielen Hinweise.

(1) Profiler:
Also obwohl ich keinen verwendet habe, habe ich die Funktion an unterschiedlichen Stellen mittels der Stopuhr (clock.h) gemessen. Und wie gesagt 22 Sekunden in den 3 verschachtelten Schleifen. (Dabei habe ich vergessen zu erwähnen, dass dies für 1000-maligen Aufruf von 1600 Datenpunkten gilt). Davon braucht er allein für die Berechnung des tanh 4 Sekunden. Also rund 18 Sekunden für die Schleifen...
(In einem Array war die Zeit bei 4-5 Sekunden...)

(2) Übergabe by-reference:
Dies hat mir eine Zeitersparnis von 1 Sekunde gebarcht.
-> Also schliese ich aus, dass das Problem von hier kommt

(3) alles in ein Vector:
Da die Schichten alle unterschiedlich groß sind, ist dass
eher eine "Notlösung". (Ich hatte nur zur Vereinfachung geschrieben,
dass sie alle gleichgroß sind. Sorry da hab ich mich unglücklich
ausgedrückt)

Sollten es keine anderen Ideen geben, was wäre eine gute
alternativ Struktur zu den Vectoren?

Mal eine ganz andere Frage: Führst du das Programm im Debug - oder Release-Modus aus?

ComputerCarl

Leider sagt mir auch das nicht viel.
Aber ich hab mein Code kompeliert und die
Exe ausgeführt. (Beantwortet das die Frage?)

cooky451

ComputerCarl schrieb:

(3) alles in ein Vector:
Da die Schichten alle unterschiedlich groß sind, ist dass
eher eine "Notlösung".

Wie hast du es dann mit Arrays gemacht?

ComputerCarl schrieb:

Exe ausgeführt. (Beantwortet das die Frage?)

Nein. Welchen Compiler nutzt du? (GCC/MSVC)

hustbaer

ComputerCarl schrieb:

(3) alles in ein Vector:
Da die Schichten alle unterschiedlich groß sind, ist dass
eher eine "Notlösung". (Ich hatte nur zur Vereinfachung geschrieben,
dass sie alle gleichgroß sind. Sorry da hab ich mich unglücklich
ausgedrückt)

OK.
Damit kannst du aber sicher immer noch das 2D Array jeder Schicht in einen "flachen" vector<double> packen, oder?
Das würde sicher schon einiges bringen.

ComputerCarl

(1) Wie hast du es dann mit Arrays gemacht?
Grenzen der Schleifen-Durchläufe auf Konstante festgesetzt und
Rechnung mit vergleichbaren Zahlen durchgeführt.
Nichts interesanntes... Ich wollte nur ein Gefühl dafür bekommen
wie lange ich für die Berechnung mit einem Array gewartet hätte.

(2) Welchen Compiler nutzt du?
Dev-C++ 4.9.9.2

SeppJ

Da wir das hier schon oft genug hatten: Ich wette mal, dass du gar keinen optimierten Code betrachtest. Niemand interessiert sich für Geschwindigkeitsvergleiche im Debugmodus.

cooky451

ComputerCarl schrieb:

(2) Welchen Compiler nutzt du?
Dev-C++ 4.9.9.2

oO
Bitte teste das mal mit VS 2010 (Release) oder g++ (-O3). Trotzdem, ich kann mir schon vorstellen, dass Arrays hier schneller sein können. Wie hustbaer ja schon erklärt hat, hängt auch ein mehrdimensionales Array im Speicher am Stück, während die Vektoren ihren Speicher alle einzeln anfordern. Da könnte ein std::vector<std::array<std::array<...>>> schon schneller sein.

ComputerCarl

Ich habe jetzt das Programm nochmal mit g++ getestet und es gab einen riesen Zeitunterschied. Dennoch ist mir und meinem Übungsleiter nicht klar, wieso es noch so verhältnismäßig langsam abläuft. Wir haben ca. 30 min. reingeschaut.
Na ja er wird es noch einem C++ Kenner vorlegen und ich werde posten, wenn ich eine Antwort erhalten habe.
Erstmal aber vielen Dank für Tipps und Anregungen.

SeppJ

Gib uns doch einfach mal das vollständige Programm, dann können wir unseren Senf dazu abgeben.

Bleibt nochmal zusammenzufassen:
vector<vector<Typ>> ist was anderes als Typ[M][N], da bei letzterem sowohl die innere als auch die äußere Dimension statisch sind. Durch die doppelte Dynamik ist das schon deutlich langsamer. Typ[M][N] entspricht array<array<Typ, N>, M>, vector<vector<Typ>> entspricht **Typ. Meistens will man übrigens <vector<array<Typ, N>>, was in C (*Typ)[N] entspricht.

Und unoptimierter STL-Code ist oftmals sehr langsam, weil
1. Die Funktionen nicht inline werden
2. Oftmals auch noch Debugfeatures aktiv sind.
Optimiert man den Code, erhält man Maschinencode der ziemlich exakt dem des äquivalenten C-Konstrukts entspricht.
Das C-Array ist dagegen immer recht schnell, auch ohne Optimierung. Dafür ist es bei dem C-Array gar nicht möglich, überhaupt Debugoptionen einzuschalten. außerdem interessiert beim Debuggen niemand die Geschwindigkeit und wenn man Debugcode ausliefert, macht man etwas falsch.

Wenn beides zusammenkommt, erhält man die beobachteten Risenunterschiede. Wenn du mal optimierst, bekommst du nur noch die Kosten der Dynamik. Die können bei höherer Verschachtelungstiefe (>2) auch ziemlich hoch werden. Da muss man eben wissen, ob man die Dynamik braucht oder nicht. Falls ja, dann fuhrt kein Weg dran vorbei, falls nein, dann hat man das falsche Konstrukt benutzt.

otze

ComputerCarl schrieb:

Ich habe jetzt das Programm nochmal mit g++ getestet und es gab einen riesen Zeitunterschied. Dennoch ist mir und meinem Übungsleiter nicht klar, wieso es noch so verhältnismäßig langsam abläuft. Wir haben ca. 30 min. reingeschaut.

Es ist total einfach:

1. Matrix-Vector oder Matrix-Matrix Multiplikationen sind auf modernen Rechnern _nicht_ trivial, auch wenn der naive Algorithmus das nahe legt. Wenn dein Übungsleiter eine Referenzimplementierung mit MATLAB hat, ist das erst mal für dich unschlagbar, solange du nicht externe Bibliotheken wie ATLAS, Eigen oder MKL in die Wagschale wirfst.

2. std::vector<std::vector<double> > ist eine Katastrophe für die Geschwindigkeit. Es liegt nicht am std::vector, sondern dass die einzelnen Zeilen deines Arrays quer im Speicher verstreut sind.

3. Du solltest nicht die Datenpunkte einzeln verarbeiten, sondern stattdessen immer ein Set von 100 oder mehr Datenpunkten auf einmal. Rechnest du die Formeln damit durch wird aus jeder matrix-vector multiplikation eine matrix-matrix multiplikation. Die sind zum einen noch fixer implementierbar, zum anderen kriegst du damit noch ein sehr gutes Datenalignment deiner Eingabevektoren.

Ich geh das mal durch, weil ich die selbe Evolution auch durchgemacht habe:
Punkt 1 gibt dir ca Faktor 2.
Punkt 2 alleine brachte in meinen Experimenten so gut wie gar nichts, da der Bottleneck dank miesen Datenalignment woanders lag.
Punkt 2+3 zusammen brachten Faktor 10 auf dem MNIST Datensatz und einem Autoencoder Netzwerk(Neuronen 756x768x768 ). Runtime Unterschied: vorher 22 Minuten, danach 150sec.