Spice: Fein granulare Parallelverarbeitung in Zig mit Overhead unter einer Nanosekunde

 (github.com/judofyr)
2 Punkte von GN⁺ 2024-08-14 | 1 Kommentare | Auf WhatsApp teilen
  • Spice ist ein Forschungsprojekt für Zig, das mit Heartbeat Scheduling Parallelisierbarkeit zu Funktionen hinzufügt und den Overhead dabei unter 1 ns halten will
  • Das Kerndesign ist eine Fallback-Struktur: Mit fork wird Arbeit markiert, die ein anderer Thread übernehmen kann; wenn sie aber von keinem Thread geholt wird, führt der aktuelle Thread sie bei join selbst aus
  • Im Benchmark zum Summieren eines binären Baums mit 100 Millionen Knoten lag der Overhead von Rayon mit 1 Thread bei etwa 15 ns und bei 16 Threads bei rund dem 4,5-Fachen des Baselines; Spice erzielte bei 16 Threads fast unverändert einen Geschwindigkeitsgewinn von etwa 11x gegenüber der Baseline
  • Bei sehr kurz laufenden Aufgaben wie 1000 Knoten gab es bei Rayon mit 32 Threads Fälle, in denen die Gesamtzeit 60x langsamer wurde; Spice startet dagegen gar kein Multithreading, wenn es entscheidet, dass Parallelverarbeitung nicht nötig ist, und lässt zusätzliche Threads schlafen
  • Der aktuelle Stand hat Defizite bei Tests, Dokumentation, Unterstützung für Arrays und Slices sowie zusätzlichen Benchmarks, verwendet häufig @panic, und der Autor weist darauf hin, dass man sich vor einem Produktionseinsatz der vielen Einschränkungen bewusst sein muss

Welches Problem Spice lösen will

  • Spice ist ein Projekt, das in Zig sehr fein granulare Parallelverarbeitung mit geringem Overhead umsetzen will
  • Das Ziel ist, dass Nutzer sich nicht ständig Sorgen machen müssen, ob ein Programm durch zusätzliche Parallelisierung langsamer wird
  • Für maximale Performance sind weiterhin sorgfältige Benchmarks nötig, aber Spice ist grundsätzlich so entworfen, dass das Hinzufügen von Parallelität praktisch keinen nennenswerten Overhead verursacht
  • Das Projekt ist vor allem ein Forschungsprojekt; wer einen Produktionseinsatz erwägt, sollte die Einschränkungen zuerst prüfen
  • In einem Update von September 2024 wurde Chili vorgestellt, ein Rust-Port dieser Idee

Nutzung und zentrale API

  • Die parallelen Funktionen von Spice nehmen *spice.Task als Parameter und nutzen ihn zur Koordination der Arbeit
  • Rekursive Aufrufe oder Aufrufe von parallelisierbaren Funktionen dürfen nicht direkt erfolgen, sondern müssen über t.call aufgerufen werden
  • fork richtet Arbeit ein, die von einem anderen Thread ausgeführt werden kann
  • Die Funktion muss nach fork selbst auch direkt sinnvolle Arbeit ausführen
  • join wartet darauf, ob ein anderer Thread die Arbeit abgeschlossen hat, kann aber null zurückgeben
    • null signalisiert, dass kein anderer Thread diese Arbeit übernommen hat
    • In diesem Fall muss der aktuelle Thread die Arbeit selbst ausführen

Das Design „Nicht jede Arbeit kommt aus einer Queue“

  • Die Kernidee von Spice ist, dass nicht jede Arbeit in einer Queue beginnt
  • fork signalisiert, dass es Arbeit gibt, die ein anderer Thread ausführen könnte; wenn andere Threads beschäftigt sind, verarbeitet der aktuelle Thread sie jedoch wie bei normaler sequentieller Ausführung selbst
  • Wenn keine Parallelisierung möglich ist, beschränkt sich Spice auf dem Hot Path im Wesentlichen auf push/pop in einer Queue, ohne die Queue-Einträge tatsächlich zu inspizieren
  • Die tatsächliche Koordination mit anderen Threads findet bei einem festen Heartbeat statt
    • Etwa alle 100 Mikrosekunden prüft ein Thread seine aktuelle Arbeits-Queue
    • Die oberste Arbeit in der Queue wird an einen wartenden anderen Thread übergeben
    • Weil die Heartbeat-Frequenz niedrig ist, bleibt der Gesamt-Overhead klein, selbst wenn dabei einige hundert ns verbraucht werden

Vergleich mit Rayon-Benchmarks

  • Das Summieren eines binären Baums mit 100 Millionen Knoten ist ein Fall, in dem die eigentliche Berechnung sehr schnell ist und der Overhead eines Parallel-Frameworks besonders deutlich sichtbar wird
  • Sowohl Rusts Rayon als auch Spice werden in Form einer gut les- und nachvollziehbaren Fork/Join-API verglichen
  • Im Rayon-Benchmark wurde ein Overhead von etwa 15 ns gemessen
    • Die Zeit stieg von 7,48 ns auf 22,99 ns
    • Mit 4 Threads war man ungefähr wieder auf dem Niveau der sequentiellen Performance, nutzte aber die CPU viermal so stark aus
    • Mit 16 Threads ergab sich gegenüber Rayon selbst etwa 14x Beschleunigung, gegenüber der Baseline aber nur etwa 4,5x
  • Spice zeigt beim Wechsel von 1 auf 16 Threads eine Beschleunigung von etwa 11x
    • Das skaliert etwas schlechter als Rayon, aber wegen des niedrigen Overheads bleibt der Geschwindigkeitsgewinn gegenüber der Baseline fast vollständig erhalten
  • Der Benchmark lief auf einer Google-Cloud-Instanz vom Typ c4-standard-16 mit 16 Kernen
  • Warum die Zig-Baseline etwa doppelt so schnell ist wie die Rust-Baseline, ist nicht klar
    • Laut compiled assembly speichert Rust fünf Register auf dem Stack, Zig dagegen drei

Verhalten bei kleinen Aufgaben

  • Das Summieren eines binären Baums mit 1000 Knoten ist eine extrem kurze Aufgabe mit einer Gesamtlaufzeit von nur wenigen Mikrosekunden
  • Bei Rayon lag der Overhead hier noch höher, bei etwa 19 ns, und die Performance verschlechterte sich mit jedem zusätzlichen Thread weiter
  • Auf einer Maschine mit 16 Kernen wurde die Gesamtlaufzeit bei 32 Threads 60x langsamer
    • Daraus lässt sich nicht sicher schließen, dass dieselbe Verlangsamung auch auf einer 32-Kern-Maschine auftritt
    • Trotzdem wird dieses Skalierungsverhalten als besorgniserregend bewertet
  • Die klassische Einschätzung bei Parallelverarbeitung lautet, dass sie sich nur lohnt, wenn „genug Arbeit“ vorhanden ist
    • Was als „genug Arbeit“ gilt, muss unter Umständen per inputabhängigem Benchmarking ermittelt werden
    • Bei Eingaben wie binären Bäumen, deren Gesamtgröße sich nicht allein an der Wurzel erkennen lässt, ist es schwer zu entscheiden, ob es sich um eine kleine Aufgabe handelt
    • Wenn 90 % der Arbeitslast aus kleinen Eingaben bestehen, kann eine extreme Verlangsamung zum Problem werden
    • Und wenn sich ein Programm weiterentwickelt, verschiebt sich auch die Schwelle dafür, was als genug Arbeit gilt
  • Spice entscheidet im selben 1000-Knoten-Fall, dass die Laufzeit zu kurz ist, um Multithreading zu starten
    • Zusätzliche Threads bleiben im Schlafzustand
    • Die Kerne können für andere Programme verwendet werden

Unterschiede zwischen Work-Stealing und Spice

  • Spice bietet ein Fork/Join-Modell, das üblicherweise über Work-Stealing implementiert wird
  • Bei klassischem Work-Stealing hat jeder Thread seine lokale Arbeits-Queue und stiehlt, wenn diese leer ist, Arbeit vom Ende der Queue eines anderen Threads
  • Die Ineffizienzen von Work-Stealing lassen sich auf drei Punkte reduzieren
    • Alle Aufgaben werden zu generischen Formen von „dynamischen Funktionsaufrufen“, was Kosten für dynamischen Dispatch verursacht
    • Die lokale Queue ist praktisch eine Queue, aus der alle Threads stehlen können, weshalb atomare Operationen nötig sind
    • Bei Queue-Konkurrenz entsteht Spinning, das unter bestimmten Bedingungen zu 10- bis 100-facher Verlangsamung führen kann
  • Spice reduziert diese Ineffizienzen direkt
    • Dynamischer Dispatch in der Arbeits-Queue wird nur verwendet, wenn Arbeit an andere Threads geschickt wird
    • Arbeit, die innerhalb eines einzelnen Threads ausgeführt wird, nutzt normale Funktionsaufrufe
    • Ein Push in die Arbeits-Queue wird über Stack-Pointer, aktuellen Stack-Frame und Registerspeicherung abgewickelt, ohne Synchronisation mit anderen Threads
    • Es gibt keine while-Schleifen ohne wait()-Aufruf und damit auch kein Spinning

Implementierungsdetails

  • Optimierung durch statischen Dispatch

    • Spice geht davon aus, dass fork-Arbeit in den meisten Fällen nicht von anderen Threads übernommen wird, und dupliziert den entsprechenden Ausführungspfad innerhalb der Funktion
    • Wenn keine andere Ausführung stattfindet, verhält sich das Programm wie die sequentielle Version mit nur einigen zusätzlichen, gut vorhersagbaren Branches
    • Diese Struktur ist günstig für Inlining, andere Codeoptimierungen und die CPU-Ausführung

  • Heartbeat-Signalisierung mit niedrigem Overhead

    • Heartbeat Scheduling führt Scheduling lokal und mit niedriger Frequenz aus
    • Etwa alle 100 Mikrosekunden schaut ein Thread in seine lokale Arbeits-Queue und schickt Arbeit an andere Threads
    • Wenn alle 100 Mikrosekunden 100 ns verbraucht werden, liegt der Gesamt-Overhead bei etwa 0,1 %
    • Statt OS-Signalen wird ein kooperativer Ansatz mit tick() verwendet
      • Beim Einsatz des Helpers t.call wird tick() automatisch aufgerufen
      • Ein separater Heartbeat-Thread setzt periodisch den atomaren Heartbeat-Wert jedes Threads von false auf true
      • tick() liest diesen Wert und führt bei true den Heartbeat-Code aus
    • Die Heartbeat-Funktion muss als cold markiert sein; andernfalls steigt der Overhead deutlich

  • Globaler Mutex ohne Konkurrenz

    • Der Thread-Pool von Spice hat einen einzelnen Mutex, der an mehreren Stellen gelockt wird
    • Ein globaler Mutex wird erst dann zum Problem, wenn Threads tatsächlich blockieren
    • Durch den Heartbeat führt in Spice normalerweise nur ein Thread zur selben Zeit den Heartbeat aus
    • Während der Lock gehalten wird, läuft kein User-Code; geschützt werden nur einfache Speicherzugriffe mit konstanter Laufzeit

  • Verzweigungsfreie doppelt verkettete Liste

    • Spice nutzt eine doppelt verkettete Liste, um die Arbeits-Queue zu verfolgen
    • fork() hängt am Ende an, join() nimmt vom Ende, falls noch Arbeit vorhanden ist, und beim Senden an einen Hintergrund-Worker wird vorn entnommen
    • Ein gewöhnliches Append braucht normalerweise eine Bedingung, um zu prüfen, ob die Liste leer ist
    • Spice verwendet einen immer vorhandenen Sentinel-Head-Knoten, damit die Liste nie leer ist und push/pop ohne Branches erfolgen kann

  • Minimaler Stack-Verbrauch

    • Future kennt die Zustände queued oder executing
    • Der Heartbeat schaltet eine queued future in executing um
    • Zusätzlicher Zustand für den executing-Zustand wird in einer separat per Pool allozierten Struktur gehalten, um den Stack-Verbrauch einer queued future zu reduzieren
    • Zur Unterscheidung von queued/executing wird eine manuell getaggte Union verwendet, bei der geprüft wird, ob das erste Feld prev_or_null den Wert null hat

  • Werteübergabe über Register

    • Task enthält einen Pointer auf den owning worker und einen Pointer auf das Ende der Arbeits-Queue
    • Da LLVM die Übergabe von Structs oft über den Stack abwickelt, definiert Spice callWithContext, das worker und job_tail als separate Funktionsparameter entgegennimmt
    • Diese Funktion wird immer inline aufgerufen, damit die Pointer-Parameter über Register übergeben werden

Forschungsgrundlage und verwandte Arbeiten

  • Spice basiert auf Forschung zu Heartbeat Scheduling
  • “The best multicore-parallelization refactoring you've never heard of” stellt das Konzept von Heartbeat Scheduling kurz vor; das Paper konzentriert sich auf einen einzelnen Use Case, beschreibt die Methode aber in verallgemeinerbarer Form
    • Die Lösung dieses Papers transformiert den Code in einen Continuation-Passing-Style, um zwischen sequentieller und paralleler Ausführung umzuschalten
    • Spice begann als Experiment mit diesem Ansatz, zeigte dabei aber einen Overhead von mehr als 10 ns
  • “Heartbeat scheduling: provable efficiency for nested parallelism” ist das Paper, das Heartbeat Scheduling erstmals vorstellte
    • Es bietet viele konzeptionelle Informationen, basiert in der Implementierung aber auf Interpreter-Integration und fokussiert sich stärker auf theoretische Garantien
  • “Task parallel assembly language for uncompromising parallelism” ist eine Folgearbeit, die die Heartbeat-Performance mit einer benutzerdefinierten Assembly-Sprache und OS-Signaling verbessert
    • Eine Integration in bestehende Programmiersprachen gilt als schwierig

Aktuelle Einschränkungen

  • Spice kann bei falscher Nutzung ruppiges Verhalten zeigen
    • Besonders empfindlich ist es bei der Verwendung von fork und join
    • Verbesserungen wären durch Compile-Time-Checks, Assertions im Debug-Modus und API-Änderungen möglich
  • Trotz viel Concurrency-Code beträgt die Testabdeckung 0
  • Für einen häufigen Anwendungsfall fein granulierter Parallelverarbeitung, nämlich die Verarbeitung einzelner Elemente in Arrays und Slices, gibt es keine native Unterstützung
  • Es fehlt an guter Dokumentation, die die Nutzung erklärt
  • Getestet wird derzeit vor allem an einem einzelnen kleinen Benchmark
    • Dieser Benchmark soll zwar repräsentativ sein, aber zur Validierung der Ergebnisse sind weitere Benchmarks nötig
  • In der Fehlerbehandlung wird häufig @panic verwendet
    • Für eine angemessene Zig-Bibliothek müssten Fehlerfälle umfassender berücksichtigt werden
  • Es braucht zusätzliche Benchmarks und Tests, um zu sehen, wie gut Spice unter Zig ReleaseSafe funktioniert
  • Die gesamte Codebasis umfasst etwa 500 Zeilen, und der Autor hat derzeit aus Zeitmangel keine aktiven Entwicklungspläne zur weiteren Verbesserung von Spice
  • Verbesserungen durch Forks oder Reimplementierungen in anderen Sprachen werden empfohlen

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-08-14
Meinungen auf Hacker News

  • Diese Implementierung basiert auf Heartbeat Scheduling, einer jüngeren Forschungsrichtung, und erreicht durch Amortisierung der Kosten für das Erzeugen von Parallelität eine Art dynamische automatische Steuerung der Arbeitseinheiten.
    Zugehörige Papers:
    (2018) Heartbeat Scheduling: Provable Efficiency for Nested Parallelism. https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf
    (2021) Task Parallel Assembly Language for Uncompromising Parallelism. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
    (2024) Compiling Loop-Based Nested Parallelism for Irregular Workloads. https://users.cs.northwestern.edu/~simonec/files/Research/pa...
    (2024) Automatic Parallelism Management. https://www.cs.cmu.edu/~swestric/24/popl24-par-manage.pdf

    • Das ist wirklich interessant; als Spice geschrieben wurde, kannte ich nur die ersten beiden Papers.
      Die beiden späteren werde ich mir auf jeden Fall ebenfalls ansehen.

  • Ich habe den Code nicht im Detail gelesen, aber die Formulierung Overhead unter 1 Nanosekunde wirkt wie ein missverständlicher Marketing-Slogan.
    Auf den ersten Blick scheint es ein komplizierter Messwert für „Zeit pro Arbeitseinheit“ zu sein, berechnet in einer Situation, in der die Zahl der Threads viel kleiner ist als die Zahl der „Aufgaben“.

    • Ich bin der Autor.
      Mir war klar, dass manche auf diese Formulierung negativ reagieren würden; die Absicht war aber, besser verständlich zu machen, wann und wie genau man Spice und Rayon einsetzen sollte.
      Ich empfehle, die Benchmark-Dokumentation zu lesen: https://github.com/judofyr/spice/blob/main/bench/README.md
      Wenn man parallelen Code vergleicht, stellt man üblicherweise nur eine sequenzielle/Referenzimplementierung einer parallelen Implementierung gegenüber, die alle Threads (16) nutzt. Im 100M-Fall lagen die Werte bei Rayon bei 7,48 ns für die sequenzielle Version und 1,64 ns für Rayon; dann kommt man leicht zu dem Schluss: „Rayon war bei diesem Problem 4,5-mal schneller, hat aber 16 Threads verwendet, also passt es nicht gut.“ Das ist zwar richtig, aber daraus lässt sich schwer lernen, wie es sich auf andere Problemtypen übertragen lässt.
      Wenn man denselben Benchmark mit unterschiedlicher Thread-Zahl ausführt, zeigen sich interessantere Dinge. Rayons Scheduler ist ziemlich gut darin, Arbeit auf separate Threads aufzuteilen, aber der gesamte Mechanismus zur Ausführung von Tasks hat etwa 15 ns Overhead. Selbst wenn dieses Programm ein völlig nutzloses Beispiel ist, lernt man daraus etwas, das sich später anwenden lässt: Wenn man Rayon verwendet, sollte die kleinste Arbeitseinheit wahrscheinlich ungefähr größer als 7 ns sein. Eine Ausnahme gilt, wenn es wichtiger ist, die Gesamtlatenz zu senken, selbst wenn das zulasten des Gesamtdurchsatzes geht.
      Die Rayon-Dokumentation nennt keine Zahlen und sagt nur: „Konzeptionell ähnelt ein join()-Aufruf dem Erzeugen zweier Threads, die jeweils eine Closure ausführen, aber die Implementierung ist deutlich anders und hat einen sehr geringen Overhead“: https://docs.rs/rayon/latest/rayon/fn.join.html
      Wenn ich irreführen wollte, hätte ich gesagt: „Spice bringt eine 10-fache Beschleunigung und Rayon eine 4,5-fache, also ist Spice doppelt so schnell wie Rayon.“
    • Damit „Overhead unter 1 Nanosekunde“ ein missverständlicher Marketing-Slogan wäre, müsste 1-Thread-Spice minus nicht-parallele Referenzimplementierung größer als 1 ns sein.
      Die Testergebnisse stützen die Behauptung: https://github.com/judofyr/spice/tree/main/bench
    • Ich denke, das entspricht auch der zitierten ökologischen Nische von Rayon.
      Man muss Tausende bis Millionen von Tasks verarbeiten, möchte innerhalb von Dutzenden Kernen so weit wie möglich parallelisieren und nicht vom Scheduling-Overhead aufgefressen werden; deshalb betrachtet man den Overhead pro Task.
    • Als es gestern auf Reddit auftauchte, habe ich Bedenken zu den Benchmarks geäußert.
      Der Benchmark behauptet einen Overhead von 0,36 ns pro Aufruf, umfasst aber nur die Rechenfunktion. Es gibt einen zweiten Thread, der das Scheduling übernimmt, der aber nicht in die Overhead-Zahl einfließt. Es scheint auf einer Maschine mit 8 Hyperthreading-Kernen, also 16 Threads, gelaufen zu sein; bei angenommenen 3 GHz wäre das wortwörtlich ein Overhead von einem Taktzyklus.
      Mit jedem zusätzlichen Thread steigt der Overhead wegen Lock-Contention. Bei 16 Threads wächst er auf 3,6 ns, also um den Faktor 10. Wenn das stimmt, würde es bedeuten, dass der Overhead von 0,36 ns einen konfliktfreien Lock enthält – was unmöglich ist. In den Benchmark-Daten gibt es noch weitere Merkwürdigkeiten. Entweder verstehe ich nicht, was tatsächlich gemessen wird, oder der Benchmark-Code enthält einen Bug.
      Wenn man alle Werte multipliziert, scheint die Zeit in Millisekunden gemessen zu werden. Die Laufzeit wird berechnet und bei der Umrechnung in Millisekunden ganzzahlig. Verwenden Benchmarker normalerweise nicht eine bessere Genauigkeit als das? Vielleicht wurde einfach nur time prog verwendet und die Daten sind deshalb sehr verrauscht, oder es wurde für diesen Zweck eine völlig unbrauchbare Metrik gewählt.
    • Wenn man das README liest, ist meiner Ansicht nach sehr präzise erklärt, was die Behauptung im Titel genau bedeutet.
      Es gibt keinen völlig unmissverständlichen Titel, und dieser Titel ist in Ordnung. Ich habe ihn so verstanden, dass es sich um eine Library mit extrem niedriger Latenz nach einer bestimmten Messgröße handelt, und im README konnte man diese Messgröße nachsehen. Ziemlich klar.

  • Ich bin mit diesem Bereich nicht besonders vertraut, aber das hier vorgestellte Concurrency-Modell gefällt mir
    Auch das README ist sehr gut geschrieben; schon beim Lesen bekommt man ein Gefühl dafür, was passiert. An ein paar Stellen musste ich allerdings den Kopf schieflegen. Zum Glück ist der Code ziemlich gut lesbar

    • Wenn man im Debug-Modus mit zig build baut, kommt Baseline,3.92809172, Spice 1 thread,19.1012624 heraus
      Wenn man im ReleaseSafe-Modus mit zig build --release=safe baut, kommt Baseline,3.264224280000001, Spice 1 thread,3.78043278 heraus
      Spice hat also ohne Release-Build einen ziemlich großen Performance-Einbruch. Die Referenzimplementierung wird im Debug-Build-Modus von Zig nicht im selben Ausmaß langsamer
      Verwendete Version war zig 0.13.0

  • Eine interessante Forschungsarbeit; nicht nur der Code selbst, sondern auch die Begründungen sind gut, und die Dokumentation ist gut geschrieben
    Auch das Paper zu Heartbeat Scheduling von 2018 ist lesenswert: https://www.andrew.cmu.edu/user/mrainey/papers/heartbeat.pdf

  • Liste der Einschränkungen des Projekts: https://github.com/judofyr/spice?tab=readme-ov-file#limitati...

    • Dieses Projekt ist großartig, und der Autor verdient viel Anerkennung dafür, dass er sich die Zeit genommen hat, es zum Laufen zu bringen und mit der HN-Community zu teilen
      HN ist im Allgemeinen auch dafür bekannt, übermäßig kritisch oder pessimistisch zu reagieren
      Es ist gut, dass der Autor die Grenzen seines Projekts anerkennt; dadurch nimmt er dem üblichen Zynismus weitgehend den Wind aus den Segeln
      Bei der Stelle „Mangel an Tests: Spice enthält viel kniffligen Concurrency-Code, hat aber 0 Testabdeckung. Das sollte verbessert werden, bevor Spice verantwortungsvoll für wichtige Aufgaben eingesetzt wird“ denke ich: Unabhängig davon, ob man die korrekte Ausführung wichtiger Aufgaben testet, sollte eine Bibliothek, die kniffligen Concurrency-Code implementiert, zumindest Regressionstests haben
      Aus Sicht eines Endnutzers frage ich mich, welche Garantie es gibt, dass eine Funktion, die heute funktioniert, morgen nicht durch eine subtile, bösartige Regression kaputtgeht
      SQLite hat 590-mal mehr Testcode und Testskripte als reinen C-Quellcode https://www.sqlite.org/testing.html. Neben Stabilität und Portabilität ist auch das einer der Gründe, warum SQLite zur faktischen Standard-Embedded-Datenbank der Welt geworden ist
      Das ist zwar ein etwas erzwungener Vergleich von Äpfeln mit Birnen, aber der allgemeine Punkt gilt weiterhin: Regressionstests schaffen Stabilität und Vertrauen in ein Projekt
      Dort, wo ich arbeite, erstellen wir, wenn grundlegende Regressionstests unbedingt verschoben werden müssen, normalerweise ein Folgeticket im selben Epic, sodass sie zumindest vor dem Release des Features/Epics geschrieben werden

  • Laut Beschreibung wird in den Workern Busy Waiting verwendet, um Latenzen im Nanosekundenbereich zu erreichen
    Ich frage mich, wie realistisch Busy Waiting in großen Anwendungen mit zehntausenden Tasks ist. Wenn die Tasks nicht Thread-basiert, sondern asynchron sind, könnte es möglich sein, weil es nur so viele Wartende gibt wie die Größe N des Executor-Threadpools. In jedem Fall dürfte eine solche Struktur mehr Energie verbrauchen
    In diesem Zusammenhang frage ich mich schon lange, ob es eine Möglichkeit gibt, dass der Producer den Consumer schneller aufweckt, ohne Busy Waiting zu verwenden. Zum Beispiel, ob es möglich wäre, den Consumer innerhalb des Zeitscheibchens des Producers auszuführen
    Ebenfalls dazu frage ich mich, ob eine Userspace-Operation FUTEX_WAKE möglich werden könnte, sodass sich die Kosten für das Aufwecken des Consumers auf die übliche Hälfte reduzieren ließen, also nur auf die Kosten auf Consumer-Seite

  • Es sind auch saubere, gute Papers verlinkt
    Allerdings hätte ich mir als Vergleichsgegenstand OpenMP-Tasks gewünscht. Von Rayon habe ich gehört, dass es den Ruf hat, etwas langsam zu sein

  • Kooperatives Scheduling ist die Grundlage vieler Muster, die hervorragende Kennzahlen liefern

    • Es handelt sich aber nicht um kooperatives Scheduling in dem Sinne, dass Tasks einander Yield geben
      Es ist eher eine Form der Kooperation, bei der einige Tasks an andere Threads übergeben werden können, und auch das passiert nicht immer, sondern nur einmal pro Heartbeat. Da Scheduling selten stattfindet, sind die amortisierten Kosten gering

  • Auch das README unter bench ist einen Blick wert: https://github.com/judofyr/spice/blob/main/bench/README.md