[gelöst] Vector ist wesentlich langsamer als Array?
-
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?
-
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.
-
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.
-
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 ivector< 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+1Verschachtelte 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 Indexx + y * SizeX + z * SizeX * SizeYzu.
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.
-
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?
-
Leider sagt mir auch das nicht viel.
Aber ich hab mein Code kompeliert und die
Exe ausgeführt. (Beantwortet das die Frage?)
-
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)
-
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.
-
(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
-
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.
-
ComputerCarl schrieb:
(2) Welchen Compiler nutzt du?
Dev-C++ 4.9.9.2oO
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.
-
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.
-
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.
-
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.
-
otze schrieb:
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
Das gehört zwar nicht zum Thema, aber gibt es bei einer der genannten Bibliotheken einfache Benchmarks, also so etwas wie zwei 1500x1500 große Matrizen multiplizieren? Ich würde das gerne mal gegen etwas Händisches testen.
-
Solche Bibliotheken bieten nicht einfach nur hochoptimierte Implementierungen der naiven Algorithmen.
Der wesentliche Punkt bei solchen Numeriklibs ist, dass sie algorithmisch optimale Lösungen für spezielle Strukturen wie z.B. sparse Matritzen etc. bieten. Sowas ist nicht einfach so mal schnell händisch gemacht. Da muss man zuerst mal einige fette Bücher wälzen und Paper lesen...
-
Es mag sein, dass eine einfache Multiplikation einer quadratischen Matrix überhaupt nicht die Möglichkeiten einer solchen Bibliothek ausreizt, aber interessant fände ich es trotzdem.
-
SeppJ schrieb:
Gib uns doch einfach mal das vollständige Programm, dann können wir unseren Senf dazu abgeben.
Ich glaube nicht, dass das sonderlich leserlich wird. Ich wäre aber sehr dankbar, wenn jemand eine gute Alternativ-Struktur vorschlagen kann.
Mein Programm-Aufruf soll wie folgt lauten:
Programm.exe Set_A Set_B 2 4 3 2
-> Set_A, Set_B sind Punkte aus Klasse A und B die über mein
Netz trainiert werden sollen.
-> 2 4 3 2 gibt die jeweiligen Schichten an
(also 1. Schicht 2 Neuronen, 2. Schicht 4 Neuronen...)Also hier der Code:
#include <vector> #include <fstream> #include <math.h> #include <iostream> #include <time.h> using namespace std; class MLP { private: vector< vector<double> > training_set_A; vector< vector<double> > training_set_B; vector< vector<double> > M; vector< vector<double> > delta; vector< vector< vector<double> > > DELTA; vector< vector< vector<double> > > w; /////////////////// // Read-Input vector< vector<double> > read_input(string path_to_file) { ifstream input; input.open(path_to_file.c_str(), ios::in); string input_text = ""; string number = ""; vector< vector<double> > coord_vector; vector<double> data; data.push_back(-1); while(!input.eof()) { while(input_text != "\t" && input_text != "\n" && !input.eof()) { number += input_text; input_text = input.get(); } float test = atof(number.c_str()); data.push_back(test); number = ""; if(input_text == "\n" || input.eof()) {coord_vector.push_back(data); data.clear(); data.push_back(-1);} input_text = input.get(); } return coord_vector; } /////////////////// // Aktivierungsimpuls durch Netzwerk schicken void activate(vector<double> *tmp, double beta, double bias) { 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(beta * (wTx - bias)); } } } /////////////////// // Back-Propagandation void back_prop(vector<double> target_vector, double beta, double bias, double learning_rate) { // Letzte Schicht in MLP for(int i = 1; i < this->M[this->M.size() - 1].size(); i++) { this->delta[this->delta.size()-1][i] = (target_vector[i] - this->M[this->M.size() - 1] [i]) * (beta * (1 - pow(this->M[this->M.size() - 1] [i], 2))); } // Schichten vor letzter Schicht des MLP for(int i = this->M.size() - 2; i >= 0; i--) { for(int j = 0; j < this->M[i].size(); j++) { double sum = 0; for(int k = 1; k < this->M[i+1].size(); k++) {sum += this->delta[i+1][k] * this->w[i][j][k];} this->delta[i][j] = sum * (beta * (1 - pow(this->M[i][j],2))); } } // Neue Gewichtung Berechnen (noch nicht Anpassen) for(int i = 0; i < this->w.size(); i++) { for(int j = 0; j < this->w[i].size(); j++) { for(int k = 1; k < this->w[i][j].size(); k++) { DELTA[i][j][k] = learning_rate * this->delta[i+1][k] * this->M[i][j]; } } } } /////////////////// // Gewichte Anpassen void adjust_weights() { for(int i = 0; i < this->w.size(); i++) { for(int j = 0; j < this->w[i].size(); j++) { for(int k = 1; k < this->w[i][j].size(); k++) { w[i][j][k] += this->DELTA[i][j][k]; } } } } public: /////////////////// // Konstruktor MLP(int argc, char *argv[]) { // Einlesen der Trainings-Daten this->training_set_A = this->read_input(argv[1]); this->training_set_B = this->read_input(argv[2]); // Initialisierung der Schichten mit den Gewichten for(int l = 3; l < argc; l++) { vector<double> Ml; vector<double> deltal; for(int i = 0; i < atoi(argv[l])+1; i++) { if(i == 0) { Ml.push_back(-1); deltal.push_back(-1); } else { Ml.push_back(0); deltal.push_back(0); } } this->M.push_back(Ml); this->delta.push_back(deltal); vector< vector< vector<double> > > level1w; vector< vector< vector<double> > > level1d; for(int i = 0; i < M.size() - 1; i++) { vector<vector<double> > level2w; vector<vector<double> > level2d; for(int j = 0; j < M[i].size(); j++) { vector<double> level3w; vector<double> level3d; for(int k = 0; k < M[i+1].size(); k++) { if(k == 0){ level3w.push_back(0); level3d.push_back(0); } else { double random_weight = rand() / double(RAND_MAX); double w_tilde = 1/atof(argv[l-1]); random_weight *= 2 * w_tilde; random_weight -= w_tilde; level3w.push_back(random_weight); level3d.push_back(0); } } level2w.push_back(level3w); level2d.push_back(level3d); } level1w.push_back(level2w); level1d.push_back(level2d); } this->w = level1w; this->DELTA = level1d; } } /////////////////// // Online learning mit zufaelliger Reihenfolge void learning(int menue, int epoche, double beta, double bias, double learning_rate) { int length = this->training_set_A.size() + this->training_set_B.size() - 1; int length_A = this->training_set_A.size(); int number[length]; for(int i = 0; i < length; i++) {number[i] = i;} clock_t start, end; start = clock(); for(int e = 0; e < epoche; e++) { double mse = 0; for(int i = 0; i < length; i++) { int rand_index = rand() % (length-i); if(number[rand_index] >= length_A) { // ist B this->activate(&this->training_set_B[number[rand_index] - length_A], beta, bias); vector<double> target; target.push_back(-1); target.push_back(-1); target.push_back(1); double res = 0; for(int j = 1; j < this->M[this->M.size()-1].size(); j++) {res += pow(target[j] - this->M[this->M.size()-1][j], 2);} mse += res/(this->training_set_A.size()+this->training_set_B.size()); this->back_prop(target, beta, bias, learning_rate); if(menue == 1) {this->adjust_weights();} } else{ // ist A this->activate(&this->training_set_A[number[rand_index]], beta, bias); vector<double> target; target.push_back(-1); target.push_back(1); target.push_back(-1); double res = 0; for(int j = 1; j < this->M[this->M.size()-1].size(); j++) {res += pow(target[j] - this->M[this->M.size()-1][j], 2);} mse += res/(this->training_set_A.size()+this->training_set_B.size()); this->back_prop(target, beta, bias, learning_rate); if(menue == 1) {this->adjust_weights();} } if(menue == 2) {this->adjust_weights();} int space = number[rand_index]; number[rand_index] = number[(length-i)-1]; number[(length-i)-1] = space; } if(e % 1000 == 0) { cout << e << " / " << epoche << "\tM-S-Error: " << mse << "\t"; end = clock(); cout << "runtime: " << (end - start) / CLOCKS_PER_SEC << " sec." << endl; start = clock(); } } } /////////////////// // Ausgabe von den Gewichten des MLP's void print_weights() { for(int i = 0; i < this->w.size(); i++) { cout << "Gewicht der Schicht " << i << " -> " << i+1 << endl; for(int j = 0; j < this->w[i].size(); j++) { for(int k = 0; k < this->w[i][j].size(); k++) { cout << w[i][j][k] << " "; } cout << endl; } cout << endl << endl; } } }; int main(int argc, char *argv[]) { MLP *tmp = new MLP(argc, argv); MLP *tmp2 = new MLP(argc, argv); cout << endl << endl; clock_t start, end; start = clock(); cout << "Online-Learning:" << endl; tmp->learning(1, 5000, 0.1, 0, 0.1); end = clock(); cout << endl; tmp->print_weights(); cout << "runtime: " << (end - start) / CLOCKS_PER_SEC << " sec." << endl; cout << "\n\n-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-\n\n" << endl << endl; start = clock(); cout << "Batch-Learning:" << endl; tmp2->learning(2, 5000, 0.1, 0, 0.1); end = clock(); cout << endl; tmp2->print_weights(); cout << "runtime: " << (end - start) / CLOCKS_PER_SEC << " sec." << endl; return 0; }
