Das kann durch aus passieren.
Dein Programm ist korrekt. Dann ist die groesse von wlist5 vielleicht der Punkt
wo realloc kopieren muss. => das macht aber keine 5 Minuten aus.
Dein Rechner hat nicht genuegent Hauptspeicher. Das stimmt wohl
auch nicht weil Du wahrscheinlich auch auf der faui05 arbeitest.
Dein Programm ist doch nicht korrekt.
Uebersetze Dein Programm einmal mit
gcc -g -lefence -o wsort wsort.c
Vielleicht hilft es ja den Fehler zu finden.
Ohne Multithreading komm ich defintiv nicht unter 520 bei der 4er.
Mit Threads wurschtelt sichs noch etwas eigen herum.
Bin mit der real jetzt sowas bei 470, user bei 600.
fsort5 schmeißt mir im übrigen SegFaults für die wlist4…?
Aber fsort6 ist einfach nur krass! Ich hab gleich mal die Ausgabe ge-diff-t, weil ichs net glauben konnte 
Okay, fsort6 ließt sehr wahrscheinlich sehr schnell ein. Die Ausgabe muss in meinen Augen Wort für Wort erfolgen, da die Wörter ja nach wie vor ungeordnet herumliegen und nur die Zeiger sortiert sind.
Bleibt im Endeffekt die Tatsache, dass fsort6 fürs Sortieren wohl um die 180 bis 200ms bei wlist4 benötigt. Wahnsinn…
Wobei auf faui05 durch die 2 Opterons ja 4 Threads gleichzeitig echt parallel laufen können, oder?
zu 2, ich habs auf meinem heimrechner laufen lassen, der hat 512 MB RAM, müsst eigentlich reichen. Okay des -lefence geht bei mir nicht warum auch immer (ich hab kanotix drauf hab wohl nicht alles installiert was man so braucht) habs jetzt mal auch auf dem uni rechner laufen lassen(mit wlist4 als input) und folgende fehlermeldung bekommen
ElectricFence Exiting: mprotect() failed: Cannot allocate memory
diff der ausgaben von fsort und wsort lieferte auch unterschiede, was auf meinem heimrechner nicht der fall war.
Die Fehlermeldung hilft uns nicht wirklich weiter. Sie besagt nur das
der malloc-Implementierung von efence der Speicher ausgegangen ist.
Was bei 2GB-Adressraum und 14MB Daten in wlist5 vielleicht
auf einen Fehler hinweist, aber nicht wirklich was bedeuten muss. 
Dann probieren wir es als naechstes mit einem besseren Tool.
valgrind wsort < /tmp/wlist4 > /dev/null
Das finde ich schon beachtlich.
Danke fuer den Hinweis ist gefixt.
Es sind nur 2 Prozessoren Singel-Core ohne HT, aber natuerlich
koennten weitere Threads schon sortieren waerend die anderen
noch lesen bzw. schreiben.
Okay, jetzt klappt auch wlist5, ich hatte einen ganz blöden, wenn auch nicht gleich sichtbaren fehler bei malloc, der String breite, aber was mit nicht klar ist warum ging es mit wlist1 - wlist4, und nicht mit wlist5, jetzt klappts mit allen in akzeptablerzeit, (bis 4 sec unoptimiert). Hmmm. Naja werd mich noch ein bisschen damit beschäftigen und hoffe dass ich alle fehler finde falls es noch welche gibt.
Muss ich anmerken, dass ich den Hut zieh vor DeepBlue! Dessen real time ist bei 400! user 610.
Bin jetzt mit Multithreading auf 470 real und 570 user runter. Evtl geht da noch was, aber soll jetzt erstmal reichen mit Threads.
Da fsort6 (und wie ich gerade sehe gibts ein 7ener, dass bei wlist5 einfach nur beeindruckend ist…) aber wesentlich schneller ist, muss es ja wohl ganz anderes gehen. Hab da noch so nen Einfall. Allerdings ist die Implementierung wohl nicht ganz ohne, und für heute ist jetzt dann mal Ende 
wsort<wlist5>text1.txt
fsort<wlist5>text2.txt
diff text1.txt text2.txtDes ist schon richtig wenn ich mir anzeigen lassen will ob die ausgabe gleich ist, oder ???
Ich hoffe es
Sonst Hab ich ein Problem
so wie du es machst ist es richtig
Besteht ne chance auf eine extra-Übung: “wsort extrem”?
Dafür wäre ich auch.
Interessiert mich nämlich schon brennend, was da alles gezaubert wurde.
Vorschlag: Freitag, 19.5. 16 Uhr Raum 0.031 ?
Ok, klingt gut, wobei ein früherer Termin schöner wär.
Also ich bin auf jeden Fall dabei selbst wenns Freitag 16 Uhr wird!
Also noch tu ich mir schwer, meine ganzen Threads vernünftig arbeiten zu lassen, die Syncronisation macht mir zu schaffen.
Viel zu viele Threads bringen im Endeffekt auch nichts mehr, aber treiben die user time in die Höhe.
Bin jetzt momentan wieder mit der user time halbwegs an meiner Zeit der non-Multithreading Lösung dran. Der Overhead der erzeugten Threads lässt sich halt doch merken. Nur die real time ist deutlich besser:
faui05 [aufgabe2]> make time
time src/wsort </proj/i4sos/pub/aufgabe2/wlist4 >/dev/null
real 0m0.379s
user 0m0.539s
sys 0m0.029s
time src/wsort </proj/i4sos/pub/aufgabe2/wlist5 >/dev/null
real 0m0.743s
user 0m1.082s
sys 0m0.056sWas schneller ist als fsort5
Allerdings sind bei fsort6 und 7 halt auch die user times extrem schnell. Verdammt 
Ne extra Übung dazu wäre wirklich cool.
Nachtrag:
fsort7 hat ziehmlich langsame real times? ca. Faktor 3 gegenüber der user time. Wie geht denn sowas?
fsort6 ist allerdings sowohl real also auch user extrem schnell.
Hab jetzt an meiner non-Multithreading Lösung noch ein wenig rumgeschraubt und komm nun auf folgende Zeiten gegenüber fsort6:
faui05 [aufgabe2]> make time
time src/wsort </proj/i4sos/pub/aufgabe2/wlist4 >/dev/null
real 0m0.437s
user 0m0.402s
time /proj/i4sos/pub/aufgabe2/fsort6 </proj/i4sos/pub/aufgabe2/wlist4 >/dev/null
real 0m0.331s
user 0m0.255s
time src/wsort </proj/i4sos/pub/aufgabe2/wlist5 >/dev/null
real 0m0.872s
user 0m0.807s
time /proj/i4sos/pub/aufgabe2/fsort6 </proj/i4sos/pub/aufgabe2/wlist5 >/dev/null
real 0m0.578s
user 0m0.515sWie gesagt ohne Multithreading. Mal sehn wie weit man das noch treiben kann. Und dann mal sehn, ob das wieder Einbauen von Threads an bestimmten Stellen überhaupt noch was bringt, oder nicht…
Zumindest denk ich, dass die Geschwindigkeit von fsort6 nicht an Multithreading liegt? Arbeitet fsort6 überhaupt mit Threads? Ich hab da so ne Vermutung warum fsort6 so schnell ist…
Nachtrag 2:
Also jetzt denk ich ist für mich endgültig das Ende der Fahnenstange erreicht.
Das einzige, wo ich jetzt noch Zeit gut machen könnte ist wohl beim Einlesen, da hab ich nach wie vor keine Sonderbehandlung für Dateien, sondern les als Stream ein.
Hab jetzt nur noch zwei Threads, die so gut wie exakt die gleiche Laufzeit haben. Theoretisch kann ich das ohne Probleme auf 4, 8, 16 etc. Threads, die sich die Arbeit auch entsprechend linear aufteilen, ändern, bringt mir aber auf faui0X nichts. Wenn ich allerdings ein entsprechendes Cluster hätte…
fsort6(7) muss man sich wohl in der user time geschlagen geben, aber ich bin jetzt noch schön nah heran gekommen:
faui05 [aufgabe2]> make time
time src/wsort </proj/i4sos/pub/aufgabe2/wlist4 >/dev/null
real 0m0.272s
user 0m0.424s
time /proj/i4sos/pub/aufgabe2/fsort6 </proj/i4sos/pub/aufgabe2/wlist4 >/dev/null
real 0m0.310s
user 0m0.281s
time src/wsort </proj/i4sos/pub/aufgabe2/wlist5 >/dev/null
real 0m0.503s
user 0m0.805s
time /proj/i4sos/pub/aufgabe2/fsort6 </proj/i4sos/pub/aufgabe2/wlist5 >/dev/null
real 0m0.627s
user 0m0.578sAber da meine real time alle fsort’s schlägt, bin ich jetzt ja mal auf fsort8 gespannt
Hat eigentlich schon mal jemand dran gedacht Radixsort in Kombination mit Countingsort herzunehmen? Wir haben hier ja Zeilenlängen von O(1), also braucht er O(1) Durchläufe, pro Durchlauf mit Countingsort O(n+k), mit k=Anzahl der unterschiedlichen chars=O(1), also O(n), sprich: es dürfte in linearer Zeit zu machen sein. Faktoren sind halt fraglich.
War mir aber bisher zu fein das zu coden. ^^
Ich wills mal so sagen, dein Gedankengang gefällt mir … und ist mir nicht ganz fremd …
Hrhr. :>
Nachdem ich jetzt meinen Code mal als fertig deklarieren wollte, hab ich gerade einen Leichtsinnsfehler gefunden, der einfach unnötige Berechnungen macht.
Deswegen mal meine vorerst letzten, aber korrigierten Zeiten. Dateien werden nach wie vor als Stream eingelesen.
Ohne Multithreading:
faui05 [aufgabe2]> make time
time src/wsort </proj/i4sos/pub/aufgabe2/wlist4 >/dev/null
real 0m0.416s
user 0m0.383s
time src/wsort </proj/i4sos/pub/aufgabe2/wlist5 >/dev/null
real 0m0.785s
user 0m0.730sMit Threads (und im direkten Vergleich mit fsort6):
faui05 [aufgabe2]> make time
time src/wsort </proj/i4sos/pub/aufgabe2/wlist4 >/dev/null
real 0m0.258s
user 0m0.398s
time /proj/i4sos/pub/aufgabe2/fsort6 </proj/i4sos/pub/aufgabe2/wlist4 >/dev/null
real 0m0.326s
user 0m0.263s
time src/wsort </proj/i4sos/pub/aufgabe2/wlist5 >/dev/null
real 0m0.493s
user 0m0.774s
time /proj/i4sos/pub/aufgabe2/fsort6 </proj/i4sos/pub/aufgabe2/wlist5 >/dev/null
real 0m0.569s
user 0m0.521sIm Vergleich zu allen fsort’s halt schon sehr coole real times.
Die so verdammt guten user times von fsort6(7) tät ich fast auf das schieben, was andy jetzt ja angesprochen hat. Wahrschienlich relativ optimal implemeniert. Oder auch nicht, siehe nächstes Posting.
Nur falls die Frage aufkommt: qsort ist bei mir nach wie vor eingebaut und wird benutzt.
user time von fsort6
Wenn ich das Geheimnis mal lüften darf mit fsort6:
TheChip, du hast definitiv die besten Zeiten - nun von mir der Hut ab 
Soweit ich das fsort6 analysiert habe arbeitet es mit 4 Prozessen (1 Parent, 3 Childs) und das “verdeckt” die höhere user time (bin mir nicht 100% sicher aber das müsste
schon stimmen). Es arbeitet nach wie vor mit qsort.
An deine Zeiten ranzukommen wird mir wohl schlaflose Nächte bereiten - mal schaun
ob mir’s das Wert ist
Mal noch eine prinzipielle Frage:
Wenn ich mein Makefile erstelle, dann darf ich doch für meine gcc Parameter angeben was ich will? Solange -ansi -D_POSIX_SOURCE -Wall -Werror mit dabei ist?
Sprich in meiner gcc Zeile auch ein -O2(3) haben?
Oder wenn ich jetzt Threads verwende die entsprechende Lib mit -lpthread einbinden?