Ich habe 2 Spalten mit durch Tabulatoren getrennten Ganzzahlen, von denen die erste eine zufällige Ganzzahl und die zweite eine Ganzzahl ist, die die Gruppe identifiziert, die von diesem Programm generiert werden kann. ( generate_groups.cc)
#include <cstdlib>
#include <iostream>
#include <ctime>
int main(int argc, char* argv[]) {
int num_values = atoi(argv[1]);
int num_groups = atoi(argv[2]);
int group_size = num_values / num_groups;
int group = -1;
std::srand(42);
for (int i = 0; i < num_values; ++i) {
if (i % group_size == 0) {
++group;
}
std::cout << std::rand() << '\t' << group << '\n';
}
return 0;
}Ich benutze dann ein zweites Programm ( sum_groups.cc), um die Summen pro Gruppe zu berechnen.
#include <iostream>
#include <chrono>
#include <vector>
// This is the function whose performance I am interested in
void grouped_sum(int* p_x, int *p_g, int n, int* p_out) {
for (size_t i = 0; i < n; ++i) {
p_out[p_g[i]] += p_x[i];
}
}
int main() {
std::vector<int> values;
std::vector<int> groups;
std::vector<int> sums;
int n_groups = 0;
// Read in the values and calculate the max number of groups
while(std::cin) {
int value, group;
std::cin >> value >> group;
values.push_back(value);
groups.push_back(group);
if (group > n_groups) {
n_groups = group;
}
}
sums.resize(n_groups);
// Time grouped sums
std::chrono::system_clock::time_point start = std::chrono::system_clock::now();
for (int i = 0; i < 10; ++i) {
grouped_sum(values.data(), groups.data(), values.size(), sums.data());
}
std::chrono::system_clock::time_point end = std::chrono::system_clock::now();
std::cout << (end - start).count() << std::endl;
return 0;
}Wenn ich diese Programme dann auf einem Datensatz einer bestimmten Größe ausführe und dann die Reihenfolge der Zeilen desselben Datensatzes mische, berechnen die gemischten Daten die Summen ~ 2x oder schneller als die geordneten Daten.
g++ -O3 generate_groups.cc -o generate_groups
g++ -O3 sum_groups.cc -o sum_groups
generate_groups 1000000 100 > groups
shuf groups > groups2
sum_groups < groups
sum_groups < groups2
sum_groups < groups2
sum_groups < groups
20784
8854
8220
21006Ich hätte erwartet, dass die Originaldaten, die nach Gruppen sortiert sind, eine bessere Datenlokalität haben und schneller sind, aber ich beobachte das entgegengesetzte Verhalten. Ich habe mich gefragt, ob jemand den Grund vermuten kann.
quelle
.at()oder einen Debug-Modusoperator[], der Grenzen setzt Überprüfen Sie, was Sie sehen würden.sum. Anstatt dasssums.reserve(n_groups);Sie anrufen müssensums.resize(n_groups);- das hat @Shawn angedeutet.p_out[p_g[i]] += p_x[i];. Möglicherweise weisen die Gruppen in der ursprünglichen verschlüsselten Reihenfolge tatsächlich eine gute Clusterbildung hinsichtlich des Zugriffs auf dasp_outArray auf. Das Sortieren der Werte kann zu einem schlechten gruppenindizierten Zugriffsmuster führenp_out.Antworten:
Setup / mach es langsam
Erstens läuft das Programm ungefähr zur gleichen Zeit, unabhängig davon:
Die meiste Zeit wird in der Eingangsschleife verbracht. Aber da wir an der interessiert sind
grouped_sum(), lassen Sie uns das ignorieren.Wenn Sie die Benchmark-Schleife von 10 auf 1000 Iterationen ändern, wird
grouped_sum()die Laufzeit dominiert:perf diff
Jetzt können wir
perfdie heißesten Stellen in unserem Programm finden.Und der Unterschied zwischen ihnen:
Mehr Zeit in
main(), was sich wahrscheinlichgrouped_sum()eingefügt hat. Großartig, vielen Dank, perf.perf annotieren
Gibt es einen Unterschied, wo die Zeit drinnen verbracht wird
main()?Gemischt:
Sortiert:
Nein, es dominieren die gleichen zwei Anweisungen. Sie dauern also in beiden Fällen lange, sind aber noch schlimmer, wenn die Daten sortiert werden.
perf stat
Okay. Wir sollten sie jedoch gleich oft ausführen, daher muss jede Anweisung aus irgendeinem Grund langsamer werden. Mal sehen, was
perf statsagt.Nur eines fällt auf: Stalled-Cycles-Frontend .
Okay, die Anweisungspipeline blockiert. Im Frontend. Was genau das bedeutet, variiert wahrscheinlich zwischen den Mikroarchitekturen.
Ich habe allerdings eine Vermutung. Wenn Sie großzügig sind, können Sie es sogar eine Hypothese nennen.
Hypothese
Durch Sortieren der Eingabe erhöhen Sie die Lokalität der Schreibvorgänge. In der Tat werden sie sehr lokal sein; Fast alle Ergänzungen, die Sie vornehmen, werden an dieselbe Stelle wie die vorherige geschrieben.
Das ist großartig für den Cache, aber nicht großartig für die Pipeline. Sie führen Datenabhängigkeiten ein und verhindern, dass die nächste Additionsanweisung fortgesetzt wird, bis die vorherige Addition abgeschlossen ist (oder das Ergebnis auf andere Weise für nachfolgende Anweisungen verfügbar gemacht hat ).
Das ist dein Problem.
Ich glaube.
Es reparieren
Mehrere Summenvektoren
Versuchen wir mal etwas. Was wäre, wenn wir mehrere Summenvektoren verwenden würden, bei jeder Addition zwischen ihnen wechseln und diese am Ende zusammenfassen würden? Es kostet uns ein wenig Lokalität, sollte aber die Datenabhängigkeiten beseitigen.
(Der Code ist nicht schön; verurteile mich nicht, Internet !!)
(Oh, und ich habe auch die Berechnung für n_groups korrigiert; sie war um eins verschoben.)
Ergebnisse
Nachdem ich mein Makefile so konfiguriert habe, dass
-DNSUMS=...es dem Compiler ein Argument gibt, kann ich Folgendes tun:Die optimale Anzahl von Summenvektoren hängt wahrscheinlich von der Pipeline-Tiefe Ihrer CPU ab. Meine 7 Jahre alte Ultrabook-CPU kann die Pipeline wahrscheinlich mit weniger Vektoren maximieren, als eine neue schicke Desktop-CPU benötigen würde.
Mehr ist natürlich nicht unbedingt besser. Als ich mit 128 Summenvektoren verrückt wurde, litten wir mehr unter Cache-Fehlern - was sich daran zeigt, dass die gemischte Eingabe langsamer als sortiert wurde, wie Sie es ursprünglich erwartet hatten. Wir haben den Kreis geschlossen! :) :)
Summe pro Gruppe im Register
(Dies wurde in einer Bearbeitung hinzugefügt)
Agh, Nerd hat geschnippt ! Wenn Sie wissen, dass Ihre Eingabe sortiert wird und Sie nach noch mehr Leistung suchen, ist das folgende Umschreiben der Funktion (ohne zusätzliche Summenarrays) zumindest auf meinem Computer noch schneller.
Der Trick in diesem Fall besteht darin, dass der Compiler die
gsumVariable, die Summe der Gruppe, in einem Register speichern kann. Ich vermute (kann aber sehr falsch sein), dass dies schneller ist, da die Rückkopplungsschleife in der Pipeline hier kürzer sein kann und / oder weniger Speicherzugriffe. Ein guter Branchenprädiktor macht die zusätzliche Überprüfung der Gruppengleichheit billig.Ergebnisse
Es ist schrecklich für gemischte Eingaben ...
... ist aber rund 40% schneller als meine "viele Summen" -Lösung für sortierte Eingaben.
Viele kleine Gruppen sind langsamer als einige große. Ob dies die schnellere Implementierung ist oder nicht, hängt also wirklich von Ihren Daten ab. Und wie immer auf Ihrem CPU-Modell.
Vektoren mit mehreren Summen, mit Versatz anstelle von Bitmaskierung
Sopel schlug vier abgewickelte Ergänzungen als Alternative zu meinem Bitmaskierungsansatz vor. Ich habe eine verallgemeinerte Version ihres Vorschlags implementiert, die unterschiedlich umgehen kann
NSUMS. Ich zähle darauf, dass der Compiler die innere Schleife für uns abwickelt (was zumindest für ihn der Fall warNSUMS=4).Ergebnisse
Zeit zu messen. Beachten Sie, dass ich, seit ich gestern in / tmp gearbeitet habe, nicht genau die gleichen Eingabedaten habe. Daher sind diese Ergebnisse nicht direkt mit den vorherigen vergleichbar (aber wahrscheinlich nahe genug).
Ja, die innere Schleife mit
NSUMS=8ist die schnellste auf meinem Computer. Im Vergleich zu meinem "lokalen Gsum" -Ansatz hat es auch den zusätzlichen Vorteil, dass es für die gemischte Eingabe nicht schrecklich wird.Interessant zu bemerken:
NSUMS=16wird schlimmer alsNSUMS=8. Dies kann daran liegen, dass immer mehr Cache-Fehler auftreten oder dass wir nicht über genügend Register verfügen, um die innere Schleife ordnungsgemäß abzuwickeln.quelle
perf.Hier ist der Grund, warum sortierte Gruppen langsamer sind als nicht gespeicherte Gruppen.
Hier ist zunächst der Assembler-Code für die Summierungsschleife:
Schauen wir uns die Add-Anweisung an, die der Hauptgrund für dieses Problem ist.
Wenn der Prozessor diesen Befehl zuerst ausführt, gibt er eine Speicherleseanforderung (Ladeanforderung) an die Adresse in edx aus, addiert dann den Wert von ecx und gibt dann eine Schreibanforderung (Speicheranforderung) für dieselbe Adresse aus.
Es gibt eine Funktion bei der Neuordnung des Prozessoraufrufspeichers
und es gibt eine Regel
Wenn also die nächste Iteration die Add-Anweisung erreicht, bevor die Schreibanforderung abgeschlossen ist, wartet sie nicht, wenn sich die EDX-Adresse vom vorherigen Wert unterscheidet, und gibt die Leseanforderung aus. Sie wird über die ältere Schreibanforderung neu angeordnet, und die Add-Anweisung wird fortgesetzt. Wenn die Adresse jedoch dieselbe ist, wartet der Befehl add, bis der alte Schreibvorgang abgeschlossen ist.
Beachten Sie, dass die Schleife kurz ist und der Prozessor sie schneller ausführen kann, als der Speichercontroller die Anforderung zum Schreiben in den Speicher abgeschlossen hat.
Bei sortierten Gruppen lesen und schreiben Sie daher viele Male hintereinander von derselben Adresse, sodass die Leistungssteigerung durch Neuordnung des Speichers verloren geht. Wenn zufällige Gruppen verwendet werden, hat jede Iteration wahrscheinlich eine andere Adresse, sodass der Lesevorgang nicht auf älteres Schreiben wartet und vorbestellt wird. Die Anweisung zum Hinzufügen wartet nicht auf die vorherige Anweisung.
quelle