À quelle vitesse vont les pipes Linux ? (2022)

 (mazzo.li)
1 points par GN⁺ 2023-10-06 | 1 commentaires | Partager sur WhatsApp
  • En traçant le débit des pipes Linux avec perf et une analyse du chemin noyau, l’implémentation simple basée sur write/read, initialement à 3.7GiB/s, est finalement poussée jusqu’à 62.5GiB/s
  • Le point de départ du goulot d’étranglement vient du fait qu’un pipe fonctionne comme un ring buffer contenant des références vers des pages de 4KiB, ce qui cumule les coûts de copie, d’allocation de pages, de verrouillage et d’attente/réveil
  • vmsplice et splice réduisent les copies entre la mémoire utilisateur et les buffers du noyau, portant le débit à environ 12.7GiB/s puis 32.8GiB/s respectivement
  • Ensuite, le coût de conversion d’une plage d’adresses virtuelles en struct page devient visible, et l’utilisation de huge pages de 2MiB réduit la charge de parcours des tables de pages, ce qui fait monter le débit à 51.0GiB/s
  • La dernière optimisation, SPLICE_F_NONBLOCK avec une busy loop, augmente encore le débit, mais monopolise un cœur CPU pendant l’attente de disponibilité

Objectif de l’expérience et performances de référence

  • L’objectif est d’examiner comment les pipes Unix sont implémentés sous Linux, puis d’optimiser progressivement un programme de test qui écrit et lit des données via un pipe
  • L’environnement de test utilise un CPU Intel Skylake i7-8550U et Linux 5.17 ; comme l’implémentation interne de Linux évolue en permanence, les chiffres peuvent varier selon l’environnement
  • Le point de départ est un programme qui envoie de façon répétée un buffer de 256KiB dans un pipe via les appels système write et read
    • write réécrit en boucle le même buffer de 256KiB
    • read lit un total de 10GiB et affiche le débit
    • Le code est disponible dans pipes-speed-test
  • Comme point de comparaison, un programme FizzBuzz hautement optimisé produit environ 36.2GiB/s mesurés avec pv
    • FizzBuzz utilise des blocs de 256KiB, soit la taille du cache L2
    • Cette expérience utilise les mêmes blocs de 256KiB, mais sans calculer le contenu de sortie, afin d’approcher la limite du pipe IO
  • Le résultat de la première implémentation est le suivant
    • ./write | ./read
    • 3.7GiB/s, buffer de 256KiB, 40960 itérations, 10GiB transférés au total

Pourquoi write et read sont lents

  • Avec perf record -g et perf report, on constate qu’environ 47 % du temps côté write est consommé dans pipe_write
  • À l’intérieur de pipe_write, copy_page_from_iter et __alloc_pages occupent une part importante
    • copie des données
    • allocation de pages
    • ordonnancement
    • attente et réveil
    • acquisition et libération de verrous
  • Un pipe Linux est un ring buffer contenant des références de pages
    • pipe_inode_info contient head, tail et un tableau de pipe_buffer
    • pipe_buffer contient struct page *page, offset et len
    • Sur x86-64, la taille de page standard est de 4KiB
    • Le ring buffer contient 16 slots par défaut ; dans l’exemple, un pipe à 8 slots peut contenir jusqu’à 32KiB
  • head indique l’extrémité d’écriture et tail l’extrémité de lecture
    • Si le pipe est plein, write se bloque
    • Si le pipe est vide, read se bloque
  • pipe_write suit globalement cette séquence
    • si le pipe est déjà plein, il attend qu’un espace se libère
    • s’il reste de la place dans le buffer pointé par head, il le remplit d’abord
    • s’il reste des données et des slots libres, il alloue une nouvelle page, la remplit et met à jour head
  • pipe_read fait l’inverse : il consomme les pages, libère celles qui ont été entièrement lues, puis met à jour tail
  • Sur ce chemin, chaque page est copiée deux fois
    • une fois de la mémoire utilisateur vers le noyau
    • puis une seconde fois du noyau vers la mémoire utilisateur
  • Les copies se font par pages de 4KiB, avec entre les deux de la synchronisation ainsi que des allocations et libérations de pages
  • Sur la même machine, une lecture RAM séquentielle mono-thread atteignait environ 16GiB/s ; vu la complexité du chemin des pipes, il n’est pas surprenant que write/read soient environ 4 fois plus lents

Réduire les copies avec vmsplice et splice

  • En IO rapide, le coût des copies entre la mémoire utilisateur et les buffers du noyau peut devenir le principal goulot d’étranglement
  • Linux fournit, autour des pipes, des appels système permettant des transferts sans copie
    • splice : déplace des données entre un pipe et un descripteur de fichier
    • vmsplice : déplace des données de la mémoire utilisateur vers un pipe
  • vmsplice utilise un tableau de struct iovec pour désigner les buffers à insérer dans le pipe
    • la valeur de retour est le nombre d’octets effectivement placés dans le pipe
    • à cause de la limite de taille du ring buffer du pipe, l’intégralité de la taille demandée peut ne pas entrer en une seule fois
  • vmsplice relie la mémoire utilisateur au pipe sans la copier ; il faut donc veiller à ne pas réutiliser le buffer avant que le lecteur n’ait consommé les données
  • Le programme FizzBuzz utilise pour cela un double buffering
    • un buffer de 256KiB est divisé en deux moitiés de 128KiB
    • la taille du pipe est fixée à 128KiB, ce qui donne 32 slots sur la base de pages de 4KiB
    • les deux demi-buffers sont remplis en alternance puis envoyés dans le pipe avec vmsplice
  • Le programme de test ne réécrit pas réellement le contenu du buffer, mais conserve malgré tout le double buffering pour rester proche de la structure d’un vrai générateur de sortie
  • Remplacer write par vmsplice fait monter le débit à 12.7GiB/s
    • le volume de copie est réduit de moitié
    • cela représente plus de 3 fois les performances de write/read
  • Si l’on remplace aussi la lecture par splice, on supprime toutes les copies et le débit monte à 32.8GiB/s
  • Il faut toutefois rester prudent avec la sûreté de vmsplice
    • une page peut voir sa durée de vie prolongée si elle est splice à nouveau
    • on ne sait pas clairement si l’absence de SPLICE_F_GIFT suffit à la rendre sûre
    • l’utilisation sûre de pipes zero-copy demande une attention particulière

iov_iter_get_pages et le coût de conversion des pages

  • Après l’adoption de vmsplice et splice, perf montre que le temps est largement concentré dans le chemin de vmsplice
    • iov_iter_get_pages
    • __mutex_lock.constprop.0
    • add_to_pipe
  • iov_iter_get_pages convertit la plage de mémoire virtuelle d’un struct iovec fourni à vmsplice en une liste de struct page que le pipe peut contenir
  • Les processus utilisent des adresses virtuelles, pas des adresses physiques
    • le CPU traduit les adresses virtuelles en adresses physiques via les tables de pages
    • sur x86-64, la taille de page standard est de 4KiB
    • les tables de pages x86-64 sont décrites comme une structure en arbre à 4 niveaux avec un facteur de 512 à chaque niveau
  • Le pipe_buffer d’un pipe référence des struct page
    • struct page est la structure centrale utilisée par le noyau pour gérer une page physique et ses métadonnées associées
    • vmsplice doit donc convertir la plage de mémoire virtuelle d’entrée en références de pages physiques
  • À l’intérieur de iov_iter_get_pages, la majeure partie du temps est passée dans get_user_pages_fast
    • avec un buffer de 128KiB et des pages de 4KiB, il faut obtenir un total de 32 pages
    • le code du pipe appelle en pratique cette fonction avec nr_pages = 16 à la fois et répète si nécessaire, mais le nombre total de pages splice reste de 32
  • get_user_pages_fast parcourt les tables de pages en logiciel, de façon similaire à ce que fait le CPU, afin de collecter les struct page
  • Tant que l’appelant utilise les pages, il faut incrémenter le compteur de références du struct page pour éviter que la page physique ne soit réutilisée
    • ensuite, put_page doit diminuer ce compteur de références
  • Si l’on remplit le buffer au départ avec memset, les entrées des tables de pages sont créées à l’avance, ce qui évite le chemin lent de get_user_pages_fast
    • sans memset, le débit tombe à 25.0GiB/s dans l’exemple
    • avec les huge pages, ce phénomène ne se manifeste pas de la même manière

Réduire le coût de gestion des pages avec les huge pages

  • x86-64 prend en charge, en plus des pages standard de 4KiB, des huge pages de 2MiB et de 1GiB
    • les expériences suivantes ne traitent que des huge pages de 2MiB
    • les pages de 1GiB sont relativement rares et jugées excessives pour ce cas
  • Les huge pages représentent la même plage mémoire avec moins de pages, ce qui réduit le coût de gestion
    • lors de la traduction d’une adresse virtuelle en adresse physique, un niveau de table de pages disparaît aussi
    • elles peuvent également aider à réduire la pression sur le TLB du CPU
  • Dans cette expérience, le goulot d’étranglement direct n’est pas le parcours matériel des tables de pages, mais le chemin logiciel du noyau dans get_user_pages_fast
  • Sous Linux, on peut demander l’usage de huge pages en allouant une mémoire alignée sur 2MiB puis en appelant madvise(..., MADV_HUGEPAGE)
  • L’application des huge pages fait monter le débit à 51.0GiB/s
  • Ce gain ne vient pas du fait qu’un struct page pointerait tel quel vers une page de 2MiB
    • le code du noyau suppose généralement qu’un struct page représente la taille de page standard de l’architecture courante
    • une huge page est représentée par une head struct page et plusieurs tail struct page
    • une huge page de 2MiB peut ainsi être représentée par jusqu’à 512 struct page sur la base de 4KiB
  • Malgré cela, une fois la première entrée trouvée, les struct page suivantes peuvent être générées via une simple boucle, ce qui réduit le coût de parcours répété des tables de pages
  • Les noyaux postérieurs à Linux 5.17 incluent struct folio, qui identifie explicitement la head page et réduit le besoin de vérifications head/tail à l’exécution

Réduire le coût de synchronisation avec une busy loop

  • Après l’introduction des huge pages, perf met en évidence le temps passé dans wait_for_space et __wake_up_common_lock
    • coût de l’attente d’un espace disponible pour écrire
    • coût du réveil du côté lecteur
  • Pour éviter ce coût de synchronisation, vmsplice et splice peuvent utiliser SPLICE_F_NONBLOCK
    • si le pipe n’est pas disponible pour l’écriture, l’appel retourne immédiatement EAGAIN
    • l’appelant tourne alors en busy loop jusqu’à ce que l’opération devienne possible
  • Avec cette busy loop, le débit monte jusqu’à 62.5GiB/s
  • Le coût est lui aussi très clair
    • le cœur CPU est entièrement monopolisé pendant l’attente que vmsplice ou splice soit prêt
    • on échange davantage d’utilisation CPU contre moins de latence ou plus de débit
  • Au final, ce benchmark synthétique passe d’environ 3.5GiB/s à environ 65GiB/s

Détails restants et sujets pratiques

  • Le travail d’optimisation s’est fait en lisant à la fois la sortie de perf et le code source de Linux
  • Les sujets abordés dépassent les seuls pipes et le splicing, et touchent à des thèmes plus larges de programmation haute performance

    • Opérations sans copie

      • ring buffers
      • pagination et mémoire virtuelle
      • surcharge de synchronisation
      • dans du code réel, les deux buffers sont alloués séparément pour réduire la contention sur les tables de pages
      • get_user_pages incrémente le compteur de références des entrées de table de pages et put_page le décrémente
      • si les deux buffers utilisent des entrées de tables de pages distinctes, la contention sur la modification des compteurs de références diminue
      • le test a été exécuté avec taskset pour épingler les processus ./write et ./read sur deux cœurs
      • le dépôt inclut aussi un benchmark synthétique pour get_user_pages_fast
      • il permet de mesurer la différence de vitesse avec ou sans huge pages
      • le splicing reste un concept ambigu et risqué, et les problèmes associés continuent de peser sur les développeurs du noyau

À lire aussi

1 commentaires

 
GN⁺ 2023-10-06
Avis sur Hacker News

  • Si j’ai bien compris, vmsplice, lorsqu’il est utilisé simultanément des deux côtés, lecture et écriture, ressemble davantage à un petit mécanisme de mémoire partagée entre deux processus
    Autrement dit, les deux processus doivent faire preuve d’une extrême prudence quant au moment où ils lisent et écrivent dans le tampon, et à la manière de le restituer après utilisation. C’est rapide, mais aussi effrayant, et il est dommage que l’implémentation naïve que tout le monde serait susceptible d’écrire soit 20 fois plus lente que les performances possibles

    • Si vous essayez d’écrire la version 20 fois plus rapide, vos collègues trouveront que vous rendez les choses excessivement complexes et que vous ne jouez pas collectif
    • vmsplice ne semble pas vraiment être un petit mécanisme de mémoire partagée entre deux processus. Il ne prend en charge le zero copy que de la mémoire utilisateur vers le pipe ; dans l’autre sens, il y a une copie
      Pour plus de détails, voir https://mazzo.li/posts/fast-pipes.html#fn10

  • Je me demande s’il existe une bibliothèque de traitement de données qui abstrait les pipes, sockets, fichiers et la mémoire tout en effectuant ce genre d’optimisations
    J’aimerais savoir s’il existe une telle bibliothèque en C, C++, Rust ou dans un autre langage système. Comme je ne suis pas familier avec des API comme splice() et vmsplice() mentionnées dans l’article, je me demande s’il existe une bibliothèque qui exploite automatiquement ce type d’optimisation lorsque c’est possible pour construire des applications bas niveau. Je me demande aussi si libuv, tokio ou Netty gèrent cela automatiquement sous Linux ; d’après une recherche rapide, il semble que ce soit peut-être le cas

    • Cela peut aller à contre-courant de l’approche habituelle, mais comme ce n’est pas portable, cela ne vaut pas vraiment la peine de l’abstraire. Il est probable qu’on finisse par l’implémenter soi-même là où c’est nécessaire
      Le code de plus haut niveau utilise rarement ce genre de fonctionnalité, car elle est assez spécialisée et doit être adaptée à Linux. Si l’on se contente de déplacer des données sous Linux sans les examiner, splice est utile. Des applications comme les proxys TCP/UDP en ont clairement besoin, mais cela ne convient pas tellement à un serveur HTTP ordinaire. Si vous développez ce type d’application, vous croiserez souvent des mots-clés comme zero copy, et splice sera l’un des premiers résultats que vous verrez
    • Il existe un crate pour tokio. Ce n’est pas automatique, mais cela peut être intéressant : https://lib.rs/crates/tokio-splice
    • Cosh mérite qu’on s’y intéresse. Je suis justement en train de lire l’article et d’y réfléchir ; c’est un modèle qui fournit une abstraction de passage de messages tout en autorisant des optimisations
      Il ne semble pas très connu en dehors du milieu de la recherche, et écrire une implémentation efficace de Cosh risque de prendre pas mal de temps. En résumé, il y a trois modes de transfert : move, share et copy. Par exemple, un transfert move remet entièrement au destinataire des données sur lesquelles l’expéditeur dispose de droits de lecture/écriture, et peut être implémenté par un remappage de mémoire virtuelle dans les tables de pages. Il existe aussi des attributs strong/weak indiquant si l’on peut faire confiance à l’expéditeur et au destinataire pour coopérer, ou s’il faut au contraire les isoler strictement par remappage des permissions de mémoire virtuelle. Honnêtement, je ne sais pas si cela peut être optimisé suffisamment bien pour rivaliser de façon fiable avec quelque chose comme des pipes ultra-optimisés ; cela pourrait devenir un problème de « compilateur suffisamment intelligent ». Mais je pense que cela vaut quand même la peine d’essayer
      [1] https://barrelfish.org/publications/trios14-baumann-cosh.pdf

  • Discussion antérieure à 2022 : https://news.ycombinator.com/item?id=31592934

  • Un fait surprenant que j’ai découvert par hasard il y a 4 ans, c’est que l’utilisation des pipes Linux peut produire un comportement non déterministe
    https://www.gibney.org/the_output_of_linux_pipes_can_be_inde...

    • Ce n’est pas si surprenant. Le pipe créé ne transmet en réalité aucune des données envoyées par echo
      (echo red; echo green 1>&2) | echo blue crée deux sous-shells séparés par le symbole |. Un sous-shell étant un processus enfant du shell courant, il hérite de propriétés importantes comme la table des descripteurs de fichiers ouverts. Les deux sous-shells s’exécutent simultanément, et le shell parent ne fait qu’appeler wait() jusqu’à la fin de tous les processus enfants. Il est globalement impossible de prédire quel enfant s’exécutera en premier, et sur un système multicœur ils peuvent littéralement s’exécuter en même temps. La sortie standard du sous-shell de gauche est reliée à l’extrémité écriture du pipe, et l’entrée standard du sous-shell de droite à l’extrémité lecture. Mais echo blue ne lit pas son entrée, il ne fait qu’écrire en sortie, donc rien n’est lu depuis le pipe. echo green >&2 envoie sa sortie standard vers la destination pointée par l’erreur standard, et non vers le pipe. Au final, echo green et echo blue écrivent dans le même fichier, probablement directement dans le terminal, ce qui crée une condition de concurrence ; l’ordre dépend de celui qui est planifié en premier
    • En y réfléchissant un peu plus, c’est tout à fait naturel. Les programmes d’un pipeline s’exécutent simultanément
      Sinon, les pipelines ne seraient pas utiles. Par exemple, dans un pipeline qui télécharge un fichier tar avec curl puis l’extrait immédiatement, si l’on attendait la fin de curl avant d’exécuter tar, il faudrait résoudre des problèmes comme l’endroit où stocker le gros fichier tar intermédiaire. tar doit tourner en même temps que curl pour garder un petit buffer et s’exécuter rapidement. Le seul flux de contrôle entre les programmes d’un pipeline passe par l’entrée standard et la sortie standard. Dans l’exemple, on écrit sur l’erreur standard, donc cela ne fait évidemment pas partie du flux de contrôle déterministe
    • Si vous aimez les entrées/sorties sans copie rapides sous Linux, cet article vaut aussi le détour
      Au passage, pour éviter toute confusion, « Indeterministic » est un terme de philosophie ; le terme d’informatique est « nondeterministic »
      0. https://blog.superpat.com/zero-copy-in-linux-with-sendfile-a...
    • Est-ce vraiment si surprenant ? Il serait plus facile de dissiper la confusion en sachant quelle sortie était attendue, et pourquoi
      Cette commande a probablement été écrite volontairement de façon étrange, et un relecteur de code aurait clairement haussé un sourcil. Il y a bien echo red, mais il n’est transmis nulle part. C’est peut-être une blague sur le « red herring ». echo green va vers l’erreur standard, donc il n’apparaît que s’il se termine avant echo blue. L’ordre exact dépend du buffering de sortie, qui dépend du time slice attribué en premier, et varie selon le nombre de CPU et la charge. C’est donc non déterministe, mais de la même manière que top est non déterministe
    • Y a-t-il des cas où cela cause de vrais problèmes ? Honnêtement, cet exemple semble assez artificiel

  • En résumé, en supposant que les deux programmes soient écrits de façon aussi optimale que possible, la vitesse maximale d’un pipe est proche de la vitesse à laquelle un cœur du système peut lire et écrire
    Fondamentalement, comme le noyau mappe les mêmes pages de mémoire physique depuis la sortie standard d’un programme vers l’entrée standard d’un autre, l’opération est sans copie ou, dans les situations moins optimales, proche d’une copie unique rapide. Une fois qu’on sait cela, réaliser des tâches très performantes avec des scripts shell qui chaînent deux outils ou plus via des pipes devient à la fois gratifiant et amusant. C’est l’un des outils les plus utiles de la boîte à outils

    • Les pipes ne sont sans copie que lorsqu’on utilise splice ou vmsplice. Ces appels système propres à Linux sont difficiles à utiliser, en particulier vmsplice
      La grande majorité des programmes et filtres shell ne les utilisent pas, à l’exception notable de pv, et paient donc le coût d’une copie vers la mémoire du noyau puis d’une recopie en sortie
    • La limite sérieuse des pipes, à ma connaissance, est qu’ils ne peuvent bufferiser que 64 Ko / 16 pages sur Linux x86. En général, il y a de fortes chances que ce soit plus lent que la bande passante cœur-mémoire
    • Ce n’est donc pas aussi important que ne l’imaginent les programmeurs qui utilisent beaucoup les threads
      Selon ses caractéristiques de charge, l’application en cours de développement peut probablement être implémentée plus proprement avec des pipes + processus, ou avec des threads verts / en espace utilisateur. Ce sera peut-être moins confortable, mais le passage de messages vaut généralement mieux que l’enfer des interblocages
    • Ce qui est drôle, c’est que des gens ou des équipes dépensent des semaines et beaucoup d’argent pour obtenir de moins bons résultats
    • Je ne connais pas bien cette magie système, mais les données doivent-elles vraiment remonter entièrement jusqu’à la mémoire ? Ou bien le cache évite-t-il cet aller-retour ?

  • Cet article explique comment rendre les pipes Linux plus rapides, mais d’autres méthodes comme la mémoire partagée ou les files de messages peuvent tout de même être plus rapides
    Dans les systèmes qui doivent déplacer rapidement beaucoup de données, les étapes supplémentaires des pipes peuvent ralentir l’ensemble. Quand plusieurs threads partagent des données, les pipes peuvent aussi créer plus de problèmes que d’autres approches. Les améliorations décrites dans l’article peuvent donc ne pas beaucoup aider dans les situations réelles où la vitesse est critique

    • Peux-tu donner un exemple ? Lorsqu’on traite les données par lots, choisir quelque chose comme io_uring présente des avantages
      Mais pour une communication bidirectionnelle, il faut dans tous les cas notifier qu’un côté ou l’autre a des données prêtes. On ne veut pas forcément brûler du CPU en polling, et je ne vois pas très bien comment ces options gèrent cette synchronisation plus vite qu’un pipe
    • L’utilisation d’une bibliothèque de files de messages a aussi l’avantage de moins se soucier des incompatibilités entre plateformes

  • Je connaissais des notions comme les tables de pages, mais les relier à une analyse des performances via perf montre clairement à quel point elles sont centrales pour le débit

  • Les pipes sont formidables. Franchement, que l’autre processus soit sur un autre CPU ou sur une autre machine ne change pas grand-chose
    https://github.com/nathants/s4/blob/master/examples/nyc_taxi...

  • Les pipes sont suffisamment rapides pour combiner de façon répétée cat, sed, awk, cut, grep, uniq, jq, etc.