C++ massive Leistungseinbußen wegen der if-Anweisung

Question

Ich bin während While-Schleife in 4 Thread, in der Schleife bin ich Auswertung Funktion und inkrementell steigenden Zähler.

Wenn ich diese Schleife ausführen, wie ich in 4 laufenden Threads sagte, bekomme ich ~ 20 000 000 Bewertungen pro Sekunde.

Wenn ich einige zufällige Mutation für die Sequenz hinzufügen, bekomme ich ~ 13 000 000 Bewertungen pro Sekunde.

while(1) { 
    if (dist(mt) == 0) { 
     sequence[distDim(mt)] = -1; 
    } else { 
     sequence[distDim(mt)] = 1; 
    } 
    int fitness = EnergyFunction::evaluate(sequence); 

    mainMTX.lock(); 
    if(fitness < overallFitness) 
     overallFitness = fitness; 

    overallGeneration++; 
    mainMTX.unlock(); 
} 

Aber wenn ich einfach hinzufügen, wenn Anweisung, die prüft, ob neue Fitness kleiner als alte Fitness ist, wenn das wahr ist, dann alte Fitness mit neuer Fitness ersetzen.

Aber Leistungsverlust ist massiv! Jetzt bekomme ich ~ 20 000 Bewertungen pro Sekunde. Wenn ich zufällige Mutationen entferne, bekomme ich auch ~ 20 000 Bewertungen pro Sekunde.

Variable overallFitness deklariert als

extern int overallFitness; 

ich Probleme habe, herauszufinden, was das Problem für einen so großen Performance-Verlust ist. Vergleicht man zwei solche Zeitnahmeoperationen?

Auch glaube ich nicht, dass das Mutex-Verriegelung betrifft.

UPDATE

Dieser Leistungsverlust war nicht wegen der Verzweigungsvorhersage, sondern Compiler nur int fitness = EnergyFunction::evaluate(sequence); diesen Aufruf ignoriert.

Jetzt habe ich volatile hinzugefügt und Compiler ignoriert den Anruf nicht mehr.

Auch danke für das Hinweis auf Zweig Fehlvorhersage und atomic<int>, wusste nicht über sie!

Wegen der Atom ich auch Mutex Teil entfernen, so dass der endgültige Code wie folgt aussieht:

while(1) { 
    sequence[distDim(mt)] = lookup_Table[dist(mt)]; 
    fitness = EnergyFunction::evaluate(sequence); 
    if(fitness < overallFitness) 
     overallFitness = fitness; 
    ++overallGeneration; 
} 

Jetzt erhalte ich ~ 25 000 Bewertungen pro Sekunde.

Answer 1

Sie müssen einen Profiler ausführen, um auf den Grund zu kommen. Unter Linux verwenden Sie perf.

Meine Vermutung ist, dass EnergyFunction::evaluate() vollständig weg optimiert wird, weil Sie in den ersten Beispielen das Ergebnis nicht verwenden. So kann der Compiler das Ganze verwerfen.Sie können versuchen, den Rückgabewert an eine volatile Variable zu schreiben, die den Compiler oder Linker zwingen sollte, den Aufruf nicht zu optimieren. 1000fache Beschleunigung ist sicherlich nicht auf einen einfachen Vergleich zurückzuführen.

Answer 2

Es gibt tatsächlich eine atomare Anweisung, um ein int um 1 zu erhöhen. Also könnte ein intelligenter Compiler den Mutex komplett entfernen, obwohl ich überrascht wäre, wenn es so wäre. Sie können dies testen, indem Sie auf die Baugruppe schauen, oder indem Sie den Mutex entfernen und den Typ overallGeneration zu atomic<int> ändern und überprüfen, wie schnell es noch ist. Diese Optimierung ist mit Ihrem letzten, langsamen Beispiel nicht mehr möglich.

Wenn der Compiler außerdem sehen kann, dass evaluate dem globalen Status nicht entspricht und das Ergebnis nicht verwendet wird, kann der gesamte Aufruf an evaluate übersprungen werden. Sie können herausfinden, ob dies der Fall ist, indem Sie auf die Baugruppe schauen oder indem Sie den Anruf zu EnergyFunction::evaluate(sequence) entfernen und das Timing betrachten - wenn es nicht schneller wird, wurde die Funktion an erster Stelle nicht aufgerufen. Diese Optimierung ist mit Ihrem letzten, langsamen Beispiel nicht mehr möglich. Sie sollten den Compiler daran hindern können, EnergyFunction::evaluate(sequence) nicht auszuführen, indem Sie die Funktion in einer anderen Objektdatei (andere cpp oder Bibliothek) definieren und die Optimierung der Verbindungszeit deaktivieren.

Es gibt andere Effekte hier, die auch einen Leistungsunterschied erzeugen, aber ich kann keine anderen Effekte sehen, die einen Unterschied von Faktor 1000 erklären können. Ein Faktor 1000 bedeutet normalerweise, dass der Compiler im vorherigen Test und der Änderung betrogen hat verhindert, dass es schummelt.

Answer 3

Ich bin mir nicht sicher, ob meine Antwort eine Erklärung für solch einen dramatischen Leistungsabfall geben wird, aber es kann definitiv Einfluss darauf haben.

Im ersten Fall hinzugefügt Sie verzweigt in den unkritischen Bereich:

if (dist(mt) == 0) { 
    sequence[distDim(mt)] = -1; 
} else { 
    sequence[distDim(mt)] = 1; 
} 

In diesem Fall wird die CPU (mindestens IA) wird Verzweigungsvorhersage und im Fall der Niederlassung miss-Vorhersage führen dort ist eine Leistungsstrafe - das ist eine bekannte Tatsache.

nun die zweiten Zugabe in Bezug aufgenommen Sie einen Zweig zum kritischen Bereich:

mainMTX.lock(); 
if(fitness < overallFitness) 
    overallFitness = fitness; 

overallGeneration++; 
mainMTX.unlock(); 

die seinerseits, zusätzlich zu der „miss-Vorhersage“ Strafe der Menge an Code erhöht, was ist in diesem Bereich ausgeführt und damit die Wahrscheinlichkeit, dass andere Threads auf mainMTX.unlock(); warten müssen.

HINWEIS

Bitte stellen Sie sicher, dass alle global/gemeinsam genutzte Ressourcen wie volatile definiert sind. Andernfalls kann der Compiler sie optimieren (was eine so hohe Anzahl von Auswertungen zu Beginn erklären könnte).

Im Fall von overallFitness wird es wahrscheinlich nicht optimiert, weil es als extern deklariert ist, aber overallGeneration kann optimiert werden. Wenn dies der Fall ist, kann es diesen Leistungsabfall nach dem Hinzufügen des "echten" Speicherzugriffs im kritischen Bereich erklären.

NOTE2

Ich bin immer noch nicht sicher, dass die Erklärung, die ich bereitgestellt wird, kann eine solche erhebliche Leistungsabfall erklären. Also ich glaube, dass es einige Implementierungsdetails in dem Code geben könnte, den Sie nicht veröffentlicht haben (wie volatile zum Beispiel).

EDIT

Als Peter (@ Peter) Mark Lakata (@MarkLakata) in den einzelnen Antworten angegeben, und ich neige dazu, mit ihnen, wahrscheinlich zustimmen, dass der Grund für den Leistungsabfall ist, dass im ersten Fall fitness wurde nie verwendet, so dass der Compiler nur diese Variable zusammen mit dem Funktionsaufruf optimiert. Während im zweiten Fall fitness verwendet wurde, hat der Compiler es nicht optimiert. Guter Fang Peter und Mark! Ich habe diesen Punkt gerade verpasst.

Answer 4

Ich weiß, das ist nicht unbedingt eine Antwort auf die Frage, sondern eine Alternative zu dem Problem, wie es war.

Wird overallGeneration verwendet, während der Code ausgeführt wird? Das heißt, wird es vielleicht verwendet, um zu bestimmen, wann die Berechnung gestoppt werden soll? Wenn es nicht ist, können Sie auf die Synchronisierung eines globalen Zählers verzichten und einen Zähler pro Thread haben, und nachdem die Berechnung abgeschlossen ist, fassen Sie alle Zähler pro Thread auf eine Gesamtsumme zusammen. Auf ähnliche Weise können Sie für overallFitnessmaxFitness pro Thread verfolgen und das Maximum der vier Ergebnisse auswählen, sobald die Berechnung abgeschlossen ist.

Wenn Sie überhaupt keine Thread-Synchronisierung haben, erhalten Sie 100% CPU-Auslastung.