Les mutex les plus rapides

• Cosmopolitan Libc est connue pour fournir des binaires capables de s’exécuter sur plusieurs systèmes d’exploitation, et c’est une bibliothèque C capable d’offrir d’excellentes performances, y compris en environnement de production.
• Benchmark de mutex pour démontrer les performances : comparaison des performances d’implémentations de mutex via un test où 30 threads incrémentent le même entier 100 000 fois.
  • Windows
    • Le pthread_mutex_t de Cosmopolitan est 2,75 fois plus rapide que le SRWLOCK de Microsoft, tout en utilisant 18 fois moins de ressources CPU.
    • Le mutex de Cygwin a des performances si faibles qu’il vaudrait presque mieux utiliser un spin lock.
  • Linux
    • Le pthread_mutex_t de Cosmopolitan est 3 fois plus rapide que glibc et 11 fois plus rapide que musl libc.
    • L’utilisation CPU est 42 fois inférieure à celle de glibc et 178 fois inférieure à celle de musl libc.
  • MacOS
    • Apple Libc affiche des performances légèrement meilleures que le mutex de Cosmopolitan.
    • Cosmopolitan optimise les performances avec un algorithme fondé sur l’article d’Ulrich Drepper, "Futexes Are Tricky".

Comment est-ce possible ?

• Ces excellentes performances reposent sur la bibliothèque nsync, écrite par Mike Burrows, ingénieur de renom chez Google.
  • C’est aussi la personne qui a codé Altavista, ancien rival de Google.
• Les astuces et l’analyse de nsync
  • nsync utilise immédiatement un CAS (compare-and-swap) optimiste pour verrouiller rapidement lorsqu’il n’y a pas de contention.
  • Lorsqu’il est impossible d’acquérir le verrou, nsync ajoute le thread appelant à une liste doublement chaînée des threads en attente.
    • Chaque thread en attente reçoit son propre sémaphore dans une ligne de cache distincte et indépendante.
    • Une fois qu’un thread passe en attente, il ne touche plus au verrou principal.
    • L’importance de ce point est expliquée dans le document d’Ulrich Drepper, "What Every Programmer Should Know About Memory".
    • Quand plusieurs cœurs touchent la même ligne de cache, cela crée beaucoup de surcharge de communication dans le processeur.
  • nsync s’appuie sur le système d’exploitation via futex.
    • futex est une excellente abstraction inventée sur Linux il y a plusieurs années, qui a rapidement été adoptée sur d’autres OS.
    • Sur MacOS, cela s’appelle ulock, et sur Windows WaitOnAddress().
    • Parmi les OS pris en charge par Cosmo, le seul qui ne dispose pas de futex est NetBSD (qui implémente les sémaphores POSIX dans l’espace noyau, chaque sémaphore nécessitant la création d’un nouveau descripteur de fichier).
    • L’aspect essentiel des futex et des sémaphores est que l’OS peut mettre les threads en sommeil. Grâce à cela, nsync peut éviter de consommer du temps CPU lorsqu’il n’y a rien à faire.
  • nsync évite la famine grâce au concept de "long wait".
    • Si un thread en attente est réveillé 30 fois et échoue à acquérir le verrou en interne, un bit est ajouté au verrou pour empêcher qu’il soit pris par un thread qui n’a pas encore attendu.
    • Le CAS initial échoue alors pour tous les autres jusqu’à ce que la file d’attente se résorbe dans une certaine mesure.
  • nsync utilise le concept de "designated waker" pour accélérer le cas d’usage mesuré dans le benchmark, à savoir des verrous en contention avec de petites sections critiques.
    • Ce bit est positionné sur le verrou principal lorsqu’un thread qui tente de l’acquérir est éveillé.
    • Dans nsync, la fonction de déverrouillage se charge de réveiller le thread suivant qui attend le verrou.
    • Grâce à ce bit, le thread qui déverrouille sait qu’il n’a pas besoin de réveiller un second verrou, puisqu’un thread en attente est déjà réveillé.

Preuve en ligne

• Il est possible de constater les performances via une démonstration en direct d’un logiciel utilisant les mutex de Cosmopolitan.
• Le serveur web http://ipv4.games/ montre des performances capables de résister même à des attaques DDoS de grande ampleur.

[GN⁺]

Avis Hacker News

• Il est toujours intéressant de voir de nouvelles implémentations de mutex et de comparer leurs performances. Mais ce benchmark ressemble à un microbenchmark. En général, on teste les performances avec de gros programmes multithreadés. Sur des charges de travail complexes, les performances des mutex se manifestent différemment

  • J’ai de l’expérience dans l’écriture du verrou rapide utilisé par WebKit, et je suis la personne qui a inventé l’abstraction ParkingLot. Elle est également utilisée dans Rust et Unreal Engine

• Si les Cosmopolitan Mutexes sont bons, c’est parce qu’ils utilisent une bibliothèque appelée nsync. Cette bibliothèque a été écrite par Mike Burrows, un ingénieur renommé de Google. Mais je me demande pourquoi cette implémentation de mutex n’a pas été incluse dans le benchmark

  • Sur macOS, si l’on utilise __ulock, on peut l’implémenter plus simplement avec les fonctions wait() et notify_one() de la bibliothèque atomic de libc++

• Il y a beaucoup d’avis positifs sur Cosmo/ape/redbean, mais je n’ai encore jamais vu quelqu’un les utiliser en pratique. Je me demande si ces outils sont vraiment révolutionnaires mais pas encore largement adoptés

• J’apprécie beaucoup le projet Cosmopolitan, mais je reste sceptique face aux affirmations de supériorité exagérées. Si toutes les bibliothèques C n’ont pas adopté les mêmes astuces, c’est peut-être parce qu’elles ne sont toujours plus rapides que sur certaines architectures, certains modèles de CPU ou certaines charges de travail

• En production, la fiabilité est plus importante que la vitesse ou l’efficacité. Le plus important est d’empêcher le système de tomber en panne

• J’ai déjà corrigé un bug découvert dans la fonction de déverrouillage du mutex de nsync. Je vois des améliorations de nsync dans le projet Cosmopolitan. Je me demande s’il est sûr d’utiliser nsync upstream

• Les threads et les mutex comptent parmi les éléments les plus complexes de l’informatique. Je reste toujours sceptique tant qu’une nouvelle implémentation n’a pas été utilisée à grande échelle. Quand Java est arrivé, beaucoup de bugs liés aux threads et aux mutex sont apparus sur Solaris

• Je suis surpris de voir que nsync est bien plus rapide que SRWLOCK. J’ai déjà eu l’occasion de rétroconcevoir les SRWLOCK de win32

• Chaque fois que je vois des mutex, cela me provoque une réaction négative. J’ai travaillé à supprimer les verrous dans beaucoup de code pour les remplacer par des abstractions de file d’attente ou de messagerie. Récemment, j’explore divers algorithmes de verrouillage. J’aimerais essayer des outils de verrouillage efficaces comme nsync