Threading oder kein Threading - das ist hier die Frage.

[Fret]

Hallo zusammen!

Ich bastel momentan an einem Programm, dass ein bißchen numerische Mathematik (Integration, Optimierung) durchführen soll. Nun wollte ich gerne Threads benutzen, um die Geschwindigkeit zu steigern, da z.B. bei den Integrationsalgorithmen zwei Schritte parallel ausgeführt werden könnten. Ich habe gestern jedoch festgestellt, dass mein Programm langsamer wurde (auf einem Dual Core Rechner). Kann es sein, dass sich Threads in diesem Fall erst ab einer gewissen "Arbeitsgröße" lohnen? Ich habe den Eindruck, dass das Anlegen und Beenden der Threads länger dauert, als wenn ich einfach alle Rechenoperationen nacheinander durchführen lasse. Kann das sein oder liegt hier definitiv ein Programmierfehler von mir vor? Ich habe die threads einfach mit start() gestartet und mit join() die Ergebnisse eingesammelt.


Viele Grüße,
Arne

 

[Wildcard]

Kann es sein, dass sich Threads in diesem Fall erst ab einer gewissen "Arbeitsgröße" lohnen? Ich habe den Eindruck, dass das Anlegen und Beenden der Threads länger dauert, als wenn ich einfach alle Rechenoperationen nacheinander durchführen lasse.

Wie soll man das beantworten ohne die "Arbeitsgröße" zu kennen.

Kann das sein oder liegt hier definitiv ein Programmierfehler von mir vor?

Wie kann man dasbeantworten, ohne die Implementierung zu kennen?

 

[foobar]

Benutz doch einen Threadpool, das kann das ganze noch etwas beschleunigen.

 

[Saxony]

Hiho,

wenn der Thread ZeitOverhead > der eigentlichen Berechnungszeit ist, sollte man es nicht erst in Threads aufteilen.

Maximal einen Berechnungsthread damit die GUI nicht einfriert.

[edit]
Du willst aber bestimmt die Berechnung auf die zwei Prozessorkerne forken. Das hat aber leider nix mit der JVM zu tun. Die JVM erzeugt zwar deine Threads aber das zu Grunde liegende OS kümmert sich um die Aufteilung auf die Kerne. Ist das OS aber nun der Meinung alle deine Threads auf einem Kern abzuarbeiten, ergibt sich daraus
ThreadOverhead + Berechnungszeit + OS Scheduling für die Gesamtlaufzeit.
[/edit]

bye Saxony

 

[Fret]

Danke erstmal. Mir ist schon klar, dass für genaue Aussagen der Quellcode nützlich wäre. Ich wollte nur fragen, ob es im Prinzip möglich ist, dass die Threadverwaltung mehr Zeit braucht als der eigentliche Programmteil, der im Thread abgearbeitet werden soll. Ich hatte keinen Plan, wie aufwending die Threadverwaltung für die JVM ist...

 

[Saxony]

Ich hatte keinen Plan, wie aufwending die Threadverwaltung für die JVM ist...

Mittlerweile erzeugt die JVM nur Threads und mapped diese auf Native OS Threads. Die Threadverwaltung findet damit eigentlich im OS statt.

Füher waren die sogenannten Green Threads vom OS abgeschottet und damit alleinige Sache der JVM. Das hatte zum Beispiel den Nachteil, dass die JVM alleine die Threads nicht auf mehrere CPUs / Kerne aufteilen konnte, da sie über ihren eigenen ProcessScope nicht hinaus kam. Erst das Mapping auf OS Threads gab die Verteilung (Scheduling) an das OS weiter, welche nun nicht mehr an einen alleinigen Prozess gebunden war.
Ich weiß leider nicht ab welcher JavaVersion das Native Thread mapping der JVM nun default ist.

bye Saxony

 

[byte]

Du willst aber bestimmt die Berechnung auf die zwei Prozessorkerne forken. Das hat aber leider nix mit der JVM zu tun.

Man hat zwar keine direkte Kontrolle, aber in der Praxis lastet der Scheduler die Kerne nahezu immer gut aus.

Ist das OS aber nun der Meinung alle deine Threads auf einem Kern abzuarbeiten, ergibt sich daraus
ThreadOverhead + Berechnungszeit + OS Scheduling für die Gesamtlaufzeit.

Häufig ist Multithreading auch bei einem Kern schneller als Single-Threading, weil eine Operation den Kern nicht immer durchweg zu 100% auslastet. Es gibt immer mal Wartezeiten (z.B. durch IO usw). Details dazu siehe Thinking in Java, 4. Ed.

 

[byte]

Danke erstmal. Mir ist schon klar, dass für genaue Aussagen der Quellcode nützlich wäre. Ich wollte nur fragen, ob es im Prinzip möglich ist, dass die Threadverwaltung mehr Zeit braucht als der eigentliche Programmteil, der im Thread abgearbeitet werden soll. Ich hatte keinen Plan, wie aufwending die Threadverwaltung für die JVM ist...

Der Aufwand bei Threading und Scheduling liegt im Millisekundenbereich. In der Praxis sinds grade Operationen mit längerer Laufzeit, die man durch Multithreading optimieren will (z.B im 100er Millisekundenbereich und aufwärts). Da spielt der Scheduling-Overhead keine Rolle mehr.
Durch die Verwendung von Thread-Pools kann man den Overhead nochmal reduzieren, weil dann die nativen Threads nicht jedes mal neu allokiert werden.

 

[Saxony]

Häufig ist Multithreading auch bei einem Kern schneller als Single-Threading, weil eine Operation den Kern nicht immer durchweg zu 100% auslastet. Es gibt immer mal Wartezeiten (z.B. durch IO usw). Details dazu siehe Thinking in Java, 4. Ed.

Ähm versteh ich grad nicht was du meinst!

Arbeitet die CPU an einem Thread, dann arbeitet sie auch nur an genau diesem Thread - hat also zu dieser Zeit eine Last von 100%, da sie keinen anderen anderen Thread parallel mit verarbeiten kann.

Habe ich nur einen Thread T1 und einer CPU:

  |
T1|----------------
  |
  |
  --------------------------->t

Bei zwei Threads die sich die gleiche Arbeit teilen auf einer CPU:

  |
T1|  |---|    |--|  |---|
  |  |   |    |  |  |   |
T2|--|   |----|  |--|
  |
  --------------------------->t

Nun muss bei zwei Threads das OS aber wesentlich öfter hin und her schalten zwischen den Threads was die Sache auf einem Kern nun nicht gerade schneller macht.

bye Saxony

 

[byte]

Arbeitet die CPU an einem Thread, dann arbeitet sie auch nur an genau diesem Thread - hat also zu dieser Zeit eine Last von 100%, da sie keinen anderen anderen Thread parallel mit verarbeiten kann.

Das kommt auf die Operation an. Wenn Resourcen involviert sind (z.B. IO), dann hat die CPU häufig Wartezeiten, die man durch Multithreading sinnvoll füllen könnte.

Nun muss bei zwei Threads das OS aber wesentlich öfter hin und her schalten zwischen den Threads was die Sache auf einem Kern nun nicht gerade schneller macht.

Mir ist die Thematik durchaus bewusst. Moderne Scheduling-Algorithmen sind aber extrem effizient. Der Overhead bei einem Thread mehr oder weniger ist kaum messbar und liegt deutlich unter der Zeit, die häufig durch das Warten auf (blockende) Resourcen (wie Festplattenzugriff etc) verloren geht.

Edit: Wenn Du Dir natürlich sicher bist, dass keine der Operationen blockiert, dann macht Concurrency wirklich keinen Sinn auf 1-Prozessor/Kern Systemen.

 

[Fret]

Also meine Rechenoperation braucht ohne Threading ca 6 sek, mit Threading hat sich die Zeit ca verdoppelt. Allerdings werden ca 40000 Rechenschritte in dieser Zeit ausgeführt, die ich auf zwei Threads aufteilen wollte. Da jeder Thread nach der entsprechenden Rechenoperation stirbt (da run() erfolgreich beendet wurde) muss ich also 20000 mal einen neuen Thread erstellen, richtig? Das wäre natürlich blöd. Wie könnte ich das geschickter machen? Helfen mir da Thread-Pools?

 

[tfa]

Da machst du was falsch. Wenn du nur 2 Threads rechnen lassen willst, brauchst du auch nur 2 und nicht 20000.
Der Rechenthread darf natürlich nicht nach einer Operation sterben, wenn diese nur sher kurz ist.

 

[Fret]

Soweit war ich jetzt auch schon. Ich denke, ich muss den Code etwas umstricken, damit das geht. Vermutlich müßte doch dann jeder Thread nach erfolgter Rechenoperation warten, bis er wieder rechnen darf, oder? Mache ich das besser mit await() und signal(), oder mit wait() und notify()?

 

[byte]

Verwendest Du Java 5+ ? Dann guck Dir umbedingt das Java Concurrency Framework an. Hantierung mit wait() und notify() sollte man wenn möglich immer umgehen.

 

[Fret]

Ich verwende Java 6, ja. Du meinst Executor bzw. ExecutorService? Das Framework lässt aber doch keine Steuerung im Sinne von warten und signalisieren zu, oder? Da müßte ich doch trotzdem über ein Condition-Objekt gehen...

 

[schalentier]

Ich denke, ich muss den Code etwas umstricken, damit das geht.

Du MUSST den Code umstricken. Erklaer mal bisschen genauer, was das fuer eine Rechnung ist. Parallelisieren eines Algorithmus ist absolut nicht trivial.

 

[byte]

Ich verwende Java 6, ja. Du meinst Executor bzw. ExecutorService? Das Framework lässt aber doch keine Steuerung im Sinne von warten und signalisieren zu, oder? Da müßte ich doch trotzdem über ein Condition-Objekt gehen...

Doch lässt es. Du kannst sogar explizit Rückgabewerte aus einem Thread bekommen (siehe Callable, Future).

 

[Fret]

So, ich habe nun mal ausprobiert, die Threads über einen ExecutorService zu starten. Funktioniert auch prima, offensichtlich werden nun beide Kerne meines Rechner benutzt. Leider bringt es keinen Geschwindigkeits-Vorteil, die entsprechenden Rechenoperationen brauchen immernoch ca 8 sek im Vergleich zu ca 5 sek ohne Threading. Ich gehe also davon aus, dass der vom Threading produziert Overhang zu groß ist, als dass es sich lohnen würde. Was kann man denn sonst noch machen, um die Geschwindigkeit eines Programms zu erhöhen? Kann man den ByteCode auch in "richtigen" Code übersetzen?

 

[byte]

Die beste Art, die Performance von Quellcode zu verbessern, ist immernoch Quake-Optimization. :roll:

Aber mal im Ernst: ich glaube kaum, dass der Scheduling Overhead zufällig genauso groß ist, dass der Code am Ende die identische Laufzeit hat wie zuvor, als alles noch in einem Thread lief.
Da ist es wahrscheinlicher, dass Deine Implementierung nicht korrekt ist. Aber solange Du keinen Code zeigst, kann man nur spekulieren.

 

[Saxony]

Die beste Art, die Performance von Quellcode zu verbessern, ist immernoch Quake-Optimization. :roll:

Heu was isn das ? ???:L

bye Saxony

 

[byte]

Quake Optimization:
Die Entwickler spielen ein Jahr nur Quake. Danach läuft die Software (auf der dann aktuellen Hardware) schneller!

 

[Fret]

Der Code ist ziemlich groß, ich werde mal die wesentlichen Teile extrahieren und später posten.
Ein anderer Punkt, der die Geschwindigkeit beeinflussen könnte, ist folgendes: Ich muss eine Funktion auswerten, die das Programm aus Benutzereingaben konstruiert. D.h. der Benutzer gibt ein Modell ein, das Programm konstruiert daraus Differentialgleichungen und integriert diese. Ich habe das so gelöst, dass ich die Benutzereingaben als Variablen in arrays geschrieben habe, die dann vom Programm in einer bestimmten Art und Weise abgelaufen werden (z.B. werden die Felder/Variablen addiert oder multipliziert). Das Auswerten der Gleichungen wäre ja vermutlich schneller, wenn direkt eine "richtige" Gleichung (2x + 3) verfügbar wäre. Wie könnte man das machen?

 

[Saxony]

Das Auswerten der Gleichungen wäre ja vermutlich schneller, wenn direkt eine "richtige" Gleichung (2x + 3) verfügbar wäre. Wie könnte man das machen?

Mit einem Funktionsparser.

bye Saxony

 

[Fret]

Äh, ich glaube wir missverstehen uns. Ich habe bereits einen Parser geschrieben, der aus einer Textdatei mit chemischen Gleichungen die entsprechenden Ratengleichungen (Differentialgleichungen) ableitet. Diese sind prinzipiell recht einfach aufgebaut, es tauchen pro gleichung mehrere Terme auf, die addiert werden. Beim Parsen wird jeweils der Koeffizient des Terms und die nachfolgenden Variablen in eine Array-Struktur geschrieben. Zum Berechnen der jeweiligen Werte der Differentialgleichungen laufe ich mit einer Schleife diesen Array ab und multipliziere bzw. addiere die Werte der dort abgelegten Variablen.
Die Frage ist nun, ob das Ablaufen der Arrays vermieden und die Gleichungen geschickter in anderer Form abgespeichert werden können.
Ein zweiter Punkt wäre der folgende: Ich benutze einen Integrationsalgorithmus für steife Differentialgleichungen, der mir recht langsam vorkommt. Das ist aber dummerweise der einzige, den ich für Java gefunden habe. Kennt jemand von euch einen guten Algorithmus für sowas? In diesem werden recht oft Matrizen kopiert, ich vermute dass das eine zeitaufwendige Sache ist, oder?

Vielen Dank für eure Hilfe!