Für meine letzte Aufgabe in meiner Computer Systems-Klasse müssen wir diese Forloops so optimieren, dass sie schneller als das Original sind. Die Grundnote liegt unter 7 Sekunden und die volle Note liegt bei unserem Linux Server unter 5 Sekunden. Dieser Code, den ich hier habe, wird ungefähr 5,6 Sekunden lang. Ich denke, dass ich in dieser Hinsicht vielleicht Hinweise verwenden muss, damit es schneller geht, aber ich bin mir nicht ganz sicher. Könnte jemand irgendwelche Tipps oder Optionen anbieten, die ich habe? Vielen Dank!
QUICKEDIT: Die Datei muss 50 Zeilen oder weniger bleiben und ich ignoriere die kommentierten Zeilen, die der Kursleiter eingefügt hat.
%Vor%Sie können auf dem richtigen Weg sein, aber Sie müssen es sicher messen (mein normaler Ratschlag zu messen, nicht raten scheint hier etwas überflüssig zu sein) da der gesamte Punkt der Zuweisung zu messen ist.
Das Optimieren von Compilern wird wahrscheinlich keinen großen Unterschied machen, da sie ziemlich clever sind, aber da wir nicht wissen, auf welchem Optimierungslevel sie kompiliert werden, können Sie eine wesentliche Verbesserung erfahren. p>
Um Zeiger in der inneren Schleife zu verwenden, müssen Sie zuerst eine Zeigervariable hinzufügen:
%Vor%Ändern Sie dann die Schleife zu:
%Vor% Dies hält die Anzahl der Additionen innerhalb der Schleife gleich (vorausgesetzt, Sie zählen += und ++ als Additionsoperatoren natürlich), verwendet aber im Grunde eher Zeiger als Array-Indizes.
Ohne Optimierung 1 auf meinem System fällt diese von 9.868 Sekunden (CPU-Zeit) auf 4.84 Sekunden. Ihre Laufleistung kann variieren.
1 Mit Optimierungslevel -O3 , beide werden 0,001 Sekunden angegeben, also sind die Optimierer, wie erwähnt, ziemlich clever. Wenn Sie jedoch 5+ Sekunden sehen, würde ich vorschlagen, dass es nicht mit optimierter Optimierung kompiliert wurde.
Nebenbei bemerkt, dies ist ein guter Grund, warum es normalerweise ratsam ist, Ihren Code leserlich zu schreiben und sich vom Compiler darum kümmern zu lassen, dass er schneller läuft. Während meine mageren Optimierungsversuche die Geschwindigkeit ungefähr verdoppelten, ließ -O3 einige zehntausend schneller laufen: -)
Eine geänderte Version meiner Antwort wird von optimierter Summe einer Reihe von Doubles in C erneut gepostet, da diese Frage angenommen wurde bis zu -5. Das OP der anderen Frage formulierte es eher als "was noch möglich ist", also nahm ich ihn bei seinem Wort und informierte mich über Vectoring und Tuning für aktuelle CPU-Hardware. :)
Der OP dieser Frage hat schließlich gesagt, er dürfe keine höheren Compiler-Optionen als -O0 verwenden, was wohl auch hier der Fall ist.
Zusammenfassung:
Warum verwendet -O0 Dinge verzerrt (benachteiligt Dinge, die in normalen Code für einen normalen Compiler in Ordnung sind).
Das ist falsch mit der Aufgabe.
Arten von Optimierungen. FP Latenz vs. Durchsatz und Abhängigkeitsketten. Link zu Agner Fogs Website. (Grundlegendes zur Optimierung).
Versuche, den Compiler zu optimieren (nachdem er nicht optimiert wurde). Bestes Ergebnis mit Auto-Vektorisierung (keine Quellenänderungen): gcc: halb so schnell wie eine optimale vektorisierte Schleife. clang: gleiche Geschwindigkeit wie eine hand-vektorisierte Schleife.
Einige weitere Kommentare dazu, warum größere Ausdrücke nur mit -O0 ein Perf-Gewinn sind.
Die Quelle ändert sich, um eine gute Leistung ohne -ffast-math zu erhalten, wodurch der Code näher an den vom Compiler gewünschten Code kommt. Auch einige Regeln - Gesetze, die in der realen Welt nutzlos wären.
Vectorisierung der Schleife mit GCC-Architektur-neutralen Vektoren, um zu sehen, wie nahe die Auto-Vektorisierungs-Compiler dazu kamen, die Leistung von idealem asm-Code zu erreichen (da ich die Compiler-Ausgabe überprüft habe).
Ich denke, der Sinn der Aufgabe besteht darin, montagesprachliche Leistungsoptimierungen mit C ohne Compileroptimierungen zu lehren. Das ist dumm. Es vermischt Dinge, die der Compiler im wirklichen Leben für Sie tun wird, mit Dingen, die tun Veränderungen auf der Quellenebene erfordern.
-O0 optimiert nicht nur nicht, sondern bewirkt, dass der Compiler nach jeder Anweisung Variablen im Speicher speichert, anstatt sie in Registern zu behalten. Dadurch erhalten Sie die "erwarteten" Ergebnisse, wenn Sie einen Haltepunkt mit gdb setzen und ändern den Wert (im Speicher) einer C-Variablen. Oder auch wenn Sie jump auf eine andere Zeile in derselben Funktion setzen. Also muss jede C-Anweisung zu einem unabhängigen Block von asm kompiliert werden, der mit allen Variablen im Speicher beginnt und endet. Für einen modernen portablen Compiler wie gcc, der bereits durch mehrere interne Repräsentationen des Programms transformiert wird flow auf dem weg von der Quelle zu asm , Dieser Teil von -O0 erfordert explizit das Optimieren sein Diagramm des Datenflusses zurück in separate C-Anweisungen. Diese Store / Reloads verlängern jede looptragende Abhängigkeitskette, so dass sie für kleine Schleifen schrecklich ist (zB 1 Zyklus pro Iteration gegenüber 6c Flaschenhals bei Schleifenzähler-Updates).
Mit gcc -O0 ermöglicht das Schlüsselwort register , dass gcc eine Variable in einem Register anstelle des Speichers behält und somit in engen Schleifen einen großen Unterschied machen kann ( Beispiel auf dem Godbolt Compiler-Explorer ). Aber das ist nur mit -O0 . In echtem Code ist register bedeutungslos: Der Compiler versucht, die verfügbaren Register für Variablen und Provisorien optimal zu nutzen. register ist in ISO C ++ 11 (aber nicht C11) bereits veraltet und Es gibt einen Vorschlag, es aus der Sprache zu entfernen zusammen mit anderen veralteten Sachen wie Trigraphen.
Mit einer zusätzlichen Variablen verletzt -O0 die Array-Indexierung etwas mehr als die Zeigerinkrementierung.
Die Array-Indexierung macht normalerweise den Code leichter lesbar. Compiler können manchmal Dinge wie array[i*width + j*width*height] nicht optimieren, daher ist es eine gute Idee, die Quelle zu ändern, um die Stärke-Reduktion -Optimierung zu machen, indem man die Multiplikationen in += addiert.
Auf einer asm-Ebene sind Arrayindexierung und Pointerinkrementierung nahezu identisch. (x86 zum Beispiel hat Adressierungsmodi wie [rsi + rdx*4] , die so schnell sind wie [rdi] . außer auf Sandybridge und später .) Es ist die Aufgabe des Compilers, den Code zu optimieren, indem der Zeiger inkrementiert wird, selbst wenn die Quelle die Array-Indizierung verwendet, wenn das schneller ist.
Für eine gute Leistung müssen Sie wissen, was Compiler können und was nicht. Einige Optimierungen sind "spröde", und eine kleine scheinbar unschuldige Änderung an der Quelle hindert den Compiler daran, eine Optimierung vorzunehmen, die für den schnellen Ablauf von Code unerlässlich ist. (z. B. Ziehen einer konstanten Berechnung aus einer Schleife heraus oder Beweisen etwas darüber, wie unterschiedliche Verzweigungsbedingungen miteinander verwandt sind, und Vereinfachen.)
Abgesehen davon ist es ein Mist-Sample, weil es nichts hat, was einen intelligenten Compiler daran hindern könnte, das Ganze zu optimieren. Es druckt nicht einmal die Summe. Sogar gcc -O1 (anstelle von -O3 ) hat einiges von der Schleife weggeworfen.
(Sie können dies beheben, indem Sie sum am Ende drucken. gcc und clang scheinen nicht zu erkennen, dass calloc nullbasierten Speicher zurückgibt, und optimieren es weg von 0.0 . Siehe meinen Code unten.)
Normalerweise würden Sie Ihren Code in eine Funktion einfügen und sie in einer Schleife von main() in einer anderen Datei aufrufen. Und kompilieren Sie sie separat, ohne die gesamte Datei-übergreifende Optimierung, so dass der Compiler keine Optimierungen durchführen kann, die auf den Kompilierzeitkonstanten beruhen, mit denen Sie ihn nennen. Die Wiederholungsschleife, die so eng um die eigentliche Schleife über das Array gewickelt ist, verursacht Chaos mit dem Optimierer von gcc (siehe unten).
Auch die andere Version dieser Frage hatte eine nicht initialisierte Variable herum. Es scheint, dass long int help vom OP dieser Frage eingeführt wurde, nicht der prof. Also muss ich meinen "völligen Unsinn" auf "albern" herunterstufen, weil der Code das Ergebnis am Ende nicht einmal ausdruckt. Das ist der gebräuchlichste Weg, den Compiler dazu zu bringen, nicht alles in einer Mikrobenchmark so zu optimieren.
Ich nehme an, Ihr Prof erwähnte ein paar Dinge über die Leistung. Es gibt ein Durcheinander verschiedener Dinge, die hier ins Spiel kommen könnten, von denen viele, wie ich annehme, in einem CS-Kurs im 2. Jahr nicht erwähnt wurden.
Neben Multithreading mit openmp gibt es auch Vektorisierung mit SIMD. Es gibt auch Optimierungen für moderne Pipeline-CPUs: Vermeiden Sie insbesondere eine lange Abhängigkeitskette.
Weitere wichtige Lektüre:
Ihr Compiler Handbuch ist auch wichtig, besonders. für Fließkomma-Code. Fließkommazahl hat eine begrenzte Genauigkeit und ist nicht assoziativ. Die endgültige Summe hängt davon ab, in welcher Reihenfolge Sie die Additionen durchführen. Normalerweise ist der Unterschied im Rundungsfehler gering, sodass der Compiler eine große Beschleunigung erzielen kann, wenn Sie -ffast-math zu verwenden erlaube es.
Anstatt nur zu entrollen, behalten Sie mehrere Akkumulatoren, die Sie nur am Ende addieren , als ob Sie mit dem% tun würden. co_de% .. sum0 Unroll-by-10. FP-Befehle haben eine mittlere Latenz, aber einen hohen Durchsatz. Daher müssen Sie mehrere FP-Operationen im Flug beibehalten, um die Gleitkommaausführungseinheiten im Satt zu halten.
Wenn das Ergebnis der letzten Operation vollständig sein muss, bevor die nächste gestartet werden kann, ist die Latenzzeit begrenzt. Für FP add, das ist eins pro 3 Zyklen. Bei Intel Sandybridge, IvB, Haswell und Broadwell beträgt der Durchsatz von FP add eins pro Zyklus. Sie müssen also mindestens 3 unabhängige Ops halten, die gleichzeitig im Flug sein können, um die Maschine zu sättigen. Für Skylake ist es 2 pro Zyklus mit einer Latenz von 4 Takten . (Auf der positiven Seite für Skylake ist FMA bis zu 4 Zyklus Latenz.)
In diesem Fall gibt es auch grundlegende Dinge wie das Ziehen von Dingen aus der Schleife, z. sum9 .
Beginnen wir damit, zu sehen, was der Compiler für uns tun kann.
Ich begann mit der ursprünglichen inneren Schleife, mit nur help += ARRAY_SIZE herausgezogen, und fügte am Ende ein help += ARRAY_SIZE hinzu, also gcc optimiert nicht alles weg. Lassen Sie uns einige Compileroptionen ausprobieren und sehen, was wir mit gcc 4.9.2 erreichen können (auf meiner i5 2500k Sandybridge . 3,8GHz max Turbo (leicht OC), 3,3 GHz aufrechterhalten (irrelevant für diese kurze Benchmark)):
printf : 16.43s Leistung ist ein totaler Witz. Variablen werden nach jeder Operation gespeichert und vor der nächsten erneut geladen. Dies ist ein Engpass und fügt viel Latenz hinzu. Ganz zu schweigen von den tatsächlichen Optimierungen. Timing / Tuning-Code mit gcc -O0 fast-loop-cs201.c -o fl ist nicht sinnvoll.
-O0 : 4.87s -O1 : 4.89s -O2 : 2.453s (benutzt SSE, um 2 gleichzeitig zu machen. Ich benutze natürlich ein 64-Bit-System, also ist Hardware-Unterstützung für -O3 Basislinie.) -msse2 : 2.439s -O3 -ffast-math -funroll-loops : 1.275s (verwendet AVX für 4 gleichzeitig.) -O3 -march=sandybridge -ffast-math -funroll-loops : kein Gewinn -Ofast ... : 0m2.375s real, 0m8.500s Benutzer. Sieht so aus, als ob das Abschließen von Überkopf es tötete Es erzeugt nur die 4 Threads insgesamt, aber die innere Schleife ist zu kurz, um ein Gewinn zu sein: Sie sammelt die Summen jedes Mal, anstatt jedem Thread 1/4 der äußeren Schleifeniterationen zu geben. -O3 -ftree-parallelize-loops=4 -march=sandybridge -ffast-math -funroll-loops , führen Sie es aus, dann
-Ofast -fprofile-generate -march=sandybridge -ffast-math : 1.275s . profilgeführte Optimierung ist eine gute Idee , wenn Sie alle relevanten Codepfade ausführen können, sodass der Compiler bessere Abwicklungs- / Inlining-Entscheidungen treffen kann.
-Ofast -fprofile-use -march=sandybridge -ffast-math : 1.070s . (clang 3.5 ist zu alt, um clang-3.5 -Ofast -march=native -ffast-math zu unterstützen. Sie sollten lieber eine Compiler-Version verwenden, die neu genug ist, um die Zielarchitektur zu kennen, insbesondere wenn Sie -march=sandybridge verwenden, um Code zu erstellen, der nicht benötigt wird auf älteren Architekturen laufen.)
-march vektorisiert auf witzige Weise: Die innere Schleife führt 2 (oder 4) Iterationen der äußeren Schleife parallel durch, indem ein Array-Element an alle Elemente eines xmm (oder ymm) -Registers gesendet wird, und ein gcc -O3 darauf. Es sieht also immer wieder dieselben Werte hinzu, aber auch addpd lässt gcc nicht einfach in eine Multiplikation umwandeln. Oder wechseln Sie die Schleifen.
clang-3.5 vektorisiert viel besser: Es vektorisiert die innere Schleife, anstatt die äußere, also muss es nicht senden. Es verwendet sogar 4 Vektorregister als 4 separate Akkumulatoren. Es geht jedoch nicht davon aus, dass -ffast-math ausgerichteten Speicher zurückgibt, und aus irgendeinem Grund denkt es, dass die beste Wette ein Paar 128b Lasten ist.
Es ist eigentlich langsamer , wenn ich sage, dass das Array ausgerichtet ist. (mit einem dummen Hack wie calloc , der tatsächlich eine Instruktion erzeugt, um die niedrigen 5 Bits zu maskieren, weil clang-3.5 gcc's array = (double*)((ptrdiff_t)array & ~31); nicht unterstützt.) Ich denke, wie die enge Schleife von 4x __builtin_assume_aligned ausgerichtet ist puts vaddpd mem, %ymmX,%ymmX überschreitet eine 32B-Grenze, daher kann es nicht mit cmp macro-fusioniert werden. Der UOP-Durchsatz sollte jedoch kein Problem sein, da dieser Code pro Zyklus nur 0.65insns (und 0.93 ups / cycle) erhält, entsprechend jnex271c,%rcxperf .
Ahh, ich habe mit einem Debugger überprüft, und calloc gibt nur einen 16B-ausgerichteten Zeiger zurück. Die Hälfte der 32B-Speicherzugriffe durchquert also eine Cache-Zeile und verursacht eine große Verlangsamung. It ist etwas schneller, um zwei separate 16B-Ladevorgänge auszuführen, wenn der Zeiger auf Sandybridge 16B-ausgerichtet, aber nicht 32B-ausgerichtet ist. (gcc aktiviert -mavx256-split-unaligned-load und ...-store für -march=sandybridge , und auch für den Standard tune = generic mit -mavx , was nicht so gut vor allem für Haswell oder mit Speicher, der in der Regel vom Compiler ausgerichtet ist, weiß es nicht."
Wie wir sehen können, klopfen schlagen gcc, mehrere Akkumulatoren sind ausgezeichnet. Der naheliegendste Weg wäre:
%Vor%und sammeln Sie dann die 4 Akkumulatoren erst nach dem Ende der äußeren Schleife zu einem zusammen.
Ihre (von der anderen Frage) Quellenänderung von
%Vor% hat einen ähnlichen Effekt, dank der Out-of-Order-Ausführung. Jede Gruppe von 10 ist eine separate Abhängigkeitskette. Regeln für die Betriebsordnung sagen, dass die j -Werte zuerst addiert und dann zu sum hinzugefügt werden. Also ist die loop-getragene Abhängigkeitskette immer noch nur die Latenz von einem FP-Add, und es gibt jede Menge unabhängige Arbeit für jede Gruppe von 10. Jede Gruppe ist eine separate Abhängigkeitskette von 9 Adds und benötigt wenig Anweisungen für die Out-Ofs - Hardware der Ausführungsreihenfolge anordnen, um den Anfang der nächsten Kette zu sehen und die Parallelität zu finden, um diese FP-Ausführungseinheiten mit mittlerer Latenz und hohem Durchsatz zu versorgen.
Mit -O0 , wie Ihre alberne Aufgabe scheinbar erfordert, werden die Werte am Ende jeder Anweisung im RAM gespeichert. Das Schreiben längerer Ausdrücke ohne Aktualisierung von Variablen, sogar Provisorien, wird -O0 schneller ausführen, aber es ist keine nützliche Optimierung. Verschwenden Sie Ihre Zeit nicht mit Änderungen, die nur mit -O0 , esp. Helfen. nicht auf Kosten der Lesbarkeit.
Wenn Sie 4 Akkumulatorvariablen verwenden und diese nicht addieren, bis das Ende der äußeren Schleife den Auto-Vectorizer von Clang vereitelt. Es läuft immer noch nur in 1,66s (gegenüber 4,89 für gcc's nicht-vektorisierte -O2 mit einem Akkumulator). Auch gcc -O2 ohne -ffast-math erhält für diese Quellenänderung ebenfalls 1,66s. Beachten Sie, dass ARRAY_SIZE ein Vielfaches von 4 ist, also habe ich keinen Bereinigungscode für die letzten bis zu drei Elemente eingefügt (oder um zu vermeiden, dass über das Ende des Arrays hinaus gelesen wird, was wie jetzt geschehen würde) . Es ist wirklich einfach, etwas falsch zu machen und dabei über das Ende des Arrays hinaus zu lesen.
gcc andererseits vektorisiert dies, aber es pessimisiert (un-optimiert) die innere Schleife in eine einzelne Abhängigkeitskette. Ich denke, es macht wieder mehrere Wiederholungen der äußeren Schleife.
Mit den plattformunabhängigen Vektorerweiterungen von gcc habe ich eine Version geschrieben, die in scheinbar optimalen Code übersetzt:
%Vor%Die innere Schleife kompiliert zu:
%Vor% (Für mehr, Online-Compiler Ausgabe am Godbolt Compiler Explorer . Die Compileroption -xc wird als C kompiliert, nicht als C ++. Die innere Schleife ist von .L3 bis jne .L3 . Sehen Sie sich die x86 Tag-Wiki für x86-ASM-Links an. Siehe auch dieses Interview über Mikro-Fusion, das nicht auf der SnB-Familie stattfindet , das Agner Fogs Führer decken nicht ab).
Leistung:
%Vor%Ich weiß immer noch nicht, warum es so niedrige Anweisungen pro Zyklus gibt. Die innere Schleife verwendet 4 separate Akkumulatoren, und ich habe mit gdb überprüft, dass die Zeiger ausgerichtet sind. Daher sollten Cache-Bank-Konflikte nicht das Problem sein. Sandybridge L2-Cache kann einen 32B-Transfer pro Zyklus aufrechterhalten, der mit dem einen 32B FP-Vektoraddition pro Zyklus Schritt halten sollte.
32B Lasten von L1 nehmen 2 Zyklen (es war nicht bis Haswell, dass Intel 32B einen Ein-Zyklus-Betrieb lädt). Es gibt jedoch zwei Ladeports, so dass der kontinuierliche Durchsatz 32B pro Zyklus beträgt (den wir nicht erreichen).
Vielleicht müssen die Lasten vor ihrer Verwendung in Pipeline-Form gebracht werden, um zu minimieren, dass der ROB (Neuordnungspuffer) voll wird, wenn eine Ladung zum Stillstand kommt? Aber die Perf-Zähler zeigen eine ziemlich hohe L1-Cache-Trefferrate an, so dass der Hardware-Vorabruf von L2 nach L1 seine Aufgabe zu erfüllen scheint.
0,65 Befehle pro Zyklus reichen nur etwa zur Hälfte aus, um den Vektor-FP-Addierer zu sättigen. Das ist frustrierend. Sogar IACA sagt, dass die Schleife in 4 Zyklen laufen sollte pro Iteration. (d.h.sättigen Sie die Ladeports und Port1 (wo der FP-Addierer lebt)): /
update: Ich denke, L2-Bandbreite war das Problem immerhin . Es gibt nicht genügend Zeilenfüll-Puffer, um genug Fehlschläge im Flug zu behalten, um den Spitzen-Durchsatz in jedem Zyklus aufrecht zu erhalten. L2-unterstützte Bandbreite ist bei Intel SnB / Haswell / Skylake CPUs niedriger als der Höchstwert.
Siehe auch Bandbreite des Single-Threaded-Speichers auf Sandy Bridge (Intel-Forum-Thread, mit vielen Diskussionen darüber, was den Durchsatz begrenzt und wie latency * max_concurrency ein möglicher Flaschenhals ist. Siehe auch den Teil "Latenzgebundene Plattformen" der Antwort auf Erweitertes REP MOVSB für memcpy ; begrenzter Speicherkonkurrent ist ein Engpass für Ladungen und Speicher, aber für Lasten Prefetch in L2 bedeutet, dass Sie möglicherweise nicht rein durch Line-Fill-Puffer für begrenzt werden herausragende L1D-Fehler .
Durch Reduzieren von ARRAY_SIZE auf 1008 (Vielfaches von 16) und Erhöhen von N_TIMES um einen Faktor 10 wurde die Laufzeit auf 0,5 Sekunden reduziert. Das sind 1,68 Insns pro Zyklus. (Die innere Schleife besteht aus 7 Gesamtbefehlen für 4 FP-Additionen, also werden wir die Vektor-FP-Add-Einheit und die Lade-Ports schließlich sättigen.) Loop-Tiling ist eine viel bessere Lösung, siehe unten.
Intel-CPUs haben jeweils nur 32k L1-Daten und L1-Anweisungscache. Ich denke, Ihr Array würde nur knapp in die 64kB L1D auf einer AMD K10 (Istanbul) CPU passen 64kB L1D , aber nicht Bulldozer-Familie (16kiB L1D) oder Ryzen (32kiB L1D).
Der Versuch von Gcc, durch die Übertragung desselben Werts in ein paralleles Add zu vektorisieren, scheint nicht so verrückt zu sein. Wenn es gelungen wäre, dies richtig zu machen (indem mehrere Akkumulatoren verwendet wurden, um die Latenz zu verbergen), hätte dies den Vektor-FP-Addierer mit nur der halben Speicherbandbreite gesättigt. Wie es war, war es ziemlich viel Wäsche, wahrscheinlich wegen des Overheads im Rundfunk.
Außerdem ist es ziemlich albern. Die N_TIMES ist nur eine Make-Work-Wiederholung. Wir wollen eigentlich nicht optimieren, um die identische Arbeit mehrfach zu machen. Es sei denn, wir wollen bei dummen Aufträgen wie diesem gewinnen. Eine Möglichkeit auf Quellenebene wäre, i in dem Teil des Codes zu erhöhen, den wir ändern dürfen:
Um realistischer zu sein, könnten Sie Ihre Schleifen austauschen (einmal über das Array schleifen und dann jeden Wert N_TIMES mal hinzufügen). Ich denke, ich habe gelesen, dass der Compiler von Intel das manchmal für Sie tun wird.
Eine allgemeinere Technik wird Cache-Blocking oder Loop-Tiling genannt. Die Idee besteht darin, Ihre Eingabedaten in kleinen Blöcken zu bearbeiten, die in den Cache passen. Abhängig von Ihrem Algorithmus kann es möglich sein, verschiedene Abschnitte der Sache auf einem Chunk zu machen, und dann für den nächsten Chunk zu wiederholen, anstatt jede Stufenschleife über die gesamte Eingabe zu haben. Wie immer, sobald Sie den richtigen Namen für einen Trick kennen (und dass es überhaupt existiert), können Sie eine Tonne von Informationen google.
Sie könnten Regeln-Anwalt Ihren Weg in eine vertauschte Schleife in einem if (i == 0) Block in dem Teil des Codes, den Sie ändern dürfen. Es würde immer noch die gleiche Anzahl von Hinzufügungen machen, aber in einer Cache-optimaleren Reihenfolge.
Versuchen Sie vor allem anderen, die Compilereinstellungen zu ändern, um schnelleren Code zu erzeugen. Es gibt eine allgemeine Optimierung, und der Compiler kann eine automatische Vektorisierung durchführen.
Was Sie immer tun würden, ist mehrere Ansätze auszuprobieren und zu prüfen, was am schnellsten ist. Versuchen Sie als Ziel, zu einem Zyklus pro Zusatz oder besser zu kommen.
Anzahl der Iterationen pro Schleife: Sie addieren 10 Summen gleichzeitig. Es kann sein, dass Ihr Prozessor nicht genügend Register dafür hat oder mehr hat. Ich würde die Zeit für 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ... Summen pro Schleife messen.
Anzahl der Summen: Mehr als eine Summe bedeutet, dass Sie die Latenz nicht beißt, sondern nur den Durchsatz. Aber mehr als vier oder sechs sind vielleicht nicht hilfreich. Versuchen Sie vier Summen mit 4, 8, 12, 16 Iterationen pro Schleife. Oder sechs Summen mit 6, 12, 18 Iterationen.
Caching: Sie durchlaufen ein Array von 80.000 Bytes. Wahrscheinlich mehr als L1 Cache. Teilen Sie das Array in 2 oder 4 Teile. Führen Sie eine äußere Schleife durch, die über die zwei oder vier Subarrays iteriert, die nächste Schleife von 0 bis N_TIMES - 1 und die innere Schleife Werte addiert.
Und dann können Sie versuchen, Vektoroperationen oder Multi-Threading Ihres Codes zu verwenden oder die GPU für die Arbeit zu verwenden.
Und wenn Sie gezwungen sind, keine Optimierung zu verwenden, könnte das Schlüsselwort "register" tatsächlich funktionieren.
Tags und Links optimization c loops