Wenn ich nur alle 100 wörter anstatt bei jedem mein Hauptfeld reallocate spare ich 0.3-0.5 sekunden. Erhöh ich das noch mehr, wird die Ersparnis minimal. Aber naja, bin mal gespannt was in der Übung erzählt wird 
edit: finds übrigens sehr gut, dass hier auch direkt vom SoS1-Team ratschläge und tipps gegeben werden. thumbs up
Jetzt wird’s ja immer toller… wenn ich mein Programm auf einen Rechner im CIP-Pool kopiere und über SSH da ausführe, braucht’s gleich 12.5s während fsort immerhin 2.8s braucht. ??WTF??
fread() mit grösserem buffer, der notfalls nur ein paarmal erweitert und am schluss auf die richtige grösse geändert wird & bissel ptr-arithmetik für die behandlung der gelesenen “rohdaten”, sowie die sicherheit dass keinerlei daten rumkopiert werden bringt mir ziemlich genau den gleichen speed wie fsort im moment: 0.05 - 0.1 langsamer für wlist5 (1.710 vs 1.780)
wenn ich zusätzlich noch mit -O3 compile is sogar leicht schneller 
aber noch alles -ansi konform, also kein inline
gcc -ansi -pedantic -D_POSIX_SOURCE -Wall -Werror -O3 …
ich würde drauf tippen daß das was mit dem paging des betriebssystem zu tun hat. wenn dein speicher größer als ne speicherseite ist muss das os zwischen seiten schalten soweit ich das verstanden habe
was macht denn -O3 eigtl.?
Sodale. Habe heute “unfreiwilligerweise” meine Freizeit damit verbracht nochma wsort umzucoden. Ihr kennt das ja, man fängt 19:00 an und zack isses mitternacht.
Wenn ich mit reiner speicheraddressierung rechne, d.h. fast keine mallocs, komm ich ganz ganz knapp an fsort ran. Der bremsende Punkt ist hier wahrscheinlich fgets. Wenn ich fread nehmen würde, könnte es hinhauen. Das Prinzip is einfach, man malloced nen großen Speicherbereich und schreibt alle Strings hinternander. Die listen elemente kriegen dann die anfangspositionen der einzelnen Strings. Das geht ohne weiteres, da strcmp nur bis zum “\ 0” liest. Wer also absolut nicht zufrieden mit den Werten seines Programms ist sollte somit den nötigen Speed erhalten.
Ein anderer erstaunlicher speedboost ist folgender: Anstatt malloc(101*sizeof(char)) oder ähnliches zu machen, versucht nur den Bereich zu allocaten den ihr für euren String braucht, also mit strlen. das bringt gute 700 ms auf der faui05 maschine, falls ihr das nicht ohnehin schon so habt.
gruss und gut nacht
Danke für die Tipps. Schade, dass fgets nicht gleich noch die länge zurückliefert. 
/me wird sich wohl doch noch mal hinsetzen und ein paar Stündchen an seinen Zeilen basteln.
P.s: Hab grade die Einleitunng zu gprof überflogen. Das klingt ja sehr vielversprechend. Da wird wohl wirklich noch ein wenig Zeit drauf gehen…
frustriert gprof hat die selben Probleme wie time: 80% der Zeit gehen auf meine wrapper-funktion und 8% auf strcmp - was ja irgendwie nicht sein kann. Und im CIP krieg ichs gar nicht zum laufen. Die gmon.out wird zwar generieret aber gprof kann nichts damit anfangen. => Kompatibilitätsproblem?! :#:
jup hatte auch mal gprof im cip probiert, scheint irgendwie nicht zu gehn, sowohl mit cc als auch gcc mit -pg compiled, er erzeugt zwar eine gmon.out, beim aufruf von gprof jedoch sagt er immer: ‘gmon.out file is missing call-graph data’
komische sache, weiss da jemand näheres drüber?
fsort version 2
Ich habe auch mal fsort mit gprof untersucht.
time seconds seconds calls Ts/call Ts/call name
47.04 0.15 0.15 main
40.76 0.28 0.13 cmp_fkt
12.54 0.32 0.04 frame_dummy
So wie es scheint wird viel Zeit in cmp_fkt verbracht. Darum habe ich diese Funktion mal
einwenig verbessert. Das Result ist /proj/i4sos/pub/aufgabe2/fsort2
faui05d [fsort]>/usr/bin/time -p ./fsort2 < /tmp/wlist5.wawi > /dev/null
real 2.39 - 2.47
user 2.34 - 2.38
sys 0.06 - 0.10
faui05d [fsort]>/usr/bin/time -p ./fsort < /tmp/wlist5.wawi > /dev/null
real 2.71 - 2.78
user 2.51 - 2.58
sys 0.09 - 0.18
Ich denke das auch in fsort2 noch viel Luft drin ist. Wer will kann ja mal mit
allen Mitteln versuchen schneller zu werden, bitte eine solche Lösung dann in einer
getrennten Datei als fsort.c abgeben und nicht als wsort.c. :cheesy:
darauf hab ich gewartet, hehe
[code]faui05d [aufgabe2]> sote -s wl/wlist5
------- sort-test -------
speed test only: stdout > /dev/null
sorting with: /proj/i4sos/pub/aufgabe2/fsort2
2.350u 0.040s 0:02.39 100.0% 0+0k 0+0io 113pf+0w
sorting with: ./bin.i386/wsort
2.520u 0.140s 0:02.68 99.2% 0+0k 0+0io 114pf+0w[/code]
mal schaun ob mir noch was einfällt… 
btw, wie hast du genau im cip compiled um gprof zu verwenden… einfach mit -pg?
wie gesagt, haut nicht ganz hin, s. mein voriges posting
auf faui01 schauts etwas schöner aus 
[code]faui01 [aufgabe2]> sote -s wl/wlist5
------- sort-test -------
speed test only: stdout > /dev/null
sorting with: /proj/i4sos/pub/aufgabe2/fsort2
0.760u 0.020s 0:00.77 101.2% 0+0k 0+0io 112pf+0w
sorting with: ./bin.i386/wsort
0.830u 0.010s 0:00.83 101.2% 0+0k 0+0io 113pf+0w[/code]
mir ist grad was aufgefallen:
[code]faui05d [aufgabe2]> sote wl/wlist5
------- sort-test -------
normal test incl. comparing
sorting with: /proj/i4sos/pub/aufgabe2/fsort
2.540u 0.390s 0:03.13 93.6% 0+0k 0+0io 111pf+0w
sorting with: /proj/i4sos/pub/aufgabe2/fsort2
2.410u 0.290s 0:02.86 94.4% 0+0k 0+0io 111pf+0w
comparing…
41379a41380
attach
41388d41388
< attach
84882a84883
chteau
86158d86158
< chteau
450162a450163
rhnetal
450247d450247
< rhnetal
595273a595274,595280
varieté
varietéauffuehrung
varietés
varietétheater
varietétheatern
varietévorstellung
varietévorstellungen
595297,595303d595303
< varieté
< varietéauffuehrung
< varietés
< varietétheater
< varietétheatern
< varietévorstellung
< varietévorstellungen
cleaning…[/code]
haha, das kenne ich. man optimiert und optimiert endlos und schickt ständig alles an /dev/null ohne überhaupt zu prüfen obs noch sortiert
OOPS!
Ich habe die strcmp-Implementierung ausgetauscht, aber … okay die glibc macht
einen cast zu (unsigned char ). Ich habe das mal angepasst.
gprof auf den CIP-Kisten funktioniert eigentlich ganz normal
gcc -pg -o fsort-pg fsort.c
gprof fsort-pg gmon.out
Welchen gprof habt Ihr den im Path?
which gprof
/usr/bin/gprof
Das Problem ist nur das die libc ja nicht mit ge-Profiled wird, und dort
eigentlich die meiste Arbeit geschied strcmp, qsort, etc. Das sieht man
dann natuerlichnicht. Auch die compiler optimierung bezieht sich nur
auf die eigenen Funktionen. Darum bringen diese nicht ganz so viel.
Ich benutze fuer fsort nur -O2 und fuer fsort2 -O2 -fomit-framepointer.
ich bin im mom bei ~1,810 für mein wsort gegen ~1,460 fsort… da muss noch was rauszuholen sein.
yipppieee:
flo@heeentop:~/Projects/wsort2/src$ time ./wsort2/dev/null
real 0m2.378s
user 0m2.270s
sys 0m0.036s
flo@heeentop:~/Projects/wsort2/src$ time ./wsort2/dev/null
real 0m2.380s
user 0m2.276s
sys 0m0.032s
flo@heeentop:~/Projects/wsort2/src$ time ./wsort2/dev/null
real 0m2.492s
user 0m2.312s
sys 0m0.037s
flo@heeentop:~/Projects/wsort2/src$ time ./fsort/dev/null
real 0m2.564s
user 0m2.383s
sys 0m0.033s
flo@heeentop:~/Projects/wsort2/src$ time ./fsort/dev/null
real 0m2.566s
user 0m2.381s
sys 0m0.034s
flo@heeentop:~/Projects/wsort2/src$ time ./fsort/dev/null
real 0m2.591s
user 0m2.366s
sys 0m0.038s
auf meinem notebook auf 600mhz runtergetaktet
Wir gedenken der Opfer von heeen’s Programm.
Übung SoS1 T08 *12:15 †12.16
Übung Ti II *14:15 †14.17
Vorlesung SOS1 *16:00 †16:00
“Manche großartige Leistungen verlangen Opfer”. - Lou Tsu Wang.
ok, langsam ist das ende der optimierbarkeit erreicht (zumindest für mich :)) - hab nun auch mal einen blick in die gprof daten geworfen (ging nach wie vor nicht im cip, einziger ausweg: mit -static binden, hab dazu auch was in google gefunden, wo jemand das gleiche problem berichtet- bug? jermand meinte dann liegt wohl wenn dann am gcc, bzw den libs?!)
und siehe da: die cmp funktion hat am meisten verbraten. (welch wunder ;))
also selbige durch eigenen, etwas optimierten code ersetzt (guter tipp). da ging dann noch ein wenig was rauszuholen:
[code]faui01 [aufgabe2]> sote -s wl/wlist5
------- sort-test -------
speed test only: stdout > /dev/null
sorting with: /proj/i4sos/pub/aufgabe2/fsort2
0.760u 0.020s 0:00.79 98.7% 0+0k 0+0io 112pf+0w
sorting with: ./bin.i386/fsort
0.680u 0.050s 0:00.72 101.3% 0+0k 0+0io 112pf+0w
faui01 [aufgabe2]> sote -s wl/wlist5
------- sort-test -------
speed test only: stdout > /dev/null
sorting with: /proj/i4sos/pub/aufgabe2/fsort2
0.820u 0.020s 0:00.83 101.2% 0+0k 0+0io 112pf+0w
sorting with: ./bin.i386/fsort
0.750u 0.020s 0:00.76 101.3% 0+0k 0+0io 112pf+0w
faui01 [aufgabe2]> sote -s wl/wlist5
------- sort-test -------
speed test only: stdout > /dev/null
sorting with: /proj/i4sos/pub/aufgabe2/fsort2
0.670u 0.030s 0:00.69 101.4% 0+0k 0+0io 112pf+0w
sorting with: ./bin.i386/fsort
0.740u 0.020s 0:00.76 100.0% 0+0k 0+0io 112pf+0w[/code]
wie man sieht ist aber die genauigkeit langsam auch an ihren grenzen, da wird mal hier und mal da 10ms gebucht
ich wüsste nicht was ich an der cmp funktion optimieren könnte… ich gehe davon aus daß strcmp weitestgehendst optimiert ist, und viel mehr macht mein cmp nicht.