3. Seltsame Laufzeit Merge Sort

Seltsame Laufzeit Merge Sort

  • *

    Ich frage mich grad, warum ich vorhin nicht auch meinen Code zur Zeitmessung gepostet habe, whatever!
    Jedenfalls hat meiner im Prinzip das gleiche gemacht. Habe jetzt nochmal deinen Code laufen lassen (64bit Windows, gleicher Compiler, gleiche flags gesetzt) und ich bekomme schon wieder diese seltsame Ausgabe 😞

    `Timing size 5000000: 1.4 s

    Timing size 10000000: 2.7 s

    Timing size 15000000: 4.2 s

    Timing size 20000000: 5.5 s

    Timing size 25000000: 7.2 s

    Timing size 30000000: 8.2 s

    Timing size 35000000: 9.7 s

    Timing size 40000000: 11 s

    Timing size 45000000: 13 s

    Timing size 50000000: 14 s

    Timing size 55000000: 9.9 s

    Timing size 60000000: 11 s `

    Ich habe es dann abgebrochen, sehen aus wie bei mir die Zeiten mit diesem Knick ab 55 Mio... Kann das am Prozessor liegen? Ich habe es auf einem Intel i7 laufen lassen.

    0
  • Mod

    Cassiopeia schrieb:

    Kann das am Prozessor liegen?

    Ja, sehr sogar. Aber keine Ahnung, was hier genau los ist. Ein Programmfehler wird's jedenfalls nicht sein, wenn zwei unabhängige Messungen dieses Ergebnis haben (außerdem sind meine Programme natürlich immer richtig :p ). Ich verschieb's mal in ein allgemeineres Forum, weil das nicht mehr C++-spezifisch ist. Morgen kann ich das Programm auch mal auf einem i7-Linuxsystem testen, falls ich dran denke. Im Moment ist es mir zu spät dafür.

    0
  • C

    Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (auch C++0x und C++11) in das Forum Rund um die Programmierung verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.

    0
  • T

    Steigt bei mir ganz normal an - Centrino 2 Laptop mit 4GiB RAM und Win32.

    0
  • *

    Ich konnte es heute mal auf einem kleinen Laptop mit i3 laufen lassen nebenbei, wieder die Sache ab 55 Mio:

    Timing size 5000000: 2.7 s
Timing size 10000000: 5.3 s
Timing size 15000000: 8 s
Timing size 20000000: 11 s
Timing size 25000000: 14 s
Timing size 30000000: 16 s
Timing size 35000000: 19 s
Timing size 40000000: 22 s
Timing size 45000000: 25 s
Timing size 50000000: 28 s
Timing size 55000000: 18 s
Timing size 60000000: 20 s
Timing size 65000000: 22 s
Timing size 70000000: 24 s
Timing size 75000000: 25 s
Timing size 80000000: 27 s
Timing size 85000000: 28 s
Timing size 90000000: 30 s
Timing size 95000000: 32 s
Timing size 100000000: 33 s
This number must be zero: 0

    Vielleicht läuft bei den i-Prozessoren irgendwas grundlegendes anders, aber da kenn ich mich nicht aus..

    0
  • O

    Stromsparmodus?

    0
  • R

    baust du fuer 32bit? 🙂

    0
  • Mod

    Also ich habe es gerade auch noch einmal auf einem i7, 64-Bit Linux, mit verschiedenen Compilern ausprobiert. Das einzige, was ich gelernt habe ist, dass ich mal meinen Intelcompiler updaten sollte, da die 4.6er Version des GCC ihm deutlich davonläuft. Ansonsten nichts unerwartetes. Das Zeitverhalten ist ziemlich genau C*N*log(N) mit C = 14 Mikrosekunden für Intelcompiler und C = 11 Mikrosekunden für den neuesten GCC.

    Also vermutlich irgendwas lustiges an deinem System.

    0
  • I

    Ebenfalls i7, 64bit Linux, bekannte Flags, kein Knick:

    Timing size 5000000: 0.8 s
Timing size 10000000: 1.6 s
Timing size 15000000: 2.6 s
Timing size 20000000: 3.5 s
Timing size 25000000: 4.3 s
Timing size 30000000: 5.3 s
Timing size 35000000: 6.2 s
Timing size 40000000: 7 s
Timing size 45000000: 8 s
Timing size 50000000: 8.9 s
Timing size 55000000: 9.9 s
Timing size 60000000: 11 s
Timing size 65000000: 12 s
Timing size 70000000: 13 s
Timing size 75000000: 14 s
Timing size 80000000: 15 s
Timing size 85000000: 15 s
Timing size 90000000: 16 s
Timing size 95000000: 17 s
Timing size 100000000: 18 s
This number must be zero: 0

    Interessant ist jedoch, dass ab der Knickstelle Cassiopeias i7 die gleichen Zeiten braucht wie meiner (du kannst ja mal dein Programm weiter laufen lassen, damit wir sehen, ob das so bleibt). Was vorher bei ihm schief gegangen sein könnte, weiß ich aber nicht.

    0
  • L

    Kann es sein, dass dein System erst "aufwachen" muss, also nur bei Belastung die volle Leistung bereitstellt (Stromsparmodus wurde ja schon genannt)? Oder laufen irgendwelche Programme die sich zurückziehen wenn die CPU voll genutzt wird?

    Versuch mal das ganze Testprogramm in einer Schleife 2x hintereinander laufen zu lassen. Wenn es da nur beim 1sten mal einen Knick gibt, könnte es von sowas kommen.

    0
  • *

    rapso schrieb:

    baust du fuer 32bit? 🙂

    Danke! Daran hats gelegen. gcc hat standardmäßig nur für 32bit gebaut bei mir, bei einem 64bit Build verhalten sich die Laufzeiten normal.

    0
  • E

    AMD Phenom(tm) 9500 Quad-Core Processor

    Timing size 5000000: 1 s
    Timing size 10000000: 2.2 s
    Timing size 15000000: 3.3 s
    Timing size 20000000: 4.7 s
    Timing size 25000000: 5.9 s
    Timing size 30000000: 7.2 s
    Timing size 35000000: 8.7 s
    Timing size 40000000: 10 s
    Timing size 45000000: 11 s
    Timing size 50000000: 13 s
    Timing size 55000000: 14 s
    Timing size 60000000: 15 s
    Timing size 65000000: 16 s
    Timing size 70000000: 18 s
    Timing size 75000000: 20 s
    Timing size 80000000: 21 s
    Timing size 85000000: 23 s
    Timing size 90000000: 24 s
    Timing size 95000000: 25 s
    Timing size 100000000: 27 s
    This number must be zero: 0

    Keine Auffälligkeiten. 😉

    0
  • Mod

    Cassiopeia schrieb:

    gcc hat standardmäßig nur für 32bit gebaut bei mir, bei einem 64bit Build verhalten sich die Laufzeiten normal.

    Das finde ich aber trotzdem überraschend. 50 Millionen Integers (oder ein kleines Vielfaches davon, da die Sortierung Out-of-place erfolgt) ist eigentlich nichts besonderes. Und selbst wenn da irgendwas zu groß wird für 32-Bit, würde man doch eher erwarten, dass es wesentlich langsamer wird, nicht schneller.

    Jemand eine Erklärung?

    Wilde Spekulation: Da die Werte über 50 Millionen ungefähr dem entsprechen, was ipsec und ich auf vergleichbaren 64-Bit-i7-Systemen gemessen haben, deine Werte davor aber wesentlich langsamer sind, bremst da wohl irgendetwas bei "kleinen" Zahlen den 32-Bit Code aus. Oder es hat eine Optimierung, durch die der 64-Bit Code wesentlich schneller ist. Und bei ~50 Millionen beginnen andere Effekte zu dominieren, wie z.B. die Speicherbandbreite, so dass man immer die gleiche Laufzeit erhält, egal was der Code genau macht. Du hast nicht zufällig Lust, da mal nach Cachemisses u.ä. zu profilen?

    Ich kann auf meinem System den Effekt jedenfalls nicht nachvollziehen. Das einzige, was ich beobachte ist, dass der 32-Bit Code deutlich langsamer ist, aber konstant über alle Größen. Vielleicht spielen da aber Feinheiten der Systemkonfiguration eine Rolle, z.B. könnte mein Arbeitsspeicher schneller oder langsamer sein und der Übergang bei viel größeren oder kleineren Zahlen erfolgen.

    0
  • *

    SeppJ schrieb:

    Du hast nicht zufällig Lust, da mal nach Cachemisses u.ä. zu profilen?

    Mich würde auch interessieren, was genau das verursacht, leider weiß ich nicht, wie ich unter Windows sowas profilen kann ohne valgrind (bin noch neu in dem Gebiet). Ich habs nochmal unter Linux getestet (auf dem gleichen Rechner), da konnte ich das Problem nicht reproduzieren, egal ob 32bit- oder 64bit-Build.

    0
  • Mod

    Dann würde ich schonmal vermuten, dass das keine Sache der Hardware oder deines Programms ist und du da mit Profilen sowieso kein Ergebnis bekommst. Das ist irgendwas dummes von Windows.

    0
Anmelden zum Antworten