lsr - un `ls` ultra-rapide basé sur io_uring

• lsr est un nouveau programme de remplacement de ls(1), développé à l’aide de la bibliothèque d’E/S basée sur io_uring, ourio
• Par rapport à ls et aux outils alternatifs existants (eza, lsd, uutils ls), la vitesse d’exécution de la commande est extrêmement élevée, avec plus de 10 fois moins d’appels système
• Toutes les E/S majeures, comme l’ouverture de répertoires, stat et lstat, sont traitées de façon asynchrone et par lots avec io_uring afin de maximiser les performances. Plus il y a de fichiers, plus c’est rapide
• Zig StackFallbackAllocator est utilisé pour minimiser les appels à mmap lors des allocations mémoire
• Construit statiquement sans édition de liens dynamique, il a même un exécutable plus petit que ls classique

---

Présentation et intérêt

• Le projet lsr est un outil rapide de listage de répertoires utilisant io_uring comme alternative à la commande ls classique
• Comparé à ls, eza, lsd et uutils ls, il affiche d’excellentes performances en vitesse d’exécution et en nombre d’appels système
• Il effectue directement autant d’E/S que possible via sa bibliothèque d’E/S développée en interne, ourio
• Les benchmarks montrent que lsr offre des performances et une qualité élevées même dans des environnements contenant un grand nombre de fichiers

Résultats des benchmarks

• Les temps d’exécution de chaque commande ont été mesurés avec hyperfine dans un répertoire contenant n fichiers ordinaires
  • Pour lsr -al, sur des répertoires de 10 à 10 000 fichiers, il enregistre des temps d’exécution nettement plus courts que ls et ses alternatives
  • Exemple : avec 10 000 fichiers, lsr atteint 22.1ms, soit la meilleure performance face à ls (38.0ms), eza (40.2ms), lsd (153.4ms) et uutils ls (89.6ms)
• L’agrégation des appels système a été effectuée avec strace -c
  • lsr -al conserve un nombre d’appels très faible, de 20 au minimum (n=10) à 848 au maximum (n=10 000)
  • ls monte jusqu’à 30 396 appels (n=10 000), lsd jusqu’à 100 512, et les autres alternatives restent elles aussi dans une fourchette de plusieurs milliers à plusieurs centaines de milliers
  • Dans les mêmes conditions, lsr atteint la meilleure efficacité avec au moins 10 fois moins de syscalls

Structure et méthode d’implémentation de lsr

• Le programme fonctionne en trois étapes : analyse des arguments, collecte des données, sortie des données
• Toutes les E/S ont lieu pendant la deuxième étape, celle de la collecte des données, et tous les accès fichiers / récupérations d’informations possibles sont traités avec io_uring
  • L’ouverture du répertoire cible, stat, lstat ainsi que la récupération des informations de temps, d’utilisateur et de groupe sont tous effectués sur une base io_uring
  • Le traitement par lots de stat réduit drastiquement le nombre d’appels système
• Zig StackFallbackAllocator préalloue 1MB de mémoire pour minimiser les appels système supplémentaires comme mmap

Build statique et optimisations

• Comme il s’agit d’un build entièrement statique, sans édition de liens dynamique avec libc, le surcoût à l’exécution est nettement réduit
• Face à GNU ls, la taille du build ReleaseSmall de lsr est plus petite : 138.7KB contre 79.3KB
• En revanche, lsr ne prend pas en charge les locales (langue/région). ls classique supporte plusieurs langues, ce qui entraîne un surcoût

Analyse des appels système et des problèmes de performances

• lsd appelle clock_gettime plus de 5 fois par fichier ; la raison n’est pas claire (mesure interne du temps, etc., supposément)
• Le tri (sorting) représente une part importante du travail total (environ 30 %)
  • uutils ls est efficace en appels système, mais ralentit au niveau du traitement du tri
• L’adoption d’io_uring à elle seule montre un potentiel d’amélioration radicale des performances dans des environnements à fortes E/S, comme les serveurs

Conclusion

• Le temps de développement n’a pas été particulièrement long, et l’effet de l’optimisation des syscalls dépasse les attentes
• lsr est un remplaçant expérimental de ls qui réunit rapidité, faible nombre d’appels système et taille compacte
• Il est particulièrement adapté aux environnements avec de très gros volumes de fichiers ou aux systèmes où les performances d’E/S sont cruciales
• Malgré certaines limites fonctionnelles, comme l’absence de support des locales, il montre des résultats innovants à la fois en pratique et en benchmark

[GN⁺]

Avis Hacker News

• L’auteur du projet se présente et indique qu’un billet de présentation de lsr basé sur io_uring est disponible ici

  • Il partage son expérience sur le projet I18N chez Sun. Pour prendre en charge divers environnements (localisation, utf8, etc.), il faut ajouter de nombreux traitements au programme, ce qui fait ressentir que le coût de production du résultat et la vitesse sont inversement proportionnels. À l’origine, ls(1) d’UNIX était extrêmement rapide grâce à une conception simple, mais il s’est ralenti à mesure que se sont accumulés de petits coûts liés à l’ajout de nombreuses fonctionnalités, au système de fichiers virtuel (VFS), aux différents jeux de caractères, à la prise en charge des couleurs, etc. Il trouve intéressante la discussion sur le coût d’abstraction traité par io_uring
  • Le projet bfs utilise lui aussi io_uring (lien vers le code source). Il serait intéressant de comparer les performances de lsr et de bfs -ls. Pour l’instant, bfs n’utilise io_uring qu’en multithreading, mais cela vaudrait peut-être la peine d’envisager son usage aussi en single thread (bfs -j1)
  • Mesurer le temps avec tim (lien de présentation) semblerait meilleur qu’avec hyperfine. Comme c’est écrit en Nim, cela peut être un défi, mais la ressemblance des noms est amusante, même si elle est fortuite
  • Il envisage de porter un projet C++ vers Zig. Sa bibliothèque maison « libevring » en est encore à ses débuts, donc il reste ouvert à l’idée de la remplacer par ourio si nécessaire. Il pense qu’un support des bindings C/C++ pour un projet basé sur Zig serait utile pour migrer de C/C++ vers Zig
  • Comme ce billet de présentation explique mieux le contexte, il prévoit d’en faire le lien principal et d’ajouter le fil du dépôt au-dessus

• On se demande quelles seraient les performances de lsr sur un serveur NFS, surtout dans un environnement réseau médiocre. Il est évident qu’utiliser des syscalls POSIX bloquants avec un service réseau instable est une faiblesse de conception de NFS. Il serait intéressant d’observer dans quelle mesure io_uring atténue ce problème

  • Les concepteurs de NFS ont implémenté un système distribué qui se comporte de manière très cohérente comme un disque dur. C’était un avantage que les outils existants (ls, etc.) n’aient pas à gérer eux-mêmes les erreurs réseau. À l’origine, le protocole NFS ne conservait pas d’état, ce qui permettait au client de se rétablir automatiquement après un redémarrage du serveur. On se demande si io_uring remonte correctement les erreurs dans ce type de cas. La manière dont les timeouts NFS sont gérés est également un point d’intérêt
  • À la maison, il utilise un $HOME sur NFS depuis plusieurs PC, et tant que le réseau est bon et qu’on évite les cas difficiles comme les écritures parallèles, l’utilisabilité moyenne de NFS est plutôt satisfaisante. En revanche, il a déjà eu des difficultés à cause de déconnexions lorsque le câble réseau était instable
  • Le fait que ctrl+c ne fonctionne pas dans une application lisant un dossier NFS est un inconvénient bien connu. En théorie, l’option de montage intr permettait d’interrompre une opération en cours sur un serveur distant en lui transmettant un signal, mais cette option a été retirée de Linux il y a longtemps déjà (aujourd’hui seule l’option soft existe encore) (réf.1, réf.2 (prise en charge FreeBSD))
  • Samba a un problème similaire

• Il est intéressant de constater que, même avec 35 fois moins d’appels système, l’amélioration de vitesse n’est que d’environ 2x

  • La plupart des syscalls passent par le VDSO, donc leur coût n’est pas très élevé
  • Dans un benchmark sur io_uring lu par le passé, il arrivait que les syscalls basés sur io_uring soient plus lourds que les syscalls classiques. Malgré cela, l’amélioration reste très sensible en pratique. La source exacte ne lui revient pas, mais cela l’a marqué

• Ce projet attire davantage l’attention comme démonstration des gains de vitesse à long terme qu’on pouvait espérer d’io_uring, ou comme tutoriel sur son usage. Par rapport à des outils existants comme eza, il n’y avait pas de motivation intuitive claire expliquant pourquoi il en fallait un nouveau. Si lister dix mille fichiers prend 40 ms contre 20 ms, on a l’impression qu’à l’échelle d’une exécution isolée la différence est imperceptible

  • C’est un projet expérimental créé pour le plaisir d’apprendre à utiliser io_uring. Le gain de temps concret est minime (de l’ordre de 5 secondes économisées sur une vie), et ce n’était pas le point essentiel
  • Dans un répertoire contenant réellement des millions de fichiers JSON, exécuter ls/du peut prendre plusieurs minutes. Les commandes de base de coreutils n’exploitent souvent pas pleinement les performances des SSD modernes

• lsr est bien, mais eza reste supérieur pour la coloration et la prise en charge des icônes. Il utilise personnellement eza --icons=always -1, ce qui fait que les fichiers audio (.opus, etc.) apparaissent automatiquement avec des icônes et des couleurs, alors que dans lsr ils sont affichés comme de simples fichiers. Cela dit, lsr donne clairement l’impression d’être facile à patcher et extrêmement rapide. Il aimerait aussi voir cat et d’autres utilitaires réalisés de cette façon, et trouve intéressante l’utilisation de tangled.sh et d’atproto. Le fait que ce soit écrit en Zig lui paraît aussi plus accessible que Rust pour un débutant

  • bat est un remplaçant moderne de cat (voir bat)
  • Pour la coloration, implémenter une approche standard comme LS_COLORS/dircolors semble être la meilleure solution. GNU ls produit de jolies couleurs

• Il se demandait pourquoi tous les outils CLI n’utilisent pas io_uring. Dans son cas, lorsqu’il connecte un NVMe en USB 3.2 gen2, un outil ordinaire atteint 740 MB/s, alors qu’un outil basé sur aio ou io_uring monte jusqu’à 1005 MB/s. Il pense qu’il y a aussi un effet de stratégie de profondeur de file et de réduction des verrous

  • Pour rester portable, on écrivait traditionnellement sans branches de macros comme #ifdef, ce qui ralentit l’adoption de nouvelles technologies spécifiques à une plateforme ou à une version. Il estime qu’aujourd’hui l’avantage de compatibilité entre diverses plateformes de type POSIX est moins important qu’autrefois
  • Utiliser efficacement io_uring suppose un modèle asynchrone orienté événements. La plupart des outils CLI existants sont écrits de manière intuitive et séquentielle. Si l’async était naturellement disponible au niveau du langage, le portage serait plus simple, mais pour l’instant il faut un gros refactoring. io_uring n’est pas encore totalement stabilisé non plus, donc il pense qu’il est possible d’attendre l’arrivée d’une nouvelle technologie ou d’outils de portage automatique / d’IA
  • io_uring a connu d’importants problèmes de sécurité à ses débuts (il y a environ deux ans). Une bonne partie a été corrigée aujourd’hui, mais cela a nui à son adoption
  • io_uring est très complexe du point de vue de la sécurité
  • io_uring étant une technologie très récente, coreutils (ainsi que les paquets qui le précèdent) s’inscrit dans une tradition vieille de plusieurs décennies, et son adoption prendra encore du temps. Il faudra du temps pour qu’une approche de syscall fondée sur un « shared ring buffer » devienne la norme à la place du modèle synchrone classique

• Avec strace, on observe que lsd appelle clock_gettime environ cinq fois par fichier. La cause exacte n’est pas claire ; c’est peut-être pour calculer, pour chaque horodatage, un affichage du type « il y a x minutes/heures/jours », ou bien à cause d’un héritage de bibliothèque

  • Aujourd’hui, clock_gettime n’est plus un vrai syscall mais passe par le vDSO (voir man 7 vDSO). Il se demande si Zig n’exploite peut-être pas cette architecture

• C’est peut-être un peu hors sujet, mais il serait curieux d’avoir des retours d’expérience ou des chiffres de benchmark concrets sur la réduction, à l’échelle de la microseconde, de la latence des sockets grâce à io_uring par rapport à LD_PRELOAD dans un environnement 10G NIC sur des serveurs très orientés entreprise comme les Mellanox 4 ou 5. Les effets ne semblent pas se cumuler, et s’il y a des retours directs, il aimerait entendre des chiffres

• io_uring ne prend pas en charge getdents, donc son principal avantage se voit sur les stat en masse (par ex. ls -l). Il est un peu regrettable qu’on ne puisse pas rendre le traitement de getdents asynchrone ni le recouvrir avec d’autres opérations

  • Si POSIX standardisait l’opération NFS « readdirplus » (getdents + stat), une partie des avantages propres à io_uring serait probablement neutralisée

• Il trouve amusant qu’il existe des icônes pour les extensions .mjs et .cjs, mais pas pour des extensions comme .c, .h ou .sh