Aufgabe 2

Bachelor Systemprogrammierung
41

Das liegt an der verwendeten Shell. Wenn du die [m]sh[/m] oder die [m]bash[/m] verwendest, kommt die dreizeilige Version, bei der Standard-Shell die einzeilige. In die [m]sh[/m] kannst du wechseln, indem du ganz einfach [m]sh[/m] eingibst (logischerweise), mit [m]exit[/m] kommst du wieder raus, und mit noch mal [m]exit[/m] wird die Sitzung beendet.

Und jetzt versuche ich mit aller Gewalt - Heapsort hat leider keine Verbesserung gegenüber [m]qsort()[/m] gebracht - trotzdem noch die 0,2 Sekunden Rückstand auf TheChip wettzumachen… :anx:
Wenigstens habe ich [m]fsort[/m] bereits hinter mir gelassen.

Nachtrag: Da war wohl nicht nur beim Sortieren jemand schneller als ich. :wink:

42

Es gibt time einmal als Kommando in /usr/bin/time aber auch als Shell Builtin Command (siehe frahis posting). Deine Ausgabe sieht nach dem time kommando der tcsh aus, das der anderen nach dem der bash.

43

Per Time:

1.241u 0.096s 0:01.33 100.0% 0+0k 0+0io 0pf+0w

Profile:

Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls ms/call ms/call name
38.61 0.25 0.25 main
32.43 0.46 0.21 strcmpList
21.62 0.60 0.14 1 140.55 140.55 sortList
7.72 0.65 0.05 1 50.20 50.20 printList
0.00 0.65 0.00 1 0.00 0.00 readInput

total: 180,75 ms

80% der Rechenzeit gehet auf das Sortieren und nur 20 % auf das Main, Einlesen, Ausgaben, etc.

Waer interessant wenn Ihr auch mal ein Profil mit gprof erstellen koennt, da Gprof ein etwas genaures Profil als time erstellt :*)

44

Vergleichsmessungen
Zu den Messungen am besten kopiert Ihr die Dateien erste einmal nach /tmp. Ansonsten
wird der NFS-Durchsatz gemessen und nicht die Anwendung.

fsort verwendet qsort und strcmp. Wie in der Aufgabe beschrieben es liest auch einfach
von stdin und schreibt auf stdout. Keine Sonderbehandlung bei Dateien. Es wird kein
malloc oder realloc verwendet, aber wenn Ihr wollt kann ich das einbauen, aendert an den
Zahlen wahrscheinlich nichts.

Uebersetzt wurde es mit gcc auf der faui05 und -O2.

Ach ja. Es geht natuerlich noch schneller als fsort, ich habe da auch einige Varianten
noch auf Lager.

45

Darauf warten wir doch nur :smiley:

46

Wie soll das bitte ohne malloc oder realloc gehen?

47

Jo, das ist ne gute frage :slight_smile: Ein Hinweis wär schon super!

48

Re: ohne malloc oder realloc
Schaut doch mal unter “man sbrk” nach :slight_smile:

49

Das wsort-Rennen
Das ist ja ein richtig heisses Rennen.
Um den Geschwindigkeitsrausch am laufen zu halten
poste ich mal meine Zeiten…

faui05 [~/work/SoS-1]> for list in /proj/i4sos/pub/aufgabe2/wlist*; do echo $list; time ./wsort < $list > /dev/null; done
/proj/i4sos/pub/aufgabe2/wlist0

real 0m0.001s
user 0m0.002s
sys 0m0.000s
/proj/i4sos/pub/aufgabe2/wlist1

real 0m0.012s
user 0m0.009s
sys 0m0.003s
/proj/i4sos/pub/aufgabe2/wlist2

real 0m0.017s
user 0m0.022s
sys 0m0.002s
/proj/i4sos/pub/aufgabe2/wlist3

real 0m0.109s
user 0m0.157s
sys 0m0.006s
/proj/i4sos/pub/aufgabe2/wlist4

real 0m0.397s
user 0m0.608s
sys 0m0.015s

50

real ist doch user+sys+rauschen?!? oder hab ich da was falsch verstanden?

51

Die user time ist schlechter als meine, ich müsste auf faui05 auf sowas 510 bis 530 kommen. Aber da die real time so tief ist würde ich mal sehr sehr stark auf Multithreading tippen. :wink:

Jetzt bin ich ja fast gezwungen, das auch noch einzubauen :wink:
(sollte aber relativ einfach gehen… hab zwar dazu in C noch nie was gemacht, aber es gibt ja immer ein erstes Mal :wink: )

52

da gibt’s halt die Posixthreads.

53

http://softpixel.com/~cwright/programming/threads.c.php

Darauf bin ich grad gestoßen, werd mir das mal geben. Aber jetzt grad ist das Wetter zu geil einfach, um hier zu coden.

54

Meine erste Seite ist zu sowas immer Pronix
http://www.pronix.de/pronix-24.html

55

Meine Güte! Ich bin schon froh, wenn ich die Aufgaben in endlicher Zeit bearbeite… :rolleyes:

56

ich doch auch, man kann es ja auch übertreiben mit den benchmarks und so, :smiley:

57

Oh ja, definitiv.
Persönlich würd ich im Moment sagen ich hab nen Schlag :smiley:

Ansonsten: Gratz an DeepBlue, sehr geile real time.
Wahrscheinlich holst du auch beim Einlesen mir gegenüber was raus. Wie gesagt, da mach ich nach wie vor keine Sonderbehandlung auf Dateien.
Im Moment bekomm ich auf faui08 (ich weiß echt nicht, wie ihr auf faui05 gscheite Zeiten bekommt, bei mir schwankt das halt enorm. Kann man total vergessen) 440 real und 410 user. Aber ich denk man kann mit Threads noch bisl was machen. Edit: War ein Fehler dei der Implementierung. Noch ist der Geschwindigkeitsboost nur minimal.

58

Damit das Wocheende nicht langweilig wird
Ich habe mal ein paar Varianten von fsort noch nach /proj/i4sos/pub
kopiert.

fsort2 und fsort3 sind nicht viel schneller als fsort.

fsort5 ist multithreaded

fsort6 bzw. fsort7 ist wohl eher die unlimited Loesung, aber schneller als fsort6 zu
sein sollte keinem ein schoenes Wochenend wert sein. :wink: Wenn mir jemand
erklaert warum fsort6 so gute Zeiten liefert reicht das voellig aus.

30% besser als fsort ist auch schon eine wirklich tolle Leistung. Im letztes
Semesterhaben fsort2-3 ausgereicht.

Zum Thema kein realloc. Ich habe einfach ein eigenes kleines realloc
geschrieben, aber wie gesagt das ist fuer die Zeiten nicht wichtig.

  1. Man sollte realloc so selten wie moeglich aufrufen. Bei wlist4 wird
    realloc bei fsort etwa 20 mal aufgerufen.

  2. Man sollte nie zwei Speicherbereich abwechselnt vergroessern. Ansonsten
    muss realloc kopieren.

Wenn beides befolgt wird und wir annehmen ein realloc dauert 1000
Maschinenbefehle, was es nicht tut, dann braucht realloc auf einem
2 GHz Rechner ca. 500 ns. Also brauchen wir bei 20 Aufrufen 2 microsekunden.
In der Zeitmessung werden jedoch nur sekunden und millisekunden angezeigt.
=> Es macht keinen Unterschied. qed.

In der Aufgabe 5 duerft Ihr noch ein eigenes realloc schreiben darum
keine Panic und ein schoenes Wochenende. :wink:

59

ich hät mal ne frage, also bei wlist0 - wlist4, habe ich laufzeiten “normale” laufzeiten zb bei wlist4:

time wsort<wlist4>/dev/null

real    0m2.100s
user   0m1.624s
sys     0m0.436s

und diff liefert auch keine unterschiede zu fsort bei der ausgabe der beiden programme, also sollte der code soweit stimmen.

allerdings bricht bei wlist5 alles zusammen, naja mehr oder weniger auf jedenfall dauert des ewig mit meinem wsort (ich habs bis jetzt nicht zu ende laufen lassen aber so 5 minuten lief des schon mal), wärend es mit fsort geht.
Naja mir ist halt nicht klar warum wlist4 geht und wlist5 nicht, ist zwar doppelt so gross aber der unterschied dürfte nicht im mehrere minuten bereich ligen.

60

PANIK!!!
aaaaaaaaaaa