Die schnellsten Mutexes

• Cosmopolitan Libc ist dafür bekannt, Binärdateien bereitzustellen, die auf mehreren Betriebssystemen laufen, und ist eine C-Bibliothek, die auch in Produktionsumgebungen eine hervorragende Leistung liefern kann.
• Mutex-Benchmark als Leistungsnachweis: In einem Test, bei dem 30 Threads dieselbe Ganzzahl 100.000-mal erhöhen, wird die Leistung von Mutex-Implementierungen verglichen.
  • Windows
    • Cosmopolitan pthread_mutex_t ist 2,75-mal schneller als Microsofts SRWLOCK und verbraucht 18-mal weniger CPU-Ressourcen.
    • Der Mutex von Cygwin ist so leistungsschwach, dass ein Spinlock die bessere Wahl wäre.
  • Linux
    • Cosmopolitan pthread_mutex_t ist 3-mal schneller als glibc und 11-mal schneller als musl libc.
    • Die CPU-Nutzung ist 42-mal geringer als bei glibc und 178-mal geringer als bei musl libc.
  • MacOS
    • Apple Libc zeigt eine etwas bessere Leistung als der Mutex von Cosmopolitan.
    • Cosmopolitan optimiert die Leistung mit einem Algorithmus, der auf Ulrich Drepper's Artikel "Futexes Are Tricky" basiert.

Wie ist das möglich?

• Die hervorragende Leistung wird durch die nsync-Bibliothek erreicht, die vom renommierten Google-Ingenieur Mike Burrows geschrieben wurde.
  • Er ist auch der Entwickler, der einst Altavista, einen früheren Google-Konkurrenten, programmiert hat.
• Die Tricks und die Analyse von nsync
  • nsync verwendet sofort optimistisches CAS (compare and swap), damit das Sperren bei fehlender Konkurrenz schnell erfolgt.
  • Wenn die Sperre nicht erworben werden kann, fügt nsync den aufrufenden Thread zu einer doppelt verketteten Liste von Wartenden hinzu.
    • Jeder Wartende erhält ein eigenes Semaphore in einer separaten, unabhängigen Cache-Line.
    • Sobald ein Thread in den Wartezustand geht, fasst er die zugrunde liegende Sperre nicht mehr an.
    • Warum das wichtig ist, wird in Ulrich Drepper's Text "What Every Programmer Should Know About Memory" erklärt.
    • Wenn mehrere Kerne dieselbe Cache-Line berühren, entsteht im Prozessor ein hoher Kommunikations-Overhead.
  • nsync nutzt futexes mit Unterstützung des Betriebssystems.
    • Futexes sind eine hervorragende Abstraktion, die vor einigen Jahren unter Linux erfunden wurde und auch in anderen Betriebssystemen schnell Verbreitung fand.
    • Unter MacOS heißen sie ulock, unter Windows WaitOnAddress().
    • Das einzige von Cosmo unterstützte Betriebssystem ohne futexes ist NetBSD (dort werden POSIX-Semaphore im Kernel Space implementiert, und jedes Semaphore muss einen neuen File-Descriptor erzeugen).
    • Der entscheidende Punkt bei futexes und Semaphoren ist, dass das Betriebssystem Threads schlafen legen kann. Dadurch verbraucht nsync keine CPU-Zeit, wenn es nichts zu tun gibt.
  • nsync vermeidet Starvation mit dem Konzept des "langen Wartens" (long wait).
    • Wenn ein Wartender 30-mal aufgeweckt wurde und intern weiterhin daran scheitert, die Sperre zu erwerben, wird der Sperre ein Bit hinzugefügt, das verhindert, dass ein noch nicht wartender Thread sie übernimmt.
    • Das anfängliche CAS schlägt dann für alle anderen fehl, bis sich die Warteschlange etwas geleert hat.
  • nsync nutzt außerdem das Konzept eines "designierten Aufweckers" (designated waker), um den im Benchmark gemessenen Anwendungsfall schnell zu machen: konkurrierende Sperren mit kleinen kritischen Abschnitten.
    • Dieses Bit wird an der zugrunde liegenden Sperre gesetzt, wenn ein Thread, der versucht die Sperre zu erhalten, wach ist.
    • In nsync übernimmt die Unlock-Funktion die Aufgabe, den nächsten auf die Sperre wartenden Thread aufzuwecken.
    • Mit diesem Bit weiß der entsperrende Thread, dass er keinen zweiten Lock aufwecken muss, weil bereits einer wach ist.

Online-Nachweis

• Die Leistung lässt sich über eine Live-Demo von Software nachvollziehen, die Cosmopolitan-Mutexes verwendet.
• Der Webserver http://ipv4.games/ zeigt eine Leistung, die selbst großen DDOS-Angriffen standhalten kann.

[GN⁺]

Hacker-News-Kommentare

• Es ist immer interessant, neue Mutex-Implementierungen und ihre Performance-Vergleiche zu sehen. Allerdings wirkt dieser Benchmark wie ein Mikrobenchmark. Üblicher ist es, die Performance mit großen Multithread-Programmen zu testen. Unter komplexen Workloads zeigt sich die Performance von Mutexen anders

  • Ich habe Erfahrung damit, die in WebKit verwendeten Fast Locks zu schreiben, und bin die Person, die die ParkingLot-Abstraktion erfunden hat. Sie wird auch in Rust und der Unreal Engine verwendet

• Cosmopolitan Mutexes sind gut, weil sie eine Bibliothek namens nsync verwenden. Diese Bibliothek wurde von dem renommierten Google-Ingenieur Mike Burrows geschrieben. Ich frage mich allerdings, warum diese Mutex-Implementierung nicht in den Benchmark aufgenommen wurde

  • Wenn man unter macOS __ulock verwendet, lässt sich das einfacher mit den Funktionen wait() und notify_one() aus der atomic-Bibliothek von libc++ implementieren

• Es gibt viele positive Meinungen zu Cosmo/ape/redbean, aber ich habe noch nie jemanden gesehen, der sie tatsächlich verwendet. Ich frage mich, ob diese Tools wirklich innovativ sind, aber noch keine breite Nutzung gefunden haben

• Ich halte viel vom Cosmopolitan-Projekt, aber bei übertriebenen Überlegenheitsbehauptungen bin ich skeptisch. Der Grund, warum nicht alle C-Bibliotheken denselben Trick übernommen haben, könnte sein, dass er nur für bestimmte Architekturen, CPU-Modelle oder Workloads durchgängig schnell ist

• In Produktionsumgebungen ist Zuverlässigkeit wichtiger als Geschwindigkeit oder Effizienz. Wichtiger ist, dass das System nicht ausfällt

• Ich habe einmal einen Bug in der Mutex-Unlock-Funktion von nsync behoben. Ich sehe Verbesserungen an nsync innerhalb des Cosmopolitan-Projekts. Ich frage mich, ob es sicher ist, das Upstream-nsync zu verwenden

• Threads und Mutexe gehören zu den komplexesten Elementen der Informatik. Ich bin bei neuen Implementierungen immer skeptisch, bis sie in großem Maßstab verwendet wurden. Als Java aufkam, wurden unter Solaris viele Thread- und Mutex-Bugs sichtbar

• Ich bin überrascht, dass nsync viel schneller ist als SRWLOCK. Ich habe Erfahrung damit, win32-SRWLOCKs rückzuentwickeln

• Jedes Mal, wenn ich Mutexe sehe, kommen negative Gefühle auf. Ich habe in viel Code daran gearbeitet, Locks zu entfernen und durch Queue- oder Messaging-Abstraktionen zu ersetzen. In letzter Zeit erforsche ich verschiedene Locking-Algorithmen. Ich würde gern effiziente Locking-Tools wie nsync ausprobieren