Immutable Objekte und funktionales Programmieren in Java oder Scala

[Marco13]

Hi

Objekte "immutable" zu machen kann man, sofern ich das bisher richtig verstanden habe, als wichtigen Teilaspekt "sauberer" funktionaler Programmierung bezeichnen. Es hat in der funktionalen Welt einfach viele Vorteile und fügt sich besser in diesen eher mathematisch angehauchten Programmierstil ein.

Aber wie ist das in der Praxis? Macht der Immutable-Gedanke nicht eher (oder nur?) bei "kleinen" Objekten Sinn? Bei kleineren mathematischen Objekten, wie etwa einem 3D-Vector würde man wohl versuchen, sie immutable zu machen. Bei Sprachen mit Garbage Collection kann das auch Nachteile bringen, wie häufiges GC'en von kleinen Objekten, aber die GCs werden auch immer besser, und vielleicht ist das nur dann ein Nachteil wenn man wirklich viele Vector3D-Objekte anlegt und wieder löscht, und das ganze in einem zeitkritischen Anwendungsbereich (speziell 3D-Spiele).

Bei größeren Objekten würde das aber doch höchstens Sinn machen, wenn die nur selten verändert werden würden, oder an diesen Objekten immer relativ große Teile verändert werden würden. Wenn man sich aber z.B. vorstellt, dass man mit Graphen oder Matrizen rumhantieren will, die eben auch mal 10000x10000 Elemente oder 1 Million Knoten haben, kann es doch nicht mehr sinnvoll sein, für die Änderung EINES Eintrags der Matrix oder eines Knotens einige hundert MB Speicher zu allokieren und dort den Inhalt des "alten" Speichers reinzukopieren, dann 4 bytes zu ändern, und den "alten" Speicher in den Müll zu werfen?

Im Widerspruch dazu steht, dass man ja gerade die "großen" Objekte gerne mit mehreren Threads verarbeiten würde, und gerade dann würde die Immutabilität ja mit dem Vorteil ihrer impliziten Threadsicherheit glänzen.

Wie kann man dieses Dilemma auflösen? :bahnhof:

 

[maki]

Auch in der OOP sind immutables ein gutes Mittel, um zB. Aliasing Probleme in den Griff zu bekommen, das Design kann dadurch auch klarer werden (große Objekte aufspalten in immutables und veränderliche), dazu kommt, das immutables eigentlich immer Werteobjekte sind (keine Refrenztypen), und dadurch wiederverwendet werden können (zB. im Fliegengewicht Muster), für den GC ist der Gültigkeitsbereich wichtig, aber wenn sie sowieso wiederverwendet werden
Im Multithreadingbetrieb (auf Multiprozesormaschinen) haben sie auch ihre Vorteile, siehe zB. Scala, anstatt eine ganze Collection zu locken beim verändern wird sie kopiert, die anderen Prozessoren müssen nicht (solange) warten.

 

[Marco13]

Ja, sie haben einige Vorteile. Aber um den Punkt nochmal herauszustellen: Wenn man ein 500 MB großes Objekt hat, und man dann wegen der Immutabilität darin nicht 2 bytes ändern kann, sondern eine Kopie davon anlegen muss (in der 2 bytes geändert sind) kommt man doch aus dem Allokieren und Löschen nicht mehr raus ???:L

 

[SlaterB]

es ist wie es ist, aber man muss es ja nicht machen,

wie maki schon schrieb kann man das Objekt evtl. zerlegen und nur zum Teil austauschen,
wenn es in binärer Baum mit 2x 250MB-Kindern ist, dann muss man nur eine neue Wurzel von paar Bytes erstellen und einen der Teilbäume neu,
schon 50% gespart,

der Teilbaum von 250 MB muss auch wieder nicht komplett neu, sondern kann wieder geteilt werden usw.,
selbst bei meheren Änderungen gleichzeitig sind vielleicht nur 20 innere Knoten und 300 Bytes betroffen, der große Rest bleibt unverändert

 

[Marco13]

Hm. Das klingt jetzt für mich verwirrend. Wenn man statt des Baumes nun einen Graphen mit 1 Million Knoten betrachtet, und man will dort... irgendwas mit mehreren Threads machen, meinetwegen ein Flood-Fill (Breitensuche) das einfach nur die Knoten einfärbt - dann muss man
- für jede Farbänderung einen neuen Knoten erstellen
- für jeden neuen Knoten einen neuen Graphen erstellen
oder entweder die Knoten oder den Graphen mutable machen, womit die Threadsicherheit wieder hinüber wäre... :bahnhof:
Der "funktionale" Teil der funktionalen Programmierung ist mir ja recht sympathisch, Rekursionen und zustandsfreie Berechnungen sind ja toll, aber ... vielleicht fehlt mir noch irgendein *klick* im Kopf um zu verstehen, wie man das mit der Manipulation (d.h. Veränderung) von großen Datensätzen in Einklang bringen kann... ???:L

 

[maki]

Versuche mir mal ein Beispiel aus den Rippen zu schneiden, nicht schimpfen wenn es hinkt

Ein Graph mit einer Mio. Knoten:
Knoten beinhalten nur Struktur, sind immutable.
Die eigentlichen Daten sind mutable.

Oder umgekehrt:
Knoten beinhalten nur Struktur, sind mutable.
Die eigentlichen Daten sind immutable.

Ist da eine etwas passendere Struktur für deine Frage dabei?

 

[Landei]

Auch größere Strukturen lassen sich unveränderlich machen. Ein Graph kann man z.B. als Set von Vertexes und einer Map von Vertexes auf Edges repräsentieren, damit lassen sich Änderungen recht unproblematisch realisieren.

Eine allgemeiner Ansatz für größere Objekte ist der Zipper.

 

[Marco13]

@maki: Falls ich das jetzt richtig verstanden habe, würde man im ersten Fall die eigentlichen Daten (mutable) getrennt vom Graphen speichern. Aber dann würden die Vorteile wie Threadsicherheit ja evtl. wieder verloren gehen..!?

@Landei: Das mit dem Zipper muss ich mir mal genauer ansehen. Allerdings stelle ich es mir ziemlich aufwändig vor, "beliebige" Strukturen, die man eigentlich einfach ganz straightforward hinschreiben würde (wie z.B. den Graphen als Set<Vertex> und Map<Vertex,EdgeList>) in die formal richtige "Zipper"-Forum zu bringen.

Vielleicht habe ich auch eine "falsche" (oder zumindest unpassende) Interpretation des Wortes "Immutable". Man könnte da eigentlich unterscheiden zwischen "deep immutable" und "shallow immutable": Eine List, die mit Collections.unmodifiableList(...) erzeugt wird, ist an sich zwar "immutable", aber wirklich (deep) immutable wäre sie ja eigentlich nur, wenn sie auch NUR Immutable Objekte enthält...?

Es geht auch nicht direkt um die Lösung eines konkreten Problems, sondern eher um den allgemeinen Umgang mit großen Objekten und deren Manipulation bei funktionaler Programmierung (auch wenn die Frage an sich vielleicht einen konkreteren Anlass hat). Vielleicht ein anderes Beispiel als den Graphen, wo vielleicht die Frage deutlicher wird: Angenommen, man hat eine Matrix-Klasse, die ihre Einträge intern als float[] speichert. Wenn man nun in diese Matrix-Klasse die üblichen Methoden einbauen will, und sie immutble sein soll, dann müßte man ja schreiben

public Matrix add(Matrix other)
{
    Matrix result = new Matrix(copyOf(this.array));
    for (all entries) result.array[i] = this.array[i] + other.array[i];
    return result;
}

D.h. wenn man sowas schreibt wie

Matrix result = matrix.add(a).add(b).add(c);

dann werden da 3 mal Kopien eines (u.U. eben 500 MB großen) Arrays angelegt, die eigentlich nicht gebraucht würden.... Noch deutlicher würde die Verschwendung bei

public Matrix setElement(int x, int y, float value)
{
    Matrix result = new Matrix(copyOf(this.array));
    result[indexFor(x,y)] = value;
    return result;
}

Spätestens wenn man das in einer Schleife aufruft wie

Matrix m = new Matrix(....);
for (int i=0; i<[b]10000[/b]; i++)
{
    m = m.set(i,i,1.0f);
]

wird es doch absurd...???:L

 

[slawaweis]

Immutable spielt auch in OOP eine große Rolle. In OOP gibt es das Problem, dass wenn Referenzen auf mutable Objekte in einem anderen Objekt direkt gespeichert werden, ohne es vorher zu klonen, kann man das mutable Objekt von Außen ändern, an der Funktionalität des kapselnden Objektes vorbei. Das führt irgendwann zu Fehlern. So sind die Alternativen um diesen Fehler gleich zu vermeiden, entweder fast jedes Objekt beim Setzen zu klonen oder eben immutable Objekte zu verwenden.

In der Praxis kommt es auf die Funktionalität an. Am besten wäre es ein immutable und ein mutable Objekt zu haben, die nicht von einander ableiten, aber jeweils konvertieren können. Dann sucht man sich das besser passende Objekt für eine Aufgabe aus. In der Schnittstellenspezifikation verwendet man dann z.B. immutable Objekte, wegen Designsicherheit; bei der Verarbeitung in der Blackbox mutable Objekte, wegen der Performance.

EDIT:

D.h. wenn man sowas schreibt wie

Matrix result = matrix.add(a).add(b).add(c);

dann werden da 3 mal Kopien eines (u.U. eben 500 MB großen) Arrays angelegt, die eigentlich nicht gebraucht würden....

ganz genau, es werden 3 Kopien angelegt. Bei 3x3 Matrizen ist es auch kein Problem. Wenn man aber Probleme größerer Dimensionen hat, kann man sein Framework um zusätzliche Klassen erweitern, wie einen MatrixBuilder:

Matrix result = new MatrixBuilder().start(matrix).add(a).add(b).add(c).build();

So wird das Array im besten Fall nur einmal am Ende kopiert.

Slawa

 

[Marco13]

Am besten wäre es ein immutable und ein mutable Objekt zu haben, die nicht von einander ableiten, ...

Nicht unüblich ist ja sowas wie

interface Model {... getter ... }
interface MutableModel extends Model { ...setter... }

aber das passt in diesem Fall ja nicht. Der Gedanke mit dem MatrixBuilder ist ja so gesehen ein "Spezialfall" von solchen nicht-verwandten Mutable/Immutable Implementierungen, denn man könnte ja auch sowas machen wie

// Matrix result = new MatrixBuilder().start(matrix).add(a).add(b).add(c).build();  
   Matrix result = new MutableMatrix(matrix).add(a).add(b).add(c).buildImmutableMatrix();

Bei einzelnen Fällen kann man wohl immer eine Lösung finden, aber es ist IMHO schwierig (und schade) dass dieser Punkt so starken Einfluß auf die Schnittstellen und die Klassenstruktur haben müßte. Und diesen Punkt im wirklich funktionalen Sinne zu verallemeinern ist wohl schwierig und potentiell unschön. Das Beispiel ist etwas holprig, sorry, aber wenn man nun nicht vordefinierte Methoden wie "add(other)" haben will, sondern allgemeine....

interface MatrixFunction { Matrix f(Matrix input); }

class Matrix 
{
    Matrix apply(MatrixFunction f)
    {
        return f.f(this);
    }
}

Matrix result = matrix.apply(add).apply(sub).apply(mul).apply(scale);

muss man sich ja schon Sachen überlegen, die das ganze ziemlich unhandlich und eher wie einen krampfigen Workaround aussehen lassen würden...

 

[Landei]

Es geht auch nicht direkt um die Lösung eines konkreten Problems, sondern eher um den allgemeinen Umgang mit großen Objekten und deren Manipulation bei funktionaler Programmierung (auch wenn die Frage an sich vielleicht einen konkreteren Anlass hat). Vielleicht ein anderes Beispiel als den Graphen, wo vielleicht die Frage deutlicher wird: Angenommen, man hat eine Matrix-Klasse, die ihre Einträge intern als float[] speichert. Wenn man nun in diese Matrix-Klasse die üblichen Methoden einbauen will, und sie immutble sein soll, dann müßte man ja schreiben

public Matrix add(Matrix other)
{
    Matrix result = new Matrix(copyOf(this.array));
    for (all entries) result.array[i] = this.array[i] + other.array[i];
    return result;
}

D.h. wenn man sowas schreibt wie

Matrix result = matrix.add(a).add(b).add(c);

dann werden da 3 mal Kopien eines (u.U. eben 500 MB großen) Arrays angelegt, die eigentlich nicht gebraucht würden....

Man könnte eine statische Funktion Funktion Matrix.sum(Matrix ... m) schreiben. Oder man nutzt einen veränderlichen Datentyp, der aber nur "intern" verwendet wird, und von außen unsichtbar bleibt (schönes Beispiel ist java.math.MutableBigInteger, die package private ist und für "interne Berechnungen" von BigInteger verwendet wird).

Noch deutlicher würde die Verschwendung bei

public Matrix setElement(int x, int y, float value)
{
    Matrix result = new Matrix(copyOf(this.array));
    result[indexFor(x,y)] = value;
    return result;
}

Natürlich würde das absurd, aber nur weil man "innen" einen ungeeigneten Datentyp verwendet hat. Ist die Matrix dünn besetzt, würde man (übrigens auch im mutablen Fall) eine Map o.ä. verwenden, wo obige Operation kein Problem wäre. Ist die Matrix dicht gepackt...

a b c d
e f g h
i j k l 
m n o p

... könnte man z.B. einen Baum verwenden, bei dem jeder Knoten vier Kinder hat, also bei jedem Schritt "geviertelt" wird:

root hat die Kinder 1 (oben links), 2 (oben rechts), 3 (unten links), 4 (unten rechts)
1 hat die Kinder a, b, e, f
2 hat die Kinder c, d, g, h
3 hat die Kinder i, j, m, n
4 hat die Kinder k, l, o, p

Soll nun eine Matrix mit geändertem g -> g1 erzeugt werden, können wir die Teilbäume 1, 3 und 4 wiederverwenden, der neue Teilbaum 5 wird aus c, d, g1 und h zusammengesetzt, und die neue Matrix aus 1, 5, 3, 4. Ist die Matrix größer, wird der zu ändernde Teil relativ immer kleiner und fällt damit viel weniger ins Gewicht wie mit dem Array als Datenstruktur.

 

[Marco13]

Hmjaa... diese Matrix so als Baum zu speichern wirkt zwar im Hinblick auf das zu erreichende Ziel "mathematisch elegant", aber in der Praxis wäre das doch ein Krampf :autsch: abgesehen davon, dass man dann eben einfach keinen float-Array mehr hat, durch den man bei Multiplikationen usw. schnell durchlaufen kann. Da würde mir eine einfache und effiziente (!!!) Mutable-Implementierung, die bei bedarf eine Immutable rausspuckt, schon eher zusagen. Trotzdem kann ich mir im Moment kaum vorstellen, wie dort eine "schöne" funktionale API rauskommen soll, mit der sowas wie hier unten angedeutet einfach und effizient machbar ist...
Muss mal bei Gelegenheit ein bißchen rumspielen, mal schauen was da rauskommen könnte...

 

[Landei]

Mal ein Praxisbeispiel (auch wenn es Scala ist): Ich werkele ein wenig an der 3D-Engine Sgine. Deren Mathe-Package war zweigeteilt, es gab einen immutablen und einen mutablen Teil, weil sich der Projekt-Chef um die bei Real-Time-3D-Grafik unglaublich wichtige Performance gesorgt hat. Aber jetzt wird Sgine umgearbeitet, um die Mathe-Package eines anderen Projekts (Simplex3D) zu benutzen, nachdem sich herausgestellt hat, dass deren API einfacher und die Performance mindestens gleichwertig ist. Das lustige ist, dass diese neuen Mathe-Klassen alle immutable sind (als einziges Problem hat sich die Garbage Collection herausgestellt, es sieht aber so aus, als hätte man das inzwischen im Griff). Bei einer High-Performance Anwendung mit kleineren Matrizen, Vektoren und Quaternionen kann also eine hochoptimierte immutable Lösung mit einer mutablen Lösung mithalten, und das bei allen Vorteilen, die Unveränderlichkeit gerade im 3D-Umfeld bringt. Ich denke das spricht für sich.

 

[Landei]

Hmjaa... diese Matrix so als Baum zu speichern wirkt zwar im Hinblick auf das zu erreichende Ziel "mathematisch elegant", aber in der Praxis wäre das doch ein Krampf :autsch: abgesehen davon, dass man dann eben einfach keinen float-Array mehr hat, durch den man bei Multiplikationen usw. schnell durchlaufen kann.

Da irrst du dich, die Multiplikation kann auch rekursiv auf die Multiplikation von Teilmatrizen zurückgeführt werden - das ist kaum langsamer als ein Array. Dasselbe gilt für Determinanten und viele andere Operationen.

Im übrigen machst du etwas falsch, wenn du große Matizen mit der naiven Methode multiplizierst, denn der Strassen-Algorithmus ist schneller. Dieser Algorithmus beruht übrigens auch auf einer Unterteilung der Matrix in 4 Teilmatrizen, ihm kommt also meine vorgeschlagene Struktur entgegen.

 

[Marco13]

Hmja, weiter oben hatte ich ja schon angedeutet, dass für Matrizen und Vektoren bis 3D wohl die Vorteile überwiegen, und als größte Gefahr die schlechtere Performance durch den GC genannt.

BTW:
(als einziges Problem hat sich die Garbage Collection herausgestellt, es sieht aber so aus, als hätte man das inzwischen im Griff)
Jetzt ist nicht klar: HAT es sich als Problem herausgestellt, oder HAT man es im Griff?

Aber wenn das mit dem GC kein Problem mehr ist, ist die Immutable-Lösung natürlich schöner, gerade in Scala. (In Java gibt es das "vecmath" package mit 3D-Primitiven ... schlimm genug, dass dort sowas wie Vector3d mutable ist - die Fields x,y, und z sind auch noch public :noe: )


Aber bei größeren Matrizen können dort eben Probleme auftreten. Und in bezug auf Strassen und Divide & Conquer: Es ging - wie auch bei dem Beispiel mit den Graphen - nicht um ein unmittelbares, konkretes Problem, sondern um die allgemeine Frage, wie man mit großen Datenblöcken umgeht. Und um alles, was damit zusammenhängt (Z.B. dass man dabei durch das "Erstellen veränderter Kopien" leicht an die Grenzen des verfügbaren Speichers stößt, oder wie man z.B. ein Interface für eine funktional zu verwendende (große) Matrix vernünftig definiert)

Aber vielleicht werden meine Hirnknoten sichtbarer, wenn ich mal konkreter werde: Ich hatte mal ganz straighforward hingeschrieben, wie ein Interface für eine generische Matrix aussehen könnte. Und wenn dort eine Methode drinsteht

GenericMatrix2D<T> set(int r, int c, T t);

tauche eben die ersten Fragezeichen auf. Die Sache mit dem Baum mag ja ja formal eine Lösung sein. Die einfachste und "funktionalste" Lösung wäre da wohl die Baumknoten schlicht und einfach wieder als Matizen zu speichern (zumindest in erster Näherung). Aber wenn man die möglichen Implementierungen mal überschlagsweise vergleicht...

public GenericMatrix2D<T> set(int r, int c, T t)
{
    array[c+r*cols] = t;
    return this;
}

vs.

public GenericMatrix2D<T> set(int r, int c, T t)
{
    // Ein Blatt is einfach eine 1x1-Matrix
    if (size().equals(1,1)) 
    {    
        return createOneElementMatrixFrom(t);
    }
    GenericMatrix2D<T> result = create();
    int affected = computeAffectedIndex(r,c);

    // Teilbäume/Untermatrizen weiterverwenden
    for (int i=0; i<4; i++)
    {
        result.treeNodes[i] = this.treeNodes[i];
    }

    // Rekursiv bis zu den Blättern runterhangeln
    int localRow = computeRowInTreeNode(affected, r);
    int localCol = computeColInTreeNode(affected, c);
    result.treeNode[affected] = this.treeNode[affected].set(localRow, localCol, t);
    return result;
}

Dann ist IMHO klar, was passiert, wenn jemand die Matrix mit

for (int r=0; r<10000; r++)
{
    for (int c=0; c<10000; c++)
    {
        matrix = matrix.set(r,c,valueFor(r,c));
    }
}

mit irgendwelchen Werten füllen will. Man könnte jetzt sagen: Ja, dann muss es eben eine Methode geben wie
Matrix#fillWith(ValueProviderFunction v);
und der Benutzer ist selbst schuld, wenn er "so blöd ist, anzunehmen, dass man in einer Matrix einfach so ein Element setzen kann". Aber so ganz behagt mir das nicht. Ich muss mir wohl wirklich erstmal die Zeit nehmen, da mögliche Strukturen und Implementierungen durchzudenken, vielleicht kommt ja noch der :idea:-Effekt...

 

[Landei]

BTW:
(als einziges Problem hat sich die Garbage Collection herausgestellt, es sieht aber so aus, als hätte man das inzwischen im Griff)
Jetzt ist nicht klar: HAT es sich als Problem herausgestellt, oder HAT man es im Griff?

Es HAT sich als Problem herausgestellt (ruckelnde Darstellung), die Situation konnte aber zumindest verbessert werden und an einer weiteren Optimierung der GC wird gearbeitet.

 

[Guest2]

Moin,

ich bin ein Sympathisant von immutablen Objekten und final gehört wahrscheinlich zu dem am häufigsten genutzten Schlüsselwort in meinen Programmen (Alles "final bis zur Wurzel" ist ja praktisch immutable). Andererseits bin ich ein noch größerer Liebhaber von "zum Problem angepasste Lösungen". Und imho gibt es Probleme die sich genauso wenig in funktionale wie in immutable Lösungen quetschen lassen.

Der Grundsätzliche Ablauf innerhalb einer 3D Engine ist, dass zyklisch für jedes Frame immer wieder (fast) exakt dasselbe berechnet wird. Und die einzig existierende wirklich wichtige Kenngröße ist, das die maximale Zeit zwischen zwei Frames nicht wesentlich über 16ms steigen sollte. Was nutzt es, wenn die Engine 5000 FPS ereicht, aber jedes 1000te Frame 50ms dauert? Da kann auch imho der GC optimiert sein wie er will, entweder ich nutze meine Objekte zum großen Teil wieder und verhindere so, dass der GC überhaupt was zu tun hat, oder ich hab ne Engine die lagt.

Auch das in vecmath die Primitive public floats sind, wirkt nur merkwürdig, wenn man sie als Objekte im Sinne der OOP auffasst. Sieht man sie mehr als weiteren "nativen" Datentyp an, eben wie ein normales float nur 3Fach, wirken sie imho fast natürlich. In C würde man ein einfaches struct bauen. Aus sicht der Compiler Optimierung macht das schon Sinn. Wahrscheinlich kann der JIT Compiler relativ viele Fälle davon direkt auf die Register abbilden und dann ist es vollkommen egal, ob das Primitiv wiederverwendet wird oder nur kurz lebt, der GC hat nichts zu tun.

Auch bei großen Matrizen oder allgemein großen Blöcken von Daten auf denen "rumgerechnet" werden soll, mach immutable imho wenig Sinn. 500MB große Matrizen klingt fast schon nach HPC. Und da ist es vor allem wichtig, das 1. das Ergebnis stimmt und 2. das Ergebnis in einem annehmbaren Zeitraum zu Verfügung steht. Wenn der Cluster 2 Monate länger rechnet, warten nicht nur ne menge Leute auf die Ergebnisse, sondern am Ende stehen auch knapp 70MWh mehr auf dem Stromzähler. Immer wieder hin und her kopieren kann dann keine Lösung sein. Auch die Daten auf Bäume zu verteilen klingt erstmal super, dumm ist nur wenn der benötigte Knoten des Datensatzes dann grade aktuell im Nachbarrack steckt. Zur Synchronisation der einzelnen Threads kommt dann auch noch das "zusammenhalten" der Daten hinzu.

Hier wurden vor einiger Zeit Strömungssimulationen bei Nasenrekonstruktionen durchgeführt, und zwar während der Patient auf dem OP Tisch lag! Kommt nicht gut, wenn die Ergebnisse nicht rechtzeitig da sind, weil der Entwickler gerade ein paar "hipe" Softwaretrends nach gehächelt ist und dabei das eigentliche Problem aus den Augen verloren hat.


Das soll kein Plaidoyer für unnötige Optimierungen sein, sondern nur daran erinnern, dass es Situationen gibt, in denen man auch schon vorher ziemlich sicher sein kann, dass die "hipe" Implementierung in die Hose gehen wird. Nur weil eine Technik schon was älter ist, muss sie nicht zwangsweise unterlegen sein.

Unabhängig vom zeitkritischen ist imho eine sinnvolle / ausgewogene Implementierung auch nur für ein konkretes Problem und unter der Betrachtung des Umfeldes möglich. Das macht es für Lib Entwickler nicht einfach, es sei den die Lib Entwicker suchen sich für "Ihre" Lib eben genau eine Nische die sie füllen wollen.

(Langer Text und keine konkrete Aussage, hätte wohl Politiker werden sollen )

Gruß,
Fancy

 

[Landei]

Alles "final bis zur Wurzel" ist ja praktisch immutable

Wie kommst du darauf? Verwendest du Arrays oder Listen oder Date oder ... ? Dann ist dein Code nicht immutable.

Und wie ich schon gesagt habe, reicht es nicht, einfach alles immutable zu machen, die Datenstrukturen und Algorithmen müssen entsprechend angepasst werden.

Zu meinem Grafik-Engine-Beispiel kann ich nur sagen, dass die Integration der immutablen Mathe-Klassen beschlossen ist, auch wenn es - wie zu erwarten war - noch ein paar Probleme gibt. Wenn die Integration abgeschlossen ist, könnt ihr die Engine gern selber testen statt wild zu spekulieren.

 

[Marco13]

Dann nochmal die Frage: Wenn jemand von "Immutable" redet, meint er dann ein "shallow Immutable" oder ein "deep Immutable"? Ich würde sagen, dass nur letzteres wirklich konsequent im Hinblick auf die anvisierten Ziele ist.

Das soll ja jetzt auch kein "wildes Spekulieren" sein. Im Gegenteil. Ich habe diesen Thread erstellt, um eben NICHT mehr spekulieren zu müssen. Wobei ich ja schon gesagt habe, dass ich davon ausgehe, dass die Vorteile der Immutabilität bei "kleinen" Objekten (auch im Rahmen einer 3D-Engine) eher überwiegen, aber bei "großen" Objekten habe ich da eben (immer) noch Zweifel.

@Guest2: (Leg' dir doch mal'n account zu, Mensch :bae: ) Vielleicht war ja nicht deine Antwort, sondern meine Frage "Politikergelaber": Ich hätte auch ganz direkt fragen können: Kann es sein, dass funktionale Programmierung (und die konsequente Einhaltung von Immutabilität) bei "großen Datenblöcken" keinen Sinn macht? Aber irgendwie würde mir das nicht einleuchten. Lisp wurde ja auch nicht ausschließlich für "toy examples" und akademisches Gefrickel entwickelt. Inwieweit die mutablen Container bei Scala ein Tribut an die Java-Verwandtschaft ist, oder ein Tribut an die Effizienz, weiß ich aber nicht.
(Nebenbei, mal ganz pragmatisch formuliert: Mit immutable-Klassen eine (arraybasierte, d.h. nicht-verkettete) Liste mit n (einzeln eingefügten) Elementen zu erstellen hat Laufzeit O(n^2). Mit mutablen Listen nur O(n)....)

Und BTW: Es geht nicht um "hipe" (ich nehme an du meinst "hippe" im Sinne von "Hype-Orientierte") Implementierungen, sondern darum, dass viele Punkte bei Graphen- oder Matrizenrechnung sich unglaublich schön und elegant funktional beschreiben lassen. Und ich habe gemerkt, dass ich in meine Mini-Graphenbibliothek immer mehr funktionale Aspekte eingebracht habe, nicht weil es "hipp" ist, sondern weil es elegant, flexibel und praktisch ist (modulo der sprachlichen Unzulänglichkeiten von Java in diesem Punkt). Wenn man nun den existierenden Code existierenden Code sein lassen wollte, und versuchen wollte, eine saubere, rein funktionale Bibliothek für Graphen und/oder Matrizen zu erstellen (vielleicht eben in Scala, weil es da besser, sauberer und (jetzt modulo der für mich noch nicht ganz zu erfassenden Möglichkeiten der Sprache) auch einfacher ist, sollte man sich schon im klaren sein, was da rauskommen könnte...

 

[Guest2]

Wie kommst du darauf? Verwendest du Arrays oder Listen oder Date oder ... ? Dann ist dein Code nicht immutable.

Natürlich nutze ich Arrays, Listen und auch alles andere. Ein Beispiel:

public final class Foo {

    private static final int    SIZE   = 42;

    private final List<Integer> values = new ArrayList<Integer>(SIZE);
    private final Random        random = new Random();


    public Foo() {

        for (int i = 0; i < SIZE; i++)
            values.add(random.nextInt());

    }


    public int get(final int index) {

        return values.get(index);

    }

}


public final class Bar {

    private final List<Foo> foos = new ArrayList<Foo>();

    public Bar(){

        for(int i = 0; i < new Random().nextInt(10); i++)
            foos.add(new Foo());

    }


    public List<Foo> getFoos() {

        return Collections.unmodifiableList(foos);

    }

}

Nach meinem Empfinden sind sowohl Foo als auch Bar immutable. Und ich vermute, dass ist das was Marco mit "deep Immutable" meint. Persönlich habe ich aber auch kein Problem damit z.B. Bar um folgende Methode zu erweitern:

    public void addFoo(final Foo foo){

        foos.add(foo);

    }

Dann ist Bar natürlich nicht mehr immutable! Aber ich kann immer noch garantieren, dass es nicht durch "unbeabsichtigte Referenzen" zu Inkonsistenzen innerhalb meiner Klassen kommt.

Ich hätte auch ganz direkt fragen können: Kann es sein, dass funktionale Programmierung (und die konsequente Einhaltung von Immutabilität) bei "großen Datenblöcken" keinen Sinn macht? Aber irgendwie würde mir das nicht einleuchten. Lisp wurde ja auch nicht ausschließlich für "toy examples" und akademisches Gefrickel entwickelt.

Wenn Du so fragst, würde ich (persönliche Meinung) antworten: Ja, das macht keinen Sinn.

Und hier auf dem (Akademischen-) Höchstleistungsrechner stehen Compiler für Fortran, C, C++ und Java zur Verfügung. Kein Lisp.

(Nebenbei, mal ganz pragmatisch formuliert: Mit immutable-Klassen eine (arraybasierte, d.h. nicht-verkettete) Liste mit n (einzeln eingefügten) Elementen zu erstellen hat Laufzeit O(n^2). Mit mutablen Listen nur O(n)....)

Und genau das ist der Punkt! Da Du ja jetzt auch andeutest, dass es um Deine "Mini-Graphenbibliothek" geht, ist imho das entscheidende, wer sind die Nutzer Deiner Bibliothek und was sind deren Bedürfnisse?

Mal als Beispiel, eine Entscheidung die ich für meinen (zukünftigen open source) OpenGL Warper treffen musste. Im Allgemeinen sieht die intuitive, saubere, gebräuchliche und kompatible Schnittstelle z.B. so aus:

public void glLoadMatrixf(final float[] m);

Die Anwendung ist dann aus sicht des Nutzers vollkommen simpel! Trotzdem habe ich mich für diese Definition entschieden:

public void glLoadMatrixf(final GLPointer<FloatBuffer> m);

Was dann zur konfusen Anwendung führt als:

    private final GLPointer<FloatBuffer> glPointer = GLPointer.getFloatBuffer(16);
    private final FloatBuffer buffer = glPointer.getBuffer();

[..]

    buffer.put(0, f / aspect);

[..]

    gl.glLoadMatrixf(glPointer);

Da ich das konsequent für alles was irgendwie in die Richtung Array / Buffer / Rückgabewert geht entschieden habe, kann ich garantieren das für jeden OpenGL Aufruf zwischen dem JNI Einstiegspunkt und dem Einstiegspunkt des Grafikkartentreibers exakt 5 Maschinentakte vergehen. Bei Arrays liegt das um Größenordnungen höher.

Imho hat jede Implementierung Vorteile und Nachteile und das entscheidende ist die Abwägung zwischen diesen. Die Lücke die ich mir für meine Lib gesucht habe, ist definitiv die "ultra schlank und ultra high performance" Ecke (neben ein paar anderen Features die weder JOGL noch LWJGL bieten )

Das führt imho bei Deiner Lib zu der Frage, wollen die Nutzer Deiner Lib aus dem Quellcode lernen? Dann ist Scala, funktional und immutable bestimmt eine gute Wahl! Wollen Deine Nutzer "massenhaft" Daten "durchdrücken" und vermutlich nicht mal einen Blick in die Sourcen werfen? Dann ist O(n^2) imho inakzeptabel.

Und BTW: Es geht nicht um "hipe" (ich nehme an du meinst "hippe" im Sinne von "Hype-Orientierte") Implementierungen, sondern darum, dass viele Punkte bei Graphen- oder Matrizenrechnung sich unglaublich schön und elegant funktional beschreiben lassen. Und ich habe gemerkt, dass ich in meine Mini-Graphenbibliothek immer mehr funktionale Aspekte eingebracht habe, nicht weil es "hipp" ist, sondern weil es elegant, flexibel und praktisch ist (modulo der sprachlichen Unzulänglichkeiten von Java in diesem Punkt).

Ja, ich meinte wohl "hippe" . Was ich damit meinte ist, dass wenn man sich als Entwickler natürlich mit aktuellen Softwarenetwicklungstrends befasst (was sinnvoll und wichtig ist!) schnell der innere drang aufkommt, sein konkretes Problem auch mit diesem neuen Werkzeug lösen zu wollen.

Die Frage ist dann, wenn man einen Schritt zurückgeht und das "große Ganze" betrachtet, ist die Lösung mit ihrer Abwägung zwischen Vorteilen und Nachteilen wirklich die "beste"?

Oder ganz konkret, wäre Deine "Mini-Graphenbibliothek" wirklich noch

und praktisch

wenn sie auf O(n^2) arbeitet und für den geplanten Nutzerkreis nicht mehr anwendbar wäre?


Gruß,
Fancy

 

[Marco13]

Und ich vermute, dass ist das was Marco mit "deep Immutable" meint.

Genau. Wenn "Foo" noch eine Methode hätte
[c]void add(int v) { values.add(v); }[/c]
dann wäre "Bar" nur noch "shallow immutable": Es selbst kann nicht geändert werden, aber die Dinge, die es enthält können sich ändern.

Wenn Du so fragst, würde ich (persönliche Meinung) antworten: Ja, das macht keinen Sinn.

Das Gefühl oder die Vermutung habe ich auch. Aber irgendwie ist das widersprüchlich bzw. ich hab' da noch einen Knoten im Hirn: "Jaaa, programmiert funktional, weil dann kann man parallelisieren im Handumdrehen und braucht sich keine Gedanken um Threadsicherheit zu machen. Wenn man alles Immutable macht. Wenn man alles Immutable macht, wird es zwar langsam und unhandlich, aber durch die Parallelisierung wird es dann doch wieder schnell. Fast so schnell wie vorher."
Häh? ???:L
Also, es gibt sicher viele Bereiche wo das Sinn macht, und eine Mathebibliothek mit "kleinen" Objekten zählt da (wie schon ganz am Anfang erwähnt) vermutlich dazu. Rein formal wäre es auch für allgemeine Graphen/Matrizenbibliotheken toll, aber bei wirklich großen Datenstrukturen scheint es einzelne Operationen zu geben, wo die Immutabilität eher nachteilhaft sein dürfte. Ich muss da wirklich mal genauer drüber nachdenken. Vielleicht kann man die Unterteilung Mutable/Immutable auch sinnvoll in Interfaces verstecken, aber ... da muss ich erstmal :rtfm:en und :reflect:en...

Im Allgemeinen sieht die intuitive, saubere, gebräuchliche und kompatible Schnittstelle z.B. so aus:

public void glLoadMatrixf(final float[] m);

Naja... "sauber" aus OO-Sicht ist es eher nicht, einen rohen Array an eine Funktion zu übergeben, gerade weil man nicht weiß, ob er in der Funktion geändert wird. Bei den GL-Wrappern hat das ja eher historische Gründe....

Die Anwendung ist dann aus sicht des Nutzers vollkommen simpel! Trotzdem habe ich mich für diese Definition entschieden:

public void glLoadMatrixf(final GLPointer<FloatBuffer> m);

Was dann zur konfusen Anwendung führt als:
...
Da ich das konsequent für alles was irgendwie in die Richtung Array / Buffer / Rückgabewert geht entschieden habe, kann ich garantieren das für jeden OpenGL Aufruf zwischen dem JNI Einstiegspunkt und dem Einstiegspunkt des Grafikkartentreibers exakt 5 Maschinentakte vergehen. Bei Arrays liegt das um Größenordnungen höher.

Leicht off-topic, aber "GetPrimitiveArrayCritical" kommt schon fast einer Garantie gleich: Das klappt praktisch immer, und ist vermutlich genauso schnell wie ein GetDirectBufferAddress....

Imho hat jede Implementierung Vorteile und Nachteile und das entscheidende ist die Abwägung zwischen diesen. Die Lücke die ich mir für meine Lib gesucht habe, ist definitiv die "ultra schlank und ultra high performance" Ecke (neben ein paar anderen Features die weder JOGL noch LWJGL bieten )

Da bin ich mal gespannt, wie man die Schicht zwischen Java und OpenGL noch dünner machen kann, als sie bei JOGL schon ist... (Falls du das mit "schlank" meintest ...?)

Das führt imho bei Deiner Lib zu der Frage, wollen die Nutzer Deiner Lib aus dem Quellcode lernen? Dann ist Scala, funktional und immutable bestimmt eine gute Wahl! Wollen Deine Nutzer "massenhaft" Daten "durchdrücken" und vermutlich nicht mal einen Blick in die Sourcen werfen? Dann ist O(n^2) imho inakzeptabel.
...
Oder ganz konkret, wäre Deine "Mini-Graphenbibliothek" wirklich noch [...] wenn sie auf O(n^2) arbeitet und für den geplanten Nutzerkreis nicht mehr anwendbar wäre?

Nun, diese Lib bzw. ihre Erweiterung oder Redesign ist kein konkretes Vorhaben, eher ein "... mal schauen" - und ich dachte, dass das ggf. (m)ein erstes Scala-Projekt sein könnte (auch wenn ich da vorher noch viiieel weiter unten anfangen muss). In diesem Sinne ginge es also weniger darum, dass die Benutzer was lernen, sondern eher darum, dass ICH was lerne Aber das, was da ggf. rauskommt, sollte schon "gut" sein, so dass man es auch verwenden kann. Vermutlich hat man hier (auch, mal wieder) einen gewissen Tradeoff zwischen sauberer, schöner funktionaler oder OO-Programmierung, und den häßlichen (heutzutage schon fast als "maschinennah" zu bezeichnenden) rohen Arrays, mit denen man zwar viel Mist machen kann, aber mit denen dieser Mist rattig schnell geht...

 

[Guest2]

"Jaaa, programmiert funktional, weil dann kann man parallelisieren im Handumdrehen und braucht sich keine Gedanken um Threadsicherheit zu machen. Wenn man alles Immutable macht. Wenn man alles Immutable macht, wird es zwar langsam und unhandlich, aber durch die Parallelisierung wird es dann doch wieder schnell. Fast so schnell wie vorher."
Häh? ???:L

Lol, aber das wäre ja auch zu einfach . Imho kann man zurzeit wirklich effektive Parallelisierung nur durch pures wissen/können erreichen. Das concurrent Package von Java ist eigentlich schon verdammt gut (und intern keineswegs so trivial wie die Klassennamen vermuten lassen würden ). Wenn man allerdings an einen Punkt kommt wo das nicht mehr reicht, muss man imho "parallel denken" können. Und an der Stelle helfen dann weder Tools (MPI / OpenMP natürlich ausgenommen ) noch irgendwelche Sprachfeatures. Und schon gar nicht alles immutable zu machen .

Also, es gibt sicher viele Bereiche wo das Sinn macht, und eine Mathebibliothek mit "kleinen" Objekten zählt da (wie schon ganz am Anfang erwähnt) vermutlich dazu. Rein formal wäre es auch für allgemeine Graphen/Matrizenbibliotheken toll, aber bei wirklich großen Datenstrukturen scheint es einzelne Operationen zu geben, wo die Immutabilität eher nachteilhaft sein dürfte. Ich muss da wirklich mal genauer drüber nachdenken. Vielleicht kann man die Unterteilung Mutable/Immutable auch sinnvoll in Interfaces verstecken, aber ... da muss ich erstmal :rtfm:en und :reflect:en...

Rein von der Compileroptimierung aus gesehen, könnte es auch sinnvoll sein, nachzusehen welche Verfahren gerade im JIT Compiler implementiert sind. Ich würde vermuten, das es eine "relativ steile" Schwelle zwischen "da ist eigentlich egal was im Quellcode steht, da der JIT das eh wegoptimiert" und dem "das ist schon doppelt dumm, da der Algorithmus an sich schon ineffektiv ist und sowieso für den JIT nicht mehr greifbar ist". Oder konkret, ein Primitiv aus vecmath wegoptimiert zu bekommen ist trivial. Eine 500MB Struktur von immutable auf mutable zu ändern, Threads neu zu synchronisieren und den Algorithmus gegen einen für die neue Datenstruktur auszutauschen wohl praktisch unmöglich.

Nun, diese Lib bzw. ihre Erweiterung oder Redesign ist kein konkretes Vorhaben, eher ein "... mal schauen" - und ich dachte, dass das ggf. (m)ein erstes Scala-Projekt sein könnte (auch wenn ich da vorher noch viiieel weiter unten anfangen muss). In diesem Sinne ginge es also weniger darum, dass die Benutzer was lernen, sondern eher darum, dass ICH was lerne Aber das, was da ggf. rauskommt, sollte schon "gut" sein, so dass man es auch verwenden kann. Vermutlich hat man hier (auch, mal wieder) einen gewissen Tradeoff zwischen sauberer, schöner funktionaler oder OO-Programmierung, und den häßlichen (heutzutage schon fast als "maschinennah" zu bezeichnenden) rohen Arrays, mit denen man zwar viel Mist machen kann, aber mit denen dieser Mist rattig schnell geht...

Praktisch würde ich vermuten, dass das Ergebnis dieses Threadoff schon verdammt nah an dem liegt was man als Ergebnis bekäme, wenn man den JIT Compiler genau ansieht und "knapp unter der Schwelle" bleibt .

Da bin ich mal gespannt, wie man die Schicht zwischen Java und OpenGL noch dünner machen kann, als sie bei JOGL schon ist... (Falls du das mit "schlank" meintest ...?)

Dann mal als kleines offtopic preview bzw. ontopic Beispiel, für eine alte (fast vergessene) Technik die vermutlich jeder "hippen ()" Implementierung überlegen ist:

Auf der Java Seite gibt es für jede GL Funktion so einen "Block":

private final long glLoadMatrixf = getGLEntryPoint("glLoadMatrixf");
private native void glLoadMatrixf(final long adress, final int m);
public void glLoadMatrixf(final GLPointer<FloatBuffer> m) { glLoadMatrixf(glLoadMatrixf, m.adress); }

Auf der nativen Seite werden alle JNI Eintrittspunkte auf dieselben 5 Zeilen Code gemappt:

Java_net_pojolibs_pojogl_binding_instance_GLInstance_glAccum:
[..]
Java_net_pojolibs_pojogl_binding_instance_GLInstance_glWriteMaskEXT:

mov eax, [esp + 12]
mov ebx, [esp]
add esp, 16
mov [esp], ebx
jmp eax

Eigentlich werden also nur die obersten beiden Elemente vom Stack genommen (das sind die beiden JNI Parameter, die man auch in C sieht) und direkt in die GL Funktion des OpenGL Treibers gesprungen. Technisch ist das nur ein "goto" und kein neuer Funktionsaufruf. Das "return" aus dem Treiber springt dann praktisch "direkt in Java" zurück. Und da die Parameter so vollkommen irrelevant sind, geht das auch für jede Funktion. Ich würde fast vermuten, dünner/schlanker gehts jetzt aber nimmer .

Gruß,
Fancy

 

[Marco13]

Imho kann man zurzeit wirklich effektive Parallelisierung nur durch pures wissen/können erreichen. Das concurrent Package von Java ist eigentlich schon verdammt gut...

Hmja, vielleicht hatten wir eine unterschiedliche Interpretation von "Parallel" in diesem Fall. Ich meinte die ziemlich Low-Levelige, also nicht 10 Threads die auf einen Server irgendwelche Clients mit Daten füttern, sondern 1000000 Threads, die die Einträge von zwei 1000x1000-Matrizen addieren. Ich hatte auch mal in Erwägung gezogen, eine Domänenspezifische Sprache in Scala zu erstellen (ja, zumindest es zu versuchen ) die NESL nachbildet.... Aber vermutlich fehlen mir einfach in zu vielen Bereichen Kenntnisse, als dass das ein sinnvolles Ziel sein könnte...

Rein von der Compileroptimierung aus gesehen, könnte es auch sinnvoll sein, nachzusehen welche Verfahren gerade im JIT Compiler implementiert sind. [...] Oder konkret, ein Primitiv aus vecmath wegoptimiert zu bekommen ist trivial. Eine 500MB Struktur von immutable auf mutable zu ändern, Threads neu zu synchronisieren und den Algorithmus gegen einen für die neue Datenstruktur auszutauschen wohl praktisch unmöglich.

Die Quintessenz daraus hat sich mir jetzt nicht ganz erschlossen ???:L Was auch immer der JIT macht, man sollte sich nicht darauf verlassen, und IMHO auch keine Entwicklungen darauf trimmen - und dass irgendwelche falschen Designentscheidungen am Anfang später schwer auszubügeln sind, ist klar - deswegen auch das Prinzip "Im Zweifel lieber weglassen". Nur hier: Was weglassen? Die Mutabilität, oder die Immutabilität?

Dann mal als kleines offtopic preview bzw. ontopic Beispiel, für eine alte (fast vergessene) Technik die vermutlich jeder "hippen ()" Implementierung überlegen ist:
[...]
Auf der nativen Seite werden alle JNI Eintrittspunkte auf dieselben 5 Zeilen Code gemappt:
[...]
Ich würde fast vermuten, dünner/schlanker gehts jetzt aber nimmer .

Hat mich kurz an diesen Trick erinnert, aber vermutlich nur wegen des Assemblercodes Ja, schlanker geht es nicht mehr, aber ... Funktioniert das alles so? Also ich frag' mich ob da die JVM nicht irgendwann am Rad dreht, wie Plattform- (32/64-bit) und Betrieebssystem- (Win, Linux, Mac) unabhängig das sein kann, und was bei Fehlern in den Funktionen passiert. Es muss ja dann ALLES, was man dort übergibt, GENAU den richtigen Typ haben, der auch von der nativen Funktion erwartet wird. Bei einem selbstallokierten Pointer geht das vielleicht noch, aber zwischen int, int32, jint, long, jlong, ptr_diff und size_t gibt es SEHR subtile und umgebungsspezifische Unterschiede....

 

[Guest2]

Hmja, vielleicht hatten wir eine unterschiedliche Interpretation von "Parallel" in diesem Fall. Ich meinte die ziemlich Low-Levelige, also nicht 10 Threads die auf einen Server irgendwelche Clients mit Daten füttern, sondern 1000000 Threads, die die Einträge von zwei 1000x1000-Matrizen addieren.

Ok, daran hätte ich in der Tat nicht gedacht. Vielleicht verstehe ich Dich ja auch falsch, aber warum sollte am 1000000 Threads nehmen um 1000000 Zahlen zu addieren? Selbst wenn wir hier nicht bei Java wären und zusätzlich die Threads schon existieren würden, von der Laufzeit wird das doch ein Gau!

Klar mit ner DSL kann man das vermutlich im Quellcode "schön" schreiben, aber ist ne for Schleife in dem Fall wirklich schlechter zu lesen?

Mal auf die schnelle, schnell hingepfuscht:

public class Add {

    // 4 threads, in place add: a += b
    public static void addA(final float[] a, final float[] b) throws InterruptedException {

        if (a.length != b.length)
            throw new IllegalArgumentException();

        final int maxThreads = 4;
        final Thread[] threads = new Thread[maxThreads];
        final long time = System.currentTimeMillis();

        for (int i = 0; i < maxThreads; i++) {

            final int thread = i;

            threads[i] = new Thread(new Runnable() {

                public void run() {

                    for (int i = thread; i < a.length; i += maxThreads)
                        a[i] += b[i];

                }
            });

            threads[i].start();

        }


        for (int i = 0; i < maxThreads; i++)
            threads[i].join();

        System.out.println(maxThreads + " threads: " + (System.currentTimeMillis() - time));

    }


    // a.length threads, in place add: a += b
    public static void addB(final float[] a, final float[] b) throws InterruptedException {

        if (a.length != b.length)
            throw new IllegalArgumentException();

        final int maxThreads = a.length;
        final Thread[] threads = new Thread[maxThreads];
        final long time = System.currentTimeMillis();

        for (int i = 0; i < maxThreads; i++) {

            final int j = i;
            threads[i] = new Thread(new Runnable() {

                public void run() {

                    a[j] += b[j];

                }
            });

            threads[i].start();

        }


        for (int i = 0; i < maxThreads; i++)
            threads[i].join();

        System.out.println(maxThreads + " threads: " + (System.currentTimeMillis() - time));

    }


    public static void main(final String[] args) throws InterruptedException {

        final float[] a = new float[1000000];
        final float[] b = new float[a.length];

        final Random random = new Random();

        for (int i = 0; i < a.length; i++) {

            a[i] = random.nextFloat();
            b[i] = random.nextFloat();

        }

        addA(a, b);
        addB(a, b);

    }

}

4 threads: 10
1000000 threads: 95602

Klar, das ist jetzt nicht "schön" zu lesen (auch da es nur hingepfuscht wurde), aber will ich meinem Nutzer wirklich zumuten 95 Sekunden auf das Ergebnis zu warten, wenn es auch in 10ms geht? (Klar, wenn man die Threads recycelt wird der unterschied kleiner, aber dann sind wir wieder bei mutable vs. immutable )

Die Quintessenz daraus hat sich mir jetzt nicht ganz erschlossen ???:L Was auch immer der JIT macht, man sollte sich nicht darauf verlassen, und IMHO auch keine Entwicklungen darauf trimmen - und dass irgendwelche falschen Designentscheidungen am Anfang später schwer auszubügeln sind, ist klar - deswegen auch das Prinzip "Im Zweifel lieber weglassen".

Was ich damit meinte, ist das es eine Grenze zwischen Lesbarkeit und Performance gibt. Normalerweise treffen die meisten Entwickler diese Grenze aus Erfahrung relativ intuitiv. Und bleiben damit intuitiv unter einer Schwelle, bei der die Laufzeit, für ein minimal übersichtlichern Code, extrem steigt. Auch wenn keiner frühzeitig optimieren will, absichtlich dummen Code produzieren aber auch die wenigsten.

Diese Grenze ist normalerweise aber eben nur intuitiv getroffen. Wenn man die wissenschaftlich belegen wollte, müsste man exakt beobachten was zur Laufzeit passiert. Und durch den JIT, muss das was zur Laufzeit passiert, nicht viel mit dem zu tun haben was im Quellcode steht. Im Idealfall könnte der JIT eben aus langsamen aber lesbaren Code auch performanten Code bauen.

Nur hier: Was weglassen? Die Mutabilität, oder die Immutabilität?

Die Immutabilität!

... Funktioniert das alles so?

Ich hoffe es! Aber ich muss zugeben, das ich noch nicht alle 2066 OpenGL Funktionen einem Test unterzogen habe. Und ehrlich gesagt, weis ich auch noch nicht wie ich das machen soll . Mir ist auch nicht bekannt das irgendjemand JNI schon mal auf diese weise eingesetzt hat, das mag ja auch seinen Grund haben . Windows / Linux / 64 / 32 ist kein wesentliches Problem. Mac schon, einfach da ich keinen zur Verfügung habe.

Aber im Großen und Ganzen bin ich mit der Lib zurzeit sehr zuversichtlich!

Gruß,
Fancy

 

[Landei]

1000000 Threads wären Overkill, aber mit 1000000 Aktoren könnte das durchaus funktionieren, denn letztere skalieren wesentlich besser. Und Aktoren senden sich immutable Nachrichten.

 

[Marco13]

Ok, daran hätte ich in der Tat nicht gedacht. Vielleicht verstehe ich Dich ja auch falsch, aber warum sollte am 1000000 Threads nehmen um 1000000 Zahlen zu addieren? Selbst wenn wir hier nicht bei Java wären und zusätzlich die Threads schon existieren würden, von der Laufzeit wird das doch ein Gau!

1000000 Threads wären Overkill,...

Hmjaa, ich meinte ja (natürlich) nicht notwendigerweise "echte Java-Threads" - dass man da nicht übertreiben sollte, ist ja bekannt, aber im Hinblick auf den letzten Satz dieses Artikels: ...make sure that you make the number of threads configurable. You might want to one day run your program on a 768 core Azul Systems machine. : Es wird wohl kaum jemand in Frage stellen, dass Moore nur dann weiterhin Recht behalten kann, wenn sich die Anzahl der Cores/Prozessoren erhöht. Heute haben wir 4 Kerne, vielleicht 8, aber innerhalb kürzester Zeit werden SCC, irgendwelche Larrabee-Derivate, Cell und nicht zuletzt CUDA, OpenCL und Co die Plattformen sein, für die man programmiert, und dann hat man vieleicht 16, 64 oder auch mal 1024 Kerne. Und Java mit seinen Threads (auch mit dem concurrency-Framework) ist in seiner aktuellen Form bestenfalls für Multicore, aber nicht für Manycore-Systeme geeignet. Für mich stellt sich also die Frage, wie man für ein System progammieren kann, das "irgendwas zwischen 2 und 10000" Cores hat, und das mit "irgendwas zwischen 4 und 1000000" Threads am besten ausgelastet ist. Und ich denke, dass ein Ansatz in dem (zum Beispiel in NESL verwendeten) "Nested Parallelism" besteht. Auf ein übertrieben einfaches Beispiel bezogen: Man schreibt einfach hin "Multipliziere mir diese 16000x16000-Matrizen miteinander". Und abhängig von dem System, auf den man sich befindet, werden dort z.B.
- mit einem MPI-ähnlichen Mechanismus 4 Untermatrizen der Größe 4000x4000 nach Strassen-Manier auf 4 Systeme verteilt
- dort jeweils mit einen Java Fork/Join-ähnlichen Mechanismus jeweils 4 Untermatrizen der Größe 1000x1000 nach Strassen-Manier auf 4 "Rechengeräte" ("Devices", z.B. CPUs oder in diesem Fall GPUs) verteilt
- dort jeweils mit CUDA/OpenCL mit 1000 Threads die 1000x1000-Matrizen multipliziert
... und das ganze am Ende wieder zusammengebaut.
Aber (transparent für den Programmierer) sollte das ganze auch auf einem Handheld laufen, wo man auch nur sagt: "Multipliziere mir diese 16000x16000-Matrizen miteinander" und das ganze dann dafür sorgt, dass das ARMe kleine ARM-Prozessorchen 1000mal länger beschäftigt ist, als die Batterielaufzeit es zulassen würde

Das beantwortet vielleicht auch die Frage:

Klar mit ner DSL kann man das vermutlich im Quellcode "schön" schreiben, aber ist ne for Schleife in dem Fall wirklich schlechter zu lesen?
....
Klar, das ist jetzt nicht "schön" zu lesen (auch da es nur hingepfuscht wurde), aber will ich meinem Nutzer wirklich zumuten 95 Sekunden auf das Ergebnis zu warten, wenn es auch in 10ms geht?

In einer DSL ist das Ziel ( Making Parallel Programming Easy and Portable ) vielleicht eher erreichbar: Bei einer for-Schleife ist man auf den genauen Ablauf festgelegt, und man kann bestenfalls OpenMP-ähnliche Hinweise geben....

[b]@parallel(numThreads=1000)[/b]
for (int i=0; i<1000; i++) a[i] = b[i] + c[i];

Aber wenn dass ganze Teil einer Sprache ist, die von vornherein auf Vektoren arbeitet, steht a einfach
[c]vectorA = vectorB + vectorC[/c]
und ob das mit einem oder 1000 Threads gemacht wird, kann zur compile- oder vielleicht sogar zur Laufzeit passend zum Zielsystem entschieden werden.

Ich schweife ab.... ? ???:L

Aber dazu passt es dann doch wieder ganz gut:

Was ich damit meinte, ist das es eine Grenze zwischen Lesbarkeit und Performance gibt.

Ja, aber es wäre doch toll, wenn es diese Grenze NICHT gäbe. Ich fände es eben schön, wenn man sich diese Frage nicht stellen müßte, eber gerade um portabel parallel programmieren zu können.

Sicher gibt es schon hunderte "Verktororienterte" Sprachen, aber ... das ganze mit Java und/oder Scala compilierbar und kombinierbar zu machen wäre eben IMHO ganz interessant :reflect: Und ich bin mir eben (was der Anlass für meine Frage war) nicht sicher, ob man diese Flexibilität erreichen kann, OHNE das ganze sehr streng und sauber funktional zu gestalten, aber ich bin mir auch nicht sicher, ob eine strege, saubere funktionale Gestaltung nicht Immutabilität impliziert, und diese wiederum nicht die angesprochenen Nachteile haben könnte....

Ich hoffe es! Aber ich muss zugeben, das ich noch nicht alle 2066 OpenGL Funktionen einem Test unterzogen habe. Und ehrlich gesagt, weis ich auch noch nicht wie ich das machen soll . Mir ist auch nicht bekannt das irgendjemand JNI schon mal auf diese weise eingesetzt hat, das mag ja auch seinen Grund haben . Windows / Linux / 64 / 32 ist kein wesentliches Problem. Mac schon, einfach da ich keinen zur Verfügung habe.

Und wie löst du das potentielle Problem, dass bei einem Aufruf in Java wie
glMakeSomething(someInt, someLong, someInt);
auf der C-Seite 32, 64 und 32 bit ankommen, die C-Seite aber ein 32- oder 64-bit-System sein kann, und nicht klar ist, ob dort vielleicht 3x32 bit oder 3x64 bit erwartet werden?

 

[Guest2]

1000000 Threads wären Overkill, aber mit 1000000 Aktoren könnte das durchaus funktionieren, denn letztere skalieren wesentlich besser. Und Aktoren senden sich immutable Nachrichten.

Hmjaa, ich meinte ja (natürlich) nicht notwendigerweise "echte Java-Threads" - dass man da nicht übertreiben sollte, ist ja bekannt, aber im Hinblick auf den letzten Satz dieses Artikels: ...make sure that you make the number of threads configurable. You might want to one day run your program on a 768 core Azul Systems machine.

Hm, also eine einzelne Addition sollte im Durchschnitt nicht länger als 3 CPU Takte dauern (Daten holen, addieren, Daten schreiben). Da in der CPU alles über Pipes läuft, entsteht dabei praktisch keine weitere Wartezeit. Vollkommen egal wie Ihr eure einzelnen Additionen verteilen wollt, das dauert viel länger als 3 Takte. Und, sorry, aber 1000000 Additionen "irgendwie" auf 1000000 "Einheiten" verteilen zu wollen, macht imho keinen Sinn.

Ich vermute, das Ihr hofft, das wenn Ihr einen Ausdruck der Form

add(_).mull(_).div(_).add(_)...mul(_)...

habt, diesen sinnvoll parallelisieren zu können, in dem Ihr einfach die add / mull / div usw. Parallelisiert? Das wird imho nicht zu einem befriedigenden Ergebnis führen. Derzeit ist imho die einzige Möglichkeit, wieder einen Schritt zurück zu gehen und zu überlegen was mache ich den da? Wenn dann als Antwort z.B. kommt: "Eigentlich ist die Matrix ein LGS das ich lösen will." Dann ist die Vorgehensweise, das Verfahren in seiner Gesamtheit zu parallelisieren. Aber eben nicht einzelne Additionen.

Will man das automatisieren, also das LGS auch parallel ohne "denken" lösen, geht das mehr in Richtung Compiler- bau/ "hardcore"optimierung. Intel forscht da ihmo fleißigst dran, aber das ist noch nichts was morgen fertig sein wird.

Aber wenn dass ganze Teil einer Sprache ist, die von vornherein auf Vektoren arbeitet, steht a einfach
[c]vectorA = vectorB + vectorC[/c]
und ob das mit einem oder 1000 Threads gemacht wird, kann zur compile- oder vielleicht sogar zur Laufzeit passend zum Zielsystem entschieden werden.

Gut, Java ist da von der Notation natürlich im Nachteil, aber:

Vec a, b;
[..]
a.add(b);

Finde ich persönlich jetzt nicht so dramatisch. Wie die Implementierung aussieht ist dann wieder was anderes, aber z.B. (wieder hingepfuscht):

public class Vec {

    private static final int cores = Runtime.getRuntime().availableProcessors();

    private final int reasonableThreadsForAdd;
    private final float[] values;


    public Vec(final float[] values){

        this.values = Arrays.copyOf(values, values.length);
        this.reasonableThreadsForAdd = Math.max(Math.min(values.length / 10000, cores), 1);

    }


    public void add(final Vec v) throws InterruptedException{

        if (values.length != v.values.length)
            throw new IllegalArgumentException();


        final Thread[] threads = new Thread[reasonableThreadsForAdd];
        for (int i = 0; i < reasonableThreadsForAdd; i++) {

            final int thread = i;
            threads[thread] = new Thread(new Runnable() {

                public void run() {

                    for (int i = thread; i < values.length; i += reasonableThreadsForAdd)
                        values[i] += v.values[i];

                }
            });

            threads[i].start();

        }


        for (int i = 0; i < reasonableThreadsForAdd; i++)
            threads[i].join();

    }

}

Ja, aber es wäre doch toll, wenn es diese Grenze NICHT gäbe. Ich fände es eben schön, wenn man sich diese Frage nicht stellen müßte, eber gerade um portabel parallel programmieren zu können.

Sicher gibt es schon hunderte "Verktororienterte" Sprachen, aber ... das ganze mit Java und/oder Scala compilierbar und kombinierbar zu machen wäre eben IMHO ganz interessant :reflect: Und ich bin mir eben (was der Anlass für meine Frage war) nicht sicher, ob man diese Flexibilität erreichen kann, OHNE das ganze sehr streng und sauber funktional zu gestalten, aber ich bin mir auch nicht sicher, ob eine strege, saubere funktionale Gestaltung nicht Immutabilität impliziert, und diese wiederum nicht die angesprochenen Nachteile haben könnte....

Ich vermute, die meisten Entwickler fänden es Toll, wenn es diese Grenze nicht geben würde! Aber ich befürchte, das ist eben nichts das man konsequent durch eine Lib durchziehen kann, ohne das die Laufzeit vollkommen in den Keller geht. Mit viel Mühe, bekommt man imho wohl die öffentlichen Schnittstellen "relativ sauber", aber intern wird es dann wohl "zur Sache gehen" müssen.

Und wie schon angedeutet, ist imho die einzige echte Lösung die "hardcore" Compileroptimierung und die eigene Akzeptanz, das der eigene Quellcode dann mehr einer "Willenserklärung" entspricht als dem was am Ende auf dem "Device" läuft.

Und wie löst du das potentielle Problem, dass bei einem Aufruf in Java wie
glMakeSomething(someInt, someLong, someInt);
auf der C-Seite 32, 64 und 32 bit ankommen, die C-Seite aber ein 32- oder 64-bit-System sein kann, und nicht klar ist, ob dort vielleicht 3x32 bit oder 3x64 bit erwartet werden?

Bei einer solchen Funktion erfolgt Javaseitig implizit durch JNI (Parameter von rechts nach links):

push DWORD someInt
push QWORD someLong
push DWORT someInt
push DWORT jclass
push DWORT env
call "glMakeSomething"

gemacht. Der Stack sieht dann einfach so aus:

"return adress", env, jclass, someInt, someLong, someInt

Mein asm Code baut den Stack dann um, in:

"return adress", someInt, someLong, someInt

Und die eigentliche GL Funktion des Treibers hat dann intern ein Einfaches:

pop DWORD someInt
pop QWORT somLong
pop DWORT someInt
[..]
ret

Das ist einfach die "Art" wie Funktionen hartwareseitig Abgebildet werden. Mein Trick ist einfach, das ich die hartwareseitige GL Einsprungadresse Javaseitig einfüge (mein erster Parameter ist immer die GL Adresse der Funktion, in Deinem Beispiel hätte ich also: "private native glMakeSomething(long adress, someInt, someLong, someInt)") und auf der nativen Seite den Stack wieder um die JNI Parameter reduziere. Anschließend erfolg nur der Sprung direkt in die GL Funktion. Führt die GL Funktion ein "ret" aus, wird an die, bereits von JNI eingefügte (geschieht implizit durch das call), "return adress" zurückgesprungen.

Bei Linux / Windows ist der native Binärcode absolut identisch (lediglich das Containerformat der Laufzeitbibliothek unterscheidet sich). Aufpassen muss man nur bei Pointern, da dessen Adressen in der Tat 32 oder 64 Bit auf dem Stack einnehmen müssen.
Intern habe ich deshalb eine GLFactory die mir z.B. über GL2 gl = GLFactory.<GL2>getGLInstance(); die passende 32/64 Bit Instance zurückgibt.

Gruß,
Fancy

 

[Marco13]

Hm, also eine einzelne Addition sollte im Durchschnitt nicht länger als 3 CPU Takte dauern (Daten holen, addieren, Daten schreiben). Da in der CPU alles über Pipes läuft, entsteht dabei praktisch keine weitere Wartezeit. Vollkommen egal wie Ihr eure einzelnen Additionen verteilen wollt, das dauert viel länger als 3 Takte. Und, sorry, aber 1000000 Additionen "irgendwie" auf 1000000 "Einheiten" verteilen zu wollen, macht imho keinen Sinn.

Naja doch... Die Parallelisierung muss natürlich mit einer geegineten Granularität erfolgen. Aber dann kann sie "nested" sein, wie oben angedeutet: Man verarbeitet von einem 4000er-Block eben 4 Blöcke Parallel mit eigenen Threads, aber DIE wiederum rechnen auf Devices mit jeweils 1000 Threads. Und diese hohen Zahlen (und nur die, nicht der allgemeine Ansatz!) bezogen sich auf GPGPU, wo 1000 Threads zu erzeugen praktisch kostenlos ist, und es sich auch lohnt, wenn die Threads dann jeweils nur eine Addition oder Multiplikation machen (wobei es sich natürlich umso mehr lohnt, je mehr Arithmetik man dort unterbringt).

Ich vermute, das Ihr hofft, das wenn Ihr einen Ausdruck der Form

add(_).mull(_).div(_).add(_)...mul(_)...

habt, diesen sinnvoll parallelisieren zu können, in dem Ihr einfach die add / mull / div usw. Parallelisiert? Das wird imho nicht zu einem befriedigenden Ergebnis führen. [...]
Will man das automatisieren, also das LGS auch parallel ohne "denken" lösen, geht das mehr in Richtung Compiler- bau/ "hardcore"optimierung.

Ja, so ansatzweise. Wie oben gesagt würde es sich ggf. lohnen, die Einzelschritte zu parallelisieren. Dass man bei komplexeren Verfahren (wie dem Lösen eines LGS) dieses nicht unbedingt aus "kleinen" parallelen Building Blocks zusammenbauen müßte, sondern auch als ganzes eine optimierte Version davon anbieten könnte, ist klar - aber im Idealfall würde diese "optimierte" Version ja auch nur aus Schritten bestehen, die (jeder für sich) parallelisiert ablaufen können - vereinfacht gesagt: Es muss doch möglich sein, funktionale Programmierung und Vektormaschinen zu verheiraten?

Aber um zu versuchen, das mal wieder mehr in Richtung der ursprünglichen Frage zu lenken:

Gut, Java ist da von der Notation natürlich im Nachteil, aber:

Vec a, b;
[..]
a.add(b);

Finde ich persönlich jetzt nicht so dramatisch. Wie die Implementierung aussieht ist dann wieder was anderes...

Es ging ursprünglich nicht darum, ob man
- "a.add(b)" oder "a+=b" schreibt
sondern darum, ob man
- "a.add(b)" oder "c = a.add(b)" schreibt

Im Idealfall wäre die Implementierung dann nicht mehr sooo sehr "was anderes". Wenn man z.B. einen Strassen-Matrixmultiplikator schreiben will, dann wäre es doch toll, wenn man das so hinschreiben könnte

Matrix multiply(Matrix A, Matrix B)
{
    Matrix C11_L = A.subMatrix(1,1).multiply(B.subMatrix(1,1))
    Matrix C11_R = A.subMatrix(1,2).multiply(B.subMatrix(2,1))
    Matrix C11 = C11_L.add(C11_R);
    ...
    return MatrixFrom(C11, C12, C21, C22);
}

(bzw. wenn man's drauf anlegt auch komplett in einer Zeile, ohne die temporären Variablen - und die Multiplikationen der Untermatrizen sollten dann im Idealfall auch wieder jeweils QUASI in einem eigenen Thread erfolgen - also sowohl parallel zu einander als auch parallel in sich selbst - hat ja niemand gesagt, dass das einfach werden würde )

Eine Frage die dabei auftaucht (unabhängig vom ursprünglichen Thema)ist, dass man in der konkreten Implementierung vorher einen "Entscheidungspunkt" braucht, ähnlich wie die "reasonableThreadsForAdd" in deinem Beispiel. Übertrieben(!) pragmatisch gesagt wäre das dann sowas wie

Matrix multiply(Matrix A, Matrix B)
{
    if (A.size() < 10)
    {
         return simpleMatrixMulCPU(A,B);
    }
    if (A.size() <= 1000)
    {
        int numberOfThreads = A.size();
        return simpleMatrixMulGPU(A,B,numberOfThreads);
    }
    // Nur bei SEHR großen Matrizen den "echten" Strassen machen:
    Matrix C11_L = A.subMatrix(1,1).multiply(B.subMatrix(1,1))
    Matrix C11_R = A.subMatrix(1,2).multiply(B.subMatrix(2,1))
    Matrix C11 = C11_L.add(C11_R);
    ...
    return MatrixFrom(C11, C12, C21, C22);
}

Wobei diese Entscheidung vielleicht auch "unsichtbar" für den Programmierer getroffen werden können sollte - also nicht mehr so im Quelltext stehen müssen sollte.

Viel entscheidender an diesem Punkt ist, dass bei "sauberer" Funktionaler Programmierung (auf die die letzten Zeilen ja rauslaufen würden) bei jeder Multiplikation und Addition eigentlich eine neue Matrix erstellt werden müßte, obwohl es ja eigentlich effizienter (aber eben auf Mutabilität aufbauend) wäre, wenn man schreiben würde

Matrix result = new Matrix(A.size());
resullt.fillSubMatrix(1,1, A);
result.multiplySubMatrix(1,1,B);
...

Die rein formalen Nachteile sind klar: Wenn diese unter-Multiplikationen in verschiedenen Threads laufen, KÖNNTEN sie sich gegenseitig beeinflussen (man weiß, dass sie das nicht tun, aber man kann dieses Wissen nicht ausnutzen )

Und wie schon angedeutet, ist imho die einzige echte Lösung die "hardcore" Compileroptimierung und die eigene Akzeptanz, das der eigene Quellcode dann mehr einer "Willenserklärung" entspricht als dem was am Ende auf dem "Device" läuft.

Hmja, dass das viel mit der Umsetzung und Definition der Interpretation einer eigenen Sprache zu tun hat, war der Grund, weswegen ich dachte, dass da eine Scala-basierte DSL vielleicht ein Ansatzpunkt sein könnte....

Bei einer solchen Funktion erfolgt Javaseitig implizit durch JNI (Parameter von rechts nach links):
[...]
Und die eigentliche GL Funktion des Treibers hat dann intern ein Einfaches:

pop DWORD someInt
pop QWORT somLong
pop DWORT someInt
[..]
ret

[...]
Aufpassen muss man nur bei Pointern, da dessen Adressen in der Tat 32 oder 64 Bit auf dem Stack einnehmen müssen.
Intern habe ich deshalb eine GLFactory die mir z.B. über GL2 gl = GLFactory.<GL2>getGLInstance(); die passende 32/64 Bit Instance zurückgibt.

OK, die typedef's für QWORD und DWORD kenn' ich jetzt nur aus Windows, und ich dachte, man weiß erstmal nicht, was ein "WORD" im allgemeinen Fall ist. Ich war nur der Meinung, dass bei einer GL-Funktion wie
glMakeSomething(size_t size);
auf einem 32bit-Rechner dort ein 32bit-Wert auf dem Stack stehen muss, und bei einem 64bitter ein 64bit-Wert, und man das nicht mehr sooo 100% allgemein durch Assembler abfangen kann. Dass die GL-Funktion also entweder
pop DWORD someSize
oder
pop QWORD someSize
macht, und man das ad hoc erstmal nicht weiß. Aber wenn du meinst, dass das irgendwie geht, glaub' ich dir das mal

 

[Guest2]

Ja, so ansatzweise. Wie oben gesagt würde es sich ggf. lohnen, die Einzelschritte zu parallelisieren. Dass man bei komplexeren Verfahren (wie dem Lösen eines LGS) dieses nicht unbedingt aus "kleinen" parallelen Building Blocks zusammenbauen müßte, sondern auch als ganzes eine optimierte Version davon anbieten könnte, ist klar - aber im Idealfall würde diese "optimierte" Version ja auch nur aus Schritten bestehen, die (jeder für sich) parallelisiert ablaufen können

Ja, bei wirklich großen Daten (um mal ne Hausnummer zu sagen, 256GB Matrizen) macht man das ja in der Tat auch so. Auch weil es normalerweise Beschränkungen der Hartware gibt, die sich anders nicht lösen lassen. Dann laufen die "kleinen" eben als OpenMP und alle zusammen als MPI. Mehrere TB Daten passen nun mal realistisch nicht in den Hauptspeicher eines SMP Systems.

vereinfacht gesagt: Es muss doch möglich sein, funktionale Programmierung und Vektormaschinen zu verheiraten?

Klar, wenn Du den Einsatzzeck Deiner Lib exakt festlegst, sollte sich da auch was Sinnvolles bauen lassen.

Eine Frage die dabei auftaucht (unabhängig vom ursprünglichen Thema)ist, dass man in der konkreten Implementierung vorher einen "Entscheidungspunkt" braucht, ähnlich wie die "reasonableThreadsForAdd" in deinem Beispiel.

Ja genau, das ist das Problem. Überlege mal in einer heterogenen Umgebung, wie Du sie oben angerissen hast, also SMP, MPI, GPU, CISC, RISC,... Und all die verschiedenen Methoden die Du in Deiner Lib zur Verfügung stellen willst. Wie viele dieser Entscheidungspunkte wirst Du wohl brauchen? Und wie groß ist die Wahrscheinlichkeit, dass Du alle diese Entscheidungen nach sinnvollen Metriken triffst?

Wenn ich mich an meine HPC Vorlesung erinnere (leider nur viel zu schwach), dann hatten wir alleine einen mehrmonatigen Block der sich nur mit den Vorteilen / Nachteilen der verschiedenen Matrixmultiplikationen im Bezug auf Matrixstruktur und Rechnerarchitektur bezog.

Wenn Du das in Deiner Lib wirklich allgemein halten willst, kommt wohl das raus, was ich oben mit

aber intern wird es dann wohl "zur Sache gehen"

meinte.


Und um noch mal meinen Gedankengang von der ersten Seite aufzugreifen: Wenn Du dich entscheidest, ob Du eben z.B. eine kleine Lib zur Darstellung und Manipulation eines handlichen Graphen (das eine Extrem) oder eben eine Lib zur internen Berechnung der Daten des LHC schreiben willst (anderes Extrem), wird das alles viel einfacher.

Hinzugehen und alles funktional immutabel zu machen, und dann zu hoffen das schon alles gut wird, halte ich zumindest für schwierig in der Umsetzung.

Es ging ursprünglich nicht darum, ob man
- "a.add(b)" oder "a+=b" schreibt
sondern darum, ob man
- "a.add(b)" oder "c = a.add(b)" schreibt

Ups, ich hab gedacht da wärst Du inzwischen schon drüber weg.

Dann noch mal mein Standpunkt (der natürlich in keinster weise richtig sein muss! ):
Spielt die Laufzeit bei einer realistischen Anwendungsgröße für die Nutzer Deiner Lib eine Rolle? Wenn ja, bleibt wohl nur mutable. Wenn nicht, nimm das, was sich Deiner Meinung nach im Gesamtkontext sauberer schreiben lässt.

Aber wenn du meinst, dass das irgendwie geht, glaub' ich dir das mal

Sagen wir mal, ich glaube fest dran!

Gruß,
Fancy

 

[Marco13]

Ja, bei wirklich großen Daten (um mal ne Hausnummer zu sagen, 256GB Matrizen) macht man das ja in der Tat auch so. Auch weil es normalerweise Beschränkungen der Hartware gibt, die sich anders nicht lösen lassen. Dann laufen die "kleinen" eben als OpenMP und alle zusammen als MPI.

Ja, wie man schon sieht gibt es da eben sehr viele Techniken, die auf unterschiedlichsten Ebenen und mit unterschiedlichen Granularitäten an dieses Thema rangehen. Wenn man nun zwei solche Matrizen multiplizieren will, kann man entweder MPI verwenden, oder ein OpenMP Programm schreiben, oder sehen, wie weit man auf einem Quad-Core mit 4-8 Java-Threads kommt, oder man frickelt rum und dröselt das so auf, dass man irgendwie möglichst viel mit der GPU macht und die CPU nur zum Dispatchen und Wiederzusammensetzen verwendet. Das sind dann 5 verschiedene Programme mit 6 verschiedenen Technologien und insgesamt 70000 Zeilen Code :autsch: Dabei ist der Strassen doch eigentlich ganz kurz, und seine Funktional-ität immer die gleiche...

Klar, wenn Du den Einsatzzeck Deiner Lib exakt festlegst, sollte sich da auch was Sinnvolles bauen
...
Ja genau, das ist das Problem. Überlege mal in einer heterogenen Umgebung, wie Du sie oben angerissen hast, also SMP, MPI, GPU, CISC, RISC,... Und all die verschiedenen Methoden die Du in Deiner Lib zur Verfügung stellen willst. Wie viele dieser Entscheidungspunkte wirst Du wohl brauchen? Und wie groß ist die Wahrscheinlichkeit, dass Du alle diese Entscheidungen nach sinnvollen Metriken triffst?
lassen.

Wie gesagt: Da steckt noch keine wirklich konkrete Planung dahinter. Ich hatte nur in letzter Zeit verschiedene Themen bearbeitet, die irgendwie Überschneidungen hatten, und ... ja, nicht mal einen "Wunsch", sondern eher die Frage: "Könnte man nicht ... ? :reflect: " in mir weckte, und zwar grob sowas wie: Könnte man nicht eine Bibliothek (in Java oder Scala) schreiben, die Matrizen und Graphen (schön, sauber und) funktional behandelt (nicht weil es "hipp" ist, sondern weil es sich bei diesen Themen schon stark aufdrängt, und ja bei der Parallelisierung theoretisch und formal eigentlich viele Vorteile hat), und die gut mit einer steigenden Zahl von Recheneinheiten skaliert (!). Denn ähnlich wie Moore vorausgesagt hat, dass sich die Anzahl der Transistoren sich alle 18 Monate verdoppelt, sage ich nun voraus, dass sich die Anzahl der "durchschnittlich verfügberen Kerne" alle 18 Monate verdoppeln wird (was bei gleichbleibender Taktfrequenz und Moore's Law als Annahme keine Kunst ist aber man sollte sich darauf einstellen!!!)

Also, nochmal ganz pragmatisch zusammengefasst: Warum sollte es nicht möglich sein, EIN Programm zu schreiben, wo im Prinzip nur der Strassen drinsteht, und das startet man dann mit den Parametern
java TheProgram fileWith64000x64000Matrix.dat -mpi:4 -cpu:8 -gpu:1000
Dieses Programm könnte in seiner allgemeinsten Form ("top-level") eben IMHO nur funktional beschrieben sein. Aber wenn man dann für jedes kleine Zwischenergebnis als Tribut an die Immutabilität eine riesige, temporäre Matrix erstellen muss, wäre das eher schlecht... (BTW: Es geht nicht NUR um Matrizen, aber die bieten sich als Beispiel eben so gut an)

Wenn ich mich an meine HPC Vorlesung erinnere (leider nur viel zu schwach), dann hatten wir alleine einen mehrmonatigen Block der sich nur mit den Vorteilen / Nachteilen der verschiedenen Matrixmultiplikationen im Bezug auf Matrixstruktur und Rechnerarchitektur bezog.

Wenn Du das in Deiner Lib wirklich allgemein halten willst, kommt wohl das raus, was ich oben mit

aber intern wird es dann wohl "zur Sache gehen"

meinte.

Hmja, ich gehe auch davon aus, dass das eigentlich ein viiiieeel zu dickes Brett ist... aber ein paar erste Schritte, und seien es nur Grundlagen, und vielleicht auch nicht für die wirkliche Verwendung sondern eher als "akademisches Vorgeplenkel" um danach andere Sachen besser zu machen, könnte man ja mal versuchen...

Und um noch mal meinen Gedankengang von der ersten Seite aufzugreifen: Wenn Du dich entscheidest, ob Du eben z.B. eine kleine Lib zur Darstellung und Manipulation eines handlichen Graphen (das eine Extrem) oder eben eine Lib zur internen Berechnung der Daten des LHC schreiben willst (anderes Extrem), wird das alles viel einfacher.

Hinzugehen und alles funktional immutabel zu machen, und dann zu hoffen das schon alles gut wird, halte ich zumindest für schwierig in der Umsetzung.

Neee, das ist leicht. Die Hoffung wird halt nicht erfüllt. Aber sonst....

Spielt die Laufzeit bei einer realistischen Anwendungsgröße für die Nutzer Deiner Lib eine Rolle? Wenn ja, bleibt wohl nur mutable. Wenn nicht, nimm das, was sich Deiner Meinung nach im Gesamtkontext sauberer schreiben lässt.

Ja, nachdem weder die konkrete Anwendung, geschweige denn die Größe, und noch weniger die Nutzer (und eigentlich nicht mal die Existenz ) der Lib feststehen, wird das ganze wohl erstmal ... wie soll man sagen ... "recreational research"?

 

[Marco13]

... und wenn ich am 5.7 um 10:10 Uhr nicht diesen Thread eröffnet, sondern einfach noch eine Stunde gewartet und dann auf Heise Developer geschaut hätte, hätte sich ein Teil (aber nur ein Teil) der Diskussion erübrigt:

Auch in der Java-Welt wird das Konzept von Unveränderbarkeit (Immutability) als Entwurfsmuster populär, bei Clojure ist es die Voreinstellung: Alle Clojure-Werte sind unveränderlich; Funktionen ändern Werte niemals, sondern erzeugen neue Werte. ...

Der gleiche Mechanismus greift, wenn Listen, Vektoren oder andere Datenstrukturen nicht fünf, sondern ein paar Millionen Elemente enthalten – logisch gesehen wird dieser Wert niemals geändert, sondern eine Kopie erzeugt. Das wäre gänzlich inperformant und praxisuntauglich, wenn es wirklich so implementiert wäre. Tatsächlich teilen sich die alte und die neue Datenstruktur die gemeinsamen Elemente. Das ist als Structural Sharing bekannt, die verwendeten Datenstrukturen bezeichnet man Persistent Data Structures.

Diese Datenstrukturen sind das Herz von Clojure und sorgen dafür, Unveränderbarkeit konsequent umzusetzen.

Dann weiß ich ja jetzt, wo(nach) ich suchen muss

 

[Landei]

Dann weiß ich ja jetzt, wo(nach) ich suchen muss

Da hättest du mich bloß fragen müssen. Hier ist z.B. eine persistente Datenstruktur für eine Liste, die den Zugriff auf ein Element (der große Schwachpunkt der einfach verketteten immutablen Liste) von O(n) auf O(log(n)) drückt:

Unveränderliche Listen mit wahlfreiem Zugriff eSCALAtion Blog
Unveränderliche Listen mit wahlfreiem Zugriff in Java eSCALAtion Blog

Das Wissen über persistente Datenstrukturen ist in den letzten 15, 20 Jahren geradezu explodiert, nur dass kaum jemand was davon mitkommt, der nicht gerade Collection-Bibliotheken für funktionale Sprachen schreibt. Oder hast du z.B. schonmal den Namen Chrsi Okasaki gehört, der obige und viele andere Strukturen entwickelt hat?

 

[Marco13]

Ja, ich schaue schon gelegentlich in deinen Blog, und meine auch mich an diese Überschrift zu erinnern, aber hatte bisher noch nicht sooo viel Zeit mich intensiver mit Scala zu beschäftigen, und vermutlich war mir, wenn ich das schon gesehen hatte, die Problematik nicht bewußt... (Is' doch easy: Collections.unmodifiableList(new ArrayList()); ! )

Ich fand das halt nur einen merkwürdigen Zufall, dass genau eine Stunde später dieser Artikel veröffentlicht wurde. Ich hatte vorher schon ein bißchen im Web gesucht, aber vermutlich nicht genug und vermutlich nicht mit den richtigen Stichworten....

Das Wissen über persistente Datenstrukturen ist in den letzten 15, 20 Jahren geradezu explodiert, ...
Den Teil "über persistente Datenstrukturen" könnte man auch weglassen Ich hatte ja schon angedeutet, dass das wohl ein ziemlich dickes Brett ist, und man sich da nicht so nebenbei mal kurz den State Of The Art raufschafft...

 

[Guest2]

[..] aber man sollte sich darauf einstellen!!! [..] "akademisches Vorgeplenkel" [..] "recreational research"?

Aus der Sicht ist natürlich alles erlaubt und auch sinnvoll!

Dann finde ich die Frage aber auch spannend, ob man das als DSL, Lib oder als Pre-/Compiler-optimierer aufbauen will. So en bissel Compileroptimierung für Java fände ich ja schon spannend. Hätte man doch nur mehr Zeit.

[..]Diese Datenstrukturen sind das Herz von Clojure[..]

Ich hab inzwischen auch mal ein halbes Auge auf die internen Datenstrukturen von Clojure geworfen. Vermutlich hast Du es inzwischen auch schon selbst gefunden, falls nicht, den Code gibt es bei github. Interessant sind imho z.B. die Klassen PersistentHashMap.java und PersistentVector.java. Ein bisschen was Erklärendes dazu findet sich auch: PersistentHashMap, PersistentVector.

Klingt sicherlich alles spannend, aber wenn ich mir überlege, was exakt passiert, bei:

for(int i = 0; i< a.length; i++)
    v[i] += a[i];

Und demselben, auf den Datenstrukturen von Clojure. Nuja, sagen wir, ich bleib bei Arrays.

Gruß,
Fancy

 

[Marco13]

Dann finde ich die Frage aber auch spannend, ob man das als DSL, Lib oder als Pre-/Compiler-optimierer aufbauen will. So en bissel Compileroptimierung für Java fände ich ja schon spannend. Hätte man doch nur mehr Zeit.

Ja, die Zeit ... vielleicht geht es nich mal um Compileroptimierung, sondern (wenn man sich dem Thema erstmal so unbedarft nähert) um Compilerbau an sich. Habe mir in letzter Zeit (da ist sie ja wieder ) mal GROB solche Sachen wie LLVM angeschaut, aber das ist ja ein Monster :shock: Irgendwie bin ich nicht so sicher, wo man ansetzen könnte (vielleicht wäre es einfacher, wenn ich wüßte, was ich will ). Aber es gibt da Möglichkeiten auf so unterschiedlichen Ebenen: Von LLVM über eine eigene DSL mit Xtext (die dann auch irgendwie compiliert werden müßte) über eine DSL in Scala (was ich auch mal angefangen habe, anzutesten) bis hin zur guten, alten Library in purem Java.

In jedem Fall glaube ich, dass man eine allgemeinere Möglichkeit finden muss, parallele Programme zu beschreiben. In Scala ist Quicksort ein 5-Zeiler. Wenn das nun alles automagisch für beliebige Zielarchitekturen parallelisert werden könnte, wäre das doch toll :reflect:

Ich hab inzwischen auch mal ein halbes Auge auf die internen Datenstrukturen von Clojure geworfen. Vermutlich hast Du es inzwischen auch schon selbst gefunden, falls nicht, den Code gibt es bei github. ...

Zugegeben, danach hatte ich noch nicht genauer gesucht - es gibt da SO viele Themen, in die man sich erst noch reinfräsen müßte :rtfm: Die Stichworte sind schon vorgemerkt, aber wie schon angedeutet glaube ich, dass die bedinungslose Immutabilität nicht nur in bezug auf Rechenzeiten und Speicher, sondern auch in bezug auf den Implementierungsaufwand enorm wäre - nämlich wenn man gedenkt, solche Strukturen noch mal selbst nachzuimplementieren (so laienhaft wie ich das eben könnte...).