C++ / OpenMP - schnelles Verlassen einer parallelen Schleife

[Christoph G. (uranhexafluorid)]

Guten Morgen liebes Forum,

es handelt sich sicherlich nicht um ein mikrocontrollerrelevantes 
Problem, aber vielleicht hat ja doch jemand hier eine Idee dazu.
Ich habe eine Liste mit Teilchen-Koordinaten (x,y,z) aus einer 
Simulation in einem Textfile - die Reihenfolge dieser Teilchen ist 
wichtig, geht allerdings bei einigen nachfolgenden Operationen 
(Cluster-Erkennung) verloren. Soll heißen, ich habe einen vector mit 
Positionen (+ Cluster-Zuordnung) und eine Datei mit der richtigen 
Reihenfolge. Das möchte ich jetzt wieder zusammenbringen.
Also lese ich Zeilenweise die Datei, suche den Eintrag im vector, 
schreibe die Clusternummer in die Datei und eliminiere den Eintrag aus 
dem vector.
Das dauert mit einem Kern bei etwa 8 Millionen Einträgen ca. 14 Stunden 
- was doof ist, da das Ziel eher 100 Mio. Teilchen sind und die 
Komplexität des Problems ungefähr quadratisch wächst.
Das Durchsuchen des vectors habe ich jetzt mit OpenMP parallelisiert, 
wobei die Möglichkeit die Schleife nach Auffinden des Teilchens mittels 
break (oder goto) zu verlassen entfällt. Standardlösung aus dem Netz ist 
ein flag zu setzen und dieses dann in der Schleife abzufragen (mehrere 
Bedingungen im Schleifenkopf mag OpenMP irgendwie auch nicht).
Naja, das brachte zwar schon einen erheblichen Geschwindigkeitszuwachs, 
jedoch gehen jetzt mehr als die Hälfte der Gesamtzeit (laut valgrind) 
für das Abfragen des flag-checks drauf.
Ich habe jetzt testweise mal, sobald das flag gesetzt ist, den 
Schleifenlaufparameter i auf die Abbruchbedingung gesetzt. Das bringt 
tatsächlich nochmal einen Faktor zwei. Aber ich habe diese Lösung weder 
im Netz irgendwo gefunden (obwohl sie recht einfach ist), noch erscheint 
sie mir besonders elegant.
Daher meine beiden Fragen:
Gibt es an der Lösung etwas auszusetzen?
Gibt es eine schönere Methode die Schleifen zu beenden?

Sorry für den vielen Text, und danke schonmal für die Kommentare!

Viele Grüße,
Christoph

PS: Nun endlich der Code:
fin, fout sind fstreams; vec ein std::vector mit structs mit x,y,z und l

int x,y,z;
while(!fin.eof()){
  fin >> x; fin >> y; fin >> z;
  bool flag = true;
  int vec_size = vec.size();

#pragma omp parallel for shared(flag) schedule(dynamic, 10000)
  for(int i = 0; i < vec_size; i++){
    if(flag){
      if(vec[i].x == x && vec[i].y == y && vec[i].z == z){
        fout << x << " " << y << " " << z << " " << vec[i].l << "\n";
        vec[i] = vec[vec_size-1];
        vec.pop_back();
        flag = false;
      }
    }
    else i = vec_size;
  }
}

PPS: Ich nehme auch gerne Vorschläge für andere Methoden das zu 
erreichen!

[ffff (Gast)]

blöde frage: anstatt nach der Bearbeitung wieder zu sortieren, warum 
nicht während der Bearbeitung die eigentliche Position merken?
Also einfach eine Klasse mit 2 Attributen(Position innerhalb des 
TXT-Files und die Koordinaten), ein paar Funktionen überschreiben(magic 
members) und dann die Cluster-Berechnungen machen?!

[Peter II (Gast)]

Christoph G. schrieb:
> PPS: Ich nehme auch gerne Vorschläge für andere Methoden das zu
> erreichen!

8Millonen Einträge und dafür brauchst du 14Stunden? Was ist das für ein 
PC?

das macht dir jede Datenbank in weniger als einer Stunde.

Du musst die Daten vorher Sortiern (indizieren). Was ist vec[i].x für 
ein Datentype? Das einfachste ist ein wert der x,y,z zu berechnen der 
eindeutig ist. Diese legst du ihn in einer sortierten liste wie std::map 
ab, dann kann du extrem schnell darauf zugreifen. Braucht halt genug 
ram, sonnst müsste man sich selber etwas einfallen lasse.

Wenn du die Daten eh in einer Datenbank verwalten kannst, würde ich es 
gleich dort machen.

Gefühlt würde ich sagen, ein aktueller PC schafft das in unter 10min.

[Dr. Sommer (Gast)]

Generell ist es besser, Informationen nicht verloren gehen zu lassen 
(deine Reihenfolge) als sie nachträglich neu zu berechnen. Wie wäre es 
damit, am Anfang einen Vektor in der Größe der Teilchen Anzahl anzulegen 
und mit 0,1,2,... zu füllen, und jedes mal die Elemente i und j zu 
tauschen, wenn i und j im Teilchen Vektor getauscht werden? Das ist O(1) 
und dann hast du die Reihenfolge immehr direkt parat ohne irgendwas 
berechnen/suchen zu müssen.

Generell kann man natürlich sagen dass einzelne Text Zahlen im 
Schleifendurchlauf zu lesen langsam ist. Besser ist es die Datei am 
Anfang einmal in ein Binärformat zu konvertieren, und immer zB 1024 
Koordinaten einmal zu lesen. Außerdem gibt es schlaueren Datenstrukuren 
wie Octrees die räumliches suchen viel schneller können als ein Vektor 
mit linearer Suchen. vec_size sollte übrigens ein size_t sein und kein 
int.

[Matthias H. (hallamen)]

Falls man die Position nicht mitnehmen kann, wie bereits angedeutet, 
kann folgendes funktionieren (genug Ram vorausgesetzt):

Lies die ganze Datei ein und verpass jedem Punkt eine zusätzliche 
Koordinate (= Position in der Datei)
Sortiere sowohl diese Daten, als auch die vom Clustering -> Aufwand 
2*n*log(n)
Danach kannst in einer Iteration die Punkte vergleichen und in einer 
Bitmask die vorkommenden speichern.
Wieder zurücksortieren (unter verwendung der Zusätzlichen Koordinate) 
und rausschreiben.

Speicherbedarf bei 10^8 Partikel: ca. 3.4 GB

Generell ist es besser, vor dem Parallelisieren den algorithmischen 
Aufwand zu hinterfragen. Das bringt meistens mehr und ist einfacher zu 
debuggen :)

[Christoph G. (uranhexafluorid)]

Die Teilchenreihenfolge währende der Clustererkennung zu erhalten geht 
leider aufgrund des Algorithmus' nicht. Die Teilchen werden erst in ein 
Gitter übertragen und dann werden iterativ, aber parallel die Cluster 
gewonnen - ich geh jetzt mal nicht in die Details... (Ist ne ganz blöde 
fraktale Anordnung, den leeren Raum zwischen den Teilchen brauch ich für 
die Erkennung auch, daher frisst die ganze Aktion Massen an RAM, obwohl 
ich das Gitter mit einem vector<bool> (nicht schlagen bitte!) bilde. 
Octrees sind hierbei auch nicht wirklich hilfreich.)

Das zeilenweise Einlesen der Datei geht im Vergleich zum Rest schnell 
genug - gefühlt eine Sekunde wenn ichs am Stück mache.

x,y,z und l sind int.
Mit Datenbanken selbst habe ich wenig Erfahrung, aber selbst wenn ich 
aus den x,y,z Werten eine eindeutige Kennung errechne (ist kein 
Problem), geht es so schnell eine Liste mit 100 Mio. Einträgen zu 
sortieren?

Das mit der std::map gefällt mir aber, sollte tatsächlich erheblich 
schneller sein.

Danke euch allen für eure Anregungen!

Heut komm ich da wahrscheinlich nicht zu - aber ich zeig' euch bei 
Gelegenheit mal was rausgekommen ist.

Danke nochmal!

Viele Grüße,
Christoph

[Martin (Gast)]

Hi,

Ich glaube erst einmal nicht, dass mehr als die Hälfte der Rechenzeit 
für die Abfrage des Flags drauf geht. Ich glaube eher, dass valgrind die 
genaue Position der Überprüfung im Code nicht wieder erkennt (z.B. durch 
Compiler Optimierungen) und die Angabe falsch ist.

Gruß Martin

[Christoph G. (uranhexafluorid)]

Fürs valgrind bin ich zugegebenermaßen auf -O1 zurückgegangen. Da aber 
die else-Zeile die Ausführungszeit etwa halbiert, dürfte das schon 
ungefähr passen.
Die Teilchen sind nach der Erkennung auch nicht gleichverteilt 
zerstreut, sondern die ungefähre Position bleibt erhalten. D.h. meist 
wird der Treffer recht früh in der Schleife erfolgen - daher eben auch 
die ursprüngliche Frage.

[Peter II (Gast)]

Christoph G. schrieb:
> Das mit der std::map gefällt mir aber, sollte tatsächlich erheblich
> schneller sein.

was ist schneller, mit 1000 Leuten in einem unsortierten Telefonbuch 
einen Eintrag zu suchen oder mit 1 Person in einem normalen Telefonbuch?

[ergo (Gast)]

Mit OpenMP 4 ginge #pragma omp cancel.

Ansonsten ist flag shared, das ist schon mal eine teurer Zugriff. Und 
flushen nicht vergessen:

http://www.thinkingparallel.com/2007/06/29/breaking-out-of-loops-in-openmp/

Aus dem Bauch heraus würde ich aber tippen, daß Dir der dauernde Disk 
I/O in der Schleife mehr Performance kostet als das Flag. Was passiert, 
wenn Du das fout mal probeweise weglässt?

Und das hier:

vec.pop_back();

ist IMHO nicht thread safe. Das ist nämlich eine Schreiboperation und 
für sowas mag ein std::vector nur einen Writer. Also #pragma omp 
critical drumherum oder anders lösen.

[Christoph G. (uranhexafluorid)]

Oha, 'omp cancel' hab ich übersehen. Danke!

Die Schreiboperationen weglassen bringt keinen messbaren 
Geschwindigkeitsvorteil, ebensowenig wie das flag nicht shared zu machen 
und stattdessen zu flushen.

pop_back() selbst ist thread safe. Was passieren kann ist, dass das 
letzte chunk bzw. die letzte Teilschleife versucht auf das letzte Objekt 
zuzugreifen, welches aber schon von einem anderen thread gelöscht (um 
nicht zu sagen 'gepoppt') wurde.
Das lässt sich aber mit einer critical section auch nicht so einfach 
umgehen.
Wenn man das pop_back() aber hinter die for-Schleife setzt sollte es 
passen.
Danke für den Hinweis!

[Peter II (Gast)]

Christoph G. schrieb:
> Die Schreiboperationen weglassen bringt keinen messbaren
> Geschwindigkeitsvorteil, ebensowenig wie das flag nicht shared zu machen
> und stattdessen zu flushen.

Teste doch mal mit der map. Es macht keine sinn mit openMP 
rumzuoptimieren, wenn schon der gesamte Ansatz falsch ist.

wenn du für vec einen Vergleichsoperator schreibst, kann du deine 
stuct/klasse direkt in dem map hängen. Das sollte in 30min doch zu 
schaffen sein.

[Christoph G. (uranhexafluorid)]

Peter II schrieb:
> Teste doch mal mit der map.

Hetz mich nicht!

[Jay (Gast)]

Also sehe ich das richtig:

Du hast einen vector mit 14 Millionen Einträgen.

Du hast eine Datei mit 14 Millionen Datensätzen.

Für jeden Datensatz durchsucht du den vector nach dem korrespondierenden 
Eintrag. D.h. lineares Suchen :-(

Nach jeder Suche wird der gefundene Eintrag aus dem vector entfernt.

Richtig?


Das bedeutet, du hast (wenn ich mich nicht auf die Schnelle verrechnet 
habe) im Durchschnitt grob (N^2 - N)/2 ~= 1 * 10^14 Durchläufe der 
inneren Schleife.

Junge, Junge, Junge. Ja, die 14 Stunden Laufzeit glaube ich dir.

Die Anzahl der Durchläufe für 100 Millionen Daten wären sportliche 50 * 
10^14, also rund das 50-Fache. Aus 14 Stunden würden (unter gewissen 
Annahmen, siehe unten), ein gepflegter Monat!

Anders ausgedrückt, willst du weiter bei 14 Stunden bleiben, und unter 
der mutigen Annahme, dass die Zugriffszeiten auf die Datensätze und den 
vector konstant und unabhängig von der Datenmenge sind, dann musst du 
deinen jetzigen Algorithmus um den Faktor 50 beschleunigen. Oh je.

Also, für mich wären die Zahlen ein klarer Hinweis mal sehr zügig über 
einen anderen Algorithmus nachzudenken, statt an dem vorhandenen zu 
basteln.

[Christoph G. (uranhexafluorid)]

Gut das ich nicht im ersten Post schon geschrieben hab, dass die 
Komplexität des Algorithmus quadratisch mit der Anzahl der Einträge 
wächst - oh, Moment...

Wer mir als nächstes vorschlägt, ich soll einen anderen Weg suchen, dem 
beiß ich den Kopf ab!

Den Weg mit der map schreib ich heut Abend zusammen - bin schließlich 
kein Programmierer und hab noch was anderes zu tun.

Btw. der parallele Code von oben läuft in unter einer Stunde auf einem 
i8 Sechskerner.

[Peter II (Gast)]

Christoph G. schrieb:
> Btw. der parallele Code von oben läuft in unter einer Stunde auf einem
> i8 Sechskerner.

auf einem BMW-I8? Das der so schnell ist wusste ich gar nicht.

[Christoph G. (uranhexafluorid)]

Verdammt!  i7 natürlich ^^

[Karl H. (kbuchegg)]

Christoph G. schrieb:
> Gut das ich nicht im ersten Post schon geschrieben hab, dass die
> Komplexität des Algorithmus quadratisch mit der Anzahl der Einträge
> wächst - oh, Moment...

Und genau das hätte dich bei deiner Datenmenge schon stutzig machen 
müssen.

> Wer mir als nächstes vorschlägt, ich soll einen anderen Weg suchen, dem
> beiß ich den Kopf ab!


Es ist aber der einzig vernünftige Weg.

> Den Weg mit der map schreib ich heut Abend zusammen - bin schließlich
> kein Programmierer

Und genau da haben wir den Salat. Ein gelernter Informatiker hätte von 
vorne herein bei dieser Datenmenge nicht auf lineares Suchen gesetzt. 
Das mindeste wäre gewesen, die Daten zumindest in X Richtung zu 
sortieren und dann mit binärer Suche in logarithmischer Komplexität 
zumindest mal den Bereich auf dem File ansteuern in dem schon mal 80% 
aller anderen Daten nicht untersucht werden müssen. Mal ganz davon 
abgesehen, dass man dazu selbstverständlich kein Textfile nimmt, sondern 
ein Record-basiertes Files, in dem man jeden Record wahlfrei ansteuern 
kann.

> Btw. der parallele Code von oben läuft in unter einer Stunde auf einem i8 
Sechskerner.

Und?
Mit einer ordentlichen Wahl des Algorithmuses kommt man locker in den 
Minutenbereich. Und das auf 1 Kern.

Kurz und gut: Du hast so ziemlich alles falsch gemacht, was man nur 
falsch machen kann. Jetzt stehst du vor den Trümmern und hoffst, dass 
mehr Prozessoren  das alles noch richten werden. Irgendwie.
Das hat eigentlich noch nie wirklich funktioniert.

PS: mal ganz davon abgesehen, dass ein gelernter Informatiker auch nicht 
davor zurückschrecken würde, die Datenstruktur des Clusteralgorithmuses 
so zu pimpen, dass er bei jedem Teilchen noch eine Userdata 
durchschleift, in der er sich dann die Rückreferenz zu den Originaldaten 
reinlegt. Denn das hier ...
> Die Teilchenreihenfolge währende der Clustererkennung zu erhalten
> geht leider aufgrund des Algorithmus' nicht. Die Teilchen werden erst
> in ein Gitter übertragen und dann werden iterativ, aber parallel
> die Cluster gewonnen

... ist kein Argument.

[Christoph G. (uranhexafluorid)]

Karl Heinz schrieb:
>> Wer mir als nächstes vorschlägt, ich soll einen anderen Weg suchen, dem
>> beiß ich den Kopf ab!
>
> Es ist aber der einzig vernünftige Weg.

Evtl. war mein Sarkasmus hier etwas zu subtil...
Da mir bereits 5 mal vorgeschlagen wurde einen anderen Weg zu suchen und 
ich bereits schrieb, dass ich das auch tun werde, hielt ich erneute 
Hinweise in die Richtung für überflüssig.
Sei's drum - ihr wollt mir ja helfen und dafür bin ich dankbar.

Also, der Hinweis mit der std::map war ein Volltreffer.
Habe die unegordnete Liste erstmal in eine Datei ausgelagert (muss 
sowieso auch alte Simulationen einlesen können) und les sie jetzt in 
eine map ein, wobei ich aus den Positionen eine eindeutige Kennung 
errechne. Dann lese ich die geordnete Datei und suche die Einträge aus 
der map und speichere wieder ab.
Die Zeit zum Einlesen der ca. 8 Mio. Einträge in die map sind 11 
Sekunden, das wieder abspeichern dann 16 Sekunden, wobei hier 
wahrscheinlich ein bedeutender Teil für die Dateioperationen drauf geht. 
Also Ausführzeit von ner knappen Stunde auf 30 Sekunden verringert und 
die Komplexität ist auch nur noch linearithmisch (gibt's das Wort im 
Deutschen?).

Danke euch!

Hier die beiden Code-Schnipsel:
fin ist die Datei mit den ungeordneten Partikeln. width und depth sind 
die Seitenlängen aus der ursprünglichen Simulation.

std::map<long,int> map_order;
while(!fin.eof()){
  fin >> x; fin >> y; fin >> z; fin >> clu;
  map_order.emplace(width * depth * z + width * y + x, clu);
}

fin ist jetzt die geordnete Datei, fout der finale Output - ist 
natürlich überflüssig hier eine neue Datei anzulegen...

while(!fin.eof()){
  fin >> x; fin >> y; fin >> z;
  fout << x << " " << y << " " << z << " " << map_order[width * depth * z + width * y + x] << "\n";
}

EDIT: Huch, Formatierung vermurkst - arbeite dran... done.

[Peter II (Gast)]

Christoph G. schrieb:
> Die Zeit zum Einlesen der ca. 8 Mio. Einträge in die map sind 11
> Sekunden, das wieder abspeichern dann 16 Sekunden, wobei hier
> wahrscheinlich ein bedeutender Teil für die Dateioperationen drauf geht.
> Also Ausführzeit von ner knappen Stunde auf 30 Sekunden verringert und
> die Komplexität ist auch nur noch linearithmisch (gibt's das Wort im
> Deutschen?).


was waren denn die
> Das dauert mit einem Kern bei etwa 8 Millionen Einträgen ca. 14 Stunden

wenn es 6 Kerne sind, hätte es doch immer noch mindestens 2 stunden 
gedauert?

die 30Sekunden sind sogar nur auf einen Kern, das kannst du ja immer 
noch Verteilen. Wenn du die map nicht änderst, gibt es auch keine 
sperren zu beachten. Du könntest die Daten binär ablegen das spart auch 
noch mal etwas zeit.

[Christoph G. (uranhexafluorid)]

Ja, ich glaube bei der 14 Stunden-Version hatte ich die gefundenen 
Elemente noch nicht aus dem vector gelöscht.
Außerdem: Hyper-Threading.

Weiter optimieren werde ich das jetzt nicht - es löst das Problem in 
wirklich erträglicher Zeit und ich hab noch mehr zu tun.

Trotzdem: Nochmal danke!

[Mark B. (markbrandis)]

ergo schrieb:
> Aus dem Bauch heraus würde ich aber tippen, daß Dir der dauernde Disk
> I/O in der Schleife mehr Performance kostet als das Flag. Was passiert,
> wenn Du das fout mal probeweise weglässt?

Christoph G. schrieb:
> Die Schreiboperationen weglassen bringt keinen messbaren
> Geschwindigkeitsvorteil

Das kann ich mir eigentlich nur dann vorstellen, wenn die Disk I/O 
Operationen im Cache landen und womöglich erst nach Ablauf der Schleife 
tatsächlich endgültig durchgeführt werden.

Zugriff auf Festplatte dauert immer deutlich länger als Zugriff auf den 
Hauptspeicher. Selbst bei einer SSD sollte da noch locker eine 
Größenordnung im Vergleich zu DDR3-SDRAM dazwischen liegen, also etwa 
Faktor 10.

Wenn irgend möglich, würde ich:
1.) Die zu verarbeitenden Daten komplett in den Hauptspeicher einlesen
2.) Alle Operationen im Hauptspeicher durchführen
3.) Erst wenn das fertige Ergebnis im Hauptspeicher vorliegt, dann auf 
SSD oder Harddisk schreiben.

[Christoph G. (uranhexafluorid)]

Das Schreiben über den filestream ist sowieso gepuffert.
Und die beiden Dateien lese ich genau einmal ein - die erste in die map 
und die zweite verarbeite ich gleich, also viel dürfte da nicht mehr 
rauszuholen sein.

Wir reden jetzt über Einsparungen von ein paar Sekunden, bei einer 
Funktion die ich - wenns hoch kommt - zwei mal die Woche aufrufen werde.

Für mich ist das Problem gelöst.
Falls jemand natürlich noch eine komplett andere Herangehensweise hat, 
sehe ich sie mir schon aus Interesse natürlich gern an.