Das ist jetzt mehr ein Laber-Thema, so dringend ist das nicht.

Ich beschäftige mich zur Zeit etwas damit, wie man Laufzeiten von Algorithmen sehr genau bestimmen kann. Erster Ansatz war nattürlich GetTickCount. Das ist zu ungenau, und ich bin auf QueryPerformanceCounter gestoßen. Das läuft ganz gut, nur habe ich dabei regelmäßig Aussetzer. D.h. ein Algorithmus läuft schön ruhig in 30-40µs durch, und beim nächsten Mal auf einmal ne halbe Millisekunde. Das lässt sich nicht durch "Worst-Case" erklären sondern eher dadurch, dass Windows den Algorithmus pausiert hat und zwischendurch ein anderer Prozess werkeln durfte. Das macht das Bild kaputt, und lässt sich auch nicht durch mehrere Iterationen rausmitteln.

Dann bin ich auf GetProcessTimes gestoßen, was so überhaupt nicht funktioniert hat (den Grund kann man in der DP ab da nachlesen. Die Zahlen dabei werden zwar in 100ns-Schritten angegeben, aber die werden nur alle ca. 10ms erneuert - dann könnte ich auch Sandkörner mit nem Zollstock vermessen.

Ich suche also nach einer Möglichkeit, im Mikrosekunden-Bereich die Zeit zu ermitteln, die mein Prozess gearbeitet hat. Mit QueryPerformanceCounter und SetPriorityClass(GetCurrentProcess, REALTIME_PRIORITY_CLASS); geht das zwar ganz passabel - aber ich sehe es schon kommen, dass ein neuer Algorithmus in eine Real-Time-Enddlosschleife reinläuft, was etwas suboptimal wäre...

Also...ich bin offen für andere Ansätze .

Ich glaube nicht, dass du unter ms in Windows kommst.
Dafür brächtest du wohl ein BS, dass auch für Realtime ausgelegt ist.

Evtl. kannst du auch bei einem Multiprocessor-System einen Kern für dich reservieren... aber ich spreche jetzt rein
theoretisch. (nie versucht, nie gemacht)

Was mir aber nebenbei so einfällt.
Assembleranweisungen werden doch in Taktzyklen ausgeführt?
Z.B. hat MOV 3 Taktzyklen (oder 2... don't know)

Vielleicht lässt sich über die Gesamtzahl der Taktzyklen ein theoretischer Wert ermitteln?
(aber das ist jetzt reine Annahme)

Nur mal so eine Idee von mir:

Man könnte beim Aufruf eines Algorithmus die Prozesszeit auslesen (Frag aber nicht, wie das gehen soll ) und nach Beendigung ein weiteres mal. Diese Werte Ziehst du voneinander ab und hast die gesuchte Zeit (ich hoffe, das ganze geht auch im Millisekundenbereich oder vll auch kleiner ).

Mit der Prozesszeit meine ich die Zeit, die das Programm der CPU zugeordnet wurde. Unter Linux kann man sich die per "top" ansehen, wobei das evtl. auch unter Windows funktionieren sollte. Das sollte ja dann eigentlich ausreichen für eine genauere Zeitangabe.

Nur habe ich wie gesagt keine Ahnung wie man das Auslesen anstellen kann. sry

Ich hoffe trotzdem dir mit dem Ansatz etwas helfen zu können.


Bye
M4X1

Warum nimmtst du nicht den Durchschnittswert von 10^n Messungen? Da müsste doch auch irgendwas sehr genaues rauskommen. Ich denke, es versteht sich, den Prozess als "Echtzeit-Prozess" zu deklarieren. Sonst ist es klar, dann bekommen andere Prozesse Vorrang.

opfer.der.genauigkeit hat folgendes geschrieben:

Ich glaube nicht, dass du unter ms in Windows kommst.

Mit QuerPerformanceCounter schon - aber das hängt von der Hardware ab, wenn ich das richtig verstehe.

opfer.der.genauigkeit hat folgendes geschrieben:

Was mir aber nebenbei so einfällt. Assembleranweisungen werden doch in Taktzyklen ausgeführt? Z.B. hat MOV 3 Taktzyklen (oder 2... don't know) Vielleicht lässt sich über die Gesamtzahl der Taktzyklen ein theoretischer Wert ermitteln? (aber das ist jetzt reine Annahme)

Also theoretisch kann man die Algorithmen in 2 oder 3 Klassen einteilen, die dann alle gleich schnell sind. Die Laufzeiten hängen von drei Größen ab, jeweils mit unterschiedlichen Konstanten (die sich mehr oder weniger optimieren lassen), und die mal als Faktor, mal als Divisor und mal als Basis zum Logarithmus eingehen (die CPU-Registergröße lasse ich der Einfachheit weg, die spielt bei einer Klasse auch noch eine Rolle). Das theoretisch zu berechnen, und wann welcher besser ist, ist praktisch unmöglich. Daher die praktischen Tests (die sich bisher qualitativ auch erstaunlich gut mit den Ergebnissen in entsprechender Literatur decken ).

M4X1 hat folgendes geschrieben:

Man könnte beim Aufruf eines Algorithmus die Prozesszeit auslesen (Frag aber nicht, wie das gehen soll ) und nach Beendigung ein weiteres mal.

Genau das macht man mit GetProcessTimes - Genauigkeit: ~10ms, vieeeeel zu grob.

Yogu hat folgendes geschrieben:

Warum nimmtst du nicht den Durchschnittswert von 10^n Messungen?

Sagen wir mal so. Eine der drei erwähnten Größen lasse ich konstant (z.B. 1MB). Die anderen beiden lasse ich von 1 bis ungefähr 100 laufen. Macht 10.000 Messungen. Das mal 10 Algorithmen, sind 100.000. Manchmal brauchen die Dinger auch ein paar(-hundert) Millisekunden - wenn ich da jetzt mehr als ca. 10 Iterationen reinbaue, dann läppert sich das ganz schnell zusammen (die sehr kleinen Zeiten kommen nur bei einigen Algorithmen und nur bei großen Werten )

Aber danke schonmal für die Vorschläge - auch wenn sie mich bisher nicht weiterbringen .

Also wenn du wirklich auf so niedriger Ebene messen willst, dann geht das nur mit speziellen Profilern wie zB VTune von Intel. Damit kannst du diverse CPU performance counter messen - angefangen von Zyklen, über Anzahl der Instruktionen, Branch misspredictions, ect...
Leider ist das Ding nicht gerade billig, aber du kannst es 30 Tage lang testen. Für Windows kenn ich leider keinen vernünftigen kostenlosen Profiler, für Linux gibt es zB PAPIEX.

Gruß, Motzi

Motzi hat folgendes geschrieben:

Leider ist das Ding nicht gerade billig, aber du kannst es 30 Tage lang testen.

Wo ich das gerade les: AMD's CodeAnalyst ist kostenlos und misst im µs-Bereich. Joachim Rhode verwendet ihn in seinem Buch "Assembler".

Guter Hinweis! Ich hab CodeAnalyst bis jetzt noch nicht verwendet, soll aber auch recht gut sein (vor allem dafür, dass es kostenlos ist). Der einzige Nachteil: auf Intel System funktioniert nur das timer based profiling, aber kein event based profiling. VTune lässt sich dafür gar nicht erst auf Nicht-Intel-Maschinen installieren.

Hi,

Yogu hat folgendes geschrieben:

Warum nimmtst du nicht den Durchschnittswert von 10^n Messungen? Da müsste doch auch irgendwas sehr genaues rauskommen. Ich denke, es versteht sich, den Prozess als "Echtzeit-Prozess" zu deklarieren. Sonst ist es klar, dann bekommen andere Prozesse Vorrang.

Also die Idee finde ich ersteinmal gut...
Wenn ich die Posts richtig überflogen habe geht es bei der einen Methode ja nurnoch darum, dass Windows den Prozess schlafen legt.
Mit der mittleren Laufzeit einiger weniger Prozesse müsste das doch aber schon raus sein, oder?
Also explizit Extremwerte rauslassen.

mfG,

Für die Zeitmessung von Algorithmen gelten im Wesentlichen immer 2 Regeln:

1. Mess mehrfach
   
2. Sorg dafür, dass die gemessene Zeit ein Vielfaches der eigentlichen Laufzeit ist.

1. sollte klar sein: Mess 5-10 mal einen Durchlauf.

Das Zweite ist komplizierter zu verstehen, bezieht sich aber auf die "Sandkörner mit Zollstock messen"-Aussage: Wenn Du nicht messen kannst, wie lange ein Durchlauf brauch, mess einfach wieviel Zeit N durchläufe brauchen.

Soviel zur Theorie ... Nun zur Praxis:

1. Messen ist gut, Vermessen ist häufig
   
2. Zeiten auf einem Multitasking-System sind IMMER ungenau
   
3. Sorg dafür, dass deine Zeitscheibe frisch ist

1. ist soweit klar (hoff ich mal), 2. ergibt sich aus der Tatsache, dass andere auch mal dran kommen wollen. Wobei 2. nur gilt, wenn man Teile des Systems hat, die nicht kooperativ am Multitasking beteiligt sind. Dies trifft z.B. bei DOS zu: Unter DOS ist jegliches "Multitasking" IMMER kooperativ, solange keine Hardware-Interrupts aktiv sind. Sobald diese aktiv werden, hat man preemptives Multitasking.

Nun zu 3.: Es gibt unter Windows ein Feature (manche würden es auch "Bug" nennen), mit dem ein Prozess (selbst OHNE Realtime-Priority!!!) unendlich lange Zeit bekommt auf der CPU zu laufen. Dafür muss man nur häufig genug SetThreadPriority aufrufen, ohne seine Priorität zu ändern.

Was lehrt uns das?

1. QPC nehmen
   
2. Algorithmus mehrfach ausführen
   
3. SetThreadPriority for jedem Algorithmus-Durchlauf aufrufen
   
4. weitere Zeitmessungsmethoden verwenden
   
5. Werte, die außerhalb der Varianz liegen, aus der Messung entfernen.

Dann klappt's auch mit der Zeitmessung

Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.

BenBE hat folgendes geschrieben:

Werte, die außerhalb der Varianz liegen, aus der Messung entfernen.

Müsstest du IMHO nicht, wenn du es machst, wie in der Statistik üblich.
Modalwert, arithmetisches Mittel, Median.
Jeder Wert hat Vor- und Nachteile, der eine ist stabiler gegen Extremwerte, der andere weniger usw.
Zumal bei einer häufige Wiederholung der Messung sich auch Extremwerte einpendeln.
Ist ja bei Wahrscheinlichkeitsrechnung das Gleiche.

Das ganze kannst du dann noch grafisch darstellen und alle sind glücklich.