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

[Volker Grabsch]

On Sat, Jan 06, 2007 at 02:58:32PM +0100, Oliver Bandel wrote:
> On Sat, Jan 06, 2007 at 01:21:31AM +0100, Volker Grabsch wrote:
> > > > Was sind die genauen Anforderungen?
> > > 
> > > Developing, while taregt moves ;-)
> > 
> > Dann sollte Informationsbeschaffung an erster Stelle stehen, nicht
> > die Algorithmen.
> 
> Wat'n Spruch....tse.

Ja, hast schon recht, die rein spekulativen Teil-Threads lassen wir mal
lieber beiseite.

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

Achso, also das andere Extrem. Mehr eine Hippie-Bude als ein
Militärgelände.  ;-)

> 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.
> 
> 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?!)

Was ist denn das? Die Administration darf doch nicht zur Archillesverse
der Entwicker werden. Ihr Job ist doch das genaue Gegenteil: Die
Entwickler zu entlasten, sodass sie ihre Arbeit ungestört und
reibungslos erledigen können.

Meine persönliche Theorie ist übrigens, dass es neben dem Katzen-Gen,
das einem 9 Leben verschafft, auch ein Administrator-Gen gibt, das einem
42 Jahre verschafft. Die braucht er, um die 1x im Jahr von Usern
geplanten Anschläge auf ihn zu überleben. Aber ich will hier keinen
Sozial-Darwinismus betreiben. Auch ohne dieses Gen kann man Admin
werden. Nur wird man dann schon im ersten Arbeitsjahr einem tödlichen
"Unfall" erliegen. Das bedeutet, die noch lebenden Admins haben alle
dieses Gen, und sind sich daher darüber bewusst, dass ihnen die User
nichts anhaben können.

Anders kann ich mir solch ein clichéhaftes Adminverhalten nicht erklären.

Und ja, ich bin auch Admin (z.B. für Hostingkunden, aber auch damals zu
Schulzeiten im Schulnetzwerk), es macht Spaß, und ich habe nie auch nur
das Bedürfnis verspürt, solche Aktionen zu starten. Wenn ich doch mal
jemanden gestört habe, dem ich eigentlich helfen wollte, habe ich mich
dafür entschuldigt. Bin ich abnormal?

(Meine Theorie: Ich verdränge die Angst, nicht das Admin-Gen zu besitzen.)

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

Was soll das?

Ich: "Und wenn sie nein sagen, dann ..."
Du:  "Aber es kann eben auch ein Nein dabei heraus kommen."

So kann man nicht miteinander reden. Ich mache mir die Mühe, deine Texte
aufmerksam zu lesen, und dasselbe erwarte ich auch von dir.

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

Dem wollte ich nicht widersprechen. Ich meinte nur, dass in Sachen
DSL die LISP-Sprachen (Common LISP, Scheme) sehr interessant sind.
Dort ist dieses Konzept quasi "eingebaut".

Und deiner DSL nachher einer schicke Optik zu verpassen, weil nicht
jeder die vielen Klammern der S-Expressions mag, ist viel angenehmer
als gleich einen Parser, Interpreter, etc. zu schreiben. Die Grenze
zwischen Unterprogrammen und Interpreter verschwindet. Schon genial,
so eine programmierbare Programmiersprache.

Aus diesem Aspekt heraus ist das jedenfalls hochinteressant.

> > Und der
> > Interpreter deiner DSL, worin schreibst du den?
> 
> Soll ich antworten, oder weisst Du die Antwort bereits? ;-)

Das hast du aus dem Zusammenhang gerissen. Es ging um die Frage,
welche Programmiersprachen du verwendest, und du hast u.A. die
Antwort "DSL" gegeben. Die rhetorische Frage sollte dir eigentlich
klar machen, dass du die Antwort damit nur verschoben hast, weil
du immer noch einen Interpreter für die DSL schreiben musst.

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

Nein, das Problem war genau andersherum: Es gab zu viel von solchem
Code. Sinnlose Abfragen von NULL und sonstawas. Und warum? Weil wir
(2-Mann-Team, ich mit einem Freund) ständig Pointer benutzt haben,
als wären wir in C.

Und natürlich waren nicht alle NULL-Abfragen perfekt, und es war
nicht immer klar, wann was ein delete bekommen muss. Und das, obwohl
der Code streng hierarchische Datenstrukturen hatte, also im Prinzip
ohne jeden Garbage-Collector auskommt.

Die Antwort in C war dann: Kein "new", stattdessen lokale
Objekt-Variablen, RAII-Prinzip beachten, Referenzen und Objektkopien
statt Pointer. Schon verschwindet ne Menge Boilerplate-Code. Das
ganze ist bugfreier, und viel, viel weniger potentielle Segfaults.
Bis auf eine einzige Ausnahme kein einziges "delete". Das heißt,
keine Memory-Leaks, und trotzdem ohne Garbage-Collector. Das ist
etwas, das C++ einzigartig macht. Völlig ungewohnt aus Python,
Java, C, ...

Seit ich die Konzepte und Prinzipien von C++ besser verstanden habe,
mag ich die Sprache sogar.

> Aber es gibt Leute, die einfachgrundsätzlich zu
> faul sind, Fehlerbedingungen abzufragen oder
> nicht gewillt sind ihre Programmiertechniken anzupassen.

Nun, das ist eine andere Baustelle. Gibt's natürlich auch, und dieses
Phänomen ist unabhängig von der Programmiersprache, da stimme ich zu.
:-)

> ...es gibt eben Leute, die arbeiten gerne mit dem Debugger.
> ...und es gibt andere, die brauchen keinen Debugger.
> 
> So einfach ist das.

Es gab ein paar Unsauberkeiten, die wir allein mit Debug-Messages
nicht finden konnten. Sie resultierten aus einem teilweise falschen
Verständnis von C++, ohne Debugger hätten wir das nicht gefunden.

Aber ansonsten: Ja, ich stimme zu, wenn man ordentlich entwickelt,
braucht man den Debugger kaum. Man debuggt gleich beim Schreiben,
und zahlt dort einen viel niedrigeren Preis als später in der
Fehlersuche. Dieses Prinzip namens "Inkrementelle Programmierung"
ist aber uralt, und wird *eigentlich* jedem Neuling mit als erstes
beigebracht.

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

Ich schrieb mein Beispiel unter der Annahme, dass es mehrere GB RAM
gibt, wie du selbst geschrieben hast. Auch hier: Bitte nicht meine
Aussagen aus dem Kontext reißen. Das bringt doch nichts.

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

Jein. Auch wenn die Sortierung allein im RAM stattfindet, ist es
zu empfehlen.

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

Darauf war ich in der letzten Mail genauestens eingegangen. Ich verstehe
daher den Sinn dieser Fragen nicht.

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

Du kannst jederzeit die "Chunk"-Größe zu wählen, dass du letztlich alles
im RAM hast. Du verlierst also nichts, aber hast die Möglichkeit, den
Prozess so fein- oder grob-granular zu gestalten, wie du es brauchst.

Die optimale Blockgröße für deine Anwendung zu finden, ist dann relativ
leicht, weil du mit solch einem flexiblen Ansatz ja einfach probieren
und dann messen kannst.

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

Ja, ich meinte was völlig 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.

... hmm, das scheitert genauso wie letztes Mal. Ich weiß nicht,
wie ich das verständlich rüber bringen soll.

Andererseits magst du ja Rätsel. Also probier ich mal was: Ich gebe
dir ein Rätsel auf, und wenn du das gelöst hast, hast du auch
verstanden, was ich meine.

Gegen ist irgendeine Programmiersprache, für die du einen Compiler
schreibst. Keine Optimierung oder ähnlicher Fusel, die Sprache sei
beliebig einfach (meinetwegen nur S-Expr), und der "Maschinencode"
muss auch nicht absolut low-level sein. Du darfst z.B. auch C-Code
statt Maschinencode erzeugen. Verschwende an diesen Details also
keine Zeit. Der Compiler kriegt den Programmcode von stdin und spuckt
den Maschinencode nach stdout aus.

Einzige wichtige Bedingung: Keine Symboltabelle, keine Optimierung
des "Maschinencodes"! Alles schön einfach halten. Sonst ist das Rätsel
unlösbar.

Der zu compilierende Code bestehe aus N Tokens. Diese sind natürlich
irgendwie verschachtelt (z.B. enthält ein Funktionsaufruf Parameter,
die wiederum Funktionsaufrufe enthalten können, u.s.w.). Die maximal
Verschachtelungstiefe unseres Programmcodes sei T.

Wir sind uns sicher einig, dass die Laufzeit unseres Compilers von
der Ordnung O(N) sein wird: Doppelt soviel Tokens im Programmcode
heißt doppelt so viel Ausgabe und doppelt so lange Compiler-Laufzeit.
Soweit alles normal.

Aber der Speicherbedarf des Compilers soll nicht O(N) betragen, sondern
nur O(T)! Nach deiner Aussage müssen alle Programm-Tokens sowieso
irgendwie im RAM liegen, d.h. du würdest niemals unter O(N) kommen.
Ich behaupte jedoch, du kannst den Compiler so schreiben, dass in
O(T) arbeitet. Dein Programm kann also auch 100x so groß sein. Solange
er nicht "komplizierter" ist (also tiefer verschachtelte Sprachelemente
hat), braucht der Compiler genauso wie RAM wie vorher.

Nochmal zusammengefasst:
* billiger 1-Pass-Compiler
* Laufzeit:       O(N)
* Speicherbedarf: O(T)

Ich hoffe, das Rätsel ist inhaltlich klar. Du kannst jederzeit fragen.
Ich würde dir die Antwort auf das Rätsel gern verraten und erklären, aber
das versuche ich ja schon die ganze Zeit. Ich bin offensichtlich nicht
dazu in der Lage. Aber vielleicht bist du in der Lage, es dir selbst
zu erschließen. Viel Glück dabei!

Du wirst mit einer tiefen und meines Erachtens nach wichtigen Einsicht
belohnt.

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

Ja, aber wenn du z.B. nur ein paar kBytes zurück-"seekst", brauchst
du keine Angst vor der Performance zu haben. Dann lieber den einfacheren
Code mit "seek" schreiben, statt einen künstlichen zweiten Cache zu
bauen.

> Mehr als diese allgemeine Aussage kann man hier nicht treffen,
> denn sonst können wir gleich ein Buch schreiben.
> (Keine schlechte Idee, eigentlich, was? :))

Ein Buch über KISS, und warum verfrühte Optimierung böse ist,
mit zahlreichen Beispielen "richtig" <-> "falsch". Das wäre
lustig, ja.

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

Nein, es steckt ein noch viel wichtigerer Hinweis drin. Das heißt, soo
wichtig ist er nicht, auch nicht für dein Projekt. Aber die Tatsache,
er dir nicht klar ist, macht ihn (für dich) zu einem guten Hinweis.
Ich hoffe, du nimmst ihn an, indem du versuchst, das "Rätsel" zu lösen.

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

Was ich beschrieben habe, dürften wohl eher 3 Zeilen sein. Oder 10
Zeilen, wenn man nicht die 80-Zeichen-Grenze voll ausreizt. ;-)

In der Größenordnung 5-20 Zeilen (2-6 davon Variablendeklarationen)
habe ich gute Erfahrungen mit Shell-Scripten gemacht. Kann ich nur
empfehlen. Für alles, was höhere Ansprüche hat, würde ich dann
Python als Scriptsprache empfehlen.

(oder auch als Implementierungssprache, aber das ist ne andere Schiene.)


Viele Grüße,

    Volker

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