Inhaltsverzeichnis
Bitte unterstützen Sie dieses Buch: kaufen Sie es (PDF, EPUB, MOBI) oder spenden Sie
(Werbung, bitte nicht blockieren.)

6. Shared memory and atomics

Das ECMAScript 2017 Feature “Shared memory and atomics” wurde von Lars T. Hansen entworfen. Es führt einen neuen Konstruktor SharedArrayBuffer und ein Namespace-Objekt Atomics mit Hilfsfunktionen ein. Dieses Kapitel erklärt die Details.

6.1 Parallelität vs. Nebenläufigkeit

Bevor wir beginnen, lassen Sie uns zwei Begriffe klären, die ähnlich und doch unterschiedlich sind: „Parallelität“ und „Nebenläufigkeit“. Für sie existieren viele Definitionen; ich verwende sie wie folgt:

Beides ist eng verwandt, aber nicht dasselbe

Es ist jedoch schwierig, diese Begriffe präzise zu verwenden, weshalb ihr Austausch normalerweise kein Problem darstellt.

6.1.1 Modelle der Parallelität

Zwei Modelle der Parallelität sind:

6.2 Eine Geschichte der JS-Parallelität

6.2.1 Der nächste Schritt: SharedArrayBuffer

Was kommt als Nächstes? Für niedrigstufige Parallelität ist die Richtung ziemlich klar: SIMD und GPUs so gut wie möglich unterstützen. Für hochstufige Parallelität sind die Dinge jedoch viel weniger klar, insbesondere nach dem Scheitern von PJS.

Was benötigt wird, ist eine Möglichkeit, viele Ansätze auszuprobieren, um herauszufinden, wie man hochstufige Parallelität am besten in JavaScript bringt. Gemäß den Prinzipien des "extensible web manifesto" tut der Vorschlag "shared memory and atomics" (auch bekannt als "Shared Array Buffers") dies, indem er niedrigstufige Primitive bereitstellt, die zur Implementierung höherstufiger Konstrukte verwendet werden können.

6.3 Shared Array Buffers

Shared Array Buffers sind ein primitives Baustein für höherstufige Nebenläufigkeitsabstraktionen. Sie ermöglichen es Ihnen, die Bytes eines SharedArrayBuffer-Objekts zwischen mehreren Workern und dem Haupt-Thread zu teilen (der Puffer wird geteilt, um auf die Bytes zuzugreifen, verpacken Sie ihn in einen Typed Array). Diese Art des Teilens hat zwei Vorteile:

6.3.1 Erstellen und Senden eines Shared Array Buffers 

// main.js

const worker = new Worker('worker.js');

// To be shared
const sharedBuffer = new SharedArrayBuffer( // (A)
    10 * Int32Array.BYTES_PER_ELEMENT); // 10 elements

// Share sharedBuffer with the worker
worker.postMessage({sharedBuffer}); // clone

// Local only
const sharedArray = new Int32Array(sharedBuffer); // (B)

Sie erstellen einen Shared Array Buffer genauso wie einen normalen Array Buffer: indem Sie den Konstruktor aufrufen und die Größe des Puffers in Bytes angeben (Zeile A). Was Sie mit Workern teilen, ist der Puffer. Für Ihre eigene lokale Verwendung verpacken Sie Shared Array Buffers normalerweise in Typed Arrays (Zeile B).

Warnung: Das Klonen eines Shared Array Buffers ist der richtige Weg, ihn zu teilen, aber einige Engines implementieren immer noch eine ältere Version der API und verlangen, dass Sie ihn übertragen

worker.postMessage({sharedBuffer}, [sharedBuffer]); // transfer (deprecated)

In der endgültigen Version der API bedeutet die Übertragung eines Shared Array Buffers, dass Sie den Zugriff darauf verlieren.

6.3.2 Empfangen eines Shared Array Buffers

Die Implementierung des Workers sieht wie folgt aus.

// worker.js

self.addEventListener('message', function (event) {
    const {sharedBuffer} = event.data;
    const sharedArray = new Int32Array(sharedBuffer); // (A)

    // ···
});

Wir extrahieren zuerst den Shared Array Buffer, der an uns gesendet wurde, und verpacken ihn dann in einen Typed Array (Zeile A), damit wir ihn lokal verwenden können.

6.4 Atomics: Sicherer Zugriff auf geteilte Daten

6.4.1 Problem: Optimierungen machen Code über Worker hinweg unvorhersehbar

In einzelnen Threads können Compiler Optimierungen vornehmen, die Multi-Threaded-Code brechen.

Betrachten Sie zum Beispiel den folgenden Code:

while (sharedArray[0] === 123) ;

In einem einzelnen Thread ändert sich der Wert von sharedArray[0] niemals, während die Schleife läuft (wenn sharedArray ein Array oder Typed Array ist, das nicht auf irgendeine Weise gepatcht wurde). Daher kann der Code wie folgt optimiert werden:

const tmp = sharedArray[0];
while (tmp === 123) ;

In einer Multi-Threaded-Umgebung verhindert diese Optimierung jedoch, dass wir dieses Muster verwenden, um auf Änderungen zu warten, die in einem anderen Thread vorgenommen wurden.

Ein weiteres Beispiel ist der folgende Code:

// main.js
sharedArray[1] = 11;
sharedArray[2] = 22;

In einem einzelnen Thread können Sie diese Schreiboperationen neu anordnen, da dazwischen nichts gelesen wird. Für mehrere Threads geraten Sie in Schwierigkeiten, wenn Sie erwarten, dass die Schreibvorgänge in einer bestimmten Reihenfolge erfolgen.

// worker.js
while (sharedArray[2] !== 22) ;
console.log(sharedArray[1]); // 0 or 11

Diese Art von Optimierungen macht es praktisch unmöglich, die Aktivität mehrerer Worker zu synchronisieren, die auf denselben Shared Array Buffer zugreifen.

6.4.2 Lösung: Atomics

Der Vorschlag stellt die globale Variable Atomics bereit, deren Methoden drei Hauptanwendungsfälle haben.

6.4.2.1 Anwendungsfall: Synchronisation

Atomics-Methoden können verwendet werden, um mit anderen Workern zu synchronisieren. Zum Beispiel lassen Sie die folgenden beiden Operationen Daten lesen und schreiben und werden niemals von Compilern neu angeordnet:

Die Idee ist, normale Operationen zum Lesen und Schreiben der meisten Daten zu verwenden, während Atomics-Operationen (load, store und andere) sicherstellen, dass das Lesen und Schreiben sicher erfolgt. Oftmals werden Sie benutzerdefinierte Synchronisationsmechanismen wie Sperren verwenden, deren Implementierungen auf Atomics basieren.

Dies ist ein sehr einfaches Beispiel, das dank Atomics immer funktioniert (ich habe die Einrichtung von sharedArray weggelassen)

// main.js
console.log('notifying...');
Atomics.store(sharedArray, 0, 123);

// worker.js
while (Atomics.load(sharedArray, 0) !== 123) ;
console.log('notified');
6.4.2.2 Anwendungsfall: Auf Benachrichtigung warten

Die Verwendung einer while-Schleife, um auf eine Benachrichtigung zu warten, ist nicht sehr effizient, weshalb Atomics Operationen hat, die helfen:

6.4.2.3 Anwendungsfall: Atomare Operationen

Mehrere Atomics-Operationen führen arithmetische Berechnungen durch und können dabei nicht unterbrochen werden, was bei der Synchronisation hilft. Zum Beispiel:

Diese Operation führt ungefähr folgendes aus:

ta[index] += value;

6.4.3 Problem: Zerissene Werte

Ein weiterer problematischer Effekt bei Shared Memory sind *zerissene Werte* (Müll): Beim Lesen können Sie einen Zwischenwert sehen – weder den Wert vor dem Schreiben eines neuen Wertes in den Speicher noch den neuen Wert.

Abschnitt „Tear-Free Reads“ in der Spezifikation besagt, dass es keinen Riss gibt, wenn und nur wenn:

Mit anderen Worten, zerissene Werte sind ein Problem, wenn auf denselben Shared Array Buffer über Folgendes zugegriffen wird:

Um in diesen Fällen zerissene Werte zu vermeiden, verwenden Sie Atomics oder synchronisieren Sie.

6.5 Shared Array Buffers in der Anwendung

6.5.1 Shared Array Buffers und die Run-to-Completion-Semantik von JavaScript

JavaScript hat sogenannte *Run-to-Completion-Semantik*: Jede Funktion kann darauf vertrauen, nicht von einem anderen Thread unterbrochen zu werden, bis sie abgeschlossen ist. Funktionen werden zu Transaktionen und können vollständige Algorithmen ausführen, ohne dass jemand die Daten, auf denen sie arbeiten, in einem Zwischenzustand sieht.

Shared Array Buffers brechen Run-to-Completion (RTC): Daten, mit denen eine Funktion arbeitet, können von einem anderen Thread während der Ausführung der Funktion geändert werden. Der Code hat jedoch die vollständige Kontrolle darüber, ob diese Verletzung von RTC auftritt oder nicht: Wenn er keine Shared Array Buffers verwendet, ist er sicher.

Dies ähnelt lose der Art und Weise, wie async-Funktionen RTC verletzen. Dort opten Sie sich mit dem Schlüsselwort await für eine blockierende Operation.

6.5.2 Shared Array Buffers und asm.js und WebAssembly

Shared Array Buffers ermöglichen emscripten die Kompilierung von pthreads zu asm.js. Zitat aus einer emscripten-Dokumentationsseite:

[Shared Array Buffers ermöglichen] Emscripten-Anwendungen, den Hauptspeicher-Heap zwischen Web-Workern zu teilen. Dies, zusammen mit primitiven Operationen für Low-Level-Atomikoperationen und Futex-Unterstützung, ermöglicht emscripten die Implementierung der Pthreads (POSIX-Threads) API.

Das heißt, Sie können Multi-Threaded-C- und C++-Code in asm.js kompilieren.

Die Diskussion, wie Multi-Threading am besten in WebAssembly integriert werden kann, ist im Gange. Da Web-Worker relativ schwergewichtig sind, ist es möglich, dass WebAssembly leichtgewichtige Threads einführt. Sie können auch sehen, dass Threads auf der Roadmap für die Zukunft von WebAssembly stehen.

6.5.3 Teilen von Daten, die keine Ganzzahlen sind

Derzeit können nur Arrays von Ganzzahlen (bis zu 32 Bits lang) geteilt werden. Das bedeutet, dass die einzige Möglichkeit, andere Arten von Daten zu teilen, darin besteht, sie als Ganzzahlen zu kodieren. Hilfreiche Werkzeuge sind:

Schließlich wird es wahrscheinlich zusätzliche – höherstufige – Mechanismen zum Teilen von Daten geben. Und Experimente werden fortgesetzt, um herauszufinden, wie diese Mechanismen aussehen sollen.

6.5.4 Wie viel schneller ist Code, der Shared Array Buffers verwendet?

Lars T. Hansen hat zwei Implementierungen des Mandelbrot-Algorithmus geschrieben (wie in seinem Artikel „A Taste of JavaScript’s New Parallel Primitives“ dokumentiert, wo Sie sie online ausprobieren können): Eine serielle Version und eine parallele Version, die mehrere Web-Worker verwendet. Für bis zu 4 Web-Worker (und damit Prozessorkerne) verbessert sich die Geschwindigkeit fast linear, von 6,9 Bildern pro Sekunde (1 Web-Worker) auf 25,4 Bilder pro Sekunde (4 Web-Worker). Mehr Web-Worker bringen zusätzliche Leistungsverbesserungen, aber bescheidenere.

Hansen merkt an, dass die Geschwindigkeitssteigerungen beeindruckend sind, aber das Parallelisieren geht auf Kosten einer komplexeren Codebasis.

6.6 Beispiel

Betrachten wir ein umfassenderes Beispiel. Sein Code ist auf GitHub im Repository shared-array-buffer-demo verfügbar. Und Sie können es online ausführen.

6.6.1 Verwendung einer geteilten Sperre

Im Haupt-Thread richten wir Shared Memory ein, um eine geschlossene Sperre zu kodieren und senden sie an einen Worker (Zeile A). Sobald der Benutzer klickt, öffnen wir die Sperre (Zeile B).

// main.js

// Set up the shared memory
const sharedBuffer = new SharedArrayBuffer(
    1 * Int32Array.BYTES_PER_ELEMENT);
const sharedArray = new Int32Array(sharedBuffer);

// Set up the lock
Lock.initialize(sharedArray, 0);
const lock = new Lock(sharedArray, 0);
lock.lock(); // writes to sharedBuffer

worker.postMessage({sharedBuffer}); // (A)

document.getElementById('unlock').addEventListener(
    'click', event => {
        event.preventDefault();
        lock.unlock(); // (B)
    });

Im Worker richten wir eine lokale Version der Sperre ein (deren Zustand über einen Shared Array Buffer mit dem Haupt-Thread geteilt wird). In Zeile B warten wir, bis die Sperre entsperrt ist. In den Zeilen A und C senden wir Text an den Haupt-Thread, der ihn für uns auf der Seite anzeigt (wie er das tut, ist im vorherigen Codefragment nicht zu sehen). Das heißt, wir verwenden self.postMessage() viel wie console.log() in diesen beiden Zeilen.

// worker.js

self.addEventListener('message', function (event) {
    const {sharedBuffer} = event.data;
    const lock = new Lock(new Int32Array(sharedBuffer), 0);

    self.postMessage('Waiting for lock...'); // (A)
    lock.lock(); // (B) blocks!
    self.postMessage('Unlocked'); // (C)
});

Bemerkenswert ist, dass das Warten auf die Sperre in Zeile B den vollständigen Worker stoppt. Das ist echtes Blocking, das es in JavaScript bisher nicht gab (await in async-Funktionen ist eine Annäherung).

6.6.2 Implementierung einer geteilten Sperre

Als Nächstes betrachten wir eine ES6-ifizierte Version einer Lock-Implementierung von Lars T. Hansen, die auf SharedArrayBuffer basiert.

In diesem Abschnitt benötigen wir (unter anderem) die folgende Atomics-Funktion:

Die Implementierung beginnt mit einigen Konstanten und dem Konstruktor:

const UNLOCKED = 0;
const LOCKED_NO_WAITERS = 1;
const LOCKED_POSSIBLE_WAITERS = 2;

// Number of shared Int32 locations needed by the lock.
const NUMINTS = 1;

class Lock {

    /**
     * @param iab an Int32Array wrapping a SharedArrayBuffer
     * @param ibase an index inside iab, leaving enough room for NUMINTS
     */
    constructor(iab, ibase) {
        // OMITTED: check parameters
        this.iab = iab;
        this.ibase = ibase;
    }

Der Konstruktor speichert hauptsächlich seine Parameter in Instanz-Eigenschaften.

Die Methode zum Sperren sieht wie folgt aus:

/**
 * Acquire the lock, or block until we can. Locking is not recursive:
 * you must not hold the lock when calling this.
 */
lock() {
    const iab = this.iab;
    const stateIdx = this.ibase;
    var c;
    if ((c = Atomics.compareExchange(iab, stateIdx, // (A)
    UNLOCKED, LOCKED_NO_WAITERS)) !== UNLOCKED) {
        do {
            if (c === LOCKED_POSSIBLE_WAITERS // (B)
            || Atomics.compareExchange(iab, stateIdx,
            LOCKED_NO_WAITERS, LOCKED_POSSIBLE_WAITERS) !== UNLOCKED) {
                Atomics.wait(iab, stateIdx, // (C)
                    LOCKED_POSSIBLE_WAITERS, Number.POSITIVE_INFINITY);
            }
        } while ((c = Atomics.compareExchange(iab, stateIdx,
        UNLOCKED, LOCKED_POSSIBLE_WAITERS)) !== UNLOCKED);
    }
}

In Zeile A ändern wir die Sperre in LOCKED_NO_WAITERS, wenn ihr aktueller Wert UNLOCKED ist. Wir treten nur in den then-Block ein, wenn die Sperre bereits gesperrt ist (in diesem Fall hat compareExchange() nichts geändert).

In Zeile B (innerhalb einer do-while-Schleife) prüfen wir, ob die Sperre mit Wartenden gesperrt ist oder nicht entsperrt ist. Da wir warten werden, schaltet compareExchange() auch auf LOCKED_POSSIBLE_WAITERS um, wenn der aktuelle Wert LOCKED_NO_WAITERS ist.

In Zeile C warten wir, wenn der Sperrwert LOCKED_POSSIBLE_WAITERS ist. Der letzte Parameter, Number.POSITIVE_INFINITY, bedeutet, dass das Warten niemals abläuft.

Nach dem Aufwachen setzen wir die Schleife fort, wenn wir nicht entsperrt sind. compareExchange() schaltet auch auf LOCKED_POSSIBLE_WAITERS um, wenn die Sperre UNLOCKED ist. Wir verwenden LOCKED_POSSIBLE_WAITERS und nicht LOCKED_NO_WAITERS, weil wir diesen Wert nach dem vorübergehenden Setzen auf UNLOCKED und dem Aufwecken durch unlock() wiederherstellen müssen.

Die Methode zum Entsperren sieht wie folgt aus:

    /**
     * Unlock a lock that is held.  Anyone can unlock a lock that
     * is held; nobody can unlock a lock that is not held.
     */
    unlock() {
        const iab = this.iab;
        const stateIdx = this.ibase;
        var v0 = Atomics.sub(iab, stateIdx, 1); // A

        // Wake up a waiter if there are any
        if (v0 !== LOCKED_NO_WAITERS) {
            Atomics.store(iab, stateIdx, UNLOCKED);
            Atomics.wake(iab, stateIdx, 1);
        }
    }

    // ···
}

In Zeile A erhält v0 den Wert, den iab[stateIdx] *vor* dem Abzug von 1 hatte. Die Subtraktion bedeutet, dass wir (z. B.) von LOCKED_NO_WAITERS zu UNLOCKED und von LOCKED_POSSIBLE_WAITERS zu LOCKED wechseln.

Wenn der Wert zuvor LOCKED_NO_WAITERS war, ist er jetzt UNLOCKED und alles ist in Ordnung (es gibt niemanden, der geweckt werden muss).

Andernfalls war der Wert entweder LOCKED_POSSIBLE_WAITERS oder UNLOCKED. Im ersteren Fall sind wir jetzt entsperrt und müssen jemanden wecken (der normalerweise wieder sperren wird). Im letzteren Fall müssen wir den durch die Subtraktion entstandenen ungültigen Wert korrigieren, und die wake() tut einfach nichts.

6.6.3 Fazit für das Beispiel

Dies gibt Ihnen eine grobe Vorstellung davon, wie Sperren basierend auf SharedArrayBuffer funktionieren. Beachten Sie, dass Multi-Threaded-Code notorisch schwer zu schreiben ist, da sich Dinge jederzeit ändern können. Ein Beweis dafür: lock.js basiert auf einem Papier, das eine Futex-Implementierung für den Linux-Kernel dokumentiert. Und der Titel dieses Papiers lautet „Futexes are tricky“ (PDF).

Wenn Sie tiefer in parallele Programmierung mit Shared Array Buffers eintauchen möchten, werfen Sie einen Blick auf synchronic.js und das Dokument, auf dem es basiert (PDF).

6.7 Die API für Shared Memory und Atomics

6.7.1 SharedArrayBuffer

Konstruktor

Statische Eigenschaft

Instanz-Eigenschaften

6.7.2 Atomics

Der Hauptoperand von Atomics-Funktionen muss eine Instanz von Int8Array, Uint8Array, Int16Array, Uint16Array, Int32Array oder Uint32Array sein. Er muss einen SharedArrayBuffer umschließen.

Alle Funktionen führen ihre Operationen atomar aus. Die Reihenfolge der Store-Operationen ist festgelegt und kann von Compilern oder CPUs nicht neu geordnet werden.

6.7.2.1 Laden und Speichern
6.7.2.2 Einfache Modifikation von Typed Array-Elementen

Jede der folgenden Funktionen ändert ein Typed Array-Element an einem gegebenen Index: Sie wendet einen Operator auf das Element und einen Parameter an und schreibt das Ergebnis zurück in das Element. Sie gibt *den ursprünglichen Wert* des Elements zurück.

6.7.2.3 Warten und Aufwecken

Warten und Aufwecken erfordert, dass der Parameter ta eine Instanz von Int32Array ist.

6.7.2.4 Sonstiges

6.8 FAQ

6.8.1 Welche Browser unterstützen Shared Array Buffers?

Derzeit sind mir bekannt:

6.9 Weiterführende Lektüre

Weitere Informationen zu Shared Array Buffers und unterstützenden Technologien:

Andere JavaScript-Technologien im Zusammenhang mit Parallelität:

Hintergrundinformationen zur Parallelität:

Danksagung: Ich bin Lars T. Hansen sehr dankbar, dass er dieses Kapitel überprüft und meine Fragen zu SharedArrayBuffer beantwortet hat.

Weiter: 7. Object.entries() und Object.values()