Bottlenecks Praktikum4

neoatlant
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 14. Okt 2010 22:16

Bottlenecks Praktikum4

Beitrag von neoatlant » 18. Jan 2012 00:50

Hallo,

Es gab beim letzten Mal offensichtlich Leute die auf viel bessere Lsg, als andere gekommen sind
da ich einer von denen war die es nicht schaffen konnten die Laufzeit unter 50 sek zu unterdücken
wäre ich den leuten dankbar die es geschafft hatten, vielleicht mal ihr Geheimnisse jetzt zu
veröffentlichen :), Das wäre sehr nett für uns threads Amateure ;)

Vielen Dank im Voraus

x539
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 24. Nov 2010 15:52

Re: Bottlenecks Praktikum4

Beitrag von x539 » 18. Jan 2012 11:46

Also, bei einer 50sec Lösung wirst man bei 24 Threads eine verdammt hohe SystemZeit gemessen haben (bei mir waren es über 10 Min).

Wenn man sich jetzt mal überlegt was das Kernel alles so für Aufgaben hat: Speicher-Reservieren, Dateien Lesen, etc. kommst man zu dem Schluss,
das außer zu Beginn zum lesen der obj-Datei und zum reservieren von etwas Speicher(einmalig) keine Zeit im Kernel verbracht werden muss. Alles über 1sec Ist hier also überflüssig.

Mit 'strace' lessen sich die Kernel-Aufrufe eines Programms mitloggen, und man sieht verdammt viele FUTEX-Syscalls (fürs locking). Meine Queue scheint aber nicht einmal so ein FUTEX ausgelöst zu haben, das habe ich mit try_lock getestet, und auch eine in asm geschribene locking-Funktion(garantiert ohne FUTEX) hat keine Besserung gebracht.

Durch das Durchscrollen von 'objdump -C -d Praktikum4' (statisch gelinkt) ist mir dann aufgefallen das rand() locking benutzt.
Also habe ich alle rand() durch eine eigenes tRand() ersetzt das eigentlich nur rand_r() mit einem thread-locale seed aufruft.
Und schon waren es 24sec.

Noch ein bisschen weiter gesucht ist mir aufgefallen, das die beiden intersect methoden relativ oft new aufrufen zuscheinen. Da new zentral den Gesammten speicher verwaltet muss hier auch locking im spiel sein. Also habe ich den std::stack iterationStack (oder so) durch einen std::vertor ersetzt von dem ich weiß, dass es beim reserviern von speicher sehr großzügig ist, und so nur selten neuen speicher reservieren muss.
Das gab noch mal einen Schub nach vorne, dann habe ich den iterationStack der bei jedem aufruf neu angelegt wird duch einen festen pro thread ersetzt.

Zu guter letzt noch alles in die pr4.cpp gepackt (alle cpp dateien included) und die CMake.txt angepasst.
Time liefert:
real 0m9.287s
user 1m38.080s
sys 0m0.094s << Keine 10 Minuten mehr ;)
„Reality is that which, when you stop believing in it, doesn't go away.“ Philip K. Dick

Thomas Huxhorn
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 171
Registriert: 6. Okt 2011 15:25

Re: Bottlenecks Praktikum4

Beitrag von Thomas Huxhorn » 18. Jan 2012 16:26

Exakt das selbe habe ich auch gemacht. Komme aber nicht unter 20sec. Hast du besondere Compiler Einstellungen oder was besonderes an der Pixel/Strahl Warteschlange?

x539
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 24. Nov 2010 15:52

Re: Bottlenecks Praktikum4

Beitrag von x539 » 18. Jan 2012 18:05

Thomas Huxhorn hat geschrieben:Exakt das selbe habe ich auch gemacht. Komme aber nicht unter 20sec. Hast du besondere Compiler Einstellungen oder was besonderes an der Pixel/Strahl Warteschlange?
Also letztendlich habe ich quasi gar kein locking mehr. Ich habe eine Pixel "queue", mit queue->next() etwa:

Code: Alles auswählen

int pix = __sync_fetch_and_add(&next, 1);
x = pix % maxX;
y = pix / maxX;
(aber das hat zumindest am bei Zeiten zwischen 50 und 23 sec keinen großen Effekt gehabt)

Compilieren lasse ich mit "-O3 -march=native -mtune=native".

Was für zeiten hast du denn? User/Sys? Hast du das rand sowohl in CCamera::createRayForPixel alsauch in AOSampler::sample ersetzt?
„Reality is that which, when you stop believing in it, doesn't go away.“ Philip K. Dick

Thomas Huxhorn
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 171
Registriert: 6. Okt 2011 15:25

Re: Bottlenecks Praktikum4

Beitrag von Thomas Huxhorn » 18. Jan 2012 22:15

Bei -O3 war mein Programm zeitweise sogar langsamer als mit -O2. Seltsam das.

Hier meine Bestzeit:
real 0m21.209s
user 5m48.813s
sys 0m0.107s

Locking hab ich auch nicht wirklich. Jeder Thread muss halt abundzu sich neue Arbeit holen. Die Variable die den Fortschritt speichert ist mit einem mutex gesichert. Aber ob ich ihn jetzt ein Pixel oder 1024 holen lasse macht so gut wie kein Unterschied.

Ja, ich hab alle rand() durch rand_r() ersetzt. Jeder Thread hat seine eigne seed Variable die auch gleichzeitig die Statusvariable vom Zufallsgenerator ist.

Die blockierenden Funktionen hättest du übrigends viel einfacher mit valgrind gefunden. Da sind das nur ein paar Klicks ;)

Echt komisch. Mit all den von dir angesprochenen Optimierungen bin ich erst auf 25sec runter. Du auf 9sec. Das kann doch nicht sein? Ich habe Tage gesucht um das schneller zu machen.
Auf die 21sec bin ich erst runter gekommen, als ich die Suche durch den Baum schneller gemacht habe. Einfach kürzlich besuchte Nodes zwischenspeichern und erst die testen.

Also irgendwas musst du noch gemacht haben. Das einlesen der Datei und aufstellen des Baumes dauert so 3-4 sec, das Abspeichern des Bildes bestimmt auch nochmal 1sec. 4-5sec für setup und finish und dann 4-5sec fürs Rendern?
Also so ganz glaube ich das noch nicht.

x539
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 24. Nov 2010 15:52

Re: Bottlenecks Praktikum4

Beitrag von x539 » 18. Jan 2012 22:35

Hmm… Auf so Zeiten komme ich wenn ich

Code: Alles auswählen

#include "CScene.cpp"
#include "aosampler.cpp"
#include "vec.cpp"
…
in pr4.cpp weglasse.

Ansonsten habe ich wirklich nur minimale Änderungen: Ich teile nur einmal alle aufsummierten Farbwerte. Aber das wird gcc auch selbst können.
„Reality is that which, when you stop believing in it, doesn't go away.“ Philip K. Dick

Thomas Huxhorn
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 171
Registriert: 6. Okt 2011 15:25

Re: Bottlenecks Praktikum4

Beitrag von Thomas Huxhorn » 18. Jan 2012 22:53

Was hat denn die Laufzeit mit den include Anweisungen zu tun? Hat mich vorhin schon gewundert. Ob das dann noch compiliert oder nicht ist ja die eine Frage. Aber der Code der dann wirklich ausgeführt wird ändert sich doch kein Stück?!

Du meinst sowas hier?

Code: Alles auswählen

color = color / float(numSamplesPerPixel);
Ja stimmt, wenn man am Ende einmal über das ganze Bild läuft und die Berechnung per SSE macht könnte das schneller sein, als wenn es der Thread selbst macht. Aber da sind die intersection Berechnungen doch wesentlich aufwendiger.

kbraden
Mausschubser
Mausschubser
Beiträge: 98
Registriert: 15. Okt 2010 20:35

Re: Bottlenecks Praktikum4

Beitrag von kbraden » 19. Jan 2012 11:17

Kanns sein dass kurz vor Weihnachten weder strace noch valgrind auf node08 installiert war? Hatte nur damals nennenswert Zeit dafuer, strace war IIRC nicht da und ich habs dann aufgegeben :s

Thomas Huxhorn
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 171
Registriert: 6. Okt 2011 15:25

Re: Bottlenecks Praktikum4

Beitrag von Thomas Huxhorn » 19. Jan 2012 11:53

Gute Frage, hab mal gegoogelt.
gdi3user103@pcgris-gc08:~> ls -l /usr/bin/valgrind
-rwxr-xr-x 1 root root 14792 5. Jul 2010 /usr/bin/valgrind
gdi3user103@pcgris-gc08:~> stat /usr/bin/valgrind
File: „/usr/bin/valgrind“
Size: 14792 Blocks: 32 IO Block: 4096 reguläre Datei
Device: fd02h/64770d Inode: 14815327 Links: 1
Access: (0755/-rwxr-xr-x) Uid: ( 0/ root) Gid: ( 0/ root)
Access: 2012-01-05 18:18:50.924231707 +0100
Modify: 2010-07-05 15:28:14.000000000 +0200
Change: 2011-11-28 15:12:58.201275946 +0100

gdi3user103@pcgris-gc08:~> ls-l /usr/bin/strace
-rwxr-xr-x 1 root root 314424 5. Jul 2010 /usr/bin/strace
gdi3user103@pcgris-gc08:~> stat /usr/bin/strace
File: „/usr/bin/strace“
Size: 314424 Blocks: 616 IO Block: 4096 reguläre Datei
Device: fd02h/64770d Inode: 14815319 Links: 1
Access: (0755/-rwxr-xr-x) Uid: ( 0/ root) Gid: ( 0/ root)
Access: 2012-01-12 16:12:54.945125985 +0100
Modify: 2010-07-05 14:14:53.000000000 +0200
Change: 2011-11-28 15:12:50.773858134 +0100
Zuletzt benutzt 2012, erstellt 2010, geändert 2011.
War da nicht irgendeine EMail wegen irgendeinen Update oder so?

neoatlant
Mausschubser
Mausschubser
Beiträge: 58
Registriert: 14. Okt 2010 22:16

Re: Bottlenecks Praktikum4

Beitrag von neoatlant » 19. Jan 2012 12:24

Vielen Dank

x539
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 24. Nov 2010 15:52

Re: Bottlenecks Praktikum4

Beitrag von x539 » 19. Jan 2012 17:59

Thomas Huxhorn hat geschrieben:Was hat denn die Laufzeit mit den include Anweisungen zu tun? Hat mich vorhin schon gewundert. Ob das dann noch compiliert oder nicht ist ja die eine Frage. Aber der Code der dann wirklich ausgeführt wird ändert sich doch kein Stück?!
Es ermöglicht dem Compiler viel besser zu optimieren. Und eine ganze Reihe Funktionen zu inlinen. Das spart viele Teuere 'call/ret' aufrufe.
Du meinst sowas hier?

Code: Alles auswählen

color = color / float(numSamplesPerPixel);
Ja stimmt, wenn man am Ende einmal über das ganze Bild läuft und die Berechnung per SSE macht könnte das schneller sein, als wenn es der Thread selbst macht. Aber da sind die intersection Berechnungen doch wesentlich aufwendiger.
Jain. Ich berechne jedes Pixel schon direkt.

Code: Alles auswählen

color /= float(numSamplesPerPixel * aoNumSamples);
image[0] = color.x;
image[1] = color.y;
image[2] = color.z;
So muss ich für jedes Pixel nur einmal Dividieren und nicht jedes Sample einzeln. D.h. statt (numSamples * aoNumSamples + numSamples) Divisionen pro Pixel nur noch eine. Mit den Intersection Berechnungen hat das nix zu tun.
„Reality is that which, when you stop believing in it, doesn't go away.“ Philip K. Dick

Thomas Huxhorn
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 171
Registriert: 6. Okt 2011 15:25

Re: Bottlenecks Praktikum4

Beitrag von Thomas Huxhorn » 19. Jan 2012 18:06

Meinste echt? Das müsste dem Compiler doch egal sein, wo die Funktionen gespeichert sind. Ob sie via inline eingefügt werden oder nicht, hängt doch an ganz anderen Parameter. Ok aber, das kann ich wenn Zeit ist einfach mal selbst Testen.

Bei der Division der Farbe hast du natürlich recht. Ich werde bei Gelegenheit mal probieren wieviel das bringt.

mw1039
Computerversteher
Computerversteher
Beiträge: 346
Registriert: 12. Apr 2011 12:18

Re: Bottlenecks Praktikum4

Beitrag von mw1039 » 19. Jan 2012 18:58

x539 hat geschrieben:Es ermöglicht dem Compiler viel besser zu optimieren. Und eine ganze Reihe Funktionen zu inlinen. Das spart viele Teuere 'call/ret' aufrufe.
Das wuerde stimmen, wenn das Kompilierschema (Praeprozessor -> Compiler -> Assembler -> Linker) wirklich so steif waere, wie es in der Vorlesung zur Vereinfachung dargestellt wird. Es gibt aber eine ganze Reihe Optimierungen, die auch beim Linken noch stattfinden. Ich wuerde jetzt nicht meine Hand dafuer ins Feuer legen, dass er auch beim Linken noch inlinet, aber ich denke er tut es.
Unabhaengig davon ist es auch kein schoener Stil. Du kriegst dann Probleme mit zyklischen includes, kannst Teile deines Projekts nicht separat kompilieren, etc..
x539 hat geschrieben:Ja stimmt, wenn man am Ende einmal über das ganze Bild läuft und die Berechnung per SSE macht könnte das schneller sein, als wenn es der Thread selbst macht. Aber da sind die intersection Berechnungen doch wesentlich aufwendiger.
Ich glaube auch nicht, dass es einen grossen Unterschied macht. Der Code generiert Strahlen, verfolgt sie durch die Szene, berechnet Schnitte, .... Da sollte es unmerkbar sein, wenn man ganz am Ende pro Sample nochmal eine Division hat.

x539
Windoof-User
Windoof-User
Beiträge: 30
Registriert: 24. Nov 2010 15:52

Re: Bottlenecks Praktikum4

Beitrag von x539 » 19. Jan 2012 20:16

mw1039 hat geschrieben:
x539 hat geschrieben:Es ermöglicht dem Compiler viel besser zu optimieren. Und eine ganze Reihe Funktionen zu inlinen. Das spart viele Teuere 'call/ret' aufrufe.
Das wuerde stimmen, wenn das Kompilierschema (Praeprozessor -> Compiler -> Assembler -> Linker) wirklich so steif waere, wie es in der Vorlesung zur Vereinfachung dargestellt wird. Es gibt aber eine ganze Reihe Optimierungen, die auch beim Linken noch stattfinden. Ich wuerde jetzt nicht meine Hand dafuer ins Feuer legen, dass er auch beim Linken noch inlinet, aber ich denke er tut es.
Unabhaengig davon ist es auch kein schoener Stil. Du kriegst dann Probleme mit zyklischen includes, kannst Teile deines Projekts nicht separat kompilieren, etc..
Das gcc auch ein bisschen LTO kann habe ich schon mal gehört. Aber ich kann mir nicht vorstellen, dass das auch nur annähernd an die Ergebnisse ran kommt die ich mit dem include erreiche (der Unterschied ist wirklich extrem 5:50 vs. 1:30). Was anderes wäre es bei LLVM oder Java-Bytecode.
Dass #include "foo.cpp" extrem hässlich ist, ist mir auch bewusst. Deshalb war das auch der allerletzte schritt. Und das Ergebnis ist es einfach wert, wenn es um Performance geht.

[edit]Oh.. 'gcc -flto' kann doch recht viel, ist nur minimal langsamer(User-Time 1 bis 2 sec bei 24 threads)[/edit]
mw1039 hat geschrieben:
x539 hat geschrieben:Ja stimmt, wenn man am Ende einmal über das ganze Bild läuft und die Berechnung per SSE macht könnte das schneller sein, als wenn es der Thread selbst macht. Aber da sind die intersection Berechnungen doch wesentlich aufwendiger.
Ich glaube auch nicht, dass es einen grossen Unterschied macht. Der Code generiert Strahlen, verfolgt sie durch die Szene, berechnet Schnitte, .... Da sollte es unmerkbar sein, wenn man ganz am Ende pro Sample nochmal eine Division hat.
(Das Zitat ist nicht von mir :shock: ) Ich habe auch keinen großen Unterschied bemerkt, aber ich denke, dass gcc das auch selbst schon zusammen gefasst hat.
„Reality is that which, when you stop believing in it, doesn't go away.“ Philip K. Dick

Thomas Huxhorn
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 171
Registriert: 6. Okt 2011 15:25

Re: Bottlenecks Praktikum4

Beitrag von Thomas Huxhorn » 19. Jan 2012 20:39

Tut mir leid, wenn ich jetzt so blöd nachfrage. Aber wo soll denn die Optimierung stattfinden wenn man den ganzen Code in eine Datei kopiert, aber die Funktionen an sich noch getrennt lässt.

//edit
*zensiert*. Hast recht. Einfach -flto dem Compiler mitgeben und ich komm nun auch auf 9sec

real 0m9.341s
user 1m33.996s
sys 0m0.094s

Oh man. Hätte ich das vorher gewusst :( Das ärgert mich jetzt.

Antworten

Zurück zu „Archiv“