Vor vielen Jahren waren C-Compiler nicht besonders intelligent. Um dieses Problem zu umgehen, hat K & R das Schlüsselwort register erfunden , um den Compiler darauf hinzuweisen, dass es möglicherweise eine gute Idee wäre, diese Variable in einem internen Register zu belassen. Sie haben auch den tertiären Operator dazu gebracht, besseren Code zu generieren.

Mit der Zeit reiften die Compiler. Sie wurden sehr schlau, da ihre Flussanalyse es ihnen ermöglichte, bessere Entscheidungen darüber zu treffen, welche Werte in Registern gespeichert werden sollen, als Sie möglicherweise tun könnten. Das Schlüsselwort register wurde unwichtig.

FORTRAN kann aufgrund von Alias- Problemen für einige Arten von Vorgängen schneller als C sein . Theoretisch kann man mit sorgfältiger Codierung diese Einschränkung umgehen, damit der Optimierer schneller Code generieren kann.

Welche Codierungsmethoden stehen zur Verfügung, mit denen der Compiler / Optimierer schneller Code generieren kann?

• Wir würden uns freuen, wenn Sie die Plattform und den Compiler identifizieren, die Sie verwenden.
• Warum scheint die Technik zu funktionieren?
• Beispielcode wird empfohlen.

Hier ist eine verwandte Frage

[Bearbeiten] Bei dieser Frage geht es nicht um den gesamten Prozess zum Profilieren und Optimieren. Angenommen, das Programm wurde korrekt geschrieben, mit vollständiger Optimierung kompiliert, getestet und in Produktion genommen. Möglicherweise enthält Ihr Code Konstrukte, die den Optimierer daran hindern, die bestmögliche Arbeit zu leisten. Was können Sie tun, um diese Verbote zu überarbeiten und dem Optimierer zu ermöglichen, noch schnelleren Code zu generieren?

[Bearbeiten] Versatzbezogener Link

Schreiben Sie in lokale Variablen und geben Sie keine Argumente aus! Dies kann eine große Hilfe sein, um Aliasing-Verlangsamungen zu umgehen. Zum Beispiel, wenn Ihr Code so aussieht

void DoSomething(const Foo& foo1, const Foo* foo2, int numFoo, Foo& barOut)
{
    for (int i=0; i<numFoo, i++)
    {
         barOut.munge(foo1, foo2[i]);
    }
}

Der Compiler kennt foo1! = barOut nicht und muss daher foo1 jedes Mal durch die Schleife neu laden. Es kann auch foo2 [i] erst lesen, wenn das Schreiben in barOut abgeschlossen ist. Sie könnten anfangen, mit eingeschränkten Zeigern herumzuspielen, aber es ist genauso effektiv (und viel klarer), dies zu tun:

void DoSomethingFaster(const Foo& foo1, const Foo* foo2, int numFoo, Foo& barOut)
{
    Foo barTemp = barOut;
    for (int i=0; i<numFoo, i++)
    {
         barTemp.munge(foo1, foo2[i]);
    }
    barOut = barTemp;
}

Es klingt albern, aber der Compiler kann mit der lokalen Variablen viel schlauer umgehen, da er sich möglicherweise nicht mit einem der Argumente im Speicher überschneiden kann. Dies kann Ihnen helfen, den gefürchteten Load-Hit-Store zu vermeiden (von Francis Boivin in diesem Thread erwähnt).

Hier ist eine Codierungspraxis, die dem Compiler hilft, schnellen Code zu erstellen - jede Sprache, jede Plattform, jeder Compiler, jedes Problem:

Sie nicht verwenden , um alle cleveren Tricks , die Kraft oder sogar ermutigen, den Compiler Variablen im Speicher - Layout (einschließlich Cache und Register) , wie Sie am besten denken. Schreiben Sie zuerst ein Programm, das korrekt und wartbar ist.

Als nächstes profilieren Sie Ihren Code.

Dann und nur dann möchten Sie möglicherweise die Auswirkungen untersuchen, wenn Sie dem Compiler mitteilen, wie der Speicher verwendet wird. Nehmen Sie jeweils 1 Änderung vor und messen Sie die Auswirkungen.

Erwarten Sie, enttäuscht zu sein und in der Tat sehr hart für kleine Leistungsverbesserungen arbeiten zu müssen. Moderne Compiler für ausgereifte Sprachen wie Fortran und C sind sehr, sehr gut. Wenn Sie einen Bericht über einen „Trick“ lesen, um eine bessere Leistung des Codes zu erzielen, denken Sie daran, dass die Compiler-Autoren auch darüber gelesen haben und ihn, falls es sich lohnt, wahrscheinlich implementiert haben. Sie haben wahrscheinlich geschrieben, was Sie zuerst gelesen haben.

Die Reihenfolge, in der Sie den Speicher durchlaufen, kann tiefgreifende Auswirkungen auf die Leistung haben, und Compiler sind nicht wirklich gut darin, dies herauszufinden und zu beheben. Wenn Sie Code schreiben, müssen Sie sich der Bedenken hinsichtlich der Cache-Lokalität bewusst sein, wenn Sie Wert auf Leistung legen. Beispielsweise werden zweidimensionale Arrays in C im Zeilenhauptformat zugewiesen. Das Durchlaufen von Arrays im Spaltenhauptformat führt dazu, dass Sie mehr Cache-Fehler haben und Ihr Programm mehr an den Speicher gebunden ist als an den Prozessor:

#define N 1000000;
int matrix[N][N] = { ... };

//awesomely fast
long sum = 0;
for(int i = 0; i < N; i++){
  for(int j = 0; j < N; j++){
    sum += matrix[i][j];
  }
}

//painfully slow
long sum = 0;
for(int i = 0; i < N; i++){
  for(int j = 0; j < N; j++){
    sum += matrix[j][i];
  }
}

Allgemeine Optimierungen

Hier einige meiner Lieblingsoptimierungen. Ich habe tatsächlich die Ausführungszeiten verlängert und die Programmgröße reduziert, indem ich diese verwendet habe.

Deklarieren Sie kleine Funktionen als inlineoder Makros

Jeder Aufruf einer Funktion (oder Methode) verursacht Overhead, z. B. das Verschieben von Variablen auf den Stapel. Einige Funktionen können auch bei der Rücksendung einen Overhead verursachen. Eine ineffiziente Funktion oder Methode enthält weniger Anweisungen als der kombinierte Overhead. Dies sind gute Kandidaten für Inlining, sei es als #defineMakros oder als inlineFunktion. (Ja, ich weiß, es inlineist nur ein Vorschlag, aber in diesem Fall betrachte ich ihn als Erinnerung an den Compiler.)

Entfernen Sie toten und redundanten Code

Wenn der Code nicht verwendet wird oder nicht zum Ergebnis des Programms beiträgt, entfernen Sie ihn.

Vereinfachen Sie das Design von Algorithmen

Ich habe einmal viel Assembler-Code und Ausführungszeit aus einem Programm entfernt, indem ich die berechnete algebraische Gleichung aufgeschrieben und dann den algebraischen Ausdruck vereinfacht habe. Die Implementierung des vereinfachten algebraischen Ausdrucks nahm weniger Platz und Zeit in Anspruch als die ursprüngliche Funktion.

Abwickeln der Schleife

Jede Schleife hat einen Aufwand für die Inkrementierung und Abschlussprüfung. Um eine Schätzung des Leistungsfaktors zu erhalten, zählen Sie die Anzahl der Anweisungen im Overhead (mindestens 3: Inkrementieren, Überprüfen, zum Start der Schleife) und dividieren Sie durch die Anzahl der Anweisungen innerhalb der Schleife. Je niedriger die Zahl, desto besser.

Bearbeiten: Geben Sie ein Beispiel für das Abrollen der Schleife. Vorher:

unsigned int sum = 0;
for (size_t i; i < BYTES_TO_CHECKSUM; ++i)
{
    sum += *buffer++;
}

Nach dem Abrollen:

unsigned int sum = 0;
size_t i = 0;
**const size_t STATEMENTS_PER_LOOP = 8;**
for (i = 0; i < BYTES_TO_CHECKSUM; **i = i / STATEMENTS_PER_LOOP**)
{
    sum += *buffer++; // 1
    sum += *buffer++; // 2
    sum += *buffer++; // 3
    sum += *buffer++; // 4
    sum += *buffer++; // 5
    sum += *buffer++; // 6
    sum += *buffer++; // 7
    sum += *buffer++; // 8
}
// Handle the remainder:
for (; i < BYTES_TO_CHECKSUM; ++i)
{
    sum += *buffer++;
}

In diesem Vorteil wird ein sekundärer Vorteil erzielt: Es werden mehr Anweisungen ausgeführt, bevor der Prozessor den Anweisungscache neu laden muss.

Ich habe erstaunliche Ergebnisse erzielt, als ich eine Schleife mit 32 Anweisungen abgewickelt habe. Dies war einer der Engpässe, da das Programm eine Prüfsumme für eine 2-GB-Datei berechnen musste. Diese Optimierung in Kombination mit dem Blocklesen verbesserte die Leistung von 1 Stunde auf 5 Minuten. Das Abrollen der Schleife lieferte auch in Assemblersprache eine hervorragende Leistung. Meine memcpywar viel schneller als die des Compilers memcpy. - TM

Reduzierung von ifAussagen

Prozessoren hassen Verzweigungen oder Sprünge, da sie den Prozessor zwingen, seine Anweisungswarteschlange neu zu laden.

Boolesche Arithmetik ( Bearbeitet: Codeformat auf Codefragment angewendet, Beispiel hinzugefügt)

Konvertieren Sie ifAnweisungen in boolesche Zuweisungen. Einige Prozessoren können Anweisungen ohne Verzweigung bedingt ausführen:

bool status = true;
status = status && /* first test */;
status = status && /* second test */;

Der Kurzschluss des logischen UND- Operators ( &&) verhindert die Ausführung der Tests, wenn dies der Fall statusist false.

Beispiel:

struct Reader_Interface
{
  virtual bool  write(unsigned int value) = 0;
};

struct Rectangle
{
  unsigned int origin_x;
  unsigned int origin_y;
  unsigned int height;
  unsigned int width;

  bool  write(Reader_Interface * p_reader)
  {
    bool status = false;
    if (p_reader)
    {
       status = p_reader->write(origin_x);
       status = status && p_reader->write(origin_y);
       status = status && p_reader->write(height);
       status = status && p_reader->write(width);
    }
    return status;
};

Zuordnung von Faktorvariablen außerhalb von Schleifen

Wenn eine Variable im laufenden Betrieb innerhalb einer Schleife erstellt wird, verschieben Sie die Erstellung / Zuordnung vor die Schleife. In den meisten Fällen muss die Variable nicht bei jeder Iteration zugewiesen werden.

Faktor konstante Ausdrücke außerhalb von Schleifen

Wenn eine Berechnung oder ein variabler Wert nicht vom Schleifenindex abhängt, verschieben Sie ihn außerhalb (vor) der Schleife.

E / A in Blöcken

Lesen und Schreiben von Daten in großen Blöcken. Je größer desto besser. Zum Beispiel ist das Lesen von jeweils einem Oktekt weniger effizient als das Lesen von 1024 Oktetten mit einem Lesevorgang.
Beispiel:

static const char  Menu_Text[] = "\n"
    "1) Print\n"
    "2) Insert new customer\n"
    "3) Destroy\n"
    "4) Launch Nasal Demons\n"
    "Enter selection:  ";
static const size_t Menu_Text_Length = sizeof(Menu_Text) - sizeof('\0');
//...
std::cout.write(Menu_Text, Menu_Text_Length);

Die Effizienz dieser Technik kann visuell demonstriert werden. :-)

Verwenden Sie printf family nicht für konstante Daten

Konstante Daten können mit einem Blockschreibvorgang ausgegeben werden. Beim formatierten Schreiben wird Zeit damit verschwendet, den Text nach Formatierungen zu durchsuchen oder Formatierungsbefehle zu verarbeiten. Siehe obiges Codebeispiel.

In den Speicher formatieren und dann schreiben

Formatieren Sie charmit mehreren in ein Array und verwenden Sie sprintfdann fwrite. Dadurch kann das Datenlayout auch in "konstante Abschnitte" und variable Abschnitte unterteilt werden. Denken Sie an Seriendruck .

Deklarieren Sie konstanten Text (String-Literale) als static const

Wenn Variablen ohne das deklariert werden static, weisen einige Compiler möglicherweise Speicherplatz auf dem Stapel zu und kopieren die Daten aus dem ROM. Dies sind zwei unnötige Operationen. Dies kann mithilfe des staticPräfixes behoben werden .

Schließlich Code wie der Compiler würde

Manchmal kann der Compiler mehrere kleine Anweisungen besser optimieren als eine komplizierte Version. Auch das Schreiben von Code zur Optimierung des Compilers hilft. Wenn der Compiler spezielle Blockübertragungsanweisungen verwenden soll, schreibe ich Code, der die speziellen Anweisungen verwenden sollte.

Der Optimierer hat nicht wirklich die Kontrolle über die Leistung Ihres Programms. Verwenden Sie geeignete Algorithmen und Strukturen sowie Profil, Profil, Profil.

Das heißt, Sie sollten eine kleine Funktion aus einer Datei in einer anderen Datei nicht in einer inneren Schleife ausführen, da dies verhindert, dass sie inline wird.

Vermeiden Sie nach Möglichkeit die Adresse einer Variablen. Nach einem Zeiger zu fragen ist nicht "frei", da dies bedeutet, dass die Variable im Speicher gehalten werden muss. Sogar ein Array kann in Registern gespeichert werden, wenn Sie Zeiger vermeiden - dies ist für die Vektorisierung unerlässlich.

Was zum nächsten Punkt führt, lesen Sie das Handbuch ^ # $ @ ! GCC kann einfachen C-Code vektorisieren, wenn Sie ein __restrict__Hier und ein __attribute__( __aligned__ )Dort streuen . Wenn Sie etwas sehr Spezifisches vom Optimierer wünschen, müssen Sie möglicherweise spezifisch sein.

Bei den meisten modernen Prozessoren ist der Speicher der größte Engpass.

Aliasing: Load-Hit-Store kann in einer engen Schleife verheerend sein. Wenn Sie einen Speicherort lesen und in einen anderen schreiben und wissen, dass sie nicht zusammenhängend sind, kann das sorgfältige Einfügen eines Alias-Schlüsselworts in die Funktionsparameter dem Compiler wirklich helfen, schnelleren Code zu generieren. Wenn sich die Speicherbereiche jedoch überschneiden und Sie 'Alias' verwendet haben, steht Ihnen eine gute Debugging-Sitzung mit undefinierten Verhaltensweisen bevor!

Cache-Miss: Ich bin mir nicht sicher, wie Sie dem Compiler helfen können, da er größtenteils algorithmisch ist, aber es gibt einige Möglichkeiten, den Speicher vorab abzurufen.

Versuchen Sie auch nicht, Gleitkommawerte zu oft in int und umgekehrt zu konvertieren, da sie unterschiedliche Register verwenden. Wenn Sie von einem Typ in einen anderen konvertieren, rufen Sie den eigentlichen Konvertierungsbefehl auf, schreiben den Wert in den Speicher und lesen ihn im richtigen Registersatz zurück .

Die überwiegende Mehrheit des Codes, den die Leute schreiben, ist E / A-gebunden (ich glaube, der gesamte Code, den ich in den letzten 30 Jahren für Geld geschrieben habe, war so gebunden), daher werden die Aktivitäten des Optimierers für die meisten Leute akademisch sein.

Ich möchte die Leute jedoch daran erinnern, dass Sie den Compiler anweisen müssen, um den Code zu optimieren, damit er optimiert werden kann. Viele Leute (auch ich, wenn ich es vergesse) veröffentlichen hier C ++ - Benchmarks, die ohne Aktivierung des Optimierers bedeutungslos sind.

Verwenden Sie die Konstantenkorrektheit so oft wie möglich in Ihrem Code. Dadurch kann der Compiler viel besser optimieren.

In diesem Dokument finden Sie viele weitere Optimierungstipps: CPP-Optimierungen (ein etwas altes Dokument)

Highlights:

• Verwenden Sie Konstruktorinitialisierungslisten
• Verwenden Sie Präfixoperatoren
• Verwenden Sie explizite Konstruktoren
• Inline-Funktionen
• Vermeiden Sie temporäre Objekte
• Beachten Sie die Kosten für virtuelle Funktionen
• Objekte über Referenzparameter zurückgeben
• pro Klassenzuordnung berücksichtigen
• Betrachten Sie stl Container Allokatoren
• die Optimierung 'leeres Mitglied'
• etc

Versuchen Sie, so viel wie möglich mit statischer Einzelzuweisung zu programmieren. SSA ist genau das Gleiche wie das, was Sie in den meisten funktionalen Programmiersprachen erhalten, und genau das konvertieren die meisten Compiler Ihren Code, um ihre Optimierungen vorzunehmen, da es einfacher ist, damit zu arbeiten. Auf diese Weise werden Stellen ans Licht gebracht, an denen der Compiler verwirrt werden könnte. Außerdem funktionieren alle bis auf die schlechtesten Registerzuordnungen genauso gut wie die besten Registerzuordnungen, und Sie können einfacher debuggen, da Sie sich fast nie fragen müssen, woher eine Variable ihren Wert hat, da nur eine Stelle zugewiesen wurde.
Vermeiden Sie globale Variablen.

Wenn Sie mit Daten per Referenz oder Zeiger arbeiten, ziehen Sie diese in lokale Variablen, erledigen Sie Ihre Arbeit und kopieren Sie sie dann zurück. (es sei denn, Sie haben einen guten Grund, dies nicht zu tun)

Nutzen Sie den fast kostenlosen Vergleich mit 0, den Ihnen die meisten Prozessoren bei mathematischen oder logischen Operationen geben. Sie erhalten fast immer ein Flag für == 0 und <0, von dem Sie leicht 3 Bedingungen erhalten können:

x= f();
if(!x){
   a();
} else if (x<0){
   b();
} else {
   c();
}

ist fast immer billiger als das Testen auf andere Konstanten.

Ein weiterer Trick besteht darin, die Subtraktion zu verwenden, um einen Vergleich beim Bereichstest zu eliminieren.

#define FOO_MIN 8
#define FOO_MAX 199
int good_foo(int foo) {
    unsigned int bar = foo-FOO_MIN;
    int rc = ((FOO_MAX-FOO_MIN) < bar) ? 1 : 0;
    return rc;
} 

Dies kann sehr oft einen Sprung in Sprachen vermeiden, die boolesche Ausdrücke kurzschließen, und verhindert, dass der Compiler versuchen muss, mit dem Ergebnis des ersten Vergleichs Schritt zu halten, während er den zweiten ausführt und diese dann kombiniert. Dies mag so aussehen, als hätte es das Potenzial, ein zusätzliches Register zu verbrauchen, aber es tut es fast nie. Oft brauchst du sowieso kein Foo mehr und wenn du es tust, wird RC noch nicht verwendet, damit es dorthin gehen kann.

Wenn Sie die Zeichenfolgenfunktionen in c (strcpy, memcpy, ...) verwenden, denken Sie daran, was sie zurückgeben - das Ziel! Sie können häufig besseren Code erhalten, indem Sie Ihre Kopie des Zeigers auf das Ziel "vergessen" und ihn einfach von der Rückgabe dieser Funktionen zurückholen.

Übersehen Sie niemals die Möglichkeit, genau das zurückzugeben, was die zuletzt aufgerufene Funktion zurückgegeben hat. Compiler sind nicht so gut darin, Folgendes zu erfassen:

foo_t * make_foo(int a, int b, int c) {
        foo_t * x = malloc(sizeof(foo));
        if (!x) {
             // return NULL;
             return x; // x is NULL, already in the register used for returns, so duh
        }
        x->a= a;
        x->b = b;
        x->c = c;
        return x;
}

Natürlich können Sie die Logik in diesem Fall umkehren, wenn Sie nur einen Rückgabepunkt haben.

(Tricks, an die ich mich später erinnerte)

Es ist immer eine gute Idee, Funktionen als statisch zu deklarieren, wenn Sie können. Wenn der Compiler sich selbst beweisen kann, dass er jeden Aufrufer einer bestimmten Funktion berücksichtigt hat, kann er im Namen der Optimierung die Aufrufkonventionen für diese Funktion brechen. Compiler können häufig vermeiden, Parameter in Register oder Stapelpositionen zu verschieben, in denen aufgerufene Funktionen normalerweise erwarten, dass sich ihre Parameter befinden (dazu müssen sowohl die aufgerufene Funktion als auch die Position aller Aufrufer abweichen). Der Compiler kann auch häufig den Vorteil nutzen, zu wissen, welchen Speicher und welche Register die aufgerufene Funktion benötigt, und vermeiden, Code zu generieren, um Variablenwerte in Registern oder Speicherstellen beizubehalten, die die aufgerufene Funktion nicht stört. Dies funktioniert besonders gut, wenn nur wenige Funktionen aufgerufen werden.

Ich habe einen optimierenden C-Compiler geschrieben und hier sind einige sehr nützliche Dinge zu beachten:

1. Machen Sie die meisten Funktionen statisch. Auf diese Weise kann die interprozedurale Konstantenausbreitung und Alias-Analyse ihre Aufgabe erfüllen. Andernfalls muss der Compiler davon ausgehen, dass die Funktion von außerhalb der Übersetzungseinheit mit völlig unbekannten Werten für die Parameter aufgerufen werden kann. Wenn Sie sich die bekannten Open-Source-Bibliotheken ansehen, markieren alle Funktionen statisch, mit Ausnahme derjenigen, die wirklich extern sein müssen.

2. Wenn globale Variablen verwendet werden, markieren Sie diese nach Möglichkeit als statisch und konstant. Wenn sie einmal initialisiert werden (schreibgeschützt), ist es besser, eine Initialisierungsliste wie static const int VAL [] = {1,2,3,4} zu verwenden, da der Compiler sonst möglicherweise nicht erkennt, dass die Variablen tatsächlich initialisierte Konstanten und sind Lasten aus der Variablen können nicht durch die Konstanten ersetzt werden.

3. Verwenden Sie NIEMALS ein goto innerhalb einer Schleife, die Schleife wird von den meisten Compilern nicht mehr erkannt und es wird keine der wichtigsten Optimierungen angewendet.

4. Verwenden Sie Zeigerparameter nur bei Bedarf und markieren Sie sie nach Möglichkeit als eingeschränkt. Dies hilft der Alias-Analyse sehr, da der Programmierer garantiert, dass kein Alias ​​vorhanden ist (die interprocedurale Alias-Analyse ist normalerweise sehr primitiv). Sehr kleine Strukturobjekte sollten als Wert und nicht als Referenz übergeben werden.

5. Verwenden Sie nach Möglichkeit Arrays anstelle von Zeigern, insbesondere innerhalb von Schleifen (a [i]). Ein Array bietet normalerweise mehr Informationen für die Alias-Analyse und nach einigen Optimierungen wird ohnehin derselbe Code generiert (Suche nach Reduzierung der Schleifenstärke, wenn Sie neugierig sind). Dies erhöht auch die Wahrscheinlichkeit, dass eine schleifeninvariante Codebewegung angewendet wird.

6. Versuchen Sie, Aufrufe außerhalb der Schleife an große Funktionen oder externe Funktionen zu senden, die keine Nebenwirkungen haben (hängen Sie nicht von der aktuellen Schleifeniteration ab). Kleine Funktionen werden in vielen Fällen inline oder in Intrinsics konvertiert, die leicht zu heben sind, aber große Funktionen scheinen für den Compiler Nebenwirkungen zu haben, wenn sie dies tatsächlich nicht tun. Nebenwirkungen für externe Funktionen sind völlig unbekannt, mit Ausnahme einiger Funktionen aus der Standardbibliothek, die manchmal von einigen Compilern modelliert werden und eine schleifeninvariante Codebewegung ermöglichen.

7. Wenn Sie Tests mit mehreren Bedingungen schreiben, platzieren Sie die wahrscheinlichste zuerst. if (a || b || c) sollte if (b || a || c) sein, wenn b eher wahr ist als die anderen. Compiler wissen normalerweise nichts über die möglichen Werte der Bedingungen und welche Zweige mehr genommen werden (sie könnten anhand von Profilinformationen bekannt sein, aber nur wenige Programmierer verwenden sie).

8. Die Verwendung eines Schalters ist schneller als die Durchführung eines Tests wie if (a || b || ... || z). Überprüfen Sie zuerst, ob Ihr Compiler dies automatisch tut, einige tun es und es ist besser lesbar, das if zu haben .

Bei eingebetteten Systemen und in C / C ++ geschriebenem Code versuche ich, eine dynamische Speicherzuweisung zu vermeiden so weit wie möglich zu . Der Hauptgrund, warum ich dies tue, ist nicht unbedingt die Leistung, aber diese Faustregel hat Auswirkungen auf die Leistung.

Algorithmen, die zum Verwalten des Heaps verwendet werden, sind auf einigen Plattformen (z. B. vxworks) notorisch langsam. Schlimmer noch, die Zeit, die benötigt wird, um von einem Anruf an malloc zurückzukehren, hängt stark vom aktuellen Status des Heaps ab. Daher wird jede Funktion, die malloc aufruft, einen Leistungseinbruch erleiden, der nicht einfach zu erklären ist. Dieser Leistungseinbruch kann minimal sein, wenn der Heap noch sauber ist, aber nachdem das Gerät eine Weile ausgeführt wurde, kann der Heap fragmentiert werden. Die Anrufe werden länger dauern und Sie können nicht einfach berechnen, wie sich die Leistung im Laufe der Zeit verschlechtert. Sie können nicht wirklich eine schlechtere Fallschätzung erstellen. Der Optimierer kann Ihnen auch in diesem Fall keine Hilfe leisten. Um die Sache noch schlimmer zu machen, schlagen die Aufrufe insgesamt fehl, wenn der Heap zu stark fragmentiert wird. Die Lösung besteht darin, Speicherpools zu verwenden (z.glib Scheiben ) anstelle des Haufens. Die Zuweisungsaufrufe werden viel schneller und deterministischer, wenn Sie es richtig machen.

Ein dummer kleiner Tipp, der Ihnen jedoch mikroskopisch viel Geschwindigkeit und Code erspart.

Übergeben Sie Funktionsargumente immer in derselben Reihenfolge.

Wenn Sie f_1 (x, y, z) haben, das f_2 aufruft, deklarieren Sie f_2 als f_2 (x, y, z). Deklarieren Sie es nicht als f_2 (x, z, y).

Der Grund dafür ist, dass die C / C ++ - Plattform ABI (AKA Calling Convention) verspricht, Argumente in bestimmten Registern und Stapelpositionen zu übergeben. Wenn sich die Argumente bereits in den richtigen Registern befinden, müssen sie nicht verschoben werden.

Beim Lesen von zerlegtem Code habe ich einige lächerliche Registermischungen gesehen, weil die Leute diese Regel nicht befolgt haben.

Zwei Codiertechniken, die ich in der obigen Liste nicht gesehen habe:

Umgehen Sie den Linker, indem Sie Code als eindeutige Quelle schreiben

Während eine separate Kompilierung für die Kompilierungszeit sehr hilfreich ist, ist sie sehr schlecht, wenn Sie von Optimierung sprechen. Grundsätzlich kann der Compiler nicht über die Kompilierungseinheit hinaus optimieren, dh die vom Linker reservierte Domäne.

Wenn Sie Ihr Programm jedoch gut gestalten, können Sie es auch über eine eindeutige gemeinsame Quelle kompilieren. Das heißt, anstatt unit1.c und unit2.c zu kompilieren, verknüpfen Sie dann beide Objekte und kompilieren Sie all.c, die lediglich unit1.c und unit2.c enthalten. So profitieren Sie von allen Compiler-Optimierungen.

Es ist sehr ähnlich wie das Schreiben von Header-Programmen in C ++ (und noch einfacher in C).

Diese Technik ist einfach genug, wenn Sie Ihr Programm schreiben, um es von Anfang an zu aktivieren. Sie müssen sich jedoch auch darüber im Klaren sein, dass es einen Teil der C-Semantik ändert, und Sie können auf einige Probleme wie statische Variablen oder Makrokollisionen stoßen. Für die meisten Programme ist es einfach genug, die auftretenden kleinen Probleme zu überwinden. Beachten Sie auch, dass das Kompilieren als eindeutige Quelle viel langsamer ist und viel Speicherplatz beansprucht (normalerweise kein Problem bei modernen Systemen).

Mit dieser einfachen Technik habe ich zufällig einige Programme erstellt, die ich zehnmal schneller geschrieben habe!

Wie das Schlüsselwort register könnte auch dieser Trick bald veraltet sein. Die Optimierung durch Linker wird von den Compilern unterstützt. Gcc: Optimierung der Linkzeit .

Separate atomare Aufgaben in Schleifen

Dieser ist schwieriger. Es geht um die Interaktion zwischen dem Algorithmusdesign und der Art und Weise, wie der Optimierer die Cache- und Registerzuordnung verwaltet. Sehr oft müssen Programme eine Datenstruktur durchlaufen und für jedes Element einige Aktionen ausführen. Sehr oft können die durchgeführten Aktionen auf zwei logisch unabhängige Aufgaben aufgeteilt werden. In diesem Fall können Sie genau dasselbe Programm mit zwei Schleifen an derselben Grenze schreiben, die genau eine Aufgabe ausführen. In einigen Fällen kann das Schreiben auf diese Weise schneller sein als die eindeutige Schleife (Details sind komplexer, aber eine Erklärung kann sein, dass mit dem einfachen Task-Fall alle Variablen in Prozessorregistern gespeichert werden können und mit dem komplexeren nicht möglich sind und einige Register müssen in den Speicher geschrieben und später zurückgelesen werden, und die Kosten sind höher als bei einer zusätzlichen Flusskontrolle.

Seien Sie vorsichtig mit diesem (Profilleistungen, die diesen Trick verwenden oder nicht), da es wie die Verwendung von Register auch geringere Leistungen als verbesserte liefern kann.

Ich habe dies tatsächlich in SQLite gesehen und sie behaupten, dass es zu Leistungssteigerungen von ~ 5% führt: Fügen Sie Ihren gesamten Code in eine Datei ein oder verwenden Sie den Präprozessor, um das Äquivalent dazu zu tun. Auf diese Weise hat der Optimierer Zugriff auf das gesamte Programm und kann mehr interprozedurale Optimierungen vornehmen.

Die meisten modernen Compiler sollten gute Arbeit leisten, um die Schwanzrekursion zu beschleunigen , da die Funktionsaufrufe optimiert werden können.

Beispiel:

int fac2(int x, int cur) {
  if (x == 1) return cur;
  return fac2(x - 1, cur * x); 
}
int fac(int x) {
  return fac2(x, 1);
}

Natürlich hat dieses Beispiel keine Überprüfung der Grenzen.

Späte Bearbeitung

Ich habe zwar keine direkte Kenntnis des Codes; Es scheint klar zu sein, dass die Anforderungen für die Verwendung von CTEs unter SQL Server speziell so konzipiert wurden, dass sie über die Tail-End-Rekursion optimiert werden können.

Mach nicht immer und immer wieder die gleiche Arbeit!

Ein häufiges Antimuster, das ich sehe, geht in diese Richtung:

void Function()
{
   MySingleton::GetInstance()->GetAggregatedObject()->DoSomething();
   MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingElse();
   MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingCool();
   MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingReallyNeat();
   MySingleton::GetInstance()->GetAggregatedObject()->DoSomethingYetAgain();
}

Der Compiler muss tatsächlich ständig alle diese Funktionen aufrufen. Angenommen, Sie als Programmierer wissen, dass sich das aggregierte Objekt im Verlauf dieser Aufrufe nicht ändert, aus Liebe zu allem, was heilig ist ...

void Function()
{
   MySingleton* s = MySingleton::GetInstance();
   AggregatedObject* ao = s->GetAggregatedObject();
   ao->DoSomething();
   ao->DoSomethingElse();
   ao->DoSomethingCool();
   ao->DoSomethingReallyNeat();
   ao->DoSomethingYetAgain();
}

Im Fall des Singleton-Getter sind die Aufrufe möglicherweise nicht zu kostspielig, aber es sind sicherlich Kosten (normalerweise "Überprüfen Sie, ob das Objekt erstellt wurde, falls nicht, erstellen Sie es und geben Sie es zurück) Je komplizierter diese Kette von Gettern wird, desto mehr Zeit wird verschwendet.

1. Verwenden Sie für alle Variablendeklarationen den möglichst lokalen Bereich.

2. Verwenden Sie constwann immer möglich

3. Dont Verwendung registrieren , wenn Sie planen , sowohl zum Profil mit und ohne es

Die ersten beiden, insbesondere die erste, helfen dem Optimierer, den Code zu analysieren. Dies hilft insbesondere dabei, gute Entscheidungen darüber zu treffen, welche Variablen in Registern gespeichert werden sollen.

Die blinde Verwendung des Schlüsselworts register hilft wahrscheinlich genauso wie Ihrer Optimierung. Es ist einfach zu schwer zu wissen, worauf es ankommt, bis Sie sich die Ausgabe oder das Profil der Assembly ansehen.

Es gibt andere Dinge, die wichtig sind, um eine gute Leistung des Codes zu erzielen. Entwerfen Sie beispielsweise Ihre Datenstrukturen, um die Cache-Kohärenz zu maximieren. Aber die Frage war nach dem Optimierer.

Richten Sie Ihre Daten an nativen / natürlichen Grenzen aus.

Ich wurde an etwas erinnert, auf das ich einmal gestoßen bin, bei dem das Symptom einfach war, dass uns der Speicher ausgeht, aber das Ergebnis war eine erheblich gesteigerte Leistung (sowie eine enorme Reduzierung des Speicherbedarfs).

Das Problem in diesem Fall war, dass die von uns verwendete Software tonnenweise kleine Zuweisungen vorgenommen hat. B. vier Bytes hier, sechs Bytes dort usw. zuweisen. Viele kleine Objekte laufen ebenfalls im Bereich von 8 bis 12 Bytes. Das Problem war nicht so sehr, dass das Programm viele kleine Dinge benötigte, sondern dass es viele kleine Dinge einzeln zuordnete, wodurch jede Zuordnung auf (auf dieser speziellen Plattform) 32 Bytes aufgebläht wurde.

Ein Teil der Lösung bestand darin, einen kleinen Objektpool im Alexandrescu-Stil zusammenzustellen, ihn jedoch zu erweitern, damit ich Arrays kleiner Objekte sowie einzelne Elemente zuordnen konnte. Dies hat auch bei der Leistung immens geholfen, da mehr Elemente gleichzeitig in den Cache passen.

Der andere Teil der Lösung bestand darin, die weit verbreitete Verwendung von manuell verwalteten char * -Mitgliedern durch eine SSO-Zeichenfolge (Small-String Optimization) zu ersetzen. Bei einer Mindestzuweisung von 32 Byte habe ich eine Zeichenfolgenklasse mit einem eingebetteten 28-Zeichen-Puffer hinter einem Zeichen * erstellt, sodass 95% unserer Zeichenfolgen keine zusätzliche Zuordnung vornehmen mussten (und dann fast jedes Erscheinungsbild von manuell ersetzt habe char * in dieser Bibliothek mit dieser neuen Klasse, das hat Spaß gemacht oder nicht). Dies half auch einer Tonne bei der Speicherfragmentierung, was dann die Referenzlokalität für andere Objekte erhöhte, auf die verwiesen wurde, und in ähnlicher Weise gab es Leistungssteigerungen.

Eine nette Technik, die ich aus dem Kommentar von @MSalters zu dieser Antwort gelernt habe , ermöglicht es Compilern, eine Kopierelision durchzuführen, selbst wenn verschiedene Objekte unter bestimmten Bedingungen zurückgegeben werden:

// before
BigObject a, b;
if(condition)
  return a;
else
  return b;

// after
BigObject a, b;
if(condition)
  swap(a,b);
return a;

Wenn Sie kleine Funktionen haben, die Sie wiederholt aufrufen, habe ich in der Vergangenheit große Vorteile erzielt, indem ich sie als "statische Inline" in Header eingefügt habe. Funktionsaufrufe auf dem ix86 sind überraschend teuer.

Die nicht rekursive Neuimplementierung rekursiver Funktionen mithilfe eines expliziten Stapels kann ebenfalls viel bewirken, aber dann befinden Sie sich wirklich im Bereich von Entwicklungszeit und Gewinn.

Hier ist mein zweiter Ratschlag zur Optimierung. Wie bei meinem ersten Ratschlag ist dies ein allgemeiner Zweck, nicht sprach- oder prozessorspezifisch.

Lesen Sie das Compiler-Handbuch sorgfältig durch und verstehen Sie, was es Ihnen sagt. Verwenden Sie den Compiler bis zum Äußersten.

Ich stimme einem oder zwei der anderen Befragten zu, die festgestellt haben, dass die Auswahl des richtigen Algorithmus entscheidend für die Leistungssteigerung eines Programms ist. Darüber hinaus ist die Rendite (gemessen an der Verbesserung der Codeausführung) für die Zeit, die Sie in die Verwendung des Compilers investieren, weitaus höher als die Rendite für die Optimierung des Codes.

Ja, Compiler-Autoren stammen nicht aus einer Rasse von Codierungsriesen, und Compiler enthalten Fehler, und was laut Handbuch und Compilertheorie die Dinge schneller machen sollte, macht die Dinge manchmal langsamer. Aus diesem Grund müssen Sie Schritt für Schritt die Leistung vor und nach der Optimierung messen.

Und ja, letztendlich könnten Sie mit einer kombinatorischen Explosion von Compiler-Flags konfrontiert sein, sodass Sie ein oder zwei Skripte benötigen, um make mit verschiedenen Compiler-Flags auszuführen, die Jobs im großen Cluster in die Warteschlange zu stellen und die Laufzeitstatistiken zu erfassen. Wenn es nur Sie und Visual Studio auf einem PC sind, wird Ihnen das Interesse ausgehen, lange bevor Sie genug Kombinationen von genug Compiler-Flags ausprobiert haben.

Grüße

Kennzeichen

Wenn ich zum ersten Mal einen Code abhole, kann ich in der Regel innerhalb von a einen Faktor von 1,4 bis 2,0-mal mehr Leistung erzielen (dh die neue Version des Codes läuft in 1 / 1,4 oder 1/2 der Zeit der alten Version) Tag oder zwei durch Fummeln mit Compiler-Flags. Zugegeben, das könnte eher ein Kommentar zum Mangel an Compiler-Know-how unter den Wissenschaftlern sein, die einen Großteil des Codes, an dem ich arbeite, erstellen, als ein Symptom für meine Exzellenz. Nachdem die Compiler-Flags auf max gesetzt wurden (und es ist selten nur -O3), kann es Monate harter Arbeit dauern, bis ein weiterer Faktor von 1,05 oder 1,1 erreicht ist

Als DEC seine Alpha-Prozessoren herausbrachte, gab es eine Empfehlung, die Anzahl der Argumente für eine Funktion unter 7 zu halten, da der Compiler immer versuchen würde, automatisch bis zu 6 Argumente in Registern abzulegen.

Konzentrieren Sie sich für die Leistung zunächst auf das Schreiben von wartbarem Code - komponentenbasiert, lose gekoppelt usw. Wenn Sie also ein Teil isolieren müssen, um es neu zu schreiben, zu optimieren oder einfach nur zu profilieren, können Sie dies ohne großen Aufwand tun.

Das Optimierungsprogramm verbessert die Leistung Ihres Programms nur geringfügig.

Sie erhalten hier gute Antworten, aber sie gehen davon aus, dass Ihr Programm zunächst nahezu optimal ist, und Sie sagen

Angenommen, das Programm wurde korrekt geschrieben, mit vollständiger Optimierung kompiliert, getestet und in Produktion genommen.

Nach meiner Erfahrung kann ein Programm korrekt geschrieben sein, aber das bedeutet nicht, dass es nahezu optimal ist. Es erfordert zusätzliche Arbeit, um an diesen Punkt zu gelangen.

Wenn ich ein Beispiel geben kann, zeigt diese Antwort , wie ein vollkommen vernünftig aussehendes Programm durch Makrooptimierung über 40-mal schneller gemacht wurde . Große Beschleunigungen können nicht in jedem Fall durchgeführt werden Programm durchgeführt werden, wie es zuerst geschrieben wurde, aber in vielen (außer in sehr kleinen Programmen) kann dies meiner Erfahrung nach der .

Danach kann sich die Mikrooptimierung (der Hotspots) gut auszahlen.

Ich benutze Intel Compiler. unter Windows und Linux.

Wenn mehr oder weniger fertig, profiliere ich den Code. Halten Sie sich dann an die Hotspots und versuchen Sie, den Code zu ändern, damit der Compiler einen besseren Job macht.

Wenn ein Code rechnerisch ist und viele Schleifen enthält - der Vektorisierungsbericht im Intel-Compiler ist sehr hilfreich - suchen Sie in der Hilfe nach 'vec-report'.

Also die Hauptidee - polieren Sie den leistungskritischen Code. Was den Rest betrifft - Priorität, um korrekt und wartbar zu sein - kurze Funktionen, klarer Code, der 1 Jahr später verstanden werden konnte.

Eine Optimierung, die ich in C ++ verwendet habe, ist das Erstellen eines Konstruktors, der nichts tut. Man muss manuell init () aufrufen, um das Objekt in einen Arbeitszustand zu versetzen.

Dies hat Vorteile für den Fall, dass ich einen großen Vektor dieser Klassen benötige.

Ich rufe Reserve () auf, um den Platz für den Vektor zuzuweisen, aber der Konstruktor berührt die Speicherseite, auf der sich das Objekt befindet, nicht. Ich habe also etwas Adressraum ausgegeben, aber nicht viel physischen Speicher verbraucht. Ich vermeide die Seitenfehler, die mit den damit verbundenen Baukosten verbunden sind.

Während ich Objekte generiere, um den Vektor zu füllen, setze ich sie mit init (). Dies begrenzt meine gesamten Seitenfehler und vermeidet die Notwendigkeit, die Größe des Vektors beim Füllen zu ändern ().

Eine Sache, die ich getan habe, ist zu versuchen, teure Aktionen an Orten zu halten, an denen der Benutzer erwarten könnte, dass sich das Programm etwas verzögert. Die Gesamtleistung hängt mit der Reaktionsfähigkeit zusammen, ist jedoch nicht ganz gleich, und für viele Dinge ist die Reaktionsfähigkeit der wichtigere Teil der Leistung.

Als ich das letzte Mal wirklich Verbesserungen an der Gesamtleistung vornehmen musste, hielt ich Ausschau nach suboptimalen Algorithmen und suchte nach Stellen, an denen wahrscheinlich Cache-Probleme auftreten. Ich habe die Leistung zuerst und nach jeder Änderung profiliert und gemessen. Dann brach die Firma zusammen, aber es war trotzdem eine interessante und lehrreiche Arbeit.

Ich habe lange vermutet, aber nie bewiesen, dass das Deklarieren von Arrays, so dass sie eine Potenz von 2 als Anzahl der Elemente enthalten, es dem Optimierer ermöglicht, eine Stärke zu reduzieren, indem beim Multiplizieren ein Multiplizieren durch eine Verschiebung um eine Anzahl von Bits ersetzt wird einzelne Elemente.

Fügen Sie kleine und / oder häufig aufgerufene Funktionen oben in die Quelldatei ein. Dies erleichtert dem Compiler das Auffinden von Inlining-Möglichkeiten.