ist egal
apropos differenzen zur beispiellösung: eure fsorts verwenden ja sbrk um sich speicher zu holen, wie ihr den freigebt is mir jedenfalls schleierhaft, free kanns jedenfalls nicht sein.
in dem wissen, daß der speicher nach terminierung eh frei wird und im laufe des programms speicher nicht “wiederverwertet” wird hab ich auf frees verzichtet… ich seh schon was mir blüht…
nachdem sich wohl kaum einer so sehr wie du mit dem wsort beschäftigt hat, lässt dein übungsleiter ja vielleicht gnade vor recht ergehen 
wie gibt man denn in der minishell den pfad fuer die commandos/programme wie ls an?
muss man den selbst vor das erste argument davorstöpseln /bin/…ls …?
nee, kannst einfach execvp mit zb ls als erstem argument nehmen
Da wir’s ja jetzt verwenden müssen:
=> wir hätten es gar nicht verwendn dürfen - oder?
fsort
Ich denke fsort ist hier eigentlich O.T.
Aber warum nicht, wenn Ihr umbedingt unter der Überschrift Shell was zu fsort wissen wollt.
fsort ist entstanden als ich HiWi am Lehrstuhl war. (Ich war jung und braucht das Geld.)
Soll heissen ich würde das Heute auch anders machen. fsort hällt sich nicht an die
Aufgabenstellung, war auch nicht beabsichtigt (da 1999 geschrieben).
Im Forum habe ich auch gepostet, dass wenn jemand wirklich will, auch
alles erlaubt sei. Er sollte dann nur die Lösung als fsort.c gesondert abgegeben.
Btw. das Geheimnis warum fsort so schnell ist liegt nicht an der Benutzung von sbrk, sondern
am Lesen in einem einzigen Rutsch und dem Vermeiden vom Kopieren der Daten, das geht
auch mit relloc.
Es ist auch möglich mmap zu verwenden, damit ist man dann vielleicht sogar noch schneller.
Ok, ist wohl ot - aber mich interessierts jetzt doch.
Also mal sehen ob ichs verstanden hab (hab nämlich überlegt ob ichs noch umsetzt - war dann aber zu faul). Du allocalisierst z.B 1MB. Schiebst da stdin rein und ersetzt dann alle \n durch und setzt die Pointer. Um den letzten evtl abgeschnittenen Pointer kümmert man sich getrennt. → Man spart sich einmal kopieren und recht viel allocalisieren.
@ morty:
-
Schritt:
Ganzen stdin in einem Rutsch einlesen. z.B. 1 MB auf einmal (mit fread). Reicht der Speicher nicht reallokieren, was ohne verschieben auskommen sollte, da zwischenzeitlich kein weiterer Speicher allokiert wurde. -
Schritt:
Die gesamte Eingabe durchgehen. Dabei wird dynamisch ein zweites Array aufgebaut, dass auf die Zeilenanfänge zeigt. Auch hier sollte bei realloc() kein verschieben notwendig sein, da wieder nur für dieses eine Array neuer Speicher allokiert wird. -
Schritt:
Das Zeiger-Array aus Schritt 2 mit qsort neu sortieren. Dabei braucht man eine Hilfsfunktion zum Vergleichen. In der Aufgabenstellung stand, dass man strcmp() verwenden kann. Allerdings wäre es schneller das gleich inline in der Hilfsfunktion zu machen (Für wlist5 als Eingabe spart man sich so immerhin 13 Mio Funktionsaufrufe). -
Schritt (hat bei mir nochmal ordentlich was an Zeit gebracht)
Man könnte danach durch das sortierte Zeiger-Array gehen und jeden String einzeln ausgeben. Schneller ist es, wenn man sich wieder genügend Speicher holt und dort erstmal alles reinschreibt. Nach jedem Wort kommt natürlich ein ‘\n’. Am Ende kann man diesen Ausgabepuffer mit einem einzigen fwrite() auf stdout ausgeben.
So sah meine Lösung in etwa aus. In Schritt 2 hab ich allerdings strcmp verwendet, weil ich dachte, dass man die Funktion verwenden muss (ich sollte die Aufgaben mal ein bisschen genauer lesen 
). Aber auch damit bin ich ganz gut an fsort2 rangekommen. Die Zeiten schwanken allerdings recht stark. Mal lag fsort2 vorne, mal meine Lösung (Auch wenn ich zugeben muss, dass fsort2 öfters vorne lag ). Noch schneller wäre es vermutlich, wenn man auch den qsort() selbstschreibt. Dann kann man die Vergleichsfunktion gleich inline schreiben.
reallocieren kann man sich sparen, da man einfach nur mehrere 1 mb blöcke allocen kann und das letzte wort des vorherigen blocks in das neue kopieren kann. so hab ichs gemacht aber die frees für die blöcke weggelassen. sbrk brachte nen geschwindigkeitsvorteil aber nicht allzuviel.
hm da stellt sich mir grad folgende frage
wenn ich nen 1 mb block einlese und dann durch nen rekursiven funktionsaufruf durchgehe und die \n mit ersetze und bei jedem neuen token nen neuen rekursionsschritt mache und dabei die tokens mitzähledann bin ich beim letzten token
und hab die anzahl der tokens dort allociere ich dann ein pointerarray und lass die rekursion zurücklaufen bis ich beim ersten token bin
so kann ich in einem schritt die anzahl der tokens + die character setzen
und in ein pointerarray eintragen
dann mach ich so weiter mit nem neuen block bis ich alles eingelesen habe
am ende hab ich ne verkette liste mit pointerarrays auf speicherblöcke und die anzahl der tokens gesamt mach mir ein neues pointerarray und kopier den inhalt der pointerarrays aus der liste in das neue welches ich qsort gebe
alternativ könnte man die blöcke einzeln sortieren undschauen ob
block a character von
a-g
und block b character von e-j hat am anfang stehen haben
dann muss ich im großen pointerarray nur fragmentweise sortieren und das dürfte nochmals schneller sein als jedezeile durchzugehen und ein strcmp laufen zu lassen
wenn du das mit der rekursion machst hast du aber entweder mehrere char**, wofür du wieder ein array brauchst um die alle beim sortieren oder der ausgabe auszugeben, oder du musst eins für jeden block reallocan.
da isses einfacher einfach nen zähler hochlaufenzulassen für jedes wort, und wenn er die grenze erreich einfach mal 4000 weitere wörter reallocen.
mit deiner methode gehste aber 2x durch mit der rekursion nur 1x pro 1mb block
die frage is nur wieviel die rekursion an performanceeinbussen mit sich bringt
werde das heute abend mal ausprobieren
ich geh pro 1mb nur einmal durch. in einem rutsch werden alle gesetzt und wortpointer gespeichert.
abgesehen davon bringts ab ner gewissen blockgröße nix mehr größere blöcke zu lesen. is so ab 64kb ungefähr denk ich.
jup is mir damals auch aufgefallen, 64-128k war so die grenze in etwa, wird wohl was mit der grösse der pages zu tun haben schätz ich mal? anzahl der pfs ging irgendwann auch nimmer runter. glaub minimale was ich mal hatte war 60 oder so.
pagesize ist normalerweise 8k (aeh 8ki).
Man hat aber immer noch jedesmal den Aufwand fuer den lese-Systemaufruf wenn man in
8k-Truemmern einliest.
Ab 64-128k wird der natuerlich immer mehr vernachlaessigbar.
Wenn das System dann noch read-ahead-Strategien faehrt kommt noch dazu,
dass in der Zeit, in der man auf den bereits gelesenen 64k arbeitet schon mal weitere
Daten eingelesen werden koennen. Wenn man dann den eigentlichen read-Aufruf an’s System
absetzt, sind die Daten evtl. laengst im Hauptspeicher - und man muss nicht mehr warten.
also ich hab nun etwas gegoogled wegen der pagesize und hab mehrmals gelesen dass sie in linux defaultmäßig bei 4kb liegt was meiner meinung nach relativ wenig ist für die heutigen speichergrößen
also ich hab nun mal zuhause auf meinem rechner nachgesen da ist sie auch 4096
basiror:/home/basiror/speedsort/src# ./speedsort
Pagesize: 4096
Die Pagesize wird auch vom Prozessor vorgegeben. Der 386er z.b. hat eine Pagesize von 4KB. Später dann hat Intel auch noch zwei weitere Pagegrößen eingeführt, die allerdings mit 2 und 4 MB recht groß sind. Deswegen wird dein Linux auch 4KB Pages verwenden.
Allerdings kann es sein, dass der Algorithmus, der bei einem Page Fault bestimmt, welche Pages ausgelagert werden und wieviele “neue” eingelagert werden, gleich ein bisschen vorarbeitet und mehrere 4KB Pages auf einmal einlagert. Vielleicht werden wir in Ti2 noch lernen, wie Paging auf dem 386+ funktioniert.
4k sind absolut ausreichend, sonst hat man doch viel zu viel verschnitt. so dicke hat mans ja auch nicht.
naja 1 gb ram mit 2 2 2 5 timings + sata platten da könnten die pages schon etwas größer sein
hoffe auch dass wir das ganze zeugs mit dem paging noch etwas genauer machen und hoffentlich machen wir mal was in die richtung eigenes betriebssystem schreiben und booten