[gelöst Danke]Parallelisierung einer For-Schleife

[ComputerCarl]

Michael E. schrieb:

Das ist geraten, richtig? Rate niemals, wo die meiste Zeit verbraucht wird, sondern miss es! Schnapp dir dazu einen Profiler.

Na ja Zeitmessungen habe ich schon gemacht. Allerdings weiß ich nicht ob dafür die clock()-Funktion die beste Alternative ist. Ja und Code würde schon gehen, aber ich weiß nicht, ob da wirklich ein Mehrwert ensteht, da er wirklich lang ist und der Baum-Welsh im Netz eigentlich gut erklärt ist.

[Michael E.]

ComputerCarl schrieb:

Das eigentliche Problem ist eigentlich ein Baum-Welsh über mehrere Sequenzen.

Schon mal die Performance mit anderen Implementierungen verglichen? Z.B. http://www.kanungo.com/software/software.html#umdhmm

[Gast]

ComputerCarl schrieb:

Michael E. schrieb:

Das ist geraten, richtig? Rate niemals, wo die meiste Zeit verbraucht wird, sondern miss es! Schnapp dir dazu einen Profiler.

Na ja Zeitmessungen habe ich schon gemacht. Allerdings weiß ich nicht ob dafür die clock()-Funktion die beste Alternative ist.

Die geht klar. Zumindest wenn deine Laufzeit größer als ~10 Millisekunden ist

[ComputerCarl]

Der Link für das GNU package auf der Seite geht leider nicht.
Ich habe aber Vergleiche mit Comilitonen und einer Implementierung
meines Übungsleiters. Also die nicht parallele Version von mir
und den anderen liegt wirklich weit ab vom Schuss. Leider weiß ich
nicht wo der Geschwindigkeitgewinn bei der anderen Implementierung
gerkommt, aber anders als durch Parallelisierung kann ich mir das
nicht erklären.

als Release-Version kompiliert:
Ich bin leider mit solchen Begriffen nicht vertraut... sorry.

[Michael E.]

ComputerCarl schrieb:

als Release-Version kompiliert:
Ich bin leider mit solchen Begriffen nicht vertraut... sorry.

Darum solltest du dich als erstes kümmern: Finde in deiner IDE einen Schalter, bei dem du "Debug" und "Release" einstellen kannst. Stelle ihn auf "Release", kompiliere neu und teste das generierte Programm außerhalb der IDE (üblicherweise liegt es in einem Ordner namens "Release").

[cooky451]

UND VOR ALLEM: Nutze keinen Compiler aus dem letzten Programmierjahrtausend.

[ComputerCarl]

Also in Dev C++ finde ich solche Einstellungen nicht und
in dem jetzt frisch gedownloadten Eclipse finde ich mich
nicht zurecht. Könnten wir also nochmal die eigentliche
Frage in den Mittelpunkt der Diskusion stellen?
Ich mein, wichtig bleibt es ja so oder so...

[cooky451]

VS11 Beta installieren http://www.microsoft.com/visualstudio/11/en-us
parallel_for_each nutzen (Oder C++11 Features wie std::thread und std::future)
fertig.
Aber viel nützen wird dir das vermutlich nicht, ich tippe eher darauf, dass du irgendwo ganz unangenehme Performancelöcher hast. Aber ohne Code können wir dir da nicht helfen. Na zumindest hat VS11 einen Profiler, der zeigt dir dann schon was da so lange dauert.

[Tippgeber]

Wahrscheinlich löst sich das Performance-Problem schon dadurch, dass der Code mit GCC 4.7 übersetzt wird...

[ComputerCarl]

Was ist mit PerformanceLöcher gemeint? Unnötige Schleifen oder mehrfache Berechnugn gleicher Ergebnisse mache ich nicht. DP wird benutzt wo es geht.
Sonst werden nur Basisdatentypen und höchstens noch Vectoren verwendet.
Aber unabhängig davon wozu brauche ich denn noch diesen Profiler, wenn clock doch schon ausreicht?
Visual-Studio würde ich gerne vermeiden, da ich darin schon mal was gemacht hatte und einfach nicht wirklich zufrieden damit war. Ist es möglich das jemand mir das einfache Bsp. in meinem ersten Kommentar irgendwie in diese Threads umzuwandeln?
vielen Dank im voraus.

[cooky451]

Nö, das geht nicht. Warum? C++03 kennt keine Threads. Und dein Compiler kennt kein C++11.

[Michael E.]

cooky451 schrieb:

Aber viel nützen wird dir das vermutlich nicht, ich tippe eher darauf, dass du irgendwo ganz unangenehme Performancelöcher hast.

Ja, und zwar, dass er im Debug-Modus kompiliert.

ComputerCarl: Die Einstellung gibts auch bei Dev-C++. Den hab ich auch mal vor fast zehn Jahren verwendet, kann dir aber nicht mehr sagen, wo es geht. Wenn du im Release-Modus kompilierst, sind deine Performancesorgen höchstwahrscheinlich nicht mehr vorhanden.

[ComputerCarl]

Ich habe jetzt "MinGW" mit g++(GCC) 4.7.0 und mein Projekt ganz normal
compiliert wie es in Tutorials im Netz steht. (g++ Programm.cpp -o Programm.exe)
Der Geschwindigkeitsgewinn ist zwar merkbar (um die Hälfte reduziert), aber immer
noch nicht ausreichend für meine Zwecke.
Ist dieser Compiler ebenfalls nicht geeignet oder muss ich dem Compiler
noch zusätzliche Informationen geben, ähnlich der Release-Information?

[314159265358979__]

Übergib ihm mal als Flag -O3, das sollte einiges bringen.

[314159265358979__]

... sowie -march=native

[ComputerCarl]

Die Einstellungen bringen auch einige wichtige Sekunden, aber die Rechnungen
dauern immernoch Minuten. Müssen sie auch, es geht um große Datenmengen. Aber das
alles bringt mich wieder zurück zur Parallelisierung. Bzw. gibt es noch weitere
Compiler-technische Vorschläge?

[Ethon]

Nö. Jetzt solltest du einen Profiler auspacken und nachsehen, wo das Programm am Längsten braucht.
Wenn sich das Problem gut parallelisieren lässt, mach ruhig, schau dir dazu std::thread/std::mutex/std::fure an.

[cooky451]

Zwischen O0 und O3 liegen nur sekunden? Zeig vielleicht doch mal deinen Code.
Ansonsten mit 4.7 kannste std::thread nutzen und std::future nutzen.

[ComputerCarl]

Also ich habe erneut mit clock() Messungen durchgeführt und die meiste Zeit
geht in den 3-verschachtelten for-Schleifen drauf. (Die sind notwendig:
erste geht über alle Daten und die beiden Folgenden gehen über die Zeilen
und Spalten der Forward- und Backwardmatrix der jeweiligen Sequenz) Die Berechnung der Schätzer nimmt weniger Zeit ein. Sollte, aber vermutlich auch parallelisiert werde.
Ich werde mich jetzt einfach in die threads reinlesen. Danke nochmal an alle
Mitdiskutierer.

[Michael E.]

Wie sieht deine Definition von data_array aus? Sind das verschachtelte std::vector ? Wenn ja, geht dir hier die Cachelokalität flöten. Dazu findest du genügend Threads.