Sortieren im Stream

Sarkast

hustbaer schrieb:

*: Lesen mit so kleinen Input-Puffern ist nur schnell wenn das OS preventiv mehr Daten als angefordert wurden in den Cache liest. Wenn du aber zu viele Files aufmachst und zu wenig RAM hast, und "random" mal aus diesem mal aus jedem File ein paar kB liest, dann kann das mit dem File-Cache natürlich auch nicht mehr gut funktionieren. Das OS kann schliesslich auch kein RAM herzaubern wo keines ist.

**: Wenn das Speichermedium Flash ist (SSD, Speicherkarte, ...), bzw. allgemein eines das keine "Seek-Zeiten" hat, dann kann es sein dass deutlich kleinere Puffer für gute Performance reichen. Es kommt einfach auf das Verhältnis der "Fixkosten" einer "Seek+Read" Operation zur linearen Lesegeschwindigkeit an. Einfach verschiedene Grössen durchprobieren.

Jau, ich bin jetzt eh an der schlichtesten Lösung dran und die basiert nunmal auf möglichst sequentiellem Lesen und Schreiben. Komplizierter kann ich's später auch noch machen.
Tatsächlich scheinen Filehandles nicht besonders ressourcenschonend zu sein und das delayed write buffering fordert auch seinen Tribut, sieht man an den Timestamps der Meßwerte ganz gut.
Mal schauen, wie's aussieht, wenn ich die ersten Vollmessungen durch habe und erstmal bei konservativen Buffergrößen bleibe.

Sarkast schrieb:

Hmm, aber doch nicht, wenn ich das File elementweise vergleiche.

Richtig, aber du wolltest es ja im RAM halten und das geht spätestens beim letzten Merge nicht mehr:

Sarkast schrieb:

zersäge ich die unsortierte Datei in Chunks, die ich im Speicher halten und sortieren kann

Jetzt muß ich die Dateien nur noch elementweise Links mit Rechts vergleichen und das jeweils größere in den Outstream schreiben und das nächste Element aus demjenigen Stream lesen, wo ich das herhatte.

Exakt, also nichts mit alles im RAM halten.

hustbaer schrieb:

Es gibt kein Problem.

Da er es im RAM halten wollte, siehe oben, schon.

Mergen von zwei Blöcken ist ne Stream Operation.

So sollte man es auch machen, aber alles ins RAM geht halt nicht.

Sarkast

computertrolls schrieb:

Mergen von zwei Blöcken ist ne Stream Operation.

So sollte man es auch machen, aber alles ins RAM geht halt nicht.

Naja, das war ja genau der Ausgangspunkt meiner Frage. Mir hat das Stichwort Mergesort gefehlt, weil mir dadurch erst klar geworden ist, wie mir sortierte Teillisten (für die das RAM ja reicht) helfen.

Sarkast schrieb:

Komplizierter kann ich's später auch noch machen.

Falls du das machst, dann schau dir noch einmal meinen ersten Vorschlag an.
Da kannst du dann gleich auf mehreren Kernen unabhängig voneinander große und dann voneinander unabhängige Datenmengen im RAM sortieren.

Es ist allerdings richtig, was hustbear gesagt hat. Da könntest du dir etwas einfallen lassen und bspw. die Buckets noch einmal aufteilen:

[quoote="hustbear"]
Hat im Vergleich zum Vorschlag von computertrolls den Vorteil dass es nicht auf Kenntnis des Wertebereichs des Sort-Keys angewiesen ist und man keine Probleme mit "Buckets" bekommen kann die dann doch wieder zu gross werden.
[/quote]

hustbaer

Parallelisieren lässt sich der Mergesort ebenfalls.
Und CPU-Zeit wir hier eh nicht das Problem sein.

Bucketsort als Lösung für Datenmengen die man nicht mehr gesamt in den Speicher bekommt ist echt Betteln um Probleme.

hustbaer schrieb:

Parallelisieren lässt sich der Mergesort ebenfalls.

Du kannst zwar die Zwischenschritte parallelisieren, aber wie parallelisierst du den letzten Merge?

Und CPU-Zeit wir hier eh nicht das Problem sein.

Das Problem sind die I/O Operationen zur SSD/HD, deswegen macht es meiner Meinung nach Sinn sich einen Algorithmus zu suchen, der möglichst auf dem RAM arbeiten kann.
Mit Bucketsort geht das.
Dazu kann man das ganze noch sehr schön parallelisieren, es gibt da praktisch keine nennenswerten Konflikte.

Und ich denke schon, dass das etwas bringt, weil Vergleiche auch Geld kosten und ein Single Core ansonsten alle n Vergleiche selber durchführen muss. Eine Rechenlast, die man gut auf mehrere Kerne verteilen kann, wenn sich der Algorithmus dafür eignet.
Inwiefern und ob die I/O Operationen auf das RAM die Kerne limitieren, das müsste man einfach mal ausprobieren. Oder meinst du, die limitieren einen Kern so stark, dass selbst ein einziger Kern genügen würde?

Bucketsort als Lösung für Datenmengen die man nicht mehr gesamt in den Speicher bekommt ist echt Betteln um Probleme.

Findest du?
Warum?

Sarkast

Bitte nicht jetzt schon streiten, bin gerade erst dabei, den ersten Merge von zwei vorsortierten Teillisten fertig zu implementieren.
Wenn der erste Wurf "good enough" ist, werde ich da nicht weiter herummurksen, weil ich dafür nichtmal ein Schulterklopfen erwarten darf. Bin eigentlich ziemlich fachfremd und kein Informatiker und komme zu solchen Dingen nur, weil mich mal jemand mit den Worten: "Heh, du kannst doch programmieren, oder?" angehauen hat, seitdem landet sowas bei mir.
Und Feierabend hab ich eigentlich seit halb fünf, aber es interessiert mich nunmal.

hustbaer

computertrolls schrieb:

hustbaer schrieb:

Parallelisieren lässt sich der Mergesort ebenfalls.

Du kannst zwar die Zwischenschritte parallelisieren, aber wie parallelisierst du den letzten Merge?

Gar nicht - zumindest nicht sinnvoll. Dass das nicht unendlich skaliert ist klar. Aber es sollte gut genug für die meisten Anwendungen skalieren.

computertrolls schrieb:

Und CPU-Zeit wir hier eh nicht das Problem sein.

Das Problem sind die I/O Operationen zur SSD/HD, deswegen macht es meiner Meinung nach Sinn sich einen Algorithmus zu suchen, der möglichst auf dem RAM arbeiten kann.
Mit Bucketsort geht das.

Mit Merge-Sort geht das genau so
Ich würde sagen sogar noch viel besser, da du dir die Chunk Grössen aussuchen kannst, und nicht auf die Verteilung der Keys angewiesen bist.

computertrolls schrieb:

Dazu kann man das ganze noch sehr schön parallelisieren, es gibt da praktisch keine nennenswerten Konflikte.

Den Pass der über das Input-File drüberackert und es in Buckets aufteilt zu parallelisieren ist nicht einfach. Und genau so wie Vergleichen nicht gratis ist, ist es auch nicht gratis die Items anhand einer "Stelle" des Keys in Buckets aufzuteilen.

computertrolls schrieb:

Und ich denke schon, dass das etwas bringt, weil Vergleiche auch Geld kosten und ein Single Core ansonsten alle n Vergleiche selber durchführen muss. Eine Rechenlast, die man gut auf mehrere Kerne verteilen kann, wenn sich der Algorithmus dafür eignet.

Der letzte Merge muss single-threaded laufen, also N Vergleiche. Aber nicht N log N vergleiche. Die log N - 1 passes vor dem letzten Pass können parallel laufen.

computertrolls schrieb:

Inwiefern und ob die I/O Operationen auf das RAM die Kerne limitieren, das müsste man einfach mal ausprobieren. Oder meinst du, die limitieren einen Kern so stark, dass selbst ein einziger Kern genügen würde?

Das kommt auf viele Faktoren an. Wie gross die Items sind, wie kompliziert der Key zu vergleichen ist, wie schnell das Mass-Storage-Device ist...

computertrolls schrieb:

Bucketsort als Lösung für Datenmengen die man nicht mehr gesamt in den Speicher bekommt ist echt Betteln um Probleme.

Findest du?
Warum?

Weil es schwer so zu implementieren ist dass es keine Fälle gibt wo es einem um die Ohren fliegt. Was machst du wenn du zu viele Keys hast die in den selben Bucket gehören? Dann musst du diesen Bucket dynamisch weiter unterteilen. Kompliziert. Dabei aber aufpassen dass man insgesamt nicht in zu viele Buckets unterteilt, weil einen sonst das Erzeugen/Schreiben/Lesen von zig- oder hunderttausenden Bucket-Files umbringt. Noch komplizierter.

Ich mag generell Algorithmen nicht deren "Eigenschaften" stark von den Input-Daten abhängig sind. Hier also wie gross die Chunks werden bzw. wie viele Chunks es gibt abhängig davon wie die Keys verteilt sind. Dabei ist es viel zu einfach irgendwas zu übersehen wo dann doch wieder irgendwelche Probleme entstehen.

hustbaer

Sarkast schrieb:

Bitte nicht jetzt schon streiten,

Wir diskutieren doch bloss.

Sarkast schrieb:

bin gerade erst dabei, den ersten Merge von zwei vorsortierten Teillisten fertig zu implementieren.
Wenn der erste Wurf "good enough" ist, werde ich da nicht weiter herummurksen

Verlangt auch keiner von dir. Mach das was für dich Sinn macht!

Das passiert hier oft dass jemand ne Frage stellt, und dann weiterdiskutiert wird obwohl die Frage schon beantwortet wurde, einfach weil die anderen Forenteilnehmer Spass daran haben sozusagen.

hustbaer schrieb:

computertrolls schrieb:

Dazu kann man das ganze noch sehr schön parallelisieren, es gibt da praktisch keine nennenswerten Konflikte.

Den Pass der über das Input-File drüberackert und es in Buckets aufteilt zu parallelisieren ist nicht einfach. Und genau so wie Vergleichen nicht gratis ist, ist es auch nicht gratis die Items anhand einer "Stelle" des Keys in Buckets aufzuteilen.

Ein Thread liest den Datenstrom von Anfang bis Ende und macht daraus Teilstücke, die es im RAM in jeweils ein Arrays legt.
Sobald ein Array voll ist, wird es gleich an einen eigenen Thread abhängig von der Core-Anzahl (oder sofern Hyperthreading hier Sinn macht, auch abhängig davon) zur Weiterbearbeitung weitergegeben.

Jeder einzelne Thread der ein Array zum Bearbeiten erhalten hat kriegt ein paar echte Buckets zugewiesen und gilt als Besitzer dieser Buckets, welcher er dann, auch direkt auf die Platte schreiben darf (natürlich unter der Berücksichtigung, dass man dabei den ersten Thread nicht stört), diejenigen Buckets die schon zugewiesen wurden dürfen von anderen Threads nicht benutzt werden.
Dafür nutzen die anderen Threads dann für diese Art von Bucket einen Zwischenpuffer im RAM.

Der Zwischenpuffer wird dann nach und nach an den Besitzerthread weitergereicht und der Thread der den Zwischenpuffer hatte, legt einen neuen Zwischenpuffer im RAM an, so ist er immer ausgelastet.
Der Besitzerthread schreibt den Puffer dann auf die Platte.

Eventuell kann es Sinn machen, die ganze Aufgabe mit dem Besitzerthread der ja die schreibende Arbeit übernimmt, auch einfach dem ersten Thread, der sich sowie um das Einlesen kümmert, also die HD belegt, zu übergeben. In dem Fall arbeiten die anderen nur auf dem RAM mit ihren Zwischenpuffern. Das hat den Vorteil, dass es bei einer HD keine unnötigen Zeitverlust bezüglich der Seekzeit gibt.

Wenn die Daten dann alle in ihrem jeweiligen Bucket gelandet sind, dann kann man diese dann an die jeweiligen Threads fair und gleichmäßig nach der Bucketgröße nach und nach aufteilen.
Die Threads arbeiten dann ihren Bucket einzeln ab und sortieren ihn, wenn alles ins RAM passt, mit schnelleren Sortierverfahren wie bspw. Quicksort. Wenn sie damit fertig sind, kriegen sie den nächsten freien Bucket.

Wenn ein Bucket schon zu groß ist, könnte man für den dann immer noch Mergesort verwenden oder ihn einfach noch einmal in zwei Subbuckets aufteilen.

Sofern nötig, fügt man dann am Schluss alle sortierten Buckets aneinander.

Weil es schwer so zu implementieren ist dass es keine Fälle gibt wo es einem um die Ohren fliegt. Was machst du wenn du zu viele Keys hast die in den selben Bucket gehören? Dann musst du diesen Bucket dynamisch weiter unterteilen. Kompliziert. Dabei aber aufpassen dass man insgesamt nicht in zu viele Buckets unterteilt, weil einen sonst das Erzeugen/Schreiben/Lesen von zig- oder hunderttausenden Bucket-Files umbringt. Noch komplizierter.

Ich mag generell Algorithmen nicht deren "Eigenschaften" stark von den Input-Daten abhängig sind. Hier also wie gross die Chunks werden bzw. wie viele Chunks es gibt abhängig davon wie die Keys verteilt sind. Dabei ist es viel zu einfach irgendwas zu übersehen wo dann doch wieder irgendwelche Probleme entstehen.

Ja, die Komplexität ist höher, mit ihr auch die Fehleranfälligkeit, aber es kann auch performanter sein.
Denn Zeitaufwand für den letzten Merge bei Mergesort würde ich nämlich recht hoch einschätzen.

hustbaer

Ja, ich verstehe schon wie man es machen kann. Ich sage bloss dass es nicht einfach ist. Implementier einfach mal beide Varianten, dann siehst du vermutlich warum ich Merge-Sort besser finde.

computertrolls schrieb:

Denn Zeitaufwand für den letzten Merge bei Mergesort würde ich nämlich recht hoch einschätzen.

Und ich relativ gering. Und nu?

rapso

Sarkast schrieb:

Ich logge Messergebnisse,sehr viele (ein paar GB pro Aufzeichnung) und die passen folglich nicht auf einmal in den Speicher, landen also in einem File, das ich hinterher vollständig sortieren muß.

wirklich interesant fuer eine gute loesung waere zu wissen was fuer datensaetze du eigentlich hast.
wie gross ist ein eintrag?
welche art von daten sind enthalten? (strings? floats?)

hustbaer

Grundsätzlich hast du natürlich Recht dass Fragen nach ein paar Details meistens Sinn macht. Ich überlege mir aber gerade was es in diesem Fall für einen Unterschied machen könnte. Klar, wenn der Sort-Key klein genug ist könnte man die Keys direkt im RAM sortieren. Dann bleibt aber das Problem dass man die eigentlichen Daten noch in die korrekte Reihenfolge bringen muss, d.h. tonnenweise random Reads und das bremst auch gewaltig. Sonst fällt mir mal nix ein was hier wesentlich sein könnte.

Oder denkst du an was ganz anderes?

Sarkast

rapso schrieb:

wirklich interesant fuer eine gute loesung waere zu wissen was fuer datensaetze du eigentlich hast. wie gross ist ein eintrag?
welche art von daten sind enthalten?

Hergeleitet wird das Ganze natürlich aus digitaler Sensorik, davon bleibt aber nur die Timestamp als uint32 unberührt. Aus der Zwischenergebnisrechnung fallen dann pro Kanal zwo doubles plus stamp als set an, also 20 Bytes, davon gut 30'000 pro Meßsekunde, der typische Meßverlauf braucht so grob 6 bis 8 Minuten. Kann sein, daß ich da nochmal ein int32 dauerhaft ins set nehmen muß, ich brauch's sowieso grad zum Debuggen.

Drei bis sieben Kanäle soll die Schachtel bewältigen können.
Achso, ja, sortiert werden soll auf einen der Doubles im set. Ja, ich weiß, doubles sind unschön, aber momentan kann/will mir keiner was über die Skalierung der Meßwertaufnehmer erzählen.

Inwiefern hilft dir das?

rapso

@hustbaer @Sarkast
Grundsaetzlich ist die chance etwas zu optimieren besser wenn man mehr darueber weiss. Einfach nur "paar GB daten" ist wirklich nicht viel.
1Billion ints zu sortieren ist anders als 1Mio 1kb datensaetze. (Und datensaetze kosteneffektiv in eine vorgegebene reihenfolge zu bringen ist eine andere problemstellung. Ich glaube hier gab es sogar mal einen kleinen contest dafuer. )

Zum eigentlichen:
Sind also maximal 20byte*30'000*(8*60)*7 -> 1.87GB, das koenntest du vielleicht mit memory mapped files auf einer 32bit cpu, trotz nur 200MB freien ram, mappen. Das OS hat ein paar vorteile z.b. beim file caching, thread scheduling etc. wenn das klappt. (Dann koenntest du auch, um eine referenz zu haben, ein std sort messen).

Ich denke ich wuerde beim eigentlichen sortieren, erstmal radix sort versuchen, weil es linear durch die datei durchgeht und, sobald der datensatz ins ram passt, nur noch darauf arbeitet.

Wenn du fit bist im coden, wuerde auch nichts gegen bucketsort sprechen, zumindestens fuer den ersten durchgang. (Haengt aber auch vom wertebereich der doubles ab)

ansonsten, stell doch einen generator fuer pseudo daten rein, vielleicht hat jemand langeweile und probiert sich dran.

FILE* f=fopen("data","wb");
if(!f)
  return;
for(size_t a=0;a<30000*(60*8)*7;a++)
{
  int stamp=a;
  double x=sin((double)a);
  double y=cos((double)a);
  fwrite(&stamp,1,sizeof(stamp),f);
  fwrite(&x,1,sizeof(x),f);
  fwrite(&y,1,sizeof(y),f);
}
fclose(f);

nicht schoen, nicht schnell, aber du kannst es ja anpassen damit es representabel fuer deine datensaetze ist.

Ja, ich weiß, doubles sind unschön, aber momentan kann/will mir keiner was über die Skalierung der Meßwertaufnehmer erzählen.

Vielleicht kann dir hier im forum auch jemand dazu helfen

SideWinder

Out-of-the-box gedacht: ist es evtl. die günstigere Option 16 GB RAM zu kaufenu und das ganze via QuickSort zu sortieren?

MfG SideWinder

Jester

http://stxxl.org

und merge sort sinnvoll parallelisieren geht mit multi-way merging

hustbaer

Jester schrieb:

und merge sort sinnvoll parallelisieren geht mit multi-way merging

Geht das auch ohne Random-Access in die Teil-Listen? Der Algorithmus den ich kenne benötigt Random-Access auf Inputs und den Output und ist daher IMO für das Mergen von vielen Files die nicht zusammen in den Speicher passen nicht ideal. Kann OK sein wenn random IO schnell genug ist, aber wenn nicht dann wird die Sache dadurch vermutlich eher langsamer als schneller.

Also verglichen mit Algorithmen die mit "forward only" IO auskommen und dafür den letzten 2-way Merge in O(N) machen. Das Schreiben des Ergebnisses auf den Datenträger ist schliesslich immer O(N), und so lange man mit dem letzten Merge die Konstante nicht zu sehr nach oben treibt...

Sarkast

SideWinder schrieb:

Out-of-the-box gedacht: ist es evtl. die günstigere Option 16 GB RAM zu kaufenu und das ganze via QuickSort zu sortieren?

MfG SideWinder

Du bist lustig, ich soll also 16 GB RAM- Riegel neben den Linux- Riegel streuen und hoffen, daß die sich ineinander verlieben und heiraten?
Nee, da sind 512 MB fest aufgelötet, das müssen sich OS und Applikation teilen.

rapso schrieb:

1Billion ints zu sortieren ist anders als 1Mio 1kb datensaetze. (Und datensaetze kosteneffektiv in eine vorgegebene reihenfolge zu bringen ist eine andere problemstellung. Ich glaube hier gab es sogar mal einen kleinen contest dafuer. )

Achso, ja klar! Kleine Pakete, dafür viele.

rapso schrieb:

Zum eigentlichen:
Sind also maximal 20byte*30'000*(8*60)*7 -> 1.87GB, das koenntest du vielleicht mit memory mapped files auf einer 32bit cpu, trotz nur 200MB freien ram, mappen. Das OS hat ein paar vorteile z.b. beim file caching, thread scheduling etc. wenn das klappt. (Dann koenntest du auch, um eine referenz zu haben, ein std sort messen).

Da liegen die Hasen im Pfeffer. Schreiben tu' ich erstmal am PC, bevor ich das zum Schluß portiere. Die Erfahrungen auf dem Target- OS/FS mit caching nebst delayed wb auf das Flashdrive waren nicht sehr ermutigend, random access eine performance- Katastrophe. Das war ja auch der Ausgangspunkt, selber bestimmen zu können, was mit dem Speicher passiert, also wer ihn kriegt.
Das enthebt mich auch der Herumspielereien an den Einstellungen fürs Caching usw., weil, was am PC gut läuft, auf dem Riegel nicht zwangsweise auch gut laufen muß.

rapso schrieb:

Ich denke ich wuerde beim eigentlichen sortieren, erstmal radix sort versuchen, weil es linear durch die datei durchgeht und, sobald der datensatz ins ram passt, nur noch darauf arbeitet.
Wenn du fit bist im coden, wuerde auch nichts gegen bucketsort sprechen, zumindestens fuer den ersten durchgang. (Haengt aber auch vom wertebereich der doubles ab)

Hab der Einfachheit halber quicksort fürs Sortieren im RAM genommen, das einzig Ungünstige ist, daß es im Schnitt n * log(n), schlimmstenfalls n² Vergleiche braucht. Aber schaut momentan nach ausreichender Zügigkeit aus. Da könnte man vllt. später über mehrere Threads nachdenken.

rapso schrieb:

ansonsten, stell doch einen generator fuer pseudo daten rein, vielleicht hat jemand langeweile und probiert sich dran.

Das war das erste, was ich gemacht hab, die Meßwertaufnahme durch einen Dummy- Generator ersetzt.
Das mit der Skalierung ist noch nicht klar, weil es die Meßwertaufnehmer für 3 € , 300 € oder ca. 1000 € (pro Kanal) gibt, aber dann mit 1, 1000, 18000- facher Auflösung. Ähnlich verhält es sich mit der Zeitbasis. Ich kann nur sagen, was ich wünsche, was die kaufen ist oft was anderes.

So, die vorsortierten Listen kann ich dann wirklich rein sequentiell lesend/schreibend zusammenmergen, da müssen wirklich nur zwei Elemente in den Speicher (2 Instream, 1 Outstream). Das geht auch überraschend flott, ich hab' hier "nur" das Problem, daß sich mein Progrämmchen noch verkaspert, welche Dateien gerade zusammenzuziehen sind. Es "vergißt" entweder eine Datei oder versucht, Dateien zu öffnen, die es nicht gibt. Aber das hat mit Sortieren direkt erstmal nichts zu tun.

Jester

Du solltest Dir ünerlegen mehr als zwei streams auf einmal zu mergen. Jedes mergen erfordert einmal das vollständige lesen und schreiben aller Daten. Also warum das zweimal oder noch öfter machen, wenn man mit geringem Mehraufwand (CPU) den Datendurchsatz (I/O) senken kann.