ich entwickle seit einiger Zeit Software in Matlab und habe folgendes Problem: Da ich eigentlich aus der C/C++ - Ecke komme, verwende ich in dem Code häufig Schleifen. Wenn ich das Script dann ausführe, ist es ausgesprochen lansgam. Wie ich inzwischen gelernt habe, gibt es daher die Tendenz, Schleifen in Matlab zu vermeiden und statt dessen alles in Form von Matrix/Vektor-Multiplikationen und Matlab eigener Funktionen wie z.B. cumsum auszudrücken ("Vektorisierung"). Aus folgenden Gründen ist das aber für mich eher ungünstig
Der Code enthält auch Schleifen, die auf 3 oder 4 dimensionalen Arrays operieren. Die "Vektorisierung" spart dann vielleicht die inneren beiden Schleifen, aber die äußeren bleiben bestehen und die bleiben langsam.
Der Code soll zur Illustration in einem Text dienen, der auch für Entwickler anderer Programmiersprachen lesbar sein soll. Wenn man alles "vektorisiert", dann ist der Code für alle anderen eher schwer zu lesen (manchmal sogar für den Matlab-Entwickler selber).
Die Vektorisierung des Codes ist augesprochen viel Arbeit (und ich gebe zu, dass ich nicht besonders viel Lust dazu habe) .
Gibt es da nicht irgendeine vernünftige und praktiable Lösung, die einerseits die Vewendung von Schleifen ermöglicht, aber andererseits die Performance nicht total ruiniert?
Mir ist aufgefallen, dass Matlab-Scripte ja eigentlich nur interpretiert, aber nicht compiliert werden. Daher habe ich versucht, meine Scripte zu compilieren, in der Hoffnung, dass der Compiler solche Optimierungen dann selbstständig vornimmt. Das hat aber leider nicht geklappt. Gibt es da vielleicht noch irgendwelche Tricks?
Hallo Hörmander,
man kann nicht generell sagen, dass Schleifen schlecht sind. Es kann viele Gründe haben warum dein Code langsam ist.
Unnötige Variablen ausversehen erstellen.
Matrix pre-allocieren nicht durchgeführt.
...
Das lässt sich pauschal nicht sagen, aber du kannst mit dem profiler bzw. mit tic/toc den Flaschenhals in deinem Code finden und versuchen diesen zu beseitigen.
Seit Matlab 6.5, das ja nuin schon ein paar Jahre auf dem Buckel hat, gibt es in MATLAB einen JIT-compiler, der die Bearbeitung von Schleifen drastisch beschleunigt. Das Gerücht, dass FOR-Schleifen in MATLAB langsam sind, ist also ein wenig veraltet - trotzdem hält es sich sehr hartnäckig.
Nun gibt es Schleifen, die vektorisiert viel schneller sind, da die massiv optimierte BLAS-Bibliothek aufgerufen wird. Dagegen sehen dann sogar C-Schleifen alt aus. Viele dieser Aufrufe sehen deutlich hübscher aus als die entsprechenden Schleifen, z.B. eine Matrix-Multiplikation is als "A * B" einfach nicht zu überbieten, oder? Auch "A\B" ist in C++ ein großer Wust, weil zunächst die unterschiedlichen Fälle (über- oder unterbestimmt, sparse oder full, usw.) berücksichtigt werden müssen, und dann ein sehr kryptischer BLAS/LAPACK-Befehl erforderlich ist.
Für eine Beschleunigung die beiden inneren von 4 Schleifen zu vektorisieren, ist durchaus eine sinnvolle Idee. Wichtig ist es dabei die inneren Schleifen über die vorderen Dimensionen der Daten laufen zu lassen, da sie im speicher zusammen hängen:
Code:
x = rand(1000, 1000);
S = 0;
for i = 1:1000 for j = 1:1000
S = S + x(i, j); % Langsam % S = S + x(j, i); % Schnell: 50% processing time! end end
Nun kann Matlab auch noch eine Berechnung auf mehrere Threads aufteilen. Dies kann sogar auf einem Single-Core-Rechner schneller sein, wenn der Prozessor auf den langsamen Hauptspeicher warten muss:
Hier werden zunächst die 1000 Spalten-Summen auf mehrere Threads aufgeteilt, danach werden die berechneten 1000 Skalare zusammengezählt. Es ist allerdings schwierig einzuschätzen, wieviel schneller das ist, das viele Aspekte berücksichtigt werden müssen. In meiner Single-Core virtuellen Maschine unter Matlab 2009a ist es 50% schneller als sum(x(:))! Auf einem 8-Core-Rechner wird das mehr sein.
Ein FOR-Schleife wird dagegen im Allgemeinen nur einen einizgen Core auslasten.
Ein Drama sind FOR-Schleifen, wenn man die Ausgabe nicht pre-alloziert:
Code:
tic;
a = [];
for i = 1:10000
a(i) = rand;
end toc; % 0.345559 seconds
Und das Problem wird exponentiell schlimmer. Dies passiert in C und C++ seltener, weil man da sowieso manuell für den Speicher sorgen muss und es eine Menge zusätzlicher Zeilen benätigt, um einen in jeder Iteration wachsenden Vektor zu erzeugen. In MATLAB ist eine fehlende Pre-allozierung aber häufig auftretender Soft-Error. "Soft", weil es kein Laufzeit-Fehler ist, aber je nach Größe läuft das Programm millionenfach langsamer oder führt zu einem unnötigen Out-Of-Memory Fehler.
Zitat:
Die Vektorisierung des Codes ist augesprochen viel Arbeit (und ich gebe zu, dass ich nicht besonders viel Lust dazu habe).
Ja, wie jede Art von Hand-Optimierung ist auch die Vektorisierung sehr zeitaufwändig. Oft wird dies über die Grenzen der Vernunft hinaus betrieben. Es ist sinnlos 10 Stunden in die Optimierung zu zu investieren, wenn das Programm danach eine Stunde weniger Rechenzeit benötigt (und weniger als 10 mal läuft...).
Zitat:
Mir ist aufgefallen, dass Matlab-Scripte ja eigentlich nur interpretiert, aber nicht compiliert werden.
Das stimmt so nicht. Sehr deutlich fällt dies bei JIT-kompilierten Schleifen auf, die beim Debuggen plötzlich 100 mal langsamer werden. Die JIT-Optimierung ändert nämlich bei Bedarf die Reihenfolge der Befehle um Zeit zu sparen. Ein Debuggen wäre deshalb kaum möglich, so dass der JIT-Kompiler abgeschaltet wird, wenn ein Breakpoint in den Sourcecode gesetzt wird. Sogar der Profiler kann die JIT-Beschleunigung deaktivieren, was ziemlich ärgerlich ist: Ein mit dem Profiler gefundener Bottleneck kann bei ausgeschaltetem Profiler plötzlich 100 mal schneller laufen. Hier müsste TMW dringend nachbessern! Man braucht also manuelle TIC/TOC Messungen, um die tatsächliche Laufzeit herauszufinden.
Die Vektorisierung wird dann langsamer als die FOR-Schleifen, wenn viel temporärer Speicher für die Arrays benötigt wird. Wenn mehrer Operatoren auf den selben Daten arbeiten, ist ein C-Mex-File sinnvoll, z.B. "abs(sin(a.^2))+1", da die Verwaltung des temporär benötigten Speichers viel aufwändiger ist als die eigentliche Berechnung.
Die MATLAB Compiler beschleunigt im Allgemeinen die Programme nicht erheblich.
Man kann M-Code aber auch selbst kompilieren, man muss einfach nur einen geeigneten Compiler schreiben, siehe z.B. http://www.cs.fsu.edu/~xyuan/INTERACT-15/papers/paper10.pdf. Chun-Yu Shei et al. lassen damit manche FOR-Schleifen um den Faktor 16 schneller laufen. Dafür steigt der Aufwand beim Debuggen dramatisch an, da man bei einem Problem sowohl den Code, als auch den Compiler und den kompilierten Code überprüfen muss.
Einige MATLAB Funktionen sind suboptimal implementiert. Wenn man also ein bestimmter Befehl einen großen Teil der Laufzeit benötigt, lohnt es sich ihn genauer unter die Lupe zu nehmen. Ich konnte FILTFILT um den Faktor 20 beschleunigen, DATENUM um den Faktor 50 (wenn man einen genau definiertes Input-Format voraussetzt), GRADIENT um den Faktor 20, NORM um den Faktor 2, usw. Ein Blick in die FEX kann sich also lohnen: http://www.mathworks.com/matlabcentral/fileexchange.
Ich konnte hier im Forum schon das ein oder andere Prgramm mit den Standard-Schleifen-Regeln beschleunigen:
1. Spalten-orientiert auf die Daten zugreifen.
2. Alle wiederholten Berechnungen vor die Schleife ziehen und in temporären Variablen speichern.
3. Bei geschachtelten Schleifen wird die kürzere nach aussen gelegt.
Zusammenfassung:
1. Man sollte die Geschwindigkeit von FOR-Schleifen in MATLAB nicht unterschätzen.
2. Lineare-Algebra Methoden sind in MATLAB extrem einfach und schnell.
3. Die Gesamt-Zeit eines Programms setzt sich so zusammen:
Gesamt = Design + Programmierung + Debugging + Laufzeit
Während MATLAB bei der Laufzeit kein echter Brüller ist, ist die Programmierung und das Debuggen sehr effizient im Vergleich zu C und C++. Ein gutes Design bleibt dabei aber grundlegend, z.B. die Representation der Daten in zusammenhängenden Blöcken im Speicher. Wenn die Daten in den Prozessor-Cache passen, kann ein Programm 10 mal schneller laufen. Eine fehlende Pre-allozierung ist ein grober Programmierfehler.
4. Wenn ein Programm hübsch zu lesen sein soll, muss man es sinnvoll in Unterfunktionen aufteilen.
5. Der Aufwand zur Laufzeitoptimierung eines Programms sollte begrenzt werden. Als Daumenregel sind 10% des Codes für 90% der Laufzeit verantwortlich. Eine Vektorisierung oder anderweitige Beschleunigung in den anderen 90% wäre also vergeudetete Zeit.
6. Bei Bedarf sollten Bottlenecks in C geschrieben werden.
7. Eine geschickte Organisation der Daten wird bei großen Programmen im Allgemeinen sehr wichtig. Wenn man erstmal Daten von der Festplatte nachladen muss, läuft auch der schnellste Algorithmus im Schneckentempo.
Hallo Jan,
da du dir soviel Mühe mit dem Beitrag gemacht hast, finde ich ist er es wert in den FAQ zu stehen. Habe ihn deshalb dort auch angelegt und hoffe du hast nichts dagegen.
Aber gerne! Ich sollte wohl auch mal einen meiner Anti-EVAL-Posts dort hin kopieren, anstatt ihn jedesmal mit neuem Enthusiasmus zu verfassen.
Gruß, Jan
Hörmander
Gast
Beiträge: ---
Anmeldedatum: ---
Wohnort: ---
Version: ---
Verfasst am: 15.09.2011, 17:12
Titel:
Zunächst einmal vielen Dank für eure offenbar sogar FAQ-würdigen Antworten. Ich habe die Beiträge mit großem Interesse gelesen, jedoch gibt es noch einige Punkte, auf die ich näher eingehen möchte:
_Peter_ hat Folgendes geschrieben:
Hallo Hörmander,
man kann nicht generell sagen, dass Schleifen schlecht sind. Es kann viele Gründe haben warum dein Code langsam ist.
Unnötige Variablen ausversehen erstellen.
Matrix pre-allocieren nicht durchgeführt.
...
Das lässt sich pauschal nicht sagen, aber du kannst mit dem profiler bzw. mit tic/toc den Flaschenhals in deinem Code finden und versuchen diesen zu beseitigen.
Andere Gründe für Performance-Verlust: In meinem Fall werden keine Variablen unnötig erstellt und Speicher wird für Matrizen vor dem Schleifendurchlauf allokiert. Den Bottleneck mit tic/toc oder Profile zu ermitteln, ist in meinem Fall nicht notwendig, da der Algorithmus eigentlich nur aus der Prä-Allokierung und der Schleife besteht. Folglich werden hier nahezu 100% der Laufzeit verbraucht. Selbstverständlich kann ich nicht ausschließen, dass es noch andere Gründe für den Performance-Einbruch gibt, diese sind es jedoch nicht.
Beispiel: Um etwas konkreter diskutieren zu können, poste ich hier mal stellvertretend für die Algorithmen, um die es geht, die die folgende "LMM_Simulation" in einer Version, welche nur Schleifen und keine Vektorisierungsversuche benutzt:
for omega = 1:B.paths
B.LIBORs(:,1,omega) = B.L;
end
for omega=1:B.paths for n = 1:B.m-1
Si = 0;
for i=n+1:B.m
Si = Si + B.sigma(i) * B.tau(i) * B.LIBORs(i,n,omega) / (1 + B.tau(i) * B.LIBORs(i,n,omega));
B.LIBORs(i,n+1,omega) = B.LIBORs(i,n,omega) * exp( B.sigma(i) *((Si - B.sigma(i)*0.5)*B.tau(n) + B.Z(n,omega) *sqrt(B.tau(n))));
end end end
Das B ist hier ein Objekt, das verschiedene Daten verwaltet. Der Inhalt ist für die diskutierten Punkte eigentlich irrelevant. B.sigma und B.tau sind einfach auch Arrays, in denen benötigte Daten gespeichert sind. Der Algorithmus läuft in einem Framework, welches dafür sorgt, dass alle benötigten Daten schon vorhanden sind. Die dafür notwendige Zeit wurde nicht mitgestoppt.
Nun folgt eine Implementation, welche denselben Output liefert, bei der jedoch die innere Schleife vektorisiert wurde:
"Schleifen-Mythos" Beide Programme habe ich für B.m=10 und B.paths=1000 getestet. Im ersteren Fall benötigt der Algorithmus 24.44sec, im letzteren 1.46sec. Der Vektorisierte Algorithmus ist also erheblich schneller, obwohl er viel mehr sinnlose Berechnungen durchführt. Möglicherweise ist der "Schleifen-Mythos" genau deswegen noch so lebendig. Zum Vergleich: Ein analoger Algorithmus in C/C++ benötigt einen kaum messbaren Sekundenbruchteil.
JIT-Compiler Die Programme wurden in Matlab 7.11.0 (R2010b) geschrieben und getestet. Daher sollte der JIT-Compiler ja standardmäßig eingeschaltet sein. Mit
lässt sich der ja manuell einschalten und ausschalten. Beim Test oben war der JIT-Compiler eingeschaltet. Wenn man ihn explizit ausschaltet, ändern sich die Werte wie folgt:
Schleifen-Version: 25.56 sec
Vektorisierte Version: 6.06 sec
Folglich hat der JIT-Compiler einen deutlich messbaren Einfluss. Trotzdem beseitigt er das Schleifen-Problem nicht wirklich.
Jan S hat Folgendes geschrieben:
Zusammenfassung:
1. Man sollte die Geschwindigkeit von FOR-Schleifen in MATLAB nicht unterschätzen.
2. Lineare-Algebra Methoden sind in MATLAB extrem einfach und schnell.
3. Die Gesamt-Zeit eines Programms setzt sich so zusammen:
Gesamt = Design + Programmierung + Debugging + Laufzeit
Während MATLAB bei der Laufzeit kein echter Brüller ist, ist die Programmierung und das Debuggen sehr effizient im Vergleich zu C und C++. Ein gutes Design bleibt dabei aber grundlegend, z.B. die Representation der Daten in zusammenhängenden Blöcken im Speicher. Wenn die Daten in den Prozessor-Cache passen, kann ein Programm 10 mal schneller laufen. Eine fehlende Pre-allozierung ist ein grober Programmierfehler.
4. Wenn ein Programm hübsch zu lesen sein soll, muss man es sinnvoll in Unterfunktionen aufteilen.
5. Der Aufwand zur Laufzeitoptimierung eines Programms sollte begrenzt werden. Als Daumenregel sind 10% des Codes für 90% der Laufzeit verantwortlich. Eine Vektorisierung oder anderweitige Beschleunigung in den anderen 90% wäre also vergeudetete Zeit.
6. Bei Bedarf sollten Bottlenecks in C geschrieben werden.
7. Eine geschickte Organisation der Daten wird bei großen Programmen im Allgemeinen sehr wichtig. Wenn man erstmal Daten von der Festplatte nachladen muss, läuft auch der schnellste Algorithmus im Schneckentempo.
Zusammenfassung
1. Die Geschwindigkeit speziell dieser For-Schleifen lässt sehr zu wünschen übrig.
2. Vektorisierung speziell dieser Schleifen führt zu einem erheblichen Geschwindigkeitsvorteil.
3. Der JIT-Compiler hat dabei einen vernachlässigbaren Einfluss.
4. Der Performance-Einbruch kann nicht an der Speicherallokierung liegen.
5. Die innerste Schleife greift auf den ersten Index im Array zu, d.h. genauso wie in Jan S Beispiel oben angegeben.
6. Das vorliegende Programm ist bereits ein Unterprogramm und meines Erachtens nach nicht sinnvoll weiter aufteilbar.
Fazit: Entweder gibt es nach wie vor Beispiele von Schleifen, die eine signifikant schlechte Performance haben oder im vorliegenden Beispiel gibt es einen anderen Grund für die schlechte Performance als diesen und die oben genannten.
Unwichtige Zusatzfrage: Was genau geht beim Debuggen in Matlab "sehr effizient"? Meinst du jetzt grundsätzlich effizient oder effizient im Vergleich mit anderen Debuggern? Bisher sind mir noch keine großen Unterschiede in Sachen Komfort als z.B. bei C++ z.B. mit Visual Studio 2010 aufgefallen.
Interessant, dass die vektorisierte Version immer ungefähr gleich schnell ist, während es bei der Schleifen-Version massive Unterschiede gibt. Wenn du auch Matlab R2011a hast, dann würde ich mal schätzen, dass die leicht neuere Version die Schleifen offenbar deutlich besser verarbeitet.
Einstellungen und Berechtigungen
Du kannst Beiträge in dieses Forum schreiben. Du kannst auf Beiträge in diesem Forum antworten. Du kannst deine Beiträge in diesem Forum nicht bearbeiten. Du kannst deine Beiträge in diesem Forum nicht löschen. Du kannst an Umfragen in diesem Forum nicht mitmachen. Du kannst Dateien in diesem Forum posten Du kannst Dateien in diesem Forum herunterladen
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
Kannst du mal Matlab-Version, Betriebssystem, Prozessor und RAM des Testsystems posten?
RSS