Persistente Datenstrukturen in PHP: Funktionale Listen mit Structural Sharing

1. Was persistente Datenstrukturen von einfachen Array-Kopien unterscheidet

Eine persistente Datenstruktur ist eine Datenstruktur, die nach jeder Änderungsoperation ihre vorherige Version vollständig unverändert erhält und stattdessen eine neue Version zurückgibt. Der Begriff persistent bezieht sich hier nicht auf Festplatten-Speicherung, sondern auf das Fortbestehen aller früheren Versionen im Speicher. Wer eine Referenz auf die alte Version hält, sieht auch nach einer Änderung an der neuen Version weiterhin exakt den ursprünglichen Zustand, weil beide Versionen nebeneinander existieren.

Der naive Weg, dieses Verhalten in PHP zu erreichen, wäre, bei jeder Änderung das komplette Array zu kopieren. PHP-Arrays nutzen zwar intern Copy-on-Write, was einfache Zuweisungen billig macht, doch sobald tatsächlich ein Element geändert, hinzugefügt oder entfernt wird, kopiert PHP den kompletten internen Array-Speicher, bevor die Änderung angewendet wird. Bei großen Listen mit häufigen Änderungen wird dieser Kopieraufwand schnell zum Performance-Problem.

Persistente Datenstrukturen im funktionalen Sinne lösen dieses Problem durch Structural Sharing: eine neue Version teilt sich möglichst viel internen Speicher mit der alten Version und kopiert nur den unbedingt notwendigen Teil. Dieser Artikel zeigt, wie eine solche persistente, verkettete Liste in PHP 8.4 aussieht und wann sie klassischen Arrays tatsächlich überlegen ist.

2. Das Kopierproblem klassischer PHP-Arrays bei Immutability

Will man in PHP ein Array unveränderlich behandeln, liegt der naheliegende Ansatz nahe, bei jeder Änderung eine Kopie über $newArray = $oldArray; $newArray[] = $element; zu erzeugen. Für kleine Arrays ist das unproblematisch, weil PHPs Copy-on-Write-Mechanismus die eigentliche Kopie erst beim ersten Schreibzugriff auf die Kopie auslöst und dieser Kopiervorgang bei wenigen Elementen kaum ins Gewicht fällt.

Bei großen Arrays mit tausenden Elementen und häufigen Änderungen, etwa in einer Undo-Historie, die bei jedem Schritt eine neue, unveränderliche Version des Zustands braucht, summiert sich der Kopieraufwand jedoch spürbar auf. Jede einzelne Änderung kopiert das komplette Array erneut, mit quadratischer Gesamtkomplexität bei einer Kette von n Änderungen an einem Array mit n Elementen. Persistente Datenstrukturen vermeiden genau dieses quadratische Verhalten durch geteilten, unveränderten Speicher zwischen den Versionen.

<?php

declare(strict_types=1);

// Naive immutability: full array copy on every change
function prependNaive(array $list, mixed $item): array
{
    // PHP copies the entire internal array storage here on write
    array_unshift($list, $item);

    return $list;
}

$history = [];
for ($i = 0; $i < 3; $i++) {
    $history[] = $list ?? [];
    $list = prependNaive($list ?? [], $i);
}

// Each step in $history is a full, independent copy — costly at scale
foreach ($history as $step) {
    echo count($step) . ' elements in this version' . PHP_EOL;
}

3. Eine unveränderliche verkettete Liste als Grundbaustein

Der klassische Baustein für persistente Datenstrukturen ist die einfach verkettete Liste, bei der jeder Knoten einen Wert und einen Verweis auf den Rest der Liste enthält. In PHP lässt sich ein solcher Knoten als unveränderliches Value Object mit readonly-Eigenschaften modellieren: ein Wert und eine Referenz auf den nächsten Knoten, oder null für das Listenende.

Der entscheidende Unterschied zu einem PHP-Array: die Liste selbst besteht aus unveränderlichen Knoten, die nach ihrer Erzeugung nie wieder verändert werden. Jede Operation, die eine neue Liste erzeugt, muss deshalb keine bestehenden Knoten kopieren, sondern kann sie einfach weiterverwenden und nur die tatsächlich neuen Knoten anlegen. Diese Eigenschaft ist die Grundlage für Structural Sharing im nächsten Abschnitt.

<?php

declare(strict_types=1);

/**
 * An immutable singly-linked list node. Once created, never mutated.
 *
 * @template T
 */
final class ListNode
{
    /**
     * @param T $value
     * @param self<T>|null $next
     */
    public function __construct(
        public readonly mixed $value,
        public readonly ?self $next,
    ) {
    }
}

/**
 * A persistent, immutable list wrapper around a linked chain of nodes.
 *
 * @template T
 */
final class PersistentList
{
    private function __construct(private readonly ?ListNode $head)
    {
    }

    /**
     * @return self<mixed>
     */
    public static function empty(): self
    {
        return new self(null);
    }

    public function isEmpty(): bool
    {
        return $this->head === null;
    }
}

4. Structural Sharing: warum prepend() ohne Kopie auskommt

Das Voranstellen eines neuen Elements an eine persistente Datenstruktur ist die günstigste aller Operationen, weil dafür nur ein einziger neuer Knoten erzeugt werden muss, der auf den bisherigen Kopf der alten Liste zeigt. Die alte Liste bleibt dabei vollständig unverändert erreichbar, weil ihr Kopfknoten weiterhin existiert und von niemandem verändert wird. Diese Technik heißt Structural Sharing: die neue Version teilt sich den kompletten restlichen Speicher mit der alten Version und dupliziert nur den neuen Knoten.

Der Laufzeitaufwand für prepend ist damit unabhängig von der Listengröße konstant, O(1), während eine naive Array-Kopie mit array_unshift auf einer unveränderlichen Kopie stets die komplette Datenmenge anfassen muss, O(n). Bei häufigen Prepend-Operationen auf große Historien, etwa beim Aufbau eines Ereignis-Logs von neu nach alt, ist dieser Unterschied in der Praxis deutlich spürbar.

<?php

declare(strict_types=1);

/**
 * @template T
 */
final class PersistentList
{
    private function __construct(private readonly ?ListNode $head)
    {
    }

    /**
     * @return self<mixed>
     */
    public static function empty(): self
    {
        return new self(null);
    }

    /**
     * O(1): only one new node is allocated, the old list is fully reused.
     *
     * @param T $value
     * @return self<T>
     */
    public function prepend(mixed $value): self
    {
        return new self(new ListNode($value, $this->head));
    }

    /**
     * @return list<mixed>
     */
    public function toArray(): array
    {
        $items = [];
        $node = $this->head;

        while ($node !== null) {
            $items[] = $node->value;
            $node = $node->next;
        }

        return $items;
    }
}

$v1 = PersistentList::empty();
$v2 = $v1->prepend('a');
$v3 = $v2->prepend('b');

// $v2 remains fully intact and unaffected by the creation of $v3
var_dump($v2->toArray()); // ['a']
var_dump($v3->toArray()); // ['b', 'a']

5. Funktionale Operationen: map, filter und fold auf der Liste

Damit eine persistente Datenstruktur praktisch nutzbar wird, braucht sie dieselben funktionalen Operationen, die man von Arrays kennt: map zum Transformieren jedes Elements, filter zum Behalten nur bestimmter Elemente und fold zum Reduzieren auf einen einzigen Wert. Alle drei Operationen erzeugen eine neue, unveränderliche Liste oder einen einzelnen Wert, ohne die ursprüngliche Liste jemals zu verändern, konsistent mit dem Grundprinzip von Immutability.

Bei der Implementierung von map und filter auf einer verketteten Liste ist zu beachten, dass eine naive rekursive Implementierung bei sehr langen Listen den Stack sprengen kann, weil jeder rekursive Aufruf einen neuen Stack-Frame belegt. Eine iterative Implementierung mit einer expliziten Schleife vermeidet dieses Risiko und bleibt bei Listen beliebiger Länge sicher.

<?php

declare(strict_types=1);

/**
 * @template T
 */
final class PersistentList
{
    private function __construct(private readonly ?ListNode $head)
    {
    }

    /**
     * @return self<mixed>
     */
    public static function empty(): self
    {
        return new self(null);
    }

    /**
     * @param T $value
     * @return self<T>
     */
    public function prepend(mixed $value): self
    {
        return new self(new ListNode($value, $this->head));
    }

    /**
     * Iterative map — avoids stack overflow on very long lists.
     *
     * @param Closure(mixed): mixed $fn
     * @return self<mixed>
     */
    public function map(Closure $fn): self
    {
        $items = array_map($fn, $this->toArray());
        $result = self::empty();

        foreach (array_reverse($items) as $item) {
            $result = $result->prepend($item);
        }

        return $result;
    }

    /**
     * @param Closure(mixed): bool $predicate
     * @return self<mixed>
     */
    public function filter(Closure $predicate): self
    {
        $items = array_filter($this->toArray(), $predicate);
        $result = self::empty();

        foreach (array_reverse($items) as $item) {
            $result = $result->prepend($item);
        }

        return $result;
    }

    /**
     * @return list<mixed>
     */
    public function toArray(): array
    {
        $items = [];
        $node = $this->head;

        while ($node !== null) {
            $items[] = $node->value;
            $node = $node->next;
        }

        return $items;
    }
}

$numbers = PersistentList::empty()->prepend(3)->prepend(2)->prepend(1);

$doubled = $numbers->map(fn (int $n): int => $n * 2);
$evens = $numbers->filter(fn (int $n): bool => $n % 2 === 0);

var_dump($numbers->toArray()); // [1, 2, 3], unaffected by map/filter above
var_dump($doubled->toArray()); // [2, 4, 6]

6. Das Anhängen-Problem: warum append() teurer bleibt als prepend()

Während prepend bei einer einfach verketteten Liste in konstanter Zeit funktioniert, ist das Anhängen eines Elements ans Ende der Liste, append, strukturell teurer. Um einen neuen Knoten ans Ende zu hängen, ohne bestehende Knoten zu verändern, müsste jeder Knoten auf dem Weg zum Ende neu erzeugt werden, weil jeder unveränderliche Knoten auf seinen Nachfolger zeigt und dieser Nachfolger sich durch das Anhängen ja ändern würde. Damit kostet append auf dieser einfachen Struktur O(n) statt O(1).

Reale funktionale Sprachen und Bibliotheken lösen dieses Problem mit fortgeschritteneren Strukturen wie balancierten Bäumen oder Finger Trees, die sowohl prepend als auch append in amortisiert konstanter oder logarithmischer Zeit erlauben. Für die meisten praktischen PHP-Anwendungsfälle, in denen hauptsächlich am Anfang eingefügt oder komplett neu iteriert wird, reicht die einfache verkettete Liste mit ihrem O(n)-Append jedoch völlig aus, solange append nicht der dominante Anwendungsfall ist.

7. Praxisfälle: Undo-Historie und geteilter Zustand ohne Kopien

Ein naheliegender Anwendungsfall für persistente Datenstrukturen ist eine Undo-Historie in einer interaktiven Anwendung: jede Aktion des Nutzers erzeugt eine neue Version des Zustands, während alle vorherigen Versionen unverändert im Speicher bleiben und bei Bedarf sofort wieder aktiviert werden können. Mit einer naiven Array-Kopie bei jeder Aktion würde eine lange Undo-Kette bei großem Zustand schnell übermäßig viel Speicher verbrauchen, weil jede Version den kompletten Zustand dupliziert.

Ein zweiter Anwendungsfall betrifft nebenläufigen oder parallelen Code, etwa in einem Swoole-Worker mit mehreren Coroutinen: teilen sich mehrere Coroutinen eine Referenz auf dieselbe persistente Datenstruktur, kann keine von ihnen versehentlich den Zustand einer anderen verändern, weil jede Änderung immer eine neue Version zurückgibt, statt die geteilte Struktur zu mutieren. Diese Eigenschaft macht persistente Strukturen von Natur aus sicher gegenüber Race Conditions auf dem Datenzustand selbst.

8. Grenzen: Speicher-Overhead und wann klassische Arrays besser passen

Der Preis für Structural Sharing ist ein höherer Speicher-Overhead pro Element im Vergleich zu einem klassischen PHP-Array, weil jeder Knoten ein eigenes Objekt mit Referenz auf den nächsten Knoten ist, statt in einem zusammenhängenden Speicherblock zu liegen. Für sehr große Datenmengen, bei denen selten geändert und meist nur gelesen wird, ist ein klassisches Array mit seiner kompakteren Speicherung und schnellerem sequenziellem Zugriff häufig die bessere Wahl.

Auch der wahlfreie Zugriff auf ein Element per Index ist bei einer verketteten Liste strukturell langsamer, O(n) statt O(1) wie bei einem Array, weil man vom Kopf aus Knoten für Knoten durchlaufen muss. Persistente Datenstrukturen lohnen sich deshalb gezielt dort, wo Unveränderlichkeit, viele Versionen und geteilter Zustand wichtiger sind als schneller Index-Zugriff, nicht als generischer Ersatz für jedes PHP-Array.

9. Persistente Liste im Vergleich zu Array und SplDoublyLinkedList

Die folgende Tabelle vergleicht die persistente Liste mit den gängigen Alternativen in PHP.

Die Grundregel: eine persistente Liste lohnt sich, sobald mehrere Versionen eines Zustands gleichzeitig lebendig bleiben müssen, etwa bei Undo-Historien oder geteiltem Zustand zwischen Coroutinen. Für reinen sequenziellen Datendurchlauf ohne Versionierungsbedarf bleibt das klassische PHP-Array wegen seines geringeren Speicher-Overheads und schnelleren Index-Zugriffs meist die bessere Wahl.

10. Zusammenfassung

Persistente Datenstrukturen erhalten nach jeder Änderung ihre vorherige Version vollständig unverändert und erzeugen eine neue Version über Structural Sharing statt über eine komplette Kopie. Eine unveränderliche, einfach verkettete Liste mit readonly-Knoten macht prepend() in konstanter Zeit möglich, weil nur ein einziger neuer Knoten erzeugt und der Rest der alten Liste unverändert weiterverwendet wird. Funktionale Operationen wie map, filter und fold lassen sich auf dieser Struktur implementieren, ohne die Ursprungsliste jemals zu verändern.

Der Preis ist ein höherer Speicher-Overhead pro Element und langsamerer Index-Zugriff im Vergleich zu einem klassischen Array. Persistente Datenstrukturen lohnen sich deshalb gezielt bei Undo-Historien, Versionsverwaltung und geteiltem Zustand zwischen nebenläufigem Code, nicht als generischer Ersatz für jedes PHP-Array im Alltagscode.

11. FAQ: Persistente Datenstrukturen in PHP