[linux-l] [OT]: algorithmische Frage: Sort parallelisieren

Oliver Bandel oliver at first.in-berlin.de
Sa Jan 6 14:58:32 CET 2007


On Sat, Jan 06, 2007 at 01:21:31AM +0100, Volker Grabsch wrote:
> On Fri, Jan 05, 2007 at 08:15:51AM +0100, Oliver Bandel wrote:
> > > > Bereich Datenbankmigration, fette Files mit einigen GB Größe,
> > > > so daß man da nicht soohne weiteres die algorithmischen Probleme
> > > > oder dieder FileSize ignorieren kann.
> > > 
> > > "Datenbankmigration", das kann alles und nichts bedeuten.
> > > 
> > > Was sind die genauen Anforderungen?
> > 
> > Developing, while taregt moves ;-)
> 
> Dann sollte Informationsbeschaffung an erster Stelle stehen, nicht
> die Algorithmen.
> 

Wat'n Spruch....tse.



> > > Da sind so viele offene Fragen. Je nach Antwort könnte eine gute
> > > Lösung auch vollkommen anders aussehen. Ich finde es übrigens etwas
> > > anrüchig, dass du nur die Algorithmen und nicht die Datenstrukturen
> > > in Frage stellst.
> > [...]
> > 
> > Was findest Du daran anrüchig?
> 
> Ich will der Firma, in der du arbeitest, natürlich nichts unterstellen,
> aber deiner Beschreibung zufolge "riecht" es danach, als ob du zu
> strenge Vorgaben bekommst, die dich daran hindern, eine *wirklich* gute
> Lösung zu erarbeiten.

Nein, nicht wirklich.
Es ist eher so, daß man mich machen lässt, weil man weiss,
dass ich gute Arbeit leiste.

Letztens habe ich mal eben ein kleines Toolchen geschrieben,
den ewig lange dauernden - und nicht funktionierende -
Ansatz von "ich nehme Excel, das ist dafür gut geeignet"
beenden dürfen.

Etwas Perlund Postscript-Kenntnisse, und die Tonnenweise Logs
sind nun mit einemAufruf auf der Kommandozeile grafisch
dargestellt und jedes Statistikfile bekommt eine Seite  im pdf. :)

Vorher hatte der Kollege es versucht,mit Excel, und dann auch mit StarOffice,
aber ewig langes herum gewurschtel brachte nix.
Diese ach so tolle Lösung mit Standardsoftware, die ja die Arbeitseffektivität
so toll steigern soll, weil man nicht alles neu schreiben braucht,
klappt eben nicht, wenn diese Standardsoftware nicht in der Lage ist, die
Daten korrekt zuimportieren.

Und die Aufgabe habe ich mir selbst gesucht,so nach dem Motto: "wasmachste'n da?
Zeig ma. Oh, Excel... hmhhh." Und dann das Gefluche vom Kollegen...
...heheheh und ich dann weiter so nach dem Motto: "lassmich malmachen..." :)
Am selben Abend gab's dann die erste lauffähige Version und die ersten pdf's :)
Das war am 29.12.2006.
Das Teil wurde dann diese Woche wieder aufgegriffen, bekam Preprozessoren
für die Eingabefile-Generierung und so.

Nö, also was und wieich da arbeite, kann ich zu einem nicht unerheblichen Teil
selbst bestimmen; aber es gibt dann auch Aufgaben, die Vorgegeben sind.
Aber die Implementierungsdetails sind meine Sache.
Nur bin ich da offiziell der Perl-Scripter; auch C wäre genehm.
Aber OCaml auf breiter Front?weiss nicht. Zumindest für den einen Bereich
da, habe ich wohl nun ein OK.

Was jetzt schon in Perlistbleibt es auch; ein Teilin C habe ich auch schon
gebaut, bzw. bin ich noch dran. Ein Logfile-Rettungs-Deamon (weil manche
cronjobs die Logfiles löschen...).

Naja, nee ist schon ganz cool da.
Was nerv, sind die Windows-PCs für's Einloggen auf der Maschine.
Letztens haben mir die dummen Admins von der Windows-Front einfach meinen
Account gesperrt. Der Abend war dann nicht mehr sehr arbeitsreich und nächsten Tag
bin ich dann auch erst 10h30 da aufgetaucht.

Naja, nee, ist schon ganz cool da. Aber das Chaos (eher zu wenig
Vorgaben) kann aber auch manchmal richtig nerven. Eben keine Infos...
Naja, ich trags mittlerweile mit Fassung. :)

Aber wenn das Netz lahm ist oder derWindows-PC herum zickt oder so,
dann kriege ich da doch noch nen Schub Aggris;-)
Man tippt seinen Code, und plötzlich passiert garnix mehr, oder so.
Oder putty spinnt. (Oder die Admins schalten sich einfach drauf und deswegen
spinnt der Rechner?!)


 
[...]
> > > Und vergiss nicht: Das Dateisystem ist eine hochoptimierte hierarchische
> > > Datenbank. Das wird ebenfalls sehr gerne unterschätzt.
> > 
> > Es ist fürmanche Zwecke recht brauchbar; aber nicht für alle; deswegen
> > sind Datenbanken eben doch wichtig.
> 
> ACK.
> 
> Aber dennoch ist schon seit langer Zeit der Trend zu sehen, dass
> Datenbanken zu viel eingesetzt werden. In der BePHPUG ist das ein
> immer wieder heißes Thema.


Naja, PHP ist so datenbanklastig, weil esmit Persistenz bei
PHP ja recht mager aussieht. Also immer schön in die Datenbank...
...naja, für größere Anwendungen mag das sinnvoll sein, aber
um mal eben etwasKleinkram zu machen ist es wohl Overkill.

Aber PHP ist eh eine recht fragwürdige Sache.


> 
> > Davon abgesehen kann ich als Rad im Getriebe nicht vorgeben, welche
> > Richtung das Auto fahren soll.
> 
> Das nicht. Aber wer ein Zahnrad baut, sollte zumindest das ganze
> Getriebe sehen dürfen.
> 

Wenn nicht mal der Konstrukteur weiss, wie das Auto aussieht,
wird er es dem Zanrad auch nicht erklären können.
Und manches wird er vielleicht auch nicht erklären wollen...


[...] 
> Wenn das Problem wirklich tiefer stecken sollte, ist es zwar nicht
> deine Aufgabe, eigenmächtige riskante Aktionen durchzuführen. Aber
> der Entscheidungsträger sollte solchen Erkenntnissen nicht "vorbeugen",
> indem er wie beim Militär jedem nur die Infos gibt, "die derjenige
> braucht". Ablehnen kann er Vorschläge, die zu weit gehen, ja immer noch.


könnte, wollte, sollte.

Die Welt ist, wie sie ist, und daß man sie manchmal anders haben
will ändert sie noch nicht.
Wenn man auch das ohne Groll geniessen kann, spart man sich ne
menge Stress. :)


[...]
> > > Das hat mich auch gewundert. Die nächste anrüchtige Stelle. Du darfst
> > > den Algorithmus wählen, nicht jedoch die Programmiersprache.
> > 
> > In manchen Projekten gibt es Vorgaben.
> > Oder gibt es diemöglicherweise.
> > In Deiner Hobby-Programmierung mag das anders aussehen,
> > aber selbst in der Unimuss man dem Profnormalerweise Häppchen vorwerfen,
> > die er haben will.
> 
> Ich bin es *gerade* in der Uni gewohnt, Dinge ohne Angst hinterfragen zu
> können. Selbst in der Arbeit kann ich meine Auftraggeber mit
> "weiterführenden Gedanken" nerven. Und wenn sie nein sagen, dann erfahre
> ich in der Regel auch den Grund, und bin wieder etwas schlauer.

Klar.
Aber es kann eben auch ein Nein dabei heraus kommen.
 
[...]
> Wenn ein Übungsleiter die Lösung in Java haben will, dann spricht nichts
> dagegen, ihn zu fragen, was mit Python ist.
[...]

Und wenn er dann zu Python nein sagt, hast Du zwar eine Antwort,
wirst es vermutlich aber in Java schreiben, oder zwei Varianten
anbieten.



[...]
> > Oder noch besser DSLs.
> 
> DSLs müssen designt werden. Ist also ne ganz andere Schiene.

Ja,stimmt schon. Aber ich denke, in bestimmten Fällen ohnt sich der
Aufwand sehr wohl.

> Und der
> Interpreter deiner DSL, worin schreibst du den?

Soll ich antworten, oder weisst Du die Antwort bereits? ;-)




> 
> > > Wie ich selbst schmerzlich einsehen musste, liegen weite Welten
> > > zwischen:
> > > * C++ Code, der von C-Programmierern geschrieben wurde
> > > * C++ Code, der von Java-Programmierern geschrieben wurde
> > > * C++ Code, der von C++-Programmierern geschrieben wurde
> > > Letzteres ist sehr sauber und elegant, und eine hochinteressante
> > > herangehensweise.
> > 
> > Es liegen auch Welten zwischen einem <programmiersprache>-Programmierer
> > und dem nächsten Programmierer in <programmiersprache>.
> > Ein guter wird die Eigenheiten einer Sprache kennen, also auch,
> > wenn er von einer anderen Sprache herkommt.
> 
> Wenn jemand sich in C++ eingelebt hat, und deren Idiome etc. in ihm in
> Fleisch und Blut übergegangen sind, ist er in meinen Augen (auch) ein
> C++-Programmierer.
> 
> Ich meinte aber C++-Neulinge, also jemanden, der sich in C bzw. Java
> auskennt, die Syntax von C++ kennt, und  zum ersten oder zweiten Mal 
> eas größeres in C++ schreibt. Das sieht man einfach, wenn jemand in
> C++ mit den C-Idiomen oder den Java-Idiomen heran geht.

Ich habe mal in relativ einem *kleinen* Projekt gesehen, was passiert,
wenn ein C++-Coder in C schreibt.
Katastrophe!
Kein Wunder, daß der Krempel nicht sauber lief ;-)



> 
> Ich persönlich bin z.B. mit C-Idiomen da heran gegangen, und habe
> danach den Code gründlich aufgeräumt, als ich es besser wusste.
> Ein großer Haufen potentieller Segfaults ist gleich mit verschwunden.

Eben. Da liegen ansonsten einige Stolperfallen drinn.


> 
> > Und bei einem schlechten
> > Programmierer ist es auch egal,ob er 20 Jahre Erfahrung hat, denn
> > er wird immer Grütze schreiben!
> 
> Bin ich deshalb ein schlechter Programmierer, weil ich's nicht auf
> Anhieb richtig[tm] gemacht habe? Weil ich erst nach ein paar Wochen
> etwas über RAII gelesen habe?

Ich weiss ja nicht, was für Code Du produziert hast.
Wichtig beim Programmieren ist, daß man potentielle
Fehlerfälle alle abfragt/abfängt, oder dies zumindest
vor hat. Wenn man was übersieht, ist das eben Pech.
Aber es gibt Leute, die einfachgrundsätzlich zu
faul sind, Fehlerbedingungen abzufragen oder
nicht gewillt sind ihre Programmiertechniken anzupassen.

Die wichtigste Regel beim Programmieren lautet:
  Schreibe sauberen, zuverlässigen Code.

Hat man den falschen Algorithmus, aber sauberen Code
(damitmeine ich auch sauber strukturiert), dann
kann man Teile später, wenn eine Optimierung notwendig ist,
noch austauschen.

Aber es gibt Leute, die verfransen sich im Optimieren der Geschwindigkeit,
oder haben nicht mal diesen Anspruch, und der Code ist grauselig.
Dann sind die Debugging-Zeiten entsprechend hoch bzw. das Projekt
wird nie fertig.


> 
> Genauso erkennt man z.B. auch Python-APIs, die mit Java-Idiomen
> überflutet sind, ein klassisches Beispiel ist pyUnit.
> 
> Ich denke, auch der beste Programmierer schreibt suboptimalen Code,
> wenn er neu in einer Sprache ist. Die Frage ist nicht, wie sein
> Code anfangs aussieht, sondern wie schnell er in der Lage ist, die
> neue Idiome und Herangehensweisen, also den "Stil" einer neuen Sprache,
> sich zueigen zu machen.

Das ist ein Punkt.
Noch wichtiger ist mir aber, daß der Code nicht nachlässig
geschrieben wird. So eine Scheiss-egal-Mentalität, die
ist es, die die meisten Projekte zum Scheitern bringt, denke ich.

Mit "wird schon klappen" / "wird schon nicht daneben gehen"
fällt man dann eben irgendwann doch auf die Fresse.
Und dann viel Spaß beim suchen, wenn an zig tausenden
von Funktionsaufrufen irgendwo eine Fehlerbedingung
aufgetreten ist, man aber davon keine Meldung erhält,
weil das nicht abgefragt wurde und man einfach mit verbogenen Pointern
weiter arbeitet...

...es gibt eben Leute, die arbeiten gerne mit dem Debugger.

...und es gibt andere, die brauchen keinen Debugger.

So einfach ist das.




[...]
> > RAM ist eben am schnellsten, und da, wo Zeit Geld kostet, sollte man die
> > nicht unbedingt mitI/O verballern.
> 
> Du vergisst den Cache. Böse Falle.
> 
> Wenn dein Programm, sagen wir, in 1MB - Häppchen arbeiten kann,
> vergleichen wir mal zwei Szenarien:
> a)  1 MB lesen, verarbeiten, wieder 1 MB lesen, verarbeiten
> b)  100 MB lesen, verarbeiten, wieder 100 MB lesen, verarbeiten
> 
> Wo ist der Unterschied? Algorithmus b) braucht mindestens 1GB RAM.
> Wer ist schneller? Ich glaube, es gibt keine großen Unterschiede.
> 
> Würde b) sogar chaotisch auf die Daten zugreifen, wäre a) sogar
> schneller, weil b) den Prozessor-Cache aushebelt, während a)
> dies per Design nicht kann. (außer der Prozessor hat weniger als
> 1 MB Cache)


1GB lesen und verarbeiten und raus schreiben.
Auch das geht.

Und es geht auch nicht.
Eskommt eben immer drauf an, welche Hardware, welches OS, welche
Programmiersprache, welche Libs,... welchen Code man schreibt.



> 
> Genauso puffert das Betriebssystem. Ich habe mal Kopier-Algorithmen
> ausprobiert mit verschiedenen Puffergrößen. Kopiert man Byte-für-Byte,
> ist es grottenlahm. Nimmt man 1kb auf einmal, geht's schon schneller.
> Aber ab ca. 32kb konnte ich keinen Unterschied mehr messen.
> 
> Warum? Was hat gebremst? Die Festplatte? Nein, der Overhead bei
> den I/O-Funktionsaufrufen. Bei 32kb ist der Aufruf-Vorgang nur noch
> ein mikriger Zeitanteil, verglichten mit den 32.768 Aufrufen der
> Byte-für-Byte-Variante.

Das Problem ist mir bekannt.

Mit dem einen Kollegen haben wir letztens folgendes ausprobiert:

Nimm cp und kopiere Daten von 1GB Größe.
Dann nimm dd und kopiere die selbe Datei.

Bei beidem messe die Zeit.

Wieso ist dd schneller?

dd kann je nach eingestellter Blocksize noch drastische Unterschiede
im speed haben.
Aber wenn man schaut, wie die beiden schreiben, tun es beide mit
8MB. Und dennoch ist dd wesentlich schneller.

Was nun?

Für detail-Untersuchungen hatten wir keine Zeit,
aber nun wissen wir jedenfalls, wie wir schneller sind.
Das ist der pragmatische Ansatz: Wir könnten ewig lange
untersuchen, woran es genau liegt, oder wir nehmen einfach
die Variante, die schneller ist. Wenn man letzteres macht,
ist man selbst auch schneller. :)





> 
> Das Betriebssystem chached. Lass also das Betriebssystem entscheiden,
> in welcher Block-Größe es von der Platte liest, und wievel es davon
> im RAM cached. Das kann das Betriebssystem viel besser als du, da
> haben ja auch zahlreiche Experten den Cache auf's Optimum getrimmt.

Naja, und wie hilft mir diese Aussage, wenn ich mich zwischen
cp und dd entscheiden soll?


> 
> Natürlich gilt das nur für sequentielle Zugriffe, aber genau das
> meinte ich: Wenn du 100 MB chaotischer Daten sortierst, mach es im
> RAM.

Ja, gerne. Aber nur, wenn genug RAM drin ist.
Sonst swapt dieMaschine und man hat nix gewonnen.

Aber wenn genug RAM drin ist und die Architektur es schafft,
kann man auch 1 GB oder mehrim RAM sortieren.
Mal eben 10 GB verarbeiten: slurp, sort, write ;-)


> Wenn du hingegen mehrere Blöcke sortierter Daten mergst, brauchst
> du sie *nicht* komlett in den RAM zu laden.

OK, und das war dann also der Grund, wieso Mergesort empfohlen wurde?
Das war auch der Punkt, den ich da nicht bedacht hatte, als ich 
zu dem Kollegen anfangs meinte, parallelisiertes Sort sei Unsinn.
Ist es ja dann wohl nicht, denn die Maschine hat mehrere CPUs
und jede könnte was abarbeiten. Aber wenn die IO bremst, dann wäre
der Gewinn ggf. nicht so groß.
Vielleicht muss man sich dann was anderes ausdenken.
Evtl. temporäre Files auf jeweils andere Platten oder sowas.

Aber das ist alles spekulativ,solange man die genauen Verhältnisse
nicht kennt.




> Du kannst dann "nativ"
> sequentiell aus dem Stream einlesen, das macht den Programmcode
> einfacher und die Optimierung überlasse dem OS.

Sequentiell einlesen kann auch in die Hose gehen.
In welchen Größen lesen?
Byte-by-Byte?
10 Milliarden Calls bei großen Files?

aus man(2) write:
   write(int d, const void *buf, size_t nbytes);

Da steht die Größe nbytes.

Oder Highlevel-API?
Dann sind da evtl. mehrere Caches, also
Chases auf mehreren Ebenen, dies ich gegenseitig
behindern.

Also lieber große Chunks einlesen?
Meinst Du das?
Und wenn das auch daneben geht?





> 
> > [...]
> > > Der "Parse-Baum" ist ein abstraktes Gebilde. Er kann durch eine
> > > Datenstruktur im RAM repräsentiert sein. Aber er kann auch einfach
> > > nur als die Aufruf-Reihenfolge entsprechender Callback-Funktionen
> > > definiert werden.
> > 
> > Diese Funktionen liegen aber auch im RAM.
> > Du bestätigst also, wasich meine.
> 
> Nein, denn der Parse-Baum liegt nicht in der Struktur der Funktionen,
> sondern in ihrer Aufruf-Reihenfolge durch den Parser.

Dann liegen die eben im RAM.
Irgendwas wird schon im RAM liegen.
Dann eben Pointer auf <irgendwas>.
Und das "irgendwas" sind entweder Funktionen, oder
Positionen in Files oder die Daten selbst.

Oder meinst Du noch was anderes?



> 
> > Wir sind wieder an dem Punkt, wowir wegen anderer Sprachwahl
> > aneinander vorbei reden.
> 
> Ist möglich. Worum es mir ging, war, dass man keine extra
> Datenstrukturen im RAM aufbauen braucht, wenn man sie nachher
> doch wieder nur abläuft. Dann kann man die Ein- und Ausgabefunktioen
> auch direkt verbinden.

Dann hast Du aber trotzdem eine ("extra") Datenstrukturim RAM,
nur daß diese etwas anderes repräsentiert: eben die
Reihenfolge der Funktionen, die Du ausführen willst.



> 
> > > Wenn du z.B. vom Parser einen Baum im RAM aufbaust, bloß um diesen
> > > danach Knoten für Knoten abzuarbeiten, dann macht es doch keinen
> > > Unterschied, ob die Funktionen "start_array", etc. beim Drüberlaufen
> > > über die Datenstruktur aufgerufen werden, oder direkt vom Parser.
> > > 
> > > Gerade in Ocaml mit dem Stream-Interface, oder in Python & Co.
> > > bei Iteratoren, oder auch mittels Closures, kannst du doch deinen
> > > Code so schreiben, als ob du über eine Datenstruktur rennst, ohne
> > > dass dies wirklich passiert. (in Wahrheit wackelt der Parser den
> > > Eingabestrom ab)
> > 
> > I/O ist langsam.
> > Vielleicht meinen wir doch was anderes?
> 
> Seuqentielles Lesen aus dem Stream ist nicht langsamer. Ständiger
> Lese- und Schreibzugriff natürlich schon. Vielleicht meintest du
> ja den.

Wenn ich random access brauche und immer wieder
rewind()mache und von vorne lese, nützt eine schnelle
Leserei nix, wenn ich diePositionen im File,
die ich brauche, sowieso kenne.

Es kommt alsoimmer drauf an, wie die Bedingungen sind.
Mehr als diese allgemeine Aussage kann man hier nicht treffen,
denn sonst können wir gleich ein Buch schreiben.
(Keine schlechte Idee, eigentlich, was? :))


> 
> > Man kann auch die zu sortierenden Elemente in der Datei,
> > gepointert via File-Poitioning, indizieren.
> > Die Sortierung selbst würde ich aber immer im RAM machen.
> 
> Die Sortierung der "kleineren" Happen: Ja. Aber das ist gerade bei
> Merge-Sort nur bis zu einer gewissen Grenze sinnvoll. Danach
> verschwendest du einfach nur noch RAM.

Aha.

Wenn aber das Sortierkriterium von 10k langen Datensätzen nur
vielleicht 10 Bytes sind, dann machen die 10GB-Files,
die ich jetzt mal annehme, garkein so großes Problem mehr.
Dann sind 10M statt 10GB das, was sortiert werden müsste.
Und man bräuchte dann nur die Anfangspositionen der jew.
Datensätze im File sich noch zu merken.
Dann müsste man nicht alles einlesen; ausser am Anfang,
wenn man die Daten erst mal scannen muss,um an die
Sortier-Kriterien und Poitionen heran zu kommen.

Das hängt aber eben vom Datenformat ab, das man sortieren will.
Also spekulieren wir wieder herum.



> 
> > Man braucht dann erst zum Schluß, falls das Ergebnis wieder in
> > einer Dateilanden soll, alles der Reihe nach auslesen.
> > Aber die reine Sortierung soll im RAM laufen.
> 
> Wenn du alle Sortierschlüssel in den RAM kriegst, vielleicht ja.

Ob das geht, weiss ich nicht.
Keine Informationen vorhanden.
Aber es ist ja eh nicht mehr, was ich machen soll dort.
(Ausser, die Leut überlegen es sich doch nochmal.)


> 
> Aber wenn du die vollen Datensätze zum Vergleichen brauchst, dann
> lieber häppchenweise. Und davon war ich erstmal ausgegangen. Wiegesagt,
> es gab ja kaum Infos von dir. :-)

Hatte ja auch selber nicht mehr Infos bekommen ;-)



[...]
> > Trifft aber auch nicht ganz, wasich meine, denn bei Tie
> > ist dieKopplungIMHO zu fest. Ich meine eher sowas wie
> > Indizierung.
> 
> Ja, das kann helfen. Muss aber nicht.
> 
> Doch hey, du hast super Testdaten, um das einfach auszuprobieren. ;-)
> 

Hmhh, guter Hinweis, das mit den Testdaten.
Eigentlich der beste dieser Mail. :)

Hmhhh, wenn da imProjekt mal Luft ist, kann ich mich ja mal
interessehalber da dran setzen. :)


> > > Erst dann, wenn du dich in den Daten hin und her bewegen musst,
> > > musst du sie in den RAM laden.
> > 
> > Mussich dann nicht mal, wenn ich es somache,wie ich meinte.
> > Aber umdie Daten zu erkennen muss ich siewenigstens einmal lesen,
> > oder wenigstens das, was die Ordnung erkennen lässt (evtl. Dateininterne
> > Ordnung, FixedLengthRecords oder CRLF oder was was ich).
> > Wenn ich das gelesen habe, kann ich im RAM sortieren.
> 
> Und wenn das zu groß für den RAM ist?
> 

Daten komplett lesen heisst ja nicht, sie auch komplett im RAM zu halten.

[...]
> > Threds-Zeugs geht noch so. Dalohnt sich der Tippaufwand wenigstens ;-)
> 
> Nicht, wenn's auch ein paar Fifos und Pipelines in einem Shell-Script
> getan hätten. ;-)

Naja, ich programmiere zwar gerne in nicht-Shell-Sprachen,
aber wenn es sich auf command line Ebene mit einem Einzeiler
und Pipes erledigen lässt und auch in brauchbarer Zeitspanne,
dann ziehe ich sowas natürlich vor. :)

Gruß,
   Oliver



Mehr Informationen über die Mailingliste linux-l