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

[Volker Grabsch]

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.

> > 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. Ist natürlich nur ein Gefühl, mein Riecher kann
sich auch irren. E-Mail transportiert keine Gerüche, und das ist auch
gut so. ;-)

> > 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.

> 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.

Ich sehe auch dann gerne das Problem im Kontext, wenn es keinen Einfluss
auf die Lösung hat. Denn diese Erkenntnis, dass etwas keinen Einfluss
auf die Lösung hat, muss der Lösende haben, nicht der Entscheidungs-
träger.

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.

Aber wiegesagt, das war nur mein Eindruck von dem, was du geschrieben
hast. Ich hoffe natürlich sehr, dass es bei euch tatsächlich so zu geht.
;-)

> > 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. Zukünftige
"aus dem Rahmen springende" Ideen werden dadurch ja nur besser, weil ich
genauer die Rahmenbedingungen und das Umfeld kenne, und ein paar Mal
waren solche Ideen auch wirklich Bringer. Ich denke doch nicht nur dann
über Probleme nach, wenn ich von jemanden dazu aufgefordert werde.
Machst du ja auch nicht, sonst gäbe es diesen Thread nicht. :-)

Wenn ein Übungsleiter die Lösung in Java haben will, dann spricht nichts
dagegen, ihn zu fragen, was mit Python ist.

> > Warum
> > quälst du dich mit C rum? Ich meine, mindestens C++ wird doch wohl drin
> > sein.
> 
> Pfui. C++? Mag ich nicht. DieSyntax ist so Bloatig.

In größeren Applikationen ist es auf jeden Fall besser als C oder Java.

> Habe ausserdem mal nachgefragt und OCaml wäre kein Problem,
> soweit jedenfalls der jetzige Stand... :)

Schön. Dann kann dich ja nichts mehr aufhalten. :-)

> > Und nein, C++ ist nicht bloß C mit Klassen. Es ist viel mehr, es ist
> > Ausdrucksstark, und es hat einige einzigartige Konzepte und Prinzipien.
> 
> C++ ist nichts für meinen Geschmack.
> Ausdrucksstarksind OCaml und bes. Haskell.

Ja klar. Full ACK. Gegenüber C, Pascal und Java sticht es aber hervor.

> Oder noch besser DSLs.

DSLs müssen designt werden. Ist also ne ganz andere Schiene. Und der
Interpreter deiner DSL, worin schreibst du den?

> > 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 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.

> 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?

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.

> > Ähhm, die Dikussion hatten wir vor einiger Zeit schonmal. Also
> > nochmal *seufs*:
> > 
> > Eine Liste ist ein abstraktes Konzept. Ob dahinter eine Datenstruktur
> > im RAM liegt, oder eine sequentiell durchlaufene Datei, ist völlig
> > nebensächlich.
> [...]
> 
> Ja, ist mir klar.
> Das stimmt aber nur, wenn man es so abstrakt betrachtet und mit
> der Brille durchschaut, die genau dieses Ergebnis hervorbringt.
> 
> Schautman mit der Performance-Brille, dann erhält man da ein anderes
> Ergebnis.

Zu jedem Algorithmus und jeder konkrete Datenstruktur gehören gewisse
Performance-Eigenschaften. Vorrangig der Speicherbedarf und der Zeit-
Bedarf. Die Schnittstelle sollte unabhängig davon sein, aber der
konkrete Algorithmus und die genaue Datenstruktur wählt man doch
*gerade* in Hinblick auf die Performance, die ist doch in diesem
Stadium das einzige Unterscheidungskriterium.

> 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)

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 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.

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. Wenn du hingegen mehrere Blöcke sortierter Daten mergst, brauchst
du sie *nicht* komlett in den RAM zu laden. Du kannst dann "nativ"
sequentiell aus dem Stream einlesen, das macht den Programmcode
einfacher und die Optimierung überlasse dem OS.

> [...]
> > 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.

> 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.

> > 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.

> 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.

> 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.

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. :-)

Ich wollte lediglich das Prinzip der blockweisen Verarbeitung
klar machen, dass man eben nicht immer alles in dem RAM holen
muss, und dass man unter I/O-Vermeidung was anderes versteht als
alle mit einem Schlag einzulesen und rauszuschreiben.

> 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. ;-)

> > 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?

Ich empfehle dringend, das Ding blockweise auszurichten. Ein Block
wird im RAM sortiert, und dann werden die Blöcke über Pipelines
etc. gemerged, sodass nicht alles gleichzeitig im RAM sein braucht.

> Die Aufgabenstellung wurdemir aber nicht genau genug vorgegeben,
> so daß wir beide uns da auf Glatteis bewegen.

Jep. Lustig ist es trotzdem. ;-)

> 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. ;-)

> Aber in OCaml ist das selbstverständlich wesentlich einfacher :)

Ja, da hast du nochmal Glück gehabt. ;-)


Viele Grüße,

    Volker

-- 
Volker Grabsch
---<<(())>>---
Administrator
NotJustHosting GbR