Peredvizhnikov Engine: Lock-Free-Game-Engine, geschrieben in C++20

 (github.com/eduard-permyakov)
4 Punkte von GN⁺ 2023-09-11 | 1 Kommentare | Auf WhatsApp teilen
  • Eine vollständig Lock-Free-Game-Engine, geschrieben in C++20, die das Actor-Modell für nebenläufige Berechnungen auf den Coroutine-Primitiven der Sprache implementiert
  • Mithilfe der Actor-Modell-Abstraktion lässt sich komplexe parallele Logik entwickeln, ohne sich mit den Details der Synchronisation zwischen Threads befassen zu müssen
  • Die vollständig lock-freie Implementierung bietet Fortschrittsgarantie selbst bei beliebigem Thread-Abbruch, verhindert Deadlocks, ermöglicht vorhersehbare Latenzen bei der Reaktion auf wichtige Ereignisse und sorgt für Fehlertoleranz
  • Sie garantiert, dass die Engine weiterläuft, selbst wenn einer der Worker-Threads asynchron beendet wird
  • Die Implementierung umfasst Software Transactional Memory, Lock-Free-Queues, Lock-Free-Serialisierungsprimitive, std::atomic_shared_ptr, einen Lock-Free-Scheduler, einen Lock-Free-Speicherallokator und ein Compile-Time-DAG
  • Lock-Free-Algorithmen, Designentscheidungen und Benchmarks werden im Dokument Peredvizhnikov Engine: Design and Implementation of a Completely Lock-Free Scheduler behandelt
  • Zur Unterstützung datenorientierten Designs wurde eine In-Memory-Datenbank implementiert, die für den Zugriff auf Komponentenebene optimiert ist und große Datensätze unterstützt
  • Die In-Memory-Datenbank basiert auf den Datenstrukturen Flat Hash Map und Bitwise Trie with Bitmap
  • Derzeit wird nur Linux unterstützt, und zum Build aus dem Quellcode ist Clang++ 16 erforderlich
  • Der Quellcode wird unter der GPLv3-Lizenz bereitgestellt; die Erlaubnis, Teile oder den gesamten Code unter einer anderen Lizenz zu verwenden, kann im Einzelfall gewährt werden

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2023-09-11
Meinungen auf Hacker News

  • Im Actor-Framework wird eine gewöhnliche std::deque als Queue für Methodenzeiger verwendet, und beim Einreihen von Nachrichten wird nach dem Benaphore-Prinzip gelockt.
    Ursprünglich kombiniert man wie bei Futex atomare Operationen mit Lock-Primitiven; mein Lock-Primitiv verhält sich je nach Anzahl der Wiederholungsversuche als Kombination aus Spinlock und Mutex. In Benchmarks blockiert die Push-Funktion für Nachrichten nur sehr selten, und auch die Wahrscheinlichkeit eines Betriebssystem-Kontextwechsels ist gering. Selbst wenn gelegentlich ein gesperrter Thread ausgelagert wird, passiert das nicht häufig genug, um die Kosten eines lockfreien Algorithmus zu rechtfertigen.
    Kurz gesagt: Eine nicht-lockfreie Queue ist deutlich schneller als eine lockfreie Queue, aber man muss sehr seltene lange Latenzen durch Kontextwechsel akzeptieren, bei denen niemand den Lock bekommt. Auf moderner Hardware lassen sich pro Worker-Thread 10 Millionen Nachrichten pro Sekunde in die Queue einreihen.

    • Du sagst zwar „ursprünglich Futex“, aber Benaphore ist eine ziemlich alte Idee, und Futex ist nicht einfach „Benaphore nach Linux-Art“.
      Der Kern ist, dass tatsächlich kein Kernel-Objekt, also kein separates Lock-Primitiv, nötig ist. Genau an diesem Punkt wurde aus „das kennt doch jeder“ eine Funktion, die „sofort ins Betriebssystem gehört“.
      Beim Futex-Design verwaltet das Betriebssystem statt eines OS-Synchronisationsobjekts zur Konfliktbehandlung eine Liste von Adress→Thread-Zuordnungen. Wenn Thread T auf einem Futex an Adresse X einschläft, wird in die Liste eingetragen, dass X auf T zeigt; kommt eine Anfrage, den Futex X zu wecken, durchsucht das Betriebssystem die Liste und weckt T auf.
      Der Unterschied zeigt sich bei den Beschränkungen. Dinge wie Benaphores sind teure systemweite Ressourcen; ich meine, BeOS erlaubte nur etwa 65.536 davon pro Maschine. Ein Futex hingegen ist einfach Speicher, daher gibt es keinen Grund für eine Begrenzung.
    • Bei so einem interessanten Beitrag sollte es einen Code-Link geben. Das würde die Behauptungen belegen, und Leute wie ich finden die Idee spannend und wollen sich sofort die Implementierung ansehen.
    • Das hängt stark von den Details der Situation ab. Bei viel Contestion fällt die Performance stark ab, und sogar atomare Instruktionen können zum Flaschenhals werden (https://stackoverflow.com/q/2538070).
      Die Beobachtung, dass man in vielen Fällen einfach Locks verwenden und sich keine Sorgen machen muss, halte ich für richtig. Es gibt aber auch Anwendungen oder Situationen, in denen man es besser machen kann. Wenn der Consumer mit einer einzigen Lock-Operation alle Einträge aus der Queue nimmt und die Producer den Consumer signalisieren, kann man mit etwas Vorsicht Effizienz und Durchsatz der Queue erhöhen. Zum Beispiel sollte man nicht bei jedem eingefügten Eintrag signalisieren, sondern nur dann, wenn die Queue von leer zu nicht leer wechselt.
    • Geht es bei lockfreien Datenstrukturen nicht eher darum, die Auswirkungen von Contention zu verringern, statt bei geringer Contention den Durchsatz zu erhöhen?
    • Dass diese „Kosten akzeptabel“ sind, gilt nicht für Leute mit der strikten Anforderung, dass die erwähnten unvorhersehbaren, seltenen langen Latenzen absolut niemals auftreten dürfen.

  • Der lockfreie Scheduler sieht definitiv interessant aus, besonders die Linearisierbarkeit des Event-Broadcasts fällt auf. Allerdings liegt der Spitzenwert in den Benchmarks des Papers bei 12 Actor-Paaren (und 12 Kernen?) bei 43.500 Nachrichten pro Sekunde, und auch der Single-Core-Graph zeigt nur etwa 5.000 Nachrichten pro Sekunde; für diese Art Benchmark ist das überraschend niedrig.
    Da die Engine Linux und, wichtiger noch, x86 voraussetzt (wegen der Assembler-Instruktionen), konnte ich das noch nicht reproduzieren, aber ich würde mindestens etwa 1 Million Requests pro Sekunde pro Actor-Paar erwarten. Wenn man an Fälle wie Erlang denkt, wird der Overhead darunter prohibitiv hoch.
    Diese Engine konzentriert sich auf Message Passing, aber meiner Erfahrung nach ist dieser Ansatz sehr schwer zu handhaben. Zustandsmaschinen sind schwierig, und mit mehreren untergeordneten Actors wird es noch schwieriger. Im Kern sehe ich Actors eher als eine Möglichkeit, Zustand ohne Locks zu isolieren, als als Message Passing. Swift Actors haben es meiner Meinung nach richtig gemacht: Verwendet man Methodenaufrufe statt Nachrichten, ist das nicht nur leichter nachzuvollziehen, sondern zeigt auch zusätzliche Stellen an, an denen sich zur Laufzeit der Kontext ändern kann, ohne dass der Scheduler zwingend eingreifen muss. Gemeinsamer Zustand ist langsam und schadet der Skalierbarkeit.
    Vor Kurzem habe ich eine header-only Library gebaut, die mit C++20-Coroutinen etwas Ähnliches wie Swift Actors implementiert. Wer interessiert ist, kann nach „coroactors“ suchen. Ohne Contention komme ich auf etwa 10 Millionen Requests pro Sekunde; bei Contention und Abhängigkeit vom Scheduler fand ich selbst 1 bis 3 Millionen Requests pro Sekunde schon mit zu hohem Overhead. Besonders im Vergleich zu normalen Methodenaufrufen auf gemeinsamem Zustand, der durch einen Mutex geschützt ist. Coroutinen sind ansteckend: Nach und nach werden immer mehr Funktionen zu async-Coroutinen, und in nichttrivialen Codebasen nehmen Coroutine-Aufrufe oder Message Passing zu. Deshalb muss der Overhead so niedrig wie möglich sein; andernfalls verbringt man mehr Zeit mit Task-Wechseln als mit nützlicher Arbeit.

  • Es wird als Actor-basiert beschrieben, und das Senden einer Nachricht an einen Actor wird als gleichwertig damit erklärt, die Actor-Funktion unter einem Mutex auszuführen. Das heißt: Selbst wenn N Threads Nachrichten senden, gibt es nur einen Thread, der den Actor-Code ausführt, also wird er wie bei einem Mutex serialisiert.
    Daher gibt es technisch gesehen zwar vielleicht „vollständig Lock-free“, aber solange man Actors verwendet, keine Verbesserung der Parallelisierung.

    • Nicht unbedingt. Bei Mutex-basierten Actors bleibt, wenn der Actor-Thread angehalten wird, dieser Mutex – also der Actor-Code – gesperrt, bis der ursprüngliche Thread wieder fortgesetzt wird. Da der Mutex, den der angehaltene Thread besitzt, gesperrt ist, kann dieser Actor-Code auch bei mehr Parallelität nicht „neu gestartet“ oder „fortgesetzt“ werden.
      Diese Implementierung stützt sich stark auf wiederaufnehmbare Funktionen, sodass die Arbeit eines bereits laufenden, aber angehaltenen Actors von einem anderen parallelen Thread aufgegriffen und fortgesetzt werden kann. Siehe Seite 3 des ausgezeichneten Designdokuments: https://github.com/eduard-permyakov/peredvizhnikov-engine/bl...
      Streng genommen ist es also vielleicht nicht „paralleler“ (da die Zahl der Actors gleich bleibt), aber es scheint die verfügbare Parallelität besser zu nutzen, um dieselbe Menge an Arbeit abzuschließen.
    • Wo steht, dass „das Senden einer Nachricht an einen Actor gleichwertig damit ist, die Actor-Funktion unter einem Mutex auszuführen“? Nach meinem Verständnis bedeutet das Actor-Modell Message Passing und asynchrone Ausführung. Wenn es N Actors gibt, können im Gegenteil N Threads parallel laufen.
    • Dass es keine Verbesserung der Parallelisierung gibt, stimmt, aber es verringert die Parallelität auch nicht. Es ist eine andere Art, über Nebenläufigkeit nachzudenken, und nach meinem Maßstab eine einfachere.
      Wenn es einfacher zu durchdenken ist, sieht man auch besser, wo es bei denselben Ressourcen zu Contention kommt, und das hilft tatsächlich dabei, potenzielle Parallelität zu verbessern. Wenn man eine bestimmte Gelegenheit erkennt, bei der SMP die Geschwindigkeit erhöhen kann, kann man im Actor-Modell etwas davon abweichen und mehrere Threads aus der Message Queue lesen lassen; wenn das nicht möglich ist, fügt man mehr Actors hinzu, um die Daten besser aufzuteilen.

  • Hat jemand stark umkämpfte kritische Bereiche von STM im Vergleich zu traditionellen Mutex-Implementierungen debuggt oder profiliert? Am Ende braucht man irgendetwas, das gleichzeitige Zugriffe auf Shared Memory vermittelt, und es gibt kein kostenloses Mittagessen. Mutexe sind sehr gut optimiert, profiliert und verstanden.
    Bei STM bin ich mir dagegen nicht sicher, ob es auf demselben Niveau ist. Können Transaktionen nicht unbegrenzt (?) oft erneut versucht werden?

    • In diesem Fall ist der Vermittler der Scheduler. Er ruft tatsächlich asynchrone Blöcke auf und versucht es bei einem Fehlschlag potenziell erneut. Im Code des Originalartikels gibt es Atomic Blocks, sequenzielle Ausführung von Blöcken und zustandsbehaftete Blöcke, um jeweils nur einen Zugriff zu garantieren.
      Der Kern ist scheduler.cpp und verwendet std::coroutines.
      Das ist ähnlich wie async/await in anderen Sprachen. Der Scheduler hat eine Queue von Tasks (Coroutines) und einen Thread-Pool (N>0), der sie ausführt.
      Hier tauschen datenhaltige Tasks Nachrichten miteinander aus. Dafür braucht man keine Locks, bezahlt aber mit höherem Speicherverbrauch.
    • Tatsächlich ist bei hungerfreiem STM die Zahl der Transaktions-Retries begrenzt. Ein Beispiel ist 2PLSF, daneben gibt es mehrere andere Ansätze https://zenodo.org/record/7886718

  • Fühlt sich nach BEAM an?
    https://youtu.be/bo5WL5IQAd0?feature=shared

  • Ich habe keine Erwähnung gesehen, wie schwierig es ist, so eine Engine zu debuggen.

  • Ich habe keine Zeit, die Implementierung zu lesen, aber nur nach dem README klingt es wie ein klassisches verteiltes System zwischen Game-Threads. Muster wie Retry-Backoff dürften häufig sein.

  • Lock-free klingt zwar cool, aber ich finde, Code, der in nennenswertem Umfang atomare Operationen verwendet, sollte von formalen und möglichst maschinell verifizierten Beweisen begleitet werden. Atomare Ordnungen korrekt zu verwenden, die nicht sequenziell konsistent sind, ist einfach zu schwierig. Ich habe mehrfach falsch geschriebenen Code gesehen, und die daraus entstehenden Bugs sind die schlimmsten.

  • Wo ist die Game-Demo? Um heute als Game Engine zu gelten, braucht man auch echte Tools, Exporter für Maya oder 3DSMax sowie Kollaborationstools, Metriken, Benachrichtigungen und Ähnliches.

    • Stimme ich nicht zu. „Game Engine“ bedeutet nicht zwangsläufig „etwas, das Unity oder Unreal ersetzen kann“.

  • Es heißt zwar „Lock-free“, aber danach sieht es bisher nicht aus.
    export std::mutex iolock{};
    export std::mutex errlock{};
    SDL_PollEvent