Kriege gewaltige Unterschiede raus
Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Time zum Benchmark ungeeignet??
Gibt es ein Programm mit zuverlässigen Benchmarks, oder bin ich einfach zu blöd time zu bedienen?
öhm…du solltest es ein wenig mehr umschreiben 
Wie oft hast du es denn ausgeführt? Hast du es mal 5x hintereinander in einer schleife laufen lassen und den mittelwert genommen? Wo läuft das pro denn (im cip kannste nicht benchmarken)? Auf was für nem system (CPU, OS, etc)…
Aber um zur frage zurückzukommen…doch time ist bestimmt geeignet :-p
time ./wsort < wlist1 > blabla.txt
aber zum optimalen benchmark brauchste nen rechner wo sonst nix läuft. im cip benchmarken geht also nich wirklich.
aber jetzt wo wir schon bei zeiten sind, was sind eure zeiten so?
mein wsort is bei wlist5 schneller als das beispielprogramm “fsort”.
Da ich aber nix über dessen implementierung weiss, bringt mir das nix :>
time liefert 3 Zeitwerte:
user time: Rechenzeit des Prozesses im Anwendungsmode (d.h. waehrend der Prozess Code
den der Benutzer programmiert hat, ausfuehrt)
system time: Rechenzeit des Prozesses im Systemkern (d.h. waehrend der Prozess Code des
Betriebssystems ausfuehrt - z.B. fuer Ein-/Ausgabeoperationen)
(Details ueber Anwendungs- und Systemmodus kommen am naechsten Do. in der Vorlesung dran).
und als drittes die real vergangene Zeit.
Die ersten beiden Werte sind relativ unabhaengig von der Systemlast (das ist nur die
von genau dem Prozess verbratene Zeit, egal ,wie lang das tatsaechlich gedauert hat -
Schwankungen entstehen durch Ungenauigkeiten in der Erfassung der Rechenzeit -
das Betriebssystem guckt einfach alle 10ms mal nach, wer grade dran ist und bucht dem dann
10ms auf sein Konto).
Der dritte Wert kann abhaengig von der Last auf der Maschine sehr stark schwanken.
user time ist damit eigentlich ein ganz guter Anhaltspunkt, wie effizient das eigene Programm
kodiert ist.
Naja ist auch nicht so wirklich zufriedenstellend. Vorhin war so ich bei 300 und jetzt sind noch so 220. => fau05a. (unverändertes Programm)
Gibt es keine Möglichkeit einen Zuverlässigen Benchmark auszuführen, der alle Takte mitzählt?! Da gibt’s doch sicher was…
Naja werd den Code noch ein wenig optimieren. (Mit getchar werd ich wohl keinen Geschwindigkeitsrekord aufstellen können. 
- zumindest nicht ohne -O3)
Wenn du ordentlich benchen willst, musst du die Ausgabe in eine Datei umleiten. Die Ausgabe der Liste in der Shell sorgt besonders bei größeren Sachen für ziemliche Zeitunterschiede.
Aqua
Müsste das nicht unabhhängig davon sein, da das ja aufgabe der sh ist? Aber unabhängig davon hab ich es in eine Datei geleitet. Da ich über ssh drin bin dauert die Ausgabe etwas länger.
Eigentlich müsste das ja über gdb möglich sein, aber da hab ich mich noch nicht eingearbeitet.
Bin zu blöd für Time
Was mache ich falsch:
faui05a [~/aufgabe2]> time --version
–version: Command not found.
0.000u 0.000s 0:00.00 0.0% 0+0k 0+0io 0pf+0w
Wieso erkennt er das - / – nicht?
schätze time ist ein builtin command der Shell.
Probier mal
/usr/bin/time --version
das ist time(1).
(siehe “man tcsh”, Zeile 2694)
GNU time hat einen --version Parameter. Aber time ist auch ein eingebautes Kommando in der Bash. Gib mal which time ein und führ die Datei mit explizitem Pfad (/usr/bin/time) aus, dann verwendet er auch das Programm time…
edit Zu langsam… wie immer. :-p
edit 2 Anscheinend nicht nur Bash.
@mute: deleted
Aber zurück zum interessanten Thema: Optimieren. 
Mein Programm braucht für die wlist5 4.590s user time, während fsort 1.289s braucht… Laut gprof verbringt es die meiste Zeit (welch Wunder) mit den Sortieren. Aber was kann man da noch optimieren? Auf qsort() und strcmp() hab ich ja keinen Einfluss…
hmmm also wenn ich meins im cip laufen lass komm ich auf 4.180s gegen 2.510s mit der wlist5 … allerdings hab ich vorhin mitbekommen, dass man es sogar schneller als das fsort schaffen kann … nur ich frage mich wie das gehen soll?!?
Ich komm auf 3,2 User-sekunden. An Qsort kannst du nicht viel Optimieren. Wo du allerdings optimieren kannst, und wie ich festgestellt hab nicht zu wenig (13s → 3,2s), ist das Einlesen und Ausgaben. Und ich vermute mal das Speicher allocalisieren auch noch seine Zeit braucht. Fas ich beim Microcontroller festgestellt habe, ist dasa es welten zwischen folgenden Zeilen sind:
Var1.
i1 = 2
i2 = i1+1;
for(…){
irgendwas = arr[…][i1];
irgendwas2 = arr[…][i2];
// Weitere Rechnungen mit i1, i2
}
Var2:
i1 = 2
for(…){
irgendwas = arr[…][i1];
irgendwas2 = arr[…][i1+1];
// Weitere Rechnungen mit i1, i1+1
}
Var2 ist erheblich schneller (relative Speichersprünge)- aber dazu braucht man den ASM-code mit C-Kommentierung. Bei dem AVR-Makefile wird das automatisch gemacht, aber ich hab noch nicht so ganz rausgefunden welcher Parameter wofür zuständig ist.
Eine weiter optimirungsfunktion ist auf funktionen zu verzichten (dies trifft auf -o2 weniger und auf -o3 nicht mehr zu), und if-abfragen so zu optimieren, dass es möglichst wenig sprünge gibt.
Soviel zu meinem Wissen als nicht - Informatiker…
P.s.: Optimieren brings mich auch nur noch auf 3,1. Und die Einzige Optimierung die mir jetzt noch einfällt geht doch arg zu Lasten des Arbeitsspeichers.
Einlesen und Ausgeben hab ich eigentlich schon gnadenlos durchoptimiert (glaube ich)… Wenn ich die Sortierfunktion auskommentiere, also effektiv ein echo aus dem Programm mache, läuft es in 0.429s für wlist5.
Ich hab mal testweise den Puffer groß genug gemacht, dass er die komplette wlist5 auf ein Mal packt. Das spart ein paar ms, aber keine 3s um auf die 1.3s zu kommen, die fsort bei mir braucht…
Funktionen weg lassen sollte nur was bringen, wenn eine Funktion sehr oft aufgerufen wird… Das sind aber bei mir wieder die qsort() und strcmp(). Alle anderen werden nur 1x aufgerufen.
der vergleich zu fsort bringt eigentlich nich viel solange man nichts über dessen implementierung weiss. Es kann sein, dass fsort so sachen wie “lines über 100 zeichen raus” oder sowas nicht realisiert hat, und somit weniger if’s beinhaltet, was widerum zeit spart.
iceweasel: 0.429 sekunden für wlist5?
Wenn das Programm nur einliest und wieder ausgibt, ohne zu sortieren. Damit wollte ich überprüfen, ob der Engpass bei der Ein-/Ausgabe liegt.
Doch das ist schon realisiert. Einfach ausprobieren 
Aber ihr werdet tatsächlich schaun müssen dass *alloc seltener durchlaufen wird, auch wenn ihr evtl mehr Speicher belegt als nötig…
Interessanterweise macht es fast keinen Unterschied, ob ich einen Puffer für 1024 Zeilen oder einen für 102400 Zeilen reserviere… Ich hab sogar den Eindruck (ohne time oft genug ausgeführt zu haben), dass ein kleiner Puffer schneller läuft… :vogel:
komme für wlist5 auf 2.510 user vs 1.780 user für fsort. wie schon gesagt wurde, fsort checkt auch auf zu lange zeilen usw. und gibt auch die länge noch zusätzlich mit an, sollte das wort zu lang sein.
“verschwende” jedoch keinerlei speicher, es wird genau soviel angefordert und benutzt entsprechend der eingabemenge. da könnte man sicher noch ein wenig was optimieren, wenn man sich schon immer grössere bereiche im vorraus holt usw, bzw. die expandierung entsprechend dem wachstum abschätzt o.ä. - oder sich anguckt wie & wo der speicher angelegt wird und so möglicherweise gewisse umkopiererein vermeidet (is mir beim debuggen aufgefallen, das er da manchmal unvorteilhaft sich den speicher holt und so dann hin und her schieben muss)
übersetzen mit -O3 oder zB dann ohne -ansi & die ein oder andere funktion als inline zu deklarieren brachte bei mir nur marginale verbesserung- vielleicht auf 2.350 runter ungefährt.
ansonsten verbrat ich ausserdem auch noch um einiges mehr system zeit ungefähr des fünfache wie fsort, fast 0.5s
naja fgets() is glaub ich etwas entfernt von einer optimalen einlesemethode. wenn die files richtig gross werden, kostet das wohl schon.
der code zu fsort wär auf jeden fall mal interessant bzw. nen blick wert irgendwann