Forum: PC-Programmierung Schwankende Ausführungsgeschwindigkeit (Multithread)


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von A. R. (redegle)


Bewertung
0 lesenswert
nicht lesenswert
Hallo zusammen,

ich habe ein Phänomen dass ich mir nicht erklären kann.
Vielleicht findet sich ja einer der eine Idee hat.

Ich habe ein Programm geschrieben, dass ein lineares Gleichungssystem 
löst. Das Gleichungssystem wird auf eine einstellbare Anzahl von Threads 
aufgeteilt. Dieser Teil funktioniert auch und liefert reproduzierbare 
Ergebnisse.

Ich rufe nun in einer Schleife 10 mal hintereinander meinen Solver auf 
und messe die Ausführungszeit. In jedem Durchlauf werden die Threads 
(std::thread, c++) neu alloziert und gelöscht. In jedem Durchlauf ist 
die Ausführungszeit annähernd gleich z.B. 5,2 s (+/- 60 ms). Das ist so 
weit in Ordnung.

Wenn das Programm nun erneut aufgerufen wird und wieder 10 Messungen 
durchgeführt werden braucht eine Ausführung z.B. 8 s (+/- 60 ms).

Bei wieder erneuter Ausführung sind es dann 5,6 s +/-  60 ms

Woran kann diese liegen?
Warum ändert sich die Ausführungszeit wenn in das Programm neu starte, 
bleibt aber dann reproduzierbar?
Kann man das abstellen, so dass immer die "optimale" Ausführungszeit 
erreichbar ist?

von Amateur (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Zu wenige Informationen!

Wie gemessen? Immer nach Neustart?

Was für ein Programm? 10 Zeiler; 300MByte?

Wieviel Arbeitsspeicher X mal 10 Bytes; X mal 50 MByte?

Rechnerzustand beim Programmstart?

Abakus?
Rechenschieber?
Raspberry Pi; in Mikrosoft- oder Linux-Umgebung.
Tablet PC mit Linux oder Fenster?
Desktop-Bolide mit 128 GByte Speicher und Linux oder Fenster?

uva.

Möglicherweise ist es nur ein Fehler in Programmzeile 42!

von Clemens L. (c_l)


Bewertung
0 lesenswert
nicht lesenswert
Ich vermute einfach mal, dass das OS die Threads anders auf die CPUs 
verteilt.

Das kannst du auch selbst festlegen (aber nicht mehr mit std::).

von A. R. (redegle)


Bewertung
0 lesenswert
nicht lesenswert
@ Clemens L.,

das mit dem anderen Aufteilen der Thread hatte ich auch schon vermutet.
Aber ich erstelle alle Threads bei jedem Durchlauf neu. Müsste das 
System die Threads dann nicht jedes mal andersder aufteilen, so dass bei 
jedem Durchlauf andere Zeiten entstehen?

Wie kann ich festlegen, welcher Thread auf welchem Prozessor läuft?
Ich hätte vermutet dass das Betriebssystem dies von sich aus immer 
optimal festlegt was es aber scheinbar nicht tut.


@  Amateur,

nicht nach Neustart gemessen.
Mehrere 1000 Zeilen Code. Aber der betroffene Code sind nur paar 100 
Zeilen.
Benötigter Arbeitsspeicher während dem Ausführen etwa 100 MB.
System ist ein Server mit 32 CPUs von denen 8 verwendet werden.
Aktuell bin ich der einzige User, so dass keine anderen Prozesse störend 
sind.

von Nop (Gast)


Bewertung
0 lesenswert
nicht lesenswert
A. R. schrieb:

> Aktuell bin ich der einzige User, so dass keine anderen Prozesse störend
> sind.

Und Du hast auch kein Betriebssystem laufen? Unter Linux gibt's das 
Shellkommando "time", mit dem man sowohl walltime (irrelevant) als auch 
usertime rauskriegt.

von Nop (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Ach ja.. je nachdem, was Du tust, kann's natürlich auch an 
Speicherbelegung liegen, die mal besser und mal schlechter zum 
Cacheverhalten der CPU paßt. Das ist vor allem dann zu erwarten, wenn Du 
dynamische Allozierung benutzt - und zwar nicht nur malloc, sondern auch 
new.

Wenn Du dieses Ausmaß an Kontrolle brauchst, dann führt wohl wenig an 
statischer Speicherverwaltung vorbei.

von Peter II (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Ich denke auch, du solltest zwischen CPU-Zeit und "echt" Zeit 
unterscheiden. Man kann auch von jeden Thread die CPU-Zeit anfragen, 
also wie lange er wirklich die CPU genutzt hat.

Also nächsten kommen dann noch Probleme mit Dynamischen Takt hinzu. Die 
CPUs passend ja ihren Takt an die Gesamtauslastung an. Nach eine Pause 
wenn die CPU kalt ist, ist sie etwas schneller.

von Εrnst B. (ernst)


Bewertung
1 lesenswert
nicht lesenswert
Evtl. auch nicht zu vernachlässigen: der "Turbo Boost" der in 
Abhängigkeit der CPU-Temperatur mehr Power zur Verfügung stellt. Dann 
sollte der dritte Lauf aber der langsamste sein, wenn zwischendurch 
nicht abgekühlt wird.

von Amateur (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Hast Du mal versucht, soweit wie möglich, das Hintergrundsystem 
stillzulegen?
Also kein "nachhause" Telefonieren (update Services des Systems und der 
Programme).
Dateien indizieren: Nein Danke!
Platte defragmentieren: Nie!
Postfach: "A Ruhe gibt’s"!
Und was sonst noch so, ohne Dein explizites Kommando, (an)läuft.

Beim Programmstart hängt vieles davon ab, die "voll" Du bist;)
Das gilt sowohl für das Programm, als auch für den Speicher, der 
reserviert wird.
Gäbe es die dynamische Speicherverwaltung nicht, so würde ich 
vorschlagen: Rechne vorher aus wieviel Speicher Du brauchst und 
reserviere ihn vor dem Start des eigentlichen Programmes.
Gift ist auch, wenn Du ständig Variablen reservierst und freigibst. "Am 
Giftigsten ist es in Schleifen".
Da läuft ein eigener Hintergrundprozess, der für die Speicherverwaltung 
zuständig ist.
Also Speicher reservieren, auslagern, freigeben usw. Von außen nicht 
immer vorhersehbar, was wann geschieht. Eine Möglichkeit das Ganze noch 
homogener zu gestalten ist, gleich nach der Reservierung auf den 
Speicher zugreifen. Manche Reservierung geschieht nur scheinbar und wird 
erst beim Zugriff abgeschlossen.

von Peter II (Gast)


Bewertung
1 lesenswert
nicht lesenswert
Amateur schrieb:
> Gift ist auch, wenn Du ständig Variablen reservierst und freigibst. "Am
> Giftigsten ist es in Schleifen".
vor 20 Jahren war das mal so. so etwas macht man bei OO Programierung 
ständig und ist auch nicht störend weil Compiler darauf optimiert sind.

> Da läuft ein eigener Hintergrundprozess, der für die Speicherverwaltung
> zuständig ist.
Speicher wird erst mal von der libc verwaltet, das BS verwaltet nur 
PAGES. (die werden dann bei bedarf von der libc angeforder) und in der 
libc gibt es keinen Hintergrundprozess.

von Boris O. (bohnsorg) Benutzerseite


Bewertung
0 lesenswert
nicht lesenswert
Die Parallelisierung funktioniert immer andersDER als gedacht. Moderne 
Betriebssysteme haben mehr Probleme mit der Beschaffung neuer Ressourcen 
als der Weiterverwendung bestehender. Zudem sind die Betriebssysteme 
viel besser im Blockieren von Threads geworden, was mittlerweile fast 
die Hauptaufgabe ist. Daher ist es sinniger, einen Pool an Threads mit 
einer Queue zu verbinden und den Pool ordentlich groß zu wählen. 32.000 
Threads auf einer Windows-Maschine sind zu schaffen, das geht selbst mit 
virtuellen Maschinen wie Java oder .NET. Alle Optimierung im Vorfeld ist 
Gemurkse und sinnloses tun. Wenn du einen echten Flaschenhals entdeckt 
hast, solltest du den untersuchen.

von Nop (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Peter II schrieb:

> Speicher wird erst mal von der libc verwaltet, das BS verwaltet nur
> PAGES. (die werden dann bei bedarf von der libc angeforder) und in der
> libc gibt es keinen Hintergrundprozess.

Nicht ganz. Wenn man etwa mit calloc Speicher alloziert, dann wird der 
keineswegs wirklich genullt. calloc ist nicht malloc plus memset.

Stattdessen wird der gesamte angeforderte Speicher per MMU auf eine 
Zeropage gemappt, und erst bei Benutzung wird der dann wirklich genutzte 
Speicher auf andere Pages gemappt, wie dann auch genullt wird.

Insofern ist der Hinweis, allozierten Speicher auch erstmal 
"warmzunutzen", nicht aus der Luft gegriffen.

von Peter II (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Nop schrieb:
> Wenn man etwa mit calloc Speicher alloziert

Es ging mir um:

> Gift ist auch, wenn Du ständig Variablen reservierst und freigibst.

also
1
for(;;) {
2
  int a = 42;
3
}

und das ist sehr wohl sinnvoll, vermutlich wird dafür auch kein Speicher 
angefordert. Wenn es ein objekt ist wird es auf dem Stack angelegt, da 
gibt es dann auch kein calloc

von Nop (Gast)


Bewertung
0 lesenswert
nicht lesenswert
Peter II schrieb:

> und das ist sehr wohl sinnvoll

Ja, weil das eine normale lokale Variable ist, nur daß deren Scope auf 
den Block begrenzt ist. Es besteht ansonsten kein Unterschied dazu, die 
Variable außerhalb der Schleife lokal zu deklarieren.

Aber new/delete-Orgien könnten schon anders aussehen. Insbesondere, weil 
die normalerweise auf dem Heap landen und man über das Speicherlayout 
seiner Objekte relativ zueinander dann keinerlei Kontrolle mehr hat, was 
mit dem Caching nicht unbedingt optimal zusammenpassen muß und auch bei 
jedem Lauf anders sein könnte.

Das wiederum würde zur Beobachtung des OP passen, daß die Zeiten bei den 
Einzelläufen dieselben sind, aber nicht bei den Programmläufen. Deswegen 
meine Anregung, das in den Fall statisch zu deklarieren.

von Amateur (Gast)


Bewertung
0 lesenswert
nicht lesenswert
>for(;;) {
>  int a = 42;
>}
Das sollte auch der "dümmste", der heutigen Compiler, auf die Reihe 
bekommen.

@Peter Doppel-I
>> Gift ist auch, wenn Du ständig Variablen reservierst und freigibst. "Am
>> Giftigsten ist es in Schleifen".
>vor 20 Jahren war das mal so. so etwas macht man bei OO Programierung
>ständig und ist auch nicht störend weil Compiler darauf optimiert sind.
Das gilt aber nur für die neuartigen Compiler, mit hellseherischen 
Fähigkeiten. Meiner weis erst nach dem Setzen der Schleifenvariablen, 
wieviel Speicher demnächst fällig wird; z.B. wie oft "new" gerufen wird. 
Eine variable Anzahl vorausgesetzt.

von jibi (Gast)


Bewertung
0 lesenswert
nicht lesenswert
>Das gilt aber nur für die neuartigen Compiler, mit hellseherischen
>Fähigkeiten

Wieso, wie soll das aufm heap landen? Das ist komplett vorhersehbar.

Gruß

von Clemens L. (c_l)


Bewertung
0 lesenswert
nicht lesenswert
A. R. schrieb:
> Ich hätte vermutet dass das Betriebssystem dies von sich aus immer
> optimal festlegt

Woher soll denn das BS wissen, wie dein Programm in der Zukunft laufen 
wird?

> Wie kann ich festlegen, welcher Thread auf welchem Prozessor läuft?

Das (und An-/Abschalten des Turbos) kommt auf das BS an.

von Minimalist (Gast)


Bewertung
0 lesenswert
nicht lesenswert
A. R. schrieb:
> System ist ein Server mit 32 CPUs von denen 8 verwendet werden.

Dann sind es wahrscheinlich cache hits/misses, die verantwortlich sind.
Wenn die 32 Kerne nicht in einer physikalischen CPU sind, kann es 
passieren, das du 8 Kerne auf derselben CPU hast, oder eben auf 
verschiedenen. Im 2. Fall muss einiges an Kommunikation zwischen den 
CPUs passieren, im 1. Fall könnte alles über den Chance gehen.

Schau daher mal, ob es einen Unterschied macht, auf welchen Kernen dein 
Programm läuft. Wenn ja, hast du es!

von (prx) A. K. (prx)


Bewertung
0 lesenswert
nicht lesenswert
A. R. schrieb:
> Ich habe ein Programm geschrieben, dass ein lineares Gleichungssystem
> löst. Das Gleichungssystem wird auf eine einstellbare Anzahl von Threads
> aufgeteilt.

Wird das einmal aufgeteilt und dann arbeitet jeder auf eigenen 
Datenbereichen(*) ohne Synchronisation für sich, oder arbeiten alle 
Daten auf gemeinsamen Datenbereichen, vielleicht sogar kurzfristig 
synchronisert?

*: Alles was in einer Cache-Line landet gilt als gemeinsam benutzter 
Datenbereich, auch wenn es getrennte Variablen sind.

: Bearbeitet durch User
von A. R. (redegle)


Bewertung
0 lesenswert
nicht lesenswert
>Und Du hast auch kein Betriebssystem laufen?

Betriebssystem: Windows 7 Professional N
Entwicklungsumgebung: Microsoft Visual Studio Professional 2012
32 Bit Anwendung

>Evtl. auch nicht zu vernachlässigen: der "Turbo Boost" der in
>Abhängigkeit der CPU-Temperatur mehr Power zur Verfügung stellt.

In Anbetracht dessen, dass 10 Durchläufe nacheinander annähernd exakt 
gleich lange dauern, kann dies denke ich ausgeschlossen werden.

>Hast Du mal versucht, soweit wie möglich, das Hintergrundsystem stillzulegen?

Nein.
Ich gehe davon aus, dass ein Hintergrundprozess dafür sorgen würde, dass 
die 10 Zeitmessungen untereinander Abweichungen hätten. Da dies aber 
nicht Auftritt kann davon ausgegangen werden, dass etwas 
deterministisches passiert

Zur Speicherverwaltung:
Ich berechne vorher wie viel Speicher ich benötigte.
Es werden einmal die benötigten Arrays alloziert (die meisten direkt 
nacheinander) und direkt mit 0 initiallisiert. Der Solver greift während 
der Ausführung nur auf die vorher allozierten Arrays zu. Es wird also 
während der Ausführungszeit kein new oder delete ausgeführt.

Würde es einen Unterschied machen ob ich alle Arrays einzeln alloziere 
oder ein großes, welches ich dann über reinterpret_casts entsprechend 
aufteile und selbst verwalte? Wobei mir diese Lösung ziemlich "dreckig" 
vorkommt. Ich könnte jedoch versuchen eine Struktur anzulegen, in der 
alle Daten zusammenhängend drin sind, welche ein Thread benötigt. Auf 
die Art sollte das Caching weniger cache misses erzeugen.

>Ach ja.. je nachdem, was Du tust, kann's natürlich auch an
>Speicherbelegung liegen, die mal besser und mal schlechter zum
>Cacheverhalten der CPU paßt. Das ist vor allem dann zu erwarten, wenn Du
>dynamische Allozierung benutzt - und zwar nicht nur malloc, sondern auch
>new.

>Deswegen meine Anregung, das in den Fall statisch zu deklarieren.
Wie würde ich das machen, wenn ich erst während der Laufzeit weiß, wie 
viel Speicher ich benötige?

>Woher soll denn das BS wissen, wie dein Programm in der Zukunft laufen wird?

Indem man das Programm beoachtet und aus dem Verhalten der Vergangenheit 
auf das Verhalten der Zukunft schließt. Wie das z.B. bei einer SSHD der 
Fall ist.


Ich denke die beiden letzten Posts von Minimalist und A.K. haben das 
Problem erfasst.

Jeder Thread arbeitet zum größten Teil für sich. Es gibt jedoch 
Abhängigkeiten. Nachdem ein Thread fertig ist laufen die 
"Nachbarthreads" an. Da diese Daten benötigen. Ich habe mir mittlerweile 
mit dem "Concurrency Analyser" angeschaut was passiert und auch über 
Flags ausgeben lassen, welche Programmteile wie lange dauern.
Ergebniss ist, dass der gleiche Code im gleichen Thread manchmal länger 
dauert als sonst. Hier habe ich mir einen Code angeschaut, der nicht 
über Mutex oder Condition Variables auf andere Threads warten muss.

Ich denke also, dass das Problem durch Cache misses verursacht wird.
Kann dies von der Verteilung der Threads auf die CPUs abhängen?

Das hätte aber dann ein paar Konsequenzen.
Die Performance von meinem Programm hängt extrem davon ab, welcher 
Thread auf welchem Prozessor läuft.
Das Betriebssystem weißt den Threads bei jedem Durchlauf die gleichen 
Prozessoren zu.

Wenn ich den Prozess neu starte, bekommen die Threads wieder in jedem 
Durchlauf die gleichen Prozessoren zugewiesen, die aber jetzt andere 
sind als beim vorherigen starten.

von (prx) A. K. (prx)


Bewertung
0 lesenswert
nicht lesenswert
Es gibt sehr viele Faktoren, die in die Performance mit hineinspielen, 
und die von Unwägbarkeiten wie beispielsweise Adresslage, zeitlicher 
Verzahnung und Verteilung von Threads auf Cores abhängen, um hier ins 
Blaue sinnvoll spekulieren zu können. Caches sind auch nur ein Aspekt 
von mehreren. Für sowas haben CPUs Performance Counter, die einen 
Hinweis darauf geben können, wo die Engstelle sitzen könnte.

von jibi (Gast)


Bewertung
0 lesenswert
nicht lesenswert
>Wie würde ich das machen, wenn ich erst während der Laufzeit weiß, wie
>viel Speicher ich benötige?

Na da schaut man sich den Speicherverbrauch einiger Durchgänge an, 
darauf addiert man sich noch ein bisschen Überschuss und schon kannst du 
den Speicher vorher festlegen. Das eventuell ein bissel Speicher 
ungenutzt bleibt ist wohl bei den heutigen üblichen 16GB zu 
verschmerzen...


Gruß J

von Ruediger A. (Firma: keine) (rac)


Bewertung
0 lesenswert
nicht lesenswert
A. R. schrieb:
> Jeder Thread arbeitet zum größten Teil für sich. Es gibt jedoch
> Abhängigkeiten. Nachdem ein Thread fertig ist laufen die
> "Nachbarthreads" an. Da diese Daten benötigen. Ich habe mir mittlerweile
> mit dem "Concurrency Analyser" angeschaut was passiert und auch über
> Flags ausgeben lassen, welche Programmteile wie lange dauern.
> Ergebniss ist, dass der gleiche Code im gleichen Thread manchmal länger
> dauert als sonst. Hier habe ich mir einen Code angeschaut, der nicht
> über Mutex oder Condition Variables auf andere Threads warten muss.

Was genau meinst Du mit "Concurreny Analyzer?" Kann das auch ISRs mit 
aufzeichnen?

Wenn das bei Dir geht (Du brauchst ein bisschen Extra RAM), lad mal von 
percepio.com den tracealyzer runter und zeichne damit auf. Ich vermute, 
dass es asynchrone ISRs sind, die Dir dein Zeitverhalten zerschiessen, 
das kannst DU mit der tracealyzer Visualisierung sehr schön sehen

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.