lsr – ultraschnelles `ls` auf Basis von io_uring

• lsr ist ein neues Ersatzprogramm für ls(1), das mit der io_uring-basierten IO-Bibliothek ourio entwickelt wurde
• Im Vergleich zu bestehendem ls und Alternativen (eza, lsd, uutils ls) ist es bei der Befehlsausführung deutlich schneller und benötigt mehr als 10-mal weniger System Calls
• Zentrale IO-Vorgänge wie Verzeichnisöffnung, stat und lstat werden vollständig asynchron und gebündelt über io_uring verarbeitet, um die Leistung zu maximieren. Je mehr Dateien vorhanden sind, desto größer der Geschwindigkeitsvorteil
• Für die Speicherallokation wird Zigs StackFallbackAllocator genutzt, um mmap-Aufrufe zu minimieren
• Durch einen statischen Build ohne dynamisches Linking ist sogar die Binärgröße kleiner als bei herkömmlichem ls

---

Einführung und Bedeutung

• Das Projekt lsr ist ein schnelles Tool zur Verzeichnisauflistung, das io_uring als Alternative zum normalen ls-Befehl einsetzt
• Im Vergleich zu ls, eza, lsd und uutils ls zeigt es herausragende Werte bei Ausführungsgeschwindigkeit und Anzahl der verwendeten System Calls
• Mit der selbst entwickelten IO-Bibliothek (ourio) wird möglichst viel IO direkt abgewickelt
• Benchmarks zeigen, dass lsr auch in Umgebungen mit sehr vielen Dateien hohe Leistung und Qualität liefert

Benchmark-Ergebnisse

• Mit hyperfine wurde die Ausführungszeit der einzelnen Befehle in Verzeichnissen mit n regulären Dateien gemessen
  • lsr -al erzielte bei 10 bis 10.000 Dateien im Vergleich zu klassischem ls und Alternativen eine deutlich kürzere Laufzeit
  • Beispiel: Bei 10.000 Dateien erreichte lsr 22,1 ms und war damit schneller als klassisches ls (38,0 ms), eza (40,2 ms), lsd (153,4 ms) und uutils ls (89,6 ms)
• Die Erfassung der System Calls erfolgte mit strace -c
  • lsr -al: von mindestens 20 Aufrufen (n=10) bis maximal 848 Aufrufen (n=10.000) und damit durchgehend sehr niedrige Werte
  • ls kam auf bis zu 30.396 Aufrufe (n=10.000), lsd sogar auf 100.512; auch die übrigen Alternativen lagen im Bereich von Tausenden bis Hunderttausenden Aufrufen
  • Unter denselben Bedingungen erreicht lsr mit mindestens 10-mal weniger Syscalls die höchste Effizienz

Architektur und Implementierung von lsr

• Das Programm arbeitet in drei Phasen: Argumente parsen, Daten erfassen, Daten ausgeben
• Sämtliche IO findet in der zweiten Phase, der Datenerfassung, statt; dabei werden möglichst alle Dateizugriffe und Informationsabfragen über io_uring abgewickelt
  • Öffnen des Zielverzeichnisses, stat, lstat sowie die Abfrage von Zeit-, Benutzer- und Gruppeninformationen erfolgen alle auf Basis von io_uring
  • Durch gebündelte stat-Verarbeitung wird die Zahl der System Calls drastisch reduziert
• Mit Zigs StackFallbackAllocator werden 1 MB Speicher vorab reserviert, um zusätzliche System Calls wie mmap zu minimieren

Statischer Build und Optimierung

• Durch einen vollständig statischen Build ohne dynamisches Linking von libc fällt der Ausführungs-Overhead deutlich geringer aus
• Gegenüber GNU ls ist die Größe des ReleaseSmall-Builds von lsr mit 79,3 KB statt 138,7 KB kleiner
• Allerdings unterstützt lsr keine Locale-Einstellungen (Sprache/Region). Normales ls hat durch die Unterstützung vieler Sprachen entsprechenden Overhead

Analyse von System Calls und Leistungsaspekten

• lsd ruft pro Datei mehr als fünfmal clock_gettime auf; der Grund dafür ist unklar, vermutet werden interne Zeitmessungen oder Ähnliches
• Sortierung macht einen erheblichen Teil der Gesamtarbeit aus, etwa 30 %
  • uutils ls ist bei den System Calls effizient, wird aber bei der Sortierung langsamer
• Schon die Einführung von io_uring allein zeigt das Potenzial für bahnbrechende Leistungssteigerungen in IO-intensiven Umgebungen wie Servern

Fazit

• Die Entwicklungszeit war nicht besonders lang, und der Effekt der Syscall-Optimierung übertraf die Erwartungen
• lsr ist ein experimenteller ls-Ersatz, der hohe Geschwindigkeit, wenige System Calls und kompakte Größe gleichzeitig erreicht
• Besonders geeignet ist es für Umgebungen mit großen Dateimengen oder Systeme, in denen leistungsstarke IO entscheidend ist
• Trotz gewisser funktionaler Einschränkungen wie fehlender Locale-Unterstützung zeigt es sowohl in der Praxis als auch in Benchmarks bemerkenswert innovative Ergebnisse

[GN⁺]

Hacker-News-Kommentare

• Offenlegt, dass er der Autor des Projekts ist, und verweist darauf, dass ein Vorstellungsartikel zu dem auf io_uring basierenden lsr hier zu finden ist

  • Teilt Erfahrungen aus der Arbeit am I18N-Projekt bei Sun. Um verschiedene Umgebungen zu unterstützen (Lokalisierung, utf8 usw.), müsse man einem Programm viele zusätzliche Verarbeitungen hinzufügen, sodass Aufwand und Geschwindigkeit für die Ergebniserzeugung in einem umgekehrten Verhältnis stünden. Das ursprüngliche UNIX-ls(1) sei durch sein schlichtes Design sehr schnell gewesen, sei aber durch das Hinzufügen vieler Funktionen sowie VFS, verschiedener Zeichensätze, Farbunterstützung usw. durch die Summe kleiner Kosten langsamer geworden. Er hält das für eine interessante Diskussion über die Kosten von Abstraktion, die io_uring behandelt
  • Das bfs-Projekt verwendet ebenfalls io_uring (Link zum Quellcode). Ein Vergleich der Performance von lsr und bfs -ls wäre interessant. Derzeit nutzt bfs io_uring nur bei Multithreading, aber man könnte überlegen, es auch für einen einzelnen Thread (bfs -j1) zu verwenden
  • Mit tim (Vorstellungslink) zu messen, wäre vermutlich besser als mit hyperfine. Da es in Nim geschrieben ist, könnte das eine Hürde sein, aber dass die Namen sich ähneln, ist für einen Zufall lustig
  • Denkt darüber nach, ein C++-Projekt nach Zig zu portieren. Auch das selbst geschriebene „libevring“ ist noch in einem frühen Stadium, daher ist man offen dafür, es bei Bedarf durch ourio zu ersetzen. Wenn es für Zig-basierte Projekte Unterstützung für C/C++-Bindings gäbe, wäre das beim Umstieg von C/C++ auf Zig nützlich
  • Da der Vorstellungsartikel den Hintergrund besser erkläre, solle dieser der Hauptlink sein, und der Repo-Thread werde oben ergänzt

• Mich würde interessieren, wie sich lsr auf einem NFS-Server verhält, besonders in schlechten Netzwerkumgebungen. Es ist offensichtlich ein Nachteil des NFS-Designs, für instabile Netzwerkdienste blockierende POSIX-Syscalls zu verwenden. Es wäre auch interessant zu beobachten, inwieweit io_uring solche Probleme abmildern kann

  • Die NFS-Designer hätten verteilte Systeme so umgesetzt, dass sie sich sehr konsistent wie Festplatten verhalten. Ein Vorteil war, dass bestehende Werkzeuge (ls usw.) Netzfehler nicht selbst behandeln mussten. Das ursprüngliche NFS-Protokoll war zustandslos, sodass Clients sich nach einem Server-Neustart automatisch erholen konnten. Interessant ist, ob io_uring in solchen Fällen Fehler sauber weitergibt. Auch wie NFS-Timeouts behandelt werden, ist von Interesse
  • Zu Hause wird NFS $HOME auf mehreren PCs verwendet, und solange das Netzwerk gut ist und schwierige Fälle wie paralleles Schreiben vermieden werden, ist die durchschnittliche Nutzbarkeit von NFS ziemlich zufriedenstellend. Als allerdings ein Netzwerkkabel instabil war, gab es wegen Verbindungsabbrüchen unangenehme Erfahrungen
  • Dass ctrl+c in Apps, die gerade einen NFS-Ordner lesen, nicht funktioniert, ist eine bekannte Unannehmlichkeit. Theoretisch unterstützte die Mount-Option intr, Signale an laufende Operationen auf einem entfernten Server zu übergeben und sie damit abbrechbar zu machen, wurde unter Linux aber schon vor langer Zeit entfernt (derzeit bleibt nur die Option soft) (Referenz 1, Referenz 2 (FreeBSD-Unterstützung))
  • Samba hat ein ähnliches Problem

• Es ist interessant, dass die Zahl der Syscall-Aufrufe um das 35-Fache reduziert wurde, die Geschwindigkeitsverbesserung aber nur etwa beim Zweifachen liegt

  • Die meisten Syscalls laufen über VDSO und verursachen daher keine großen Kosten
  • In Benchmarks zu io_uring, die ich früher gelesen habe, kam io_uring-basiertes syscalling teils sogar schwergewichtiger heraus als herkömmliche Syscalls. Trotzdem ist die Verbesserung gefühlt ziemlich deutlich. Ich erinnere mich nicht mehr an die genaue Quelle, aber es ist mir im Gedächtnis geblieben

• Das Projekt ist für mich eher interessant als Beispiel für den Einsatz von io_uring mit erwarteten langfristigen Geschwindigkeitsgewinnen oder als Tutorial zur Verwendung, weniger aus praktischem Nutzen. Im Vergleich zu bestehenden Tools wie eza fehlte mir der intuitive Anreiz, warum man das braucht. Wenn das Auflisten von zehntausend Dateien 40 ms statt 20 ms dauert, würde ich den Unterschied bei einem einzelnen Lauf wohl überhaupt nicht bemerken

  • Es ist ein experimentelles Projekt, das aus Spaß entstanden ist, um den Umgang mit io_uring zu lernen. Der tatsächliche Zeitgewinn ist gering (im Leben vielleicht 5 Sekunden Ersparnis), und das war nicht der Kernpunkt
  • In Verzeichnissen mit tatsächlich Hunderttausenden oder Millionen von JSON-Dateien dauert ls/du mehrere Minuten. Standardbefehle aus coreutils nutzen die Leistung moderner SSDs oft nicht richtig aus

• lsr ist gut, aber bei Farbgebung und Icon-Unterstützung ist eza besser. Ich habe eza --icons=always -1 eingestellt, sodass Musikdateien (.opus usw.) automatisch mit Icons und Farben angezeigt werden, während sie in lsr einfach als normale Dateien erscheinen. Trotzdem merkt man deutlich, dass lsr leicht zu patchen und extrem schnell ist. Außerdem wäre es schön, wenn auch cat und andere Utilities auf diese Weise umgesetzt würden; auch die Nutzung von tangled.sh und atproto finde ich interessant. Da es in zig geschrieben ist, wirkt es auf Einsteiger zugänglicher als rust

  • „bat“ ist ein modernes Ersatztool für cat (direkt zu bat)
  • Für Farbunterstützung wäre es wohl am besten, einen Standardansatz wie LS_COLORS/dircolors zu implementieren. GNU ls sieht farblich gut aus

• Ich habe mich gefragt, warum nicht alle CLI-Tools io_uring verwenden. Wenn ich NVMe über USB 3.2 Gen2 anschließe, erreichen normale Tools bei mir 740MB/s, während aio- oder io_uring-basierte Tools bis auf 1005MB/s kommen. Ich vermute, dass auch Strategien für die Queue-Länge oder weniger Locking eine Rolle spielen

  • Für portable Builds wurde traditionell ohne Makro-Verzweigungen wie #ifdef geschrieben, daher verläuft die Einführung neuer, plattform- oder versionsspezifischer Techniken langsam. Inzwischen halte ich die Vorteile der Kompatibilität zwischen verschiedenen POSIX-artigen Plattformen nicht mehr für so groß wie früher
  • Um io_uring effizient zu nutzen, braucht man ein asynchrones, ereignisbasiertes Modell. Die meisten bestehenden CLI-Tools sind intuitiv und sequenziell geschrieben. Wenn async auf Sprachebene natürlicher wäre, ließen sie sich leichter portieren, aber derzeit wäre dafür ein größerer Refactoring-Aufwand nötig. Auch io_uring ist noch nicht vollständig stabilisiert, daher könnte man auf das nächste neue Konzept warten oder auf automatische Portierungswerkzeuge bzw. KI hoffen
  • In der frühen Einführungsphase hatte io_uring größere Sicherheitsprobleme (vor etwa zwei Jahren). Vieles davon ist inzwischen behoben, aber für die Verbreitung war das schädlich
  • io_uring ist aus Sicherheitssicht sehr schwierig
  • io_uring ist noch eine sehr neue Technik, während coreutils (und vorgelagerte Pakete) auf jahrzehntelanger Tradition beruhen; bis zur Einführung von io_uring wird es also noch dauern. Es braucht Zeit, bis Systemaufrufe nach dem Modell „gemeinsam genutzter Ringpuffer“ anstelle klassischer synchroner Aufrufe zum Standard werden

• Mit strace lässt sich beobachten, dass lsd pro Datei etwa fünfmal clock_gettime aufruft. Die genaue Ursache ist unklar; vielleicht um für jeden Zeitstempel „vor x Minuten/Stunden/Tagen“ zu berechnen, oder es ist ein Vermächtnis der verwendeten Bibliothek

  • Heutzutage ist clock_gettime kein echter Syscall mehr, sondern wird über vDSO abgewickelt (siehe man 7 vDSO). Vielleicht nutzt zig diese Struktur nicht

• Etwas off-topic vielleicht, aber ich würde gern reale Erfahrungswerte oder Benchmark-Zahlen dazu hören, um wie viele Mikrosekunden io_uring im Vergleich zu LD_PRELOAD den Socket-Latenz-Overhead in 10G-NIC-Umgebungen auf Enterprise-Servern wie Mellanox 4 oder 5 tatsächlich senkt. Es wirkt nicht so, als würden sich die Effekte addieren, daher wären konkrete Zahlen aus der Praxis interessant

• io_uring unterstützt getdents nicht, daher zeigen sich die entscheidenden Vorteile bei Bulk-stat (z. B. ls -l). Es ist etwas schade, dass sich getdents nicht asynchronisieren und überlappen lässt

  • Wenn POSIX NFS-readdirplus-Operationen (getdents + stat) standardisieren würde, könnte das einen Teil des speziellen Vorteils von io_uring wieder aufheben

• Es ist interessant, dass es Icons für die Erweiterungen .mjs und .cjs gibt, aber nicht für Dateiendungen wie .c, .h oder .sh