wie laufzeit am genausten messen?



  • hiho,

    die frage ist wahrscheinlich ein bisschen schräg aber ich weiss ehrlich gesagt nicht, wie ich die laufzeit einer funktion gut messen kann. was klar ist, ist, dass ich die funktion wiederholt ausführe und jedes mal neu messe, damit ich eine verwertbare messprobe vorliegen habe. aber wenn ich verschiedene modifikationen der funktion vergleichen möchte in ihrer performance, welche werte muss ich dann verwenden? arithmetisches mittel? mittel ohne ausreisser? median? oder gar das minimum?

    LG!



  • Was meinst du mit "verschiedene Modifikationen"? Unterschiedliche Parameter? Dann hängt es natürlich davon ab, welche Modifikation du häufig aufrufst und welche nicht. Spannend ist natürlich auch immer die Variante, die im Durchschnitt am längsten braucht.

    Wenn du ein und dieselbe Sache genügend oft misst, sollte sich eigentlich irgendwie ein Gauss um den Erwartungswert der Dauer ergeben.

    Du könntest zum Messen z.B. https://github.com/google/benchmark benutzen.



  • mit modifikationen meine ich, dass ich die funktion modifiziere. also dinge ändere, von denen ich zum beispiel glaube, dass sie die funktion schneller machen.

    meine frage ist, welchen wert ich dann optimieren soll: den median, das arithmetische mittel oder das minimum. (und ob ich "ausreisser" gezielt eliminieren soll)

    profiler und frameworks dazu sind mir durchaus bekannt, es interessiert mich aber auch von einer theoretischen seite her: welcher parameter ist in so einer situation am verlässlichsten.



  • Man kann nicht richtig verstehen, was du brauchst<"



  • Wenn du signifikante Unterschiede zwischen Median und Mittelwert hast, hast du nicht genügend oft gemessen.

    Wie lange dauert denn bei dir eine Messung? Musst du 1 Mio mal messen, um Ergebnisse im Sekundenbereich zu bekommen? Dann ist es kein Problem, einfach oft genug zu messen, sodass seine Frage keine Rolle mehr spielt.

    Dauert deine Messung dagegen 1 Stunde und eine zweite nur 50 Minuten, dann reicht das doch schon aus, um zu sehen, welche Variante schneller ist.

    Ansonten gilt wie immer: kommt darauf an, was du genau wissen willst. Wieso hast du überhaupt große Ausreißer? Was misst du eigentlich? Spielen externe Effekte eine Rolle?



  • Ich messe meistens "von Hand". D.h., zuerst einen Test schreiben, der die zu testende Funktion so oft aufruft, dass der Test ingesamt lang genug dauert, z.B. 10 Sekunden. Irgendwas im Nanosekundenbereich einzeln zu messen, macht keinen Sinn.
    Dann lasse ich das vielleicht 10-20 mal laufen und schaue, obs Ausreißer gibt. Die versuche ich zu ignorieren. Dann pendelt sich das ganze schnell ein. Ich hatte damit bisher eigentlich noch nie Probleme. Die Werte waren immer recht stabil, und wenn man was optimiert hatte, dann waren sie stabil niedriger.



  • Eine mMn. gute Variante ist die Messung so lange zu wiederholen, bis nach N (z.B. 100) Versuchen kein schnellerer Durchlauf mehr gefunden wurde als in allen Versuchen davor.
    Damit bekommt man halbwegs stabile Werte und es lässt sich einfach automatisieren.

    Eine andere Variante ist es den Mittelwert zu nehmen. Wobei ich dazu tendiere Ausreisser zu ignorieren, da einem fast immer das OS irgendwie dreinpfuscht. Diese Werte sind dann allerdings oft nicht ganz trivial zu vergleichen, vor allem wenn die Standardabweichung gross ist und die Mittelwerte knapp beieinander liegen.



  • Man könnte auch ein Histogramm erstellen, und ein paar Grundwerte nebeneinanderstellen, jeweils niedrigster Wert, höchster Wert, Bandbreite, Anzahl der Ausreißer usw.

    Oder einfach eine Tabelle bzw. mehrere, (mit den stabilsten Werten) siehe auch:
    https://www.bernd-leitenberger.de/benchmark.shtml



  • hustbaer schrieb:

    Eine mMn. gute Variante ist die Messung so lange zu wiederholen, bis nach N (z.B. 100) Versuchen kein schnellerer Durchlauf mehr gefunden wurde als in allen Versuchen davor.

    Vom lieben Volkard, diese Methode.



  • Wäre es nicht sinnvoll den Code mit "g++ -s" zu kompilieren und dann das Assembly auszuwerten. Da kann man dann doch genau zählen wie viele Schritte der Prozessor für deine Funktion benötigt.
    Dann ist egal, was dein Rechner zum Zeitpunkt der Messung noch zutun hat und mit dem richtigen Script funktioniert die Auswertung auch viel schneller.

    - so meine Theorie. Klärt mich bitte auf, wenn ich falsch liege.



  • Du liegst falsch, weil das Zählen nicht viel hilft.

    Generell gilt zwar: weniger Schritte sind besser als mehr. Aber die Schritte sind einerseits nicht gleich schnell und andererseits können moderne Prozessoren ggf. mehrere Schritte zur selben Zeit ausgeführen. Dann gibts noch so Dinge wie einen Branch-Predictor. Außerdem musst du noch schauen, welche Daten gerade im Cache sind. Kurzum: wenn du deinen Prozessor ganz exakt kennst, mag es mit viel Aufwand möglich sein, alle Effekte genau zu erkennen und den Code zu analysieren. Aber wer kennt seinen Rechner schon so exakt?

    Also ist messen die bessere Alternative.


  • Global Moderator

    Wie viele CPU-Schritte braucht denn folgender Code?

    push    rbp
            mov     rbp, rsp
            mov     DWORD PTR [rbp-4], edi
            mov     eax, DWORD PTR [rbp-4]
            imul    eax, DWORD PTR [rbp-4]
            pop     rbp
            ret
    

    Die Antwort ist nicht 7.

    (Bevor jemand fragt: Ich weiß die Antwort auch nicht (genau), ich weiß nur mit Sicherheit, dass sie nicht 7 ist.)



  • Das bringt auch nichts, weil man oft schleifen hat usw. Und Code, der alle möglichen anderen Funktionen aufruft. Wenn du Millionen von Datensätzen verarbeitest, wie willst du in Assembler erkennen, dass ein Hash Lookup viel bringen würde gegenüber einer linearen Suche?



  • SeppJ schrieb:

    Wie viele CPU-Schritte braucht denn folgender Code?

    push    rbp
            mov     rbp, rsp
            mov     DWORD PTR [rbp-4], edi
            mov     eax, DWORD PTR [rbp-4]
            imul    eax, DWORD PTR [rbp-4]
            pop     rbp
            ret
    

    Die Antwort ist nicht 7.

    (Bevor jemand fragt: Ich weiß die Antwort auch nicht (genau), ich weiß nur mit Sicherheit, dass sie nicht 7 ist.)

    Ich hab 22 bis 26 gezählt bei AMD K7 xD



  • Arcoth schrieb:

    hustbaer schrieb:

    Eine mMn. gute Variante ist die Messung so lange zu wiederholen, bis nach N (z.B. 100) Versuchen kein schnellerer Durchlauf mehr gefunden wurde als in allen Versuchen davor.

    Vom lieben Volkard, diese Methode.

    Hab ja auch gar nicht behauptet es erfunden zu haben 😃

    Ja, ich glaub ich hab das beim volkard das erste mal gesehen. IIRC hat es aber auch camper mal gepostet. Wo er es her hat weiss ich natürlich nicht, kann sein auch von volkard übernommen kann sein von woanders bzw. selbst ausgedacht.


  • Global Moderator

    Zeus schrieb:

    Ich hab 22 bis 26 gezählt bei AMD K7 xD

    Das ist ja auch noch geradezu eine einfache Architektur 😃 🙂



  • Oder nehmen wir 68K, da gibt's super einfache Zyklen Tabellen. Damit lässt sich alles exakt bestimmen. Also so lange wir nicht Shiften oder Dividieren oder ... ach, Mist 🤡



  • also unter windows gibts den performancecounter mit einer genauigkeit von (bei mir) 250 ns. das reicht normalerweise aus.
    unter linux gibts clock_gettime.

    wenn du dem prozess dann auch noch echtzeitprioritäten gibst, sollte sich die anzahl der extremen ausreißer sehr gering halten.



  • hustbaer schrieb:

    IIRC hat es aber auch camper mal gepostet.

    Und wenn ich mich recht erinnere, hat Volkard dann gefragt, ob camper es denn von ihm hat, und er meinte, das wäre möglich. Kann den Thread natürlich nicht finden.