Verwendung persistenter Datenstrukturen in nichtfunktionalen Sprachen

Rein funktionale oder nahezu rein funktionale Sprachen profitieren von dauerhaften Datenstrukturen, da sie unveränderlich sind und sich gut in den zustandslosen Stil der funktionalen Programmierung einfügen.

Von Zeit zu Zeit sehen wir jedoch Bibliotheken persistenter Datenstrukturen für (zustandsbasierte, OOP-) Sprachen wie Java. Eine Behauptung, die häufig zugunsten persistenter Datenstrukturen geäußert wird, ist, dass sie threadsicher sind, weil sie unveränderlich sind .

Der Grund dafür, dass persistente Datenstrukturen thread-sicher sind, besteht darin, dass, wenn ein Thread ein Element zu einer persistenten Auflistung "hinzufügt", der Vorgang eine neue Auflistung wie das Original zurückgibt, jedoch mit dem hinzugefügten Element. Andere Threads sehen daher die Originalkollektion. Die beiden Sammlungen haben natürlich einen großen internen Status - deshalb sind diese beständigen Strukturen effizient.

Da jedoch für verschiedene Threads unterschiedliche Datenzustände angezeigt werden, scheint es, dass persistente Datenstrukturen an sich nicht ausreichen, um Szenarien zu handhaben, in denen ein Thread eine Änderung vornimmt, die für andere Threads sichtbar ist. Dazu müssen wir anscheinend Geräte wie Atome, Referenzen, Software-Transaktionsspeicher oder sogar klassische Schlösser und Synchronisationsmechanismen verwenden.

Warum wird die Unveränderlichkeit von PDS als etwas angesehen, das der "Thread-Sicherheit" förderlich ist? Gibt es echte Beispiele, bei denen PDS bei der Synchronisierung oder bei der Lösung von Problemen mit der Parallelität helfen? Oder sind PDS einfach eine Möglichkeit, eine zustandslose Schnittstelle für ein Objekt bereitzustellen, um einen funktionalen Programmierstil zu unterstützen?

Persistente / unveränderliche Datenstrukturen lösen Parallelitätsprobleme nicht von alleine, sondern erleichtern deren Lösung erheblich.

Betrachten Sie einen Thread T1, der eine Menge S an einen anderen Thread T2 übergibt. Wenn S veränderlich ist, hat T1 ein Problem: Es verliert die Kontrolle darüber, was mit S passiert. Thread T2 kann es ändern, sodass T1 sich überhaupt nicht auf den Inhalt von S verlassen kann. Und umgekehrt - T2 kann nicht sicher sein, dass T1 ändert S nicht, während T2 darauf arbeitet.

Eine Lösung besteht darin, der Kommunikation von T1 und T2 eine Art Vertrag hinzuzufügen, damit nur einer der Threads S ändern kann. Dies ist fehleranfällig und belastet sowohl das Design als auch die Implementierung.

Eine andere Lösung ist, dass T1 oder T2 die Datenstruktur klonen (oder beide, wenn sie nicht koordiniert sind). Wenn S jedoch nicht persistent ist, ist dies eine teure O (n) -Operation.

Wenn Sie eine beständige Datenstruktur haben, sind Sie von dieser Belastung befreit. Sie können eine Struktur an einen anderen Thread übergeben und müssen sich nicht darum kümmern, was sie damit macht. Beide Threads haben Zugriff auf die Originalversion und können beliebige Operationen ausführen - dies hat keinen Einfluss darauf, was der andere Thread sieht.

Siehe auch: Persistente vs. unveränderliche Datenstruktur .

Warum wird die Unveränderlichkeit von PDS als etwas angesehen, das der "Thread-Sicherheit" förderlich ist? Gibt es echte Beispiele, bei denen PDS bei der Synchronisierung oder bei der Lösung von Problemen mit der Parallelität helfen?

Der Hauptvorteil eines PDS in diesem Fall besteht darin, dass Sie einen Teil der Daten ändern können, ohne alles eindeutig zu machen (ohne sozusagen alles tief zu kopieren). Dies hat viele potenzielle Vorteile, da Sie billige Funktionen ohne Nebenwirkungen schreiben können: Instanziieren von kopierten und eingefügten Daten, triviale Rückgängigmachungssysteme, triviale Wiedergabefunktionen in Spielen, triviale zerstörungsfreie Bearbeitung, triviale Ausnahmesicherheit usw. usw.

Man kann sich eine Datenstruktur vorstellen, die persistent, aber veränderlich wäre. Beispielsweise könnten Sie eine verknüpfte Liste, die durch einen Zeiger auf den ersten Knoten dargestellt wird, und eine Vorab-Operation verwenden, die eine neue Liste zurückgibt, die aus einem neuen Kopfknoten plus der vorherigen Liste besteht. Da Sie immer noch den Verweis auf den vorherigen Kopf haben, können Sie auf diese Liste zugreifen und sie ändern, die inzwischen auch in die neue Liste eingebettet ist. Solch ein Paradigma ist zwar möglich, bietet aber nicht die Vorteile beständiger und unveränderlicher Datenstrukturen, z. B. ist es standardmäßig sicherlich nicht threadsicher. Es kann jedoch nützlich sein, solange der Entwickler weiß, was er tut, z. B. für eine effiziente Raumnutzung. Beachten Sie auch, dass die Struktur zwar auf der Sprachebene veränderlich sein kann, dass jedoch nichts den Code daran hindert, sie zu ändern.

Kurz gesagt, ohne Unveränderlichkeit (durch die Sprache oder Konvention erzwungen) verliert die Persistenz von Datenstrukturen einige ihrer Vorteile (Threadsicherheit), andere jedoch nicht (Platzeffizienz für einige Szenarien).

Was Beispiele für nicht funktionierende Sprachen betrifft, String.substring()verwendet Java eine, wie ich es nenne, persistente Datenstruktur. Die Zeichenfolge wird durch ein Array von Zeichen sowie den Anfangs- und Endversatz des Bereichs des Arrays dargestellt, der tatsächlich verwendet wird. Wenn eine Teilzeichenfolge erstellt wird, verwendet das neue Objekt dasselbe Zeichenarray nur mit geänderten Start- und Endversätzen. Da Stringunveränderlich ist, handelt es sich (in Bezug auf die substring()Operation, nicht andere) um eine unveränderliche persistente Datenstruktur.

Die Unveränderlichkeit von Datenstrukturen ist der für die Thread-Sicherheit relevante Teil. Ihre Persistenz (Wiederverwendung vorhandener Blöcke, wenn eine neue Struktur erstellt wird) ist für die Effizienz bei der Arbeit mit solchen Sammlungen von Bedeutung. Da sie unveränderlich sind, ändert eine Operation wie das Hinzufügen eines Elements die vorhandene Struktur nicht, sondern gibt eine neue Struktur mit dem angehängten zusätzlichen Element zurück. Wenn jedes Mal, wenn die gesamte Struktur kopiert wird, beginnend mit einer leeren Sammlung und nacheinander 1000 Elemente hinzugefügt werden, um eine Sammlung mit 1000 Elementen zu erhalten, werden temporäre Objekte mit 0 + 1 + 2 + ... + 999 = erstellt Insgesamt 500000 Elemente, was eine enorme Verschwendung wäre. Bei persistenten Datenstrukturen kann dies vermieden werden, da die 1-Element-Auflistung in der 2-Element-Auflistung wiederverwendet wird, die in der 3-Element-Auflistung wiederverwendet wird, und so weiter.

Ich bin zugegebenermaßen voreingenommen, wenn ich solche Konzepte in C ++ anwende, und zwar aufgrund der Sprache und ihrer Natur sowie meiner Domäne und sogar der Art und Weise, wie wir die Sprache verwenden. Angesichts dieser Umstände halte ich unveränderliche Designs für den uninteressantesten Aspekt, wenn es darum geht, einen Großteil der mit der funktionalen Programmierung verbundenen Vorteile zu nutzen, z kombiniere sie in beliebiger Reihenfolge ohne unangenehme Überraschungen), etc.

Nehmen Sie dieses vereinfachte C ++ - Beispiel (zugegebenermaßen nicht der Einfachheit halber optimiert, um mich nicht vor irgendwelchen Bildverarbeitungsexperten in Verlegenheit zu bringen):

// Inputs an image and outputs a new one with the specified size.
Image resized_image(const Image& src, int new_w, int new_h)
{
     Image dst(new_w, new_h);
     for (int y=0; y < new_h; ++y)
     {
         for (int x=0; x < new_w; ++x)
              dst[y][x] = src.sample(x / (float)new_w, y / (float)new_h);
     }
     return dst;
}

Während die Implementierung dieser Funktion den lokalen (und temporären) Zustand in Form von zwei Zählervariablen und einem auszugebenden temporären lokalen Bild verändert, hat sie keine externen Nebenwirkungen. Es wird ein Bild eingegeben und ein neues ausgegeben. Wir können es nach Herzenslust multithreaden. Es ist leicht zu überlegen, leicht gründlich zu testen. Es ist ausnahmesicher, da das neue Bild automatisch verworfen wird und wir uns keine Gedanken über das Zurücksetzen externer Nebenwirkungen machen müssen (es werden sozusagen keine externen Bilder außerhalb des Funktionsbereichs geändert).

Ich sehe wenig zu gewinnen und möglicherweise viel zu verlieren, wenn ich Imagein C ++ im obigen Kontext unveränderlich mache , außer um die obige Funktion möglicherweise unhandlicher und möglicherweise ein bisschen weniger effizient zu implementieren.

Reinheit

Daher sind reine Funktionen (frei von externen Nebenwirkungen) für mich sehr interessant, und ich betone, wie wichtig es ist, sie auch in C ++ Teammitgliedern häufig vorzuziehen. Aber unveränderliche Entwürfe, die nur im Allgemeinen ohne Kontext und ohne Nuancen angewendet werden, sind für mich bei weitem nicht so interessant, da es angesichts des imperativen Charakters der Sprache oft nützlich und praktisch ist, in der Lage zu sein, einige lokale temporäre Objekte auf effiziente Weise zu mutieren (beides) für Entwickler und Hardware) eine reine Funktion implementieren.

Günstiges Kopieren von schweren Strukturen

Die zweitnützlichste Eigenschaft, die ich finde, ist die Fähigkeit, die wirklich umfangreichen Datenstrukturen billig zu kopieren, wenn die Kosten dafür, wie sie häufig anfallen würden, um Funktionen aufgrund ihrer strengen Eingabe / Ausgabe-Natur rein zu machen, nicht trivial wären. Dies wären keine kleinen Strukturen, die auf den Stapel passen. Das wären große, kräftige Strukturen, wie das Ganze Scenefür ein Videospiel.

In diesem Fall könnte der Kopieraufwand Möglichkeiten für eine effektive Parallelisierung verhindern, da es schwierig sein kann, Physik und Rendering effektiv zu parallelisieren, ohne sich gegenseitig zu sperren und einen Engpass zu verursachen, wenn die Physik die Szene mutiert, die der Renderer gleichzeitig zu zeichnen versucht, während er gleichzeitig eine tiefe Physik aufweist Das Kopieren der gesamten Spielszene, um nur ein Einzelbild mit angewandter Physik auszugeben, kann gleichermaßen ineffektiv sein. Wenn das physikalische System jedoch in dem Sinne "rein" wäre, dass es lediglich eine Szene eingibt und eine neue mit angewandter Physik ausgibt, und eine solche Reinheit nicht auf Kosten des astronomischen Kopieraufwands gehen würde, könnte es sicher parallel mit dem System arbeiten Renderer, ohne dass einer auf den anderen wartet.

Die Möglichkeit, die wirklich umfangreichen Daten Ihres Anwendungszustands kostengünstig zu kopieren und neue, geänderte Versionen mit minimalen Kosten für Verarbeitung und Speichernutzung auszugeben, kann also wirklich neue Türen für Reinheit und effektive Parallelität öffnen, und dort finde ich viele Lektionen zum Lernen davon, wie persistente Datenstrukturen implementiert werden. Was auch immer wir mit solchen Lektionen erstellen, muss nicht vollständig persistent sein oder unveränderliche Schnittstellen bieten (es kann beispielsweise Copy-on-Write oder ein "Builder / Transient" verwendet werden), um diese Fähigkeit zu erreichen, spottbillig zu sein nur Teile der Kopie kopieren und ändern, ohne die Speichernutzung und den Speicherzugriff zu verdoppeln, um Parallelität und Reinheit in unseren Funktionen / Systemen / Pipelines zu erreichen.

Unveränderlichkeit

Schließlich gibt es eine Unveränderlichkeit, die ich als die am wenigsten interessante von diesen dreien betrachte, die sich jedoch mit eiserner Faust durchsetzen kann, wenn bestimmte Objektdesigns nicht als lokale temporäre Elemente für eine reine Funktion, sondern in einem breiteren Kontext als wertvoll angesehen werden sollen Art von "Reinheit auf Objektebene", da in allen Methoden keine externen Nebenwirkungen mehr auftreten (keine Mutation der Mitgliedsvariablen mehr außerhalb des unmittelbaren lokalen Bereichs der Methode).

Und obwohl ich es in Sprachen wie C ++ für das am wenigsten interessante unter diesen dreien halte, kann es sicherlich das Testen und die Thread-Sicherheit und die Argumentation von nicht-trivialen Objekten vereinfachen. Es kann sich lohnen, mit der Garantie zu arbeiten, dass einem Objekt beispielsweise keine eindeutige Zustandskombination außerhalb seines Konstruktors zugewiesen werden kann, und dass wir es auch per Referenz / Zeiger frei weitergeben können, ohne uns auf Beständigkeit und Lesbarkeit zu stützen. nur Iteratoren und Handles und so, während garantiert wird (na ja, so viel wie möglich innerhalb der Sprache), dass sein ursprünglicher Inhalt nicht mutiert wird.

Aber ich finde das die am wenigsten interessante Eigenschaft, weil die meisten Objekte, die ich als nützlich erachte, vorübergehend in veränderlicher Form verwendet werden, um eine reine Funktion zu implementieren (oder sogar ein breiteres Konzept, wie ein "reines System", das ein Objekt oder eine Reihe von Objekten sein könnte) funktioniert letztendlich so, dass nur etwas eingegeben und etwas Neues ausgegeben wird, ohne etwas anderes zu berühren), und ich halte die Unveränderlichkeit, die in einer weitgehend imperativen Sprache bis zum Äußersten getragen wird, für ein eher kontraproduktives Ziel. Ich würde es sparsam für die Teile der Codebasis anwenden, wo es wirklich am meisten hilft.

Schließlich:

Es scheint, dass persistente Datenstrukturen an sich nicht ausreichen, um Szenarien zu bewältigen, in denen ein Thread eine Änderung vornimmt, die für andere Threads sichtbar ist. Dazu müssen wir anscheinend Geräte wie Atome, Referenzen, Software-Transaktionsspeicher oder sogar klassische Schlösser und Synchronisationsmechanismen verwenden.

Wenn in Ihrem Design Änderungen (im Sinne eines benutzerorientierten Designs) für mehrere Threads gleichzeitig sichtbar sein sollen, kehren wir natürlich zur Synchronisierung zurück, oder zumindest zum Zeichenbrett, um einige ausgefeilte Methoden zu finden, um damit umzugehen ( Ich habe einige sehr ausführliche Beispiele gesehen, die von Experten verwendet wurden, die sich mit solchen Problemen in der funktionalen Programmierung befassten.

Aber ich habe herausgefunden, dass, wenn Sie diese Art des Kopierens und die Fähigkeit haben, teilweise modifizierte Versionen von massiven Strukturen spottbillig auszugeben, wie Sie es zum Beispiel mit persistenten Datenstrukturen tun würden, es Ihnen oft viele Türen und Möglichkeiten öffnet Ich habe noch nie darüber nachgedacht, Code zu parallelisieren, der in einer strengen I / O-Art paralleler Pipeline völlig unabhängig voneinander laufen kann. Selbst wenn einige Teile des Algorithmus serieller Natur sein müssen, können Sie diese Verarbeitung auf einen einzelnen Thread verschieben. Wenn Sie sich jedoch auf diese Konzepte stützen, können Sie problemlos 90% der umfangreichen Arbeit parallelisieren, z