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?
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!
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::).
@ 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.
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.
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.
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.
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.
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.
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.
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.
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.
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
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.
>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.
>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ß
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.
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!
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
>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.
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.
>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
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
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.