Was sind einige gute Strategien zur Verbesserung der seriellen Leistung meines Codes?

Ich arbeite in der Computerwissenschaft und verbringe daher einen nicht unerheblichen Teil meiner Zeit damit, den wissenschaftlichen Durchsatz vieler Codes zu steigern und die Effizienz dieser Codes zu verstehen.

Nehmen wir an, ich habe den Kompromiss zwischen Leistung und Lesbarkeit / Wiederverwendbarkeit / Wartbarkeit der Software, an der ich arbeite, bewertet und festgestellt, dass es Zeit für die Leistung ist. Nehmen wir auch an, dass ich weiß, dass ich keinen besseren Algorithmus für mein Problem habe (in Bezug auf Flop / s und Speicherbandbreite). Sie können auch davon ausgehen, dass meine Codebasis in einer einfachen Sprache wie C, C ++ oder Fortran vorliegt. Nehmen wir zum Schluss an, dass der Code keine Parallelität aufweist oder dass wir nur an der Leistung eines einzelnen Kerns interessiert sind.

Was sind die wichtigsten Dinge, die Sie zuerst ausprobieren sollten? Woher weiß ich, wie viel Leistung ich erreichen kann?

Zunächst ist, wie Skillman und Dan betonten , die Profilerstellung unerlässlich. Ich persönlich benutze Intels VTune Amplifier unter Linux, da er mir einen sehr detaillierten Überblick darüber gibt, wo die Zeit für was aufgewendet wurde.

Wenn Sie den Algorithmus nicht ändern werden (dh wenn es keine größeren Änderungen gibt, die alle Ihre Optimierungen überflüssig machen), dann würde ich vorschlagen, nach einigen allgemeinen Implementierungsdetails zu suchen, die einen großen Unterschied machen können:

• Speicherlokalität : Werden gemeinsam gelesene / verwendete Daten auch gemeinsam gespeichert, oder nehmen Sie hier und da Kleinigkeiten auf?

• Speicherausrichtung : Sind Ihre Doubles tatsächlich auf 4 Bytes ausgerichtet? Wie hast du deine eingepackt structs? Um pedantisch zu sein, verwenden Sie posix_memalignanstelle von malloc.

• Cache-Effizienz : Locality kümmert sich um die meisten Probleme mit der Cache-Effizienz. Wenn Sie jedoch einige kleine Datenstrukturen haben, die Sie häufig lesen / schreiben, ist es hilfreich, wenn es sich um ein ganzzahliges Vielfaches oder einen Bruchteil einer Cache-Zeile handelt (normalerweise 64 Byte). Es ist auch hilfreich, wenn Ihre Daten an der Größe einer Cache-Zeile ausgerichtet sind. Dies kann die Anzahl der zum Laden eines Datenelements erforderlichen Lesevorgänge drastisch reduzieren.

• Vektorisierung : Nein, denken Sie nicht an handcodierten Assembler. gccBietet Vektortypen, die automatisch in SSE / AltiVec / beliebige Anweisungen übersetzt werden.

• Parallelität auf Befehlsebene : Der Bastard der Vektorisierung. Wenn einige häufig wiederholte Berechnungen nicht gut vektorisieren, können Sie versuchen, Eingabewerte zu akkumulieren und mehrere Werte gleichzeitig zu berechnen. Es ist wie ein Loop, der sich abwickelt. Was Sie hier ausnutzen, ist, dass Ihre CPU normalerweise mehr als eine Gleitkommaeinheit pro Kern hat.

• Arithmetische Genauigkeit : Wollen Sie wirklich mit doppelter Genauigkeit Arithmetik in allem , was Sie tun? Wenn Sie beispielsweise eine Korrektur in einer Newton-Iteration berechnen, benötigen Sie normalerweise nicht alle Ziffern, die Sie berechnen. Weitere Informationen finden Sie in diesem Dokument.

Einige dieser Tricks werden in daxpy_cvec diesem Thread verwendet. Wenn Sie jedoch Fortran (in meinen Büchern keine einfache Sprache) verwenden, haben Sie kaum Kontrolle über die meisten dieser "Tricks".

Wenn Sie eine dedizierte Hardware verwenden, z. B. einen Cluster, den Sie für alle Produktionsläufe verwenden, möchten Sie möglicherweise auch die Details der verwendeten CPUs nachlesen. Nicht, dass Sie direkt in Assembler etwas für diese Architektur schreiben sollten, aber es könnte Sie dazu inspirieren, einige andere Optimierungen zu finden, die Sie möglicherweise übersehen haben. Das Wissen über eine Funktion ist ein notwendiger erster Schritt, um Code zu schreiben, der sie ausnutzen kann.

Aktualisieren

Es ist schon eine Weile her, seit ich das geschrieben habe und ich hatte nicht bemerkt, dass es eine so beliebte Antwort geworden war. Aus diesem Grund möchte ich einen wichtigen Punkt hinzufügen:

• Sprechen Sie mit Ihrem lokalen Informatiker : Wäre es nicht cool, wenn es eine Disziplin gäbe, die ausschließlich Algorithmen und / oder Berechnungen effizienter / eleganter / paralleler macht, und wir könnten sie alle um Rat fragen? Nun, eine gute Nachricht, diese Disziplin existiert: Informatik. Wahrscheinlich ist Ihrer Einrichtung sogar eine ganze Abteilung gewidmet. Sprecht mit diesen Leuten.

Ich bin mir sicher, dass dies für eine Reihe von Nicht-Informatikern Erinnerungen an frustrierende Diskussionen mit dieser Disziplin wecken wird, die zu nichts geführt haben, oder Erinnerungen an die Anekdoten anderer. Lass dich nicht entmutigen. Interdisziplinäre Zusammenarbeit ist eine knifflige Sache und erfordert ein wenig Arbeit, aber die Belohnungen können enorm sein.

Nach meiner Erfahrung als Informatiker (CS) besteht der Trick darin, sowohl die Erwartungen als auch die Kommunikation in Einklang zu bringen.

Erwartungsbewusst hilft Ihnen ein CS nur, wenn er / sie Ihr Problem für interessant hält. Dies schließt den Versuch aus, einen Teil des Codes, den Sie geschrieben, aber nicht wirklich kommentiert haben, für ein Problem, das sie nicht verstehen, zu optimieren / zu vektorisieren / zu parallelisieren. CSs interessieren sich normalerweise mehr für das zugrunde liegende Problem, z. B. die Algorithmen, die zur Lösung des Problems verwendet werden. Gib ihnen nicht deine Lösung , gib ihnen dein Problem .

Stellen Sie sich auch darauf ein, dass der CS sagt, dass dieses Problem bereits gelöst ist , und geben Sie nur einen Verweis auf ein Papier. Ein Tipp: Lesen Sie dieses Dokument und implementieren Sie den vorgeschlagenen Algorithmus, falls er für Ihr Problem tatsächlich relevant ist. Dies ist keine selbstgefällige CS, sondern eine CS, die Ihnen nur geholfen hat. Seien Sie nicht beleidigt, denken Sie daran: Wenn das Problem rechnerisch nicht interessant ist, dh wenn es bereits gelöst wurde und die Lösung sich als optimal herausstellt, wird es nicht bearbeitet, geschweige denn, Sie können es programmieren.

Denken Sie in Bezug auf die Kommunikation daran, dass die meisten CSs keine Experten auf Ihrem Gebiet sind, und erklären Sie das Problem in Bezug auf das, was Sie tun, und nicht wie und warum . Wir kümmern uns normalerweise nicht wirklich um das Warum und das Wie , na ja, was wir am besten können.

Zum Beispiel arbeite ich derzeit mit einigen Computational Cosmologists daran, eine bessere Version ihres Simulationscodes zu schreiben, die auf SPH und Multipoles basiert . Es dauerte ungefähr drei Meetings, bis man aufhörte, über Dunkle Materie und Galaxienhalos zu sprechen, und bis man zum Kern der Berechnung kam, dh dass man alle Nachbarn innerhalb eines bestimmten Radius jedes Teilchens finden musste, um einige zu berechnen Quantität über ihnen, und laufen Sie dann über alle besagten Nachbarn wieder und wenden Sie diese Quantität in irgendeiner anderen Berechnung an. Bewegen Sie dann die Partikel oder zumindest einige von ihnen und wiederholen Sie den Vorgang. Sie sehen, während das erstere unglaublich interessant sein kann (es ist!), Ist das letztere, was ich verstehen muss, um anfangen zu können, über Algorithmen nachzudenken.

Aber ich weichen vom Hauptpunkt ab: Wenn Sie wirklich daran interessiert sind, Ihre Berechnung schnell zu machen, und Sie selbst kein Informatiker sind, sprechen Sie mit einem.

Wissenschaftliche Software unterscheidet sich nicht wesentlich von anderer Software, da sie weiß, was optimiert werden muss.

Die Methode, die ich benutze, ist zufälliges Anhalten . Hier sind einige der Speedups, die es für mich gefunden hat:

Wenn ein großer Teil der Zeit in Funktionen wie logund verbracht wird exp, kann ich die Argumente für diese Funktionen als Funktion der Punkte sehen, von denen aus sie aufgerufen werden. Oft werden sie wiederholt mit demselben Argument aufgerufen. Wenn dies der Fall ist, führt das Speichern von Memos zu einer massiven Beschleunigung.

Wenn ich BLAS- oder LAPACK-Funktionen verwende, verbringe ich möglicherweise einen großen Teil der Zeit mit Routinen zum Kopieren von Arrays, Multiplizieren von Matrizen, Choleski-Transformationen usw.

• Die Routine zum Kopieren von Arrays dient nicht der Geschwindigkeit, sondern der Benutzerfreundlichkeit. Möglicherweise gibt es eine weniger bequeme, aber schnellere Möglichkeit, dies zu tun.

• Routinen zum Multiplizieren oder Invertieren von Matrizen oder zum Ausführen von Choleski-Transformationen enthalten in der Regel Zeichenargumente, mit denen Optionen wie 'U' oder 'L' für das obere oder untere Dreieck angegeben werden. Auch diese sind der Einfachheit halber da. Da meine Matrizen nicht sehr groß waren, verbrachten die Routinen mehr als die Hälfte ihrer Zeit damit, die Unterroutine zum Vergleichen von Zeichen aufzurufen , um die Optionen zu entschlüsseln. Das Schreiben von Spezialversionen der teuersten mathematischen Routinen führte zu einer enormen Beschleunigung.

Wenn ich nur auf Letzteres eingehen kann: Die Matrix-Multiplikationsroutine DGEMM ruft LSAME auf, um ihre Zeichenargumente zu dekodieren. Betrachtet man die prozentuale Inklusivzeit (die einzige Statistik, die es wert ist, betrachtet zu werden), können Profiler, die als "gut" eingestuft werden, DGEMM mit einem Anteil von 80% an der Gesamtzeit und LSAME mit einem Anteil von 50% an der Gesamtzeit anzeigen. Wenn Sie das erstere betrachten, werden Sie versucht sein zu sagen: "Nun, es muss stark optimiert werden, also kann ich nicht viel dagegen tun." Wenn Sie sich das letztere ansehen, werden Sie versucht sein zu sagen: "Huh? Worum geht es hier? Das ist nur eine winzige Routine. Dieser Profiler muss falsch sein!"

Es ist nicht falsch, es sagt dir nur nicht, was du wissen musst. Aus zufälligen Pausen geht hervor, dass sich DGEMM auf 80% der Stack-Samples und LSAME auf 50% befindet. (Sie benötigen nicht viele Beispiele, um dies zu erkennen. In der Regel reichen 10 aus.) Außerdem ruft DGEMM bei vielen dieser Beispiele LSAME aus verschiedenen Codezeilen auf.

Jetzt wissen Sie also, warum beide Routinen so viel Zeit in Anspruch nehmen. Sie wissen auch, von wo in Ihrem Code sie aufgerufen werden, um die ganze Zeit zu verbringen. Das ist der Grund, warum ich willkürlich pausiere und die Profiler aus einer krassen Perspektive betrachte, egal wie gut sie sind. Sie sind mehr daran interessiert, Messungen zu erhalten, als Ihnen zu sagen, was los ist.

Es ist leicht anzunehmen, dass die mathematischen Bibliotheksroutinen bis zum n-ten Grad optimiert wurden, aber tatsächlich wurden sie so optimiert, dass sie für eine Vielzahl von Zwecken verwendet werden können. Sie müssen sehen, was wirklich los ist, und nicht, was leicht anzunehmen ist.

ADDED: Um Ihre letzten beiden Fragen zu beantworten:

Was sind die wichtigsten Dinge, die Sie zuerst ausprobieren sollten?

Nehmen Sie 10-20 Stapelproben und fassen Sie sie nicht nur zusammen, sondern verstehen Sie, was jede einzelne Ihnen sagt. Tun Sie dies zuerst, zuletzt und dazwischen. (Es gibt keinen "Versuch", junger Skywalker.)

Woher weiß ich, wie viel Leistung ich erreichen kann?

Anhand der Stapelproben können Sie sehr grob abschätzen, welcher Bruchteil der Zeit eingespart wird. (Es folgt eine -Verteilung, wobei die Anzahl der Samples ist, die angezeigt haben, was Sie korrigieren möchten, und die Gesamtzahl der Samples ist Kosten für den Code, den Sie zum Ersetzen verwendet haben, der hoffentlich klein sein wird.) Dann beträgt das Beschleunigungsverhältnis was groß sein kann. Beachten Sie, wie sich dies mathematisch verhält. Wenn und , ist der Mittelwert und die Mode von 0,5 für ein Beschleunigungsverhältnis von 2. Hier ist die Verteilung: Wenn Sie risikoavers sind, gibt es eine kleine Wahrscheinlichkeit (0,03%). Das$x$$\beta(s+1,(n-s)+1)$$s$$n$$1/(1-x)$$n=10$$s=5$$x$

$x$ ist kleiner als 0,1 für eine Beschleunigung von weniger als 11%. Dies ist jedoch die gleiche Wahrscheinlichkeit, dass größer als 0,9 ist, für ein Beschleunigungsverhältnis von mehr als 10! Wenn Sie Geld im Verhältnis zur Programmgeschwindigkeit erhalten, sind das keine schlechten Chancen.$x$

Wie ich Ihnen bereits gesagt habe, können Sie den gesamten Vorgang wiederholen, bis Sie nicht mehr können, und das zusammengesetzte Beschleunigungsverhältnis kann recht groß sein.

HINZUGEFÜGT: Lassen Sie mich als Reaktion auf Pedros Besorgnis über falsche Positive versuchen, ein Beispiel zu konstruieren, an dem deren Auftreten zu erwarten ist. Wir werden niemals auf ein potenzielles Problem einwirken, es sei denn, wir sehen es zweimal oder öfter. Daher würden wir erwarten, dass falsche Positive auftreten, wenn wir ein Problem so selten wie möglich sehen, insbesondere wenn die Gesamtzahl der Stichproben groß ist. Angenommen, wir nehmen 20 Proben und sehen sie zweimal. Das schätzt seine Kosten auf 10% der gesamten Ausführungszeit, der Art seiner Verteilung. (Der Mittelwert der Verteilung ist höher - es ist .) Die untere Kurve in der folgenden Grafik ist die Verteilung:$(s+1)/(n+2)=3/22=13.6\%$

Überlegen Sie, ob wir bis zu 40 Proben genommen haben (mehr als jemals zuvor) und nur bei zwei von ihnen ein Problem festgestellt haben. Die geschätzten Kosten (Modus) dieses Problems betragen 5%, wie in der größeren Kurve gezeigt.

Was ist ein "falsch positives"? Wenn Sie ein Problem beheben, bemerken Sie einen so geringen Gewinn als erwartet, dass Sie es bereuen, ihn behoben zu haben. Die Kurven zeigen (wenn das Problem "klein" ist), dass die Verstärkung zwar geringer sein kann als der Bruchteil der Proben, die sie zeigen, aber im Durchschnitt größer ist.

Es besteht ein weitaus größeres Risiko - ein "falsches Negativ". In diesem Fall liegt ein Problem vor, das jedoch nicht gefunden wird. (Dazu trägt eine "Bestätigungsverzerrung" bei, bei der fehlende Beweise eher als Beweise für die Abwesenheit behandelt werden.)

Was Sie mit einem Profiler erhalten (ein gutes) ist man viel genauere Messung zu erhalten (also weniger Chancen von Fehlalarmen), auf Kosten von viel weniger präzise Informationen über das, was das Problem tatsächlich ist (also weniger Chancen, es zu finden und immer irgendein Gewinn). Dies begrenzt die insgesamt erreichbare Beschleunigung.

Ich möchte Benutzer von Profilern ermutigen, die tatsächlich in der Praxis auftretenden Beschleunigungsfaktoren anzugeben.

Es gibt noch einen weiteren Punkt, der noch zu klären ist. Pedros Frage zu False Positives.

Er erwähnte, dass es schwierig sein könnte, kleine Probleme in hochoptimiertem Code zu lösen. (Für mich ist ein kleines Problem eines, das 5% oder weniger der Gesamtzeit ausmacht.)

Da es durchaus möglich ist, ein Programm zu erstellen, das mit Ausnahme von 5% absolut optimal ist, kann dieser Punkt wie in dieser Antwort nur empirisch behandelt werden . Um aus empirischen Erfahrungen zu verallgemeinern:

Ein Programm enthält in der Regel mehrere Optimierungsmöglichkeiten. (Wir können sie als "Probleme" bezeichnen, aber sie sind oftmals perfekter Code, der sich einfach erheblich verbessern lässt.) Dieses Diagramm zeigt ein künstliches Programm, das einige Zeit in Anspruch nimmt (z. B. 100s), und es enthält die Probleme A, B, C, ... das, wenn es gefunden und repariert wird, 30%, 21% usw. der ursprünglichen 100er einspart.

Beachten Sie, dass Problem F 5% der ursprünglichen Zeit kostet, es ist also "klein" und ohne 40 oder mehr Proben schwer zu finden.

Die ersten 10 Beispiele finden jedoch leicht das Problem A. ** Wenn dies behoben ist, dauert das Programm nur 70 Sekunden, bei einer Geschwindigkeitssteigerung von 100/70 = 1,43x. Das macht das Programm nicht nur schneller, es vergrößert auch die Prozentsätze der verbleibenden Probleme um dieses Verhältnis. Zum Beispiel hat Problem B ursprünglich 21 Sekunden in Anspruch genommen, was 21% der Gesamtsumme ausmachte, aber nach dem Entfernen von A benötigt B 21 Sekunden von 70 Sekunden oder 30%, so dass es einfacher ist, zu finden, wann der gesamte Prozess wiederholt wird.

Wenn der Prozess fünf Mal wiederholt wird, beträgt die Ausführungszeit 16,8 Sekunden. Davon ist das Problem F 30% und nicht 5%, sodass 10 Stichproben es leicht finden.

Das ist also der Punkt. Empirisch gesehen enthalten Programme eine Reihe von Problemen mit einer Größenverteilung, und jedes festgestellte und behobene Problem erleichtert das Auffinden der verbleibenden Probleme. Um dies zu erreichen, kann keines der Probleme übersprungen werden, da sie, falls vorhanden, Zeit in Anspruch nehmen, die Gesamtbeschleunigung begrenzen und die verbleibenden Probleme nicht vergrößern. Deshalb ist es sehr wichtig, die versteckten Probleme zu finden .

Wenn die Probleme A bis F gefunden und behoben werden, beträgt die Beschleunigung 100 / 11,8 = 8,5x. Wenn einer von ihnen verfehlt wird, zum Beispiel D, dann beträgt die Beschleunigung nur 100 / (11,8 + 10,3) = 4,5x. Das ist der Preis für falsche Negative.

Wenn der Profiler also sagt, dass es hier kein nennenswertes Problem zu geben scheint (dh ein guter Codierer, dies ist praktisch optimaler Code), ist es vielleicht richtig und vielleicht auch nicht. (Ein falsches Negativ .) Sie wissen nicht genau, ob weitere Probleme zu beheben sind, um eine höhere Geschwindigkeit zu erzielen, es sei denn, Sie versuchen eine andere Profilerstellungsmethode und stellen fest, dass dies der Fall ist. Meiner Erfahrung nach erfordert die Profilierungsmethode keine große Anzahl von Stichproben, sondern eine kleine Anzahl von Stichproben, wobei jede Stichprobe gründlich genug verstanden wird, um Optimierungsmöglichkeiten zu erkennen.

** Es dauert mindestens 2 Treffer, um ein Problem zu finden, es sei denn, man weiß vorher, dass es eine (nahezu) Endlosschleife gibt. (Die roten Häkchen stehen für 10 Zufallsstichproben); Die durchschnittliche Anzahl von Stichproben, die benötigt wird, um 2 oder mehr Treffer zu erhalten, beträgt bei einem Problem von 30% ( negative Binomialverteilung ). 10 Proben finden es mit einer Wahrscheinlichkeit von 85%, 20 Proben - 99,2% ( Binomialverteilung ). Um die Wahrscheinlichkeit, das Problem zu bekommen, in R, zu bewerten , zum Beispiel: .$2/0.3=6.67$1 - pbinom(1, numberOfSamples, sizeOfProblem)1 - pbinom(1, 20, 0.3) = 0.9923627

HINZUGEFÜGT: Der eingesparte Zeitanteil folgt einer Beta-Verteilung , wobei die Anzahl der Stichproben ist und die Anzahl, die das Problem anzeigt. Das Beschleunigungsverhältnis gleich (vorausgesetzt, dass alles von gespeichert ist), und es wäre interessant, die Verteilung von zu verstehen . Es stellt sich heraus, dass einer BetaPrime- Distribution folgt . Ich habe es mit 2 Millionen Samples simuliert und dabei folgendes Verhalten festgestellt:β ( s + 1 , ( n - s ) + 1 ) n s y 1 / ( 1 - x ) x y y - $x$$\beta(s+1,(n-s)+1)$$n$$s$$y$$1/(1-x)$$x$$y$$y-1$

         distribution of speedup
               ratio y

 s, n    5%-ile  95%-ile  mean
 2, 2    1.58    59.30   32.36
 2, 3    1.33    10.25    4.00
 2, 4    1.23     5.28    2.50
 2, 5    1.18     3.69    2.00
 2,10    1.09     1.89    1.37
 2,20    1.04     1.37    1.17
 2,40    1.02     1.17    1.08

 3, 3    1.90    78.34   42.94
 3, 4    1.52    13.10    5.00
 3, 5    1.37     6.53    3.00
 3,10    1.16     2.29    1.57
 3,20    1.07     1.49    1.24
 3,40    1.04     1.22    1.11

 4, 4    2.22    98.02   52.36
 4, 5    1.72    15.95    6.00
 4,10    1.25     2.86    1.83
 4,20    1.11     1.62    1.31
 4,40    1.05     1.26    1.14

 5, 5    2.54   117.27   64.29
 5,10    1.37     3.69    2.20
 5,20    1.15     1.78    1.40
 5,40    1.07     1.31    1.17

Die ersten beiden Spalten geben das 90% -Konfidenzintervall für das Beschleunigungsverhältnis an. Das mittlere Beschleunigungsverhältnis ist gleich Ausnahme des Falls, in dem . In diesem Fall ist es undefiniert, und wenn ich die Anzahl der simulierten Werte erhöhe, steigt der empirische Mittelwert.s = n $(n+1)/(n-s)$$s=n$$y$

Dies ist eine grafische Darstellung der Verteilung der Beschleunigungsfaktoren und ihrer Mittelwerte für 2 Treffer aus 5, 4, 3 und 2 Stichproben. Wenn zum Beispiel 3 Proben entnommen werden und 2 davon auf ein Problem stoßen und dieses Problem behoben werden kann, beträgt der durchschnittliche Beschleunigungsfaktor 4x. Wenn die 2 Treffer nur in 2 Samples zu sehen sind, ist die durchschnittliche Beschleunigung undefiniert - konzeptionell, weil Programme mit Endlosschleifen mit einer Wahrscheinlichkeit ungleich Null existieren!

Nicht nur Sie intime Kenntnis Ihrer haben müssen Compiler , haben Sie auch intime Kenntnis Ihrer Zielarchitektur und Betriebssystem .

Was kann die Leistung beeinträchtigen?

Wenn Sie die Leistung auf ein Minimum reduzieren möchten, müssen Sie bei jeder Änderung der Zielarchitektur den Code optimieren und neu optimieren. Etwas, das eine Optimierung mit einer CPU war, kann in der nächsten Revision derselben CPU suboptimal werden.

Ein hervorragendes Beispiel hierfür wären CPU-Caches. Verschieben Sie Ihr Programm von einer CPU mit einem schnellen kleinen Cache auf eine mit einem etwas langsameren, etwas größeren Cache, und Ihre Profilerstellung könnte sich erheblich ändern.

Auch wenn sich die Zielarchitektur nicht ändert, können geringfügige Änderungen an einem Betriebssystem die Leistung beeinträchtigen. Die Schadensbegrenzungs-Patches für Spectre und Meltdown hatten bei einigen Workloads erhebliche Auswirkungen, sodass diese möglicherweise eine Neubewertung Ihrer Optimierungen erforderlich machen.

Wie kann ich meinen Code optimieren?

Wenn Sie hochoptimierten Code entwickeln, müssen Sie ihn modular halten und es einfach machen, verschiedene Versionen desselben Algorithmus ein- und auszutauschen. Abhängig von den verfügbaren Ressourcen und der Größe / Komplexität von müssen Sie möglicherweise sogar die zur Laufzeit verwendete Version auswählen zu verarbeitende Daten.

Modularität bedeutet auch, dass Sie für alle Ihre optimierten und nicht optimierten Versionen dieselbe Testsuite verwenden können. Auf diese Weise können Sie überprüfen, ob sich alle gleich verhalten, und jedes einzelne schnell in einem ähnlichen Vergleich profilieren . Ich gehe in meiner Antwort auf Wie dokumentiere und unterrichte ich andere, die "bis zur Unkenntlichkeit optimiert" sind, mit rechenintensivem Code? .

Weitere Lektüre

Darüber hinaus kann ich einen Blick auf Ulrich Dreppers hervorragende Arbeit What Every Programmer Should Know About Memory ( Was jeder Programmierer über Speicher wissen sollte) werfen , deren Titel eine Hommage an David Goldbergs ebenso fantastisches What Every Computer Scientist Should Know About Floating-Point Arithmetic (Was jeder Informatiker über Fließkommaarithmetik wissen sollte) ist .

Denken Sie daran, dass jede Optimierung das Potenzial hat, eine zukünftige Anti-Optimierung zu werden. Daher sollte ein möglicher Code-Geruch in Betracht gezogen werden, um das Risiko auf ein Minimum zu reduzieren. Meine Antwort auf Ist die Mikrooptimierung beim Codieren wichtig? liefert ein konkretes Beispiel dafür aus eigener Erfahrung.

Ich denke, Sie formulieren die Frage zu eng. Meiner Ansicht nach ist es eine nützliche Einstellung, davon auszugehen, dass nur Änderungen an den Datenstrukturen und Algorithmen signifikante Leistungssteigerungen bei Codes mit mehr als ein paar 100 Zeilen bewirken können, und ich glaube, dass ich noch kein Gegenbeispiel dafür finden muss Diese behauptung.

Als erstes sollten Sie Ihren Code profilieren. Sie möchten herausfinden, welche Teile Ihres Programms Sie verlangsamen, bevor Sie mit der Optimierung beginnen. Andernfalls können Sie einen Teil Ihres Codes optimieren, der ohnehin nicht viel Ausführungszeit in Anspruch nimmt.

Linux

gprof ist ziemlich gut, aber es gibt nur an, wie viel Zeit von jeder Funktion und nicht von jeder Zeile benötigt wird.

Apple OS X

Vielleicht möchten Sie Shark ausprobieren . Sie finden sie auf der Apple Developer Site unter Downloads> Developer Tools> CHUD 4.6.2, der älteren Version hier . CHUD enthält auch andere Profilierungswerkzeuge wie das BigTop-Frontend, das PMC-Index-Suchwerkzeug, den Saturn-Profiler auf Funktionsebene und viele andere Befehle. Shark wird mit einer Kommandozeilenversion geliefert.

Nehmen Sie die Ergebnisse der Profilerstellung für Ihren Code und nehmen Sie an, Sie identifizieren ein Teil, das einen Bruchteil der Zeit in Anspruch nimmt. Wenn Sie die Leistung dieses Stücks nur um den Faktor "s" verbessern, beträgt Ihre Gesamtbeschleunigung 1 / ((1-p) + p / s). Daher können Sie Ihre Geschwindigkeit maximal um den Faktor 1 / (1-p) erhöhen. Hoffentlich hast du Gebiete mit hohem p! Dies entspricht dem Amdahlschen Gesetz für die Serienoptimierung.

Die Optimierung Ihres Codes muss sorgfältig durchgeführt werden. Nehmen wir auch an, Sie haben den Code bereits debuggt. Sie können viel Zeit sparen, wenn Sie bestimmte Prioritäten verfolgen, nämlich:

1. Verwenden Sie nach Möglichkeit hochoptimierte (oder professionell optimierte) Bibliotheken. Einige Beispiele könnten FFTW-, OpenBlas-, Intel MKL-, NAG-Bibliotheken usw. sein. Wenn Sie nicht hoch talentiert sind (wie der Entwickler von GotoBLAS), können Sie die Profis wahrscheinlich nicht schlagen.

2. Verwenden Sie einen Profiler (einige in der folgenden Liste wurden bereits in diesem Thread genannt - Intel Tune, valgrind, gprof, gcov usw.), um herauszufinden, welche Teile Ihres Codes die meiste Zeit in Anspruch nehmen. Es macht keinen Sinn, Zeit zu verschwenden, um Teile des Codes zu optimieren, die selten aufgerufen werden.

3. Sehen Sie sich in den Profiler-Ergebnissen den Teil Ihres Codes an, der die meiste Zeit in Anspruch genommen hat. Bestimmen Sie die Art Ihres Algorithmus - ist er an die CPU oder den Speicher gebunden? Jedes erfordert einen anderen Satz von Optimierungstechniken. Wenn Sie viele Cache-Ausfälle bemerken, ist der Speicher möglicherweise der Engpass. Die CPU verschwendet Taktzyklen und wartet darauf, dass Speicher verfügbar wird. Überlegen Sie, ob die Schleife in den L1 / L2 / L3-Cache Ihres Systems passt. Wenn Sie "if" -Anweisungen in Ihrer Schleife haben, überprüfen Sie, ob der Profiler etwas über die falsche Vorhersage von Zweigen sagt. Was ist die Strafe für die falsche Vorhersage von Zweigen in Ihrem System? Übrigens können Sie Zweigfehlervorhersagedaten aus den Intel Optimization Reference Manuals [1] abrufen. Beachten Sie, dass die Strafe für die falsche Vorhersage von Zweigen prozessorspezifisch ist, wie Sie im Intel-Handbuch sehen werden.

4. Beheben Sie abschließend die vom Profiler erkannten Probleme. Eine Reihe von Techniken wurde hier bereits diskutiert. Eine Reihe guter, zuverlässiger und umfassender Ressourcen zur Optimierung sind ebenfalls verfügbar. Um nur zwei zu nennen, gibt es das Intel Optimization Reference Manual [1] und die fünf Optimierungshandbücher von Agner Fog [2]. Beachten Sie, dass Sie einige Dinge möglicherweise nicht tun müssen, wenn der Compiler dies bereits tut - z. B. das Abrollen der Schleife, das Ausrichten des Speichers usw. Lesen Sie die Compiler-Dokumentation sorgfältig durch.

Verweise:

[1] Referenzhandbuch zur Optimierung der Intel 64- und IA-32-Architekturen: http://www.intel.sg/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdf

[2] Agner Fog, "Software Optimization Resources": http://www.agner.org/optimize/

• "Optimieren von Software in C ++: Ein Optimierungshandbuch für Windows-, Linux- und Mac-Plattformen"
• "Unterprogramme in Assemblersprache optimieren: Ein Optimierungshandbuch für x86-Plattformen"
• "Die Mikroarchitektur von Intel-, AMD- und VIA-CPUs: Ein Optimierungsleitfaden für Assembly-Programmierer und Compiler-Hersteller"
• Befehlstabellen: Listen der Befehlswartezeiten, Durchsätze und Mikrooperationsausfälle für Intel-, AMD- und VIA-CPUs
• "Aufrufkonventionen für verschiedene C ++ - Compiler und Betriebssysteme"

Ich bin kein Informatiker wie viele andere hier (daher könnte ich mich irren :)), aber heutzutage macht es wenig Sinn, zu viel Zeit für die serielle Leistung aufzuwenden, solange wir Standardbibliotheken verwenden. Es ist möglicherweise sinnvoller, zusätzliche Zeit und Mühe zu investieren, um den Code skalierbarer zu machen.

In jedem Fall sind hier zwei Beispiele (falls Sie sie noch nicht gelesen haben), wie die Leistung verbessert wurde (für unstrukturierte FE-Probleme).

Seriennummer : Siehe 2. Hälfte des Abstracts und verwandten Texts.

Parallel : Speziell die Initialisierungsphase in Abschnitt 4.2.

Dies ist vielleicht eher eine Meta-Antwort als eine Antwort ...

Sie müssen eine enge Vertrautheit mit Ihrem Compiler entwickeln. Sie können dies am effizientesten erreichen, indem Sie das Handbuch lesen und mit den Optionen experimentieren.

Viele der guten Ratschläge, die @Pedro ausgibt, können durch Anpassen der Kompilierung und nicht des Programms implementiert werden.

Eine einfache Möglichkeit, ein Programm zu profilieren (unter Linux), ist die Verwendung perfim statModus. Der einfachste Weg ist es einfach so zu laufen

perf stat ./my_program args ...

und es gibt Ihnen eine Reihe von nützlichen Leistungsstatistiken:

Performance counter stats for './simd_test1':

     3884.559489 task-clock                #    1.000 CPUs utilized
              18 context-switches          #    0.005 K/sec
               0 cpu-migrations            #    0.000 K/sec
             383 page-faults               #    0.099 K/sec
  10,911,904,779 cycles                    #    2.809 GHz
 <not supported> stalled-cycles-frontend
 <not supported> stalled-cycles-backend
  14,346,983,161 instructions              #    1.31  insns per cycle
   2,143,017,630 branches                  #  551.676 M/sec
          28,892 branch-misses             #    0.00% of all branches

     3.885986246 seconds time elapsed

Manchmal werden auch D-Cache-Lasten und Fehlschläge aufgelistet. Wenn Sie viele Cache-Fehler feststellen, ist Ihr Programm speicherintensiv und behandelt die Caches nicht richtig. Heutzutage werden CPUs schneller als die Speicherbandbreite, und das Problem ist normalerweise immer der Speicherzugriff.

Sie können auch versuchen, auf perf record ./my_program; perf reportwelche Weise Sie sich leicht profilieren können. Lesen Sie die Manpages, um mehr zu erfahren.