Wie schnell sind Linux-Pipes? (2022)
(mazzo.li)- Der Durchsatz von Linux-Pipes wird mit
perfund einer Analyse der Kernel-Pfade nachverfolgt; eine einfache Implementierung auf Basis vonwrite/readwird von 3,7 GiB/s schließlich auf 62,5 GiB/s gebracht - Der Ausgangspunkt des Flaschenhalses liegt darin, dass eine Pipe als Ringpuffer mit Referenzen auf 4-KiB-Seiten arbeitet und dabei Kosten für Kopieren, Seitenallokation, Locks sowie Warten und Aufwecken anfallen
vmspliceundsplicereduzieren Kopien zwischen Userspace-Speicher und Kernel-Puffern und erhöhen den Durchsatz auf etwa 12,7 GiB/s bzw. 32,8 GiB/s- Danach fällt vor allem der Aufwand auf, virtuelle Adressbereiche in
struct pageumzuwandeln; mit 2-MiB-Huge-Pages sinkt der Aufwand für Page-Table-Walks und der Durchsatz steigt auf 51,0 GiB/s - Die letzte Optimierung,
SPLICE_F_NONBLOCKzusammen mit einer Busy Loop, erhöht den Durchsatz weiter, belegt aber während des Wartens auf Bereitschaft dauerhaft CPU-Kerne
Ziel des Experiments und Basis-Performance
- Ziel ist es, zu untersuchen, wie Unix-Pipes unter Linux implementiert sind, und ein Testprogramm, das Daten in eine Pipe schreibt und daraus liest, schrittweise zu optimieren
- Die Testumgebung besteht aus einer Intel-Skylake-i7-8550U-CPU und Linux 5.17; da sich die interne Linux-Implementierung laufend ändert, können die Zahlen je nach Umgebung abweichen
- Ausgangspunkt ist ein Programm, das mit den Systemaufrufen
writeundreadwiederholt einen 256-KiB-Puffer durch eine Pipe schiebtwriteschreibt immer denselben 256-KiB-Pufferreadliest insgesamt 10 GiB und gibt den Durchsatz aus- Der Code liegt in
pipes-speed-test
- Ein zum Vergleich herangezogenes, stark optimiertes FizzBuzz-Programm gibt laut
pv-Messung mit etwa 36,2 GiB/s aus- FizzBuzz verwendet 256-KiB-Blöcke, entsprechend der Größe des L2-Caches
- Auch dieses Experiment nutzt 256-KiB-Blöcke, berechnet aber keine Ausgabedaten, sondern soll einen Wert nahe der Obergrenze der Pipe-I/O zeigen
- Das Ergebnis der ersten Implementierung lautet:
./write | ./read- 3,7 GiB/s, 256-KiB-Puffer, 40.960 Wiederholungen, insgesamt 10 GiB übertragen
Warum write und read langsam sind
- Mit
perf record -gundperf reportsieht man, dass etwa 47 % der Zeit auf derwrite-Seite inpipe_writeverbracht werden - Innerhalb von
pipe_writemachencopy_page_from_iterund__alloc_pageseinen großen Anteil aus- Datenkopien
- Seitenallokation
- Scheduling
- Warten und Aufwecken
- Erwerben und Freigeben von Locks
- Eine Linux-Pipe ist ein Ringpuffer, der Seitenreferenzen enthält
pipe_inode_infoenthälthead,tailund einpipe_buffer-Arraypipe_bufferenthältstruct page *page,offsetundlen- Die normale Seitengröße auf x86-64 beträgt 4 KiB
- Die Standardanzahl der Ringpuffer-Slots ist 16; die beispielhafte Pipe mit 8 Slots kann maximal 32 KiB aufnehmen
headbezeichnet das Schreibende,taildas Leseende- Ist die Pipe voll, blockiert
write - Ist die Pipe leer, blockiert
read
- Ist die Pipe voll, blockiert
pipe_writeläuft grob in folgender Reihenfolge ab- Wenn die Pipe bereits voll ist, wird gewartet, bis Platz frei wird
- Wenn im Puffer, auf den
headaktuell zeigt, Platz ist, wird dieser zuerst gefüllt - Wenn es leere Slots und verbleibende Daten gibt, wird eine neue Seite allokiert und gefüllt sowie
headaktualisiert
pipe_readverbraucht umgekehrt Seiten, gibt vollständig gelesene Seiten frei und aktualisierttail- Auf diesem Pfad wird jede Seite zweimal kopiert
- Einmal vom Userspace-Speicher in den Kernel
- Und erneut vom Kernel zurück in den Userspace-Speicher
- Kopiert wird in 4-KiB-Seiteneinheiten, wobei Synchronisation sowie Seitenallokation und -freigabe dazwischenliegen
- Auf derselben Maschine lag sequenzielles RAM-Lesen mit einem einzelnen Thread bei etwa 16 GiB/s; angesichts der Komplexität des Pipe-Pfads ist es nicht überraschend, dass
write/readetwa viermal langsamer sind
Kopien mit vmsplice und splice reduzieren
- Bei schnellem I/O können die Kopierkosten zwischen Userspace-Speicher und Kernel-Puffern zum Flaschenhals werden
- Linux stellt im Zusammenhang mit Pipes Systemaufrufe für kopierfreie Transfers bereit
vmsplicegibt über ein Array vonstruct iovecan, welche Puffer in die Pipe eingefügt werden sollen- Der Rückgabewert ist die Zahl der tatsächlich in die Pipe gelangten Bytes
- Wegen der Größenbeschränkung des Pipe-Ringpuffers passt die angeforderte Gesamtgröße möglicherweise nicht auf einmal hinein
- Da
vmspliceUserspace-Speicher ohne Kopie mit der Pipe verknüpft, muss man darauf achten, den Puffer nicht wiederzuverwenden, bevor die Leseseite diese Daten verbraucht hat - Das FizzBuzz-Programm nutzt dafür Double Buffering
- Der 256-KiB-Puffer wird in zwei 128-KiB-Hälften geteilt
- Die Pipe-Größe wird auf 128 KiB gesetzt, was bei 4-KiB-Seiten 32 Slots ergibt
- Die beiden Pufferhälften werden abwechselnd gefüllt und per
vmsplicein die Pipe eingefügt
- Das Testprogramm schreibt den Pufferinhalt zwar nicht tatsächlich neu, behält aber eine ähnliche Double-Buffering-Struktur bei, wie sie für ein reales Ausgabegenerierungsprogramm nötig wäre
- Wird
writedurchvmspliceersetzt, steigt der Durchsatz auf 12,7 GiB/s- Die Kopiermenge halbiert sich
- Das ist eine Verbesserung um mehr als den Faktor 3 gegenüber
write/read
- Wird auch die Leseseite auf
spliceumgestellt, werden alle Kopien entfernt und der Durchsatz steigt auf 32,8 GiB/s - Allerdings ist bei der Sicherheit von
vmspliceVorsicht geboten- Wenn Seiten erneut gesplice’t werden, kann sich ihre Lebensdauer verlängern
- Ob es auch ohne
SPLICE_F_GIFTunsicher ist, ist nicht eindeutig - Um kopierfreie Zero-Copy-Pipes sicher zu verwenden, ist besondere Vorsicht erforderlich
iov_iter_get_pages und die Kosten der Seitenumwandlung
- Nach Anwendung von
vmspliceundsplicezeigtperf, dass imvmsplice-Pfad viel Zeit anfälltiov_iter_get_pages__mutex_lock.constprop.0add_to_pipe
iov_iter_get_pageswandelt den virtuellen Speicherbereich der anvmspliceübergebenenstruct iovecin eine Liste vonstruct pageum, die die Pipe aufnehmen kann- Prozesse verwenden keine physischen Speicheradressen, sondern virtuelle Adressen
- Die CPU übersetzt virtuelle Adressen über Page Tables in physische Adressen
- Die normale Seitengröße auf x86-64 beträgt 4 KiB
- Die x86-64-Page-Table-Struktur wird als vierstufiger Baum beschrieben, mit 512 Einträgen pro Stufe
- Der
pipe_buffereiner Pipe referenziertstruct pagestruct pageist die zentrale Kernel-Struktur zum Umgang mit physischen Seiten und den zugehörigen Metadaten- Daher muss
vmspliceden virtuellen Eingabespeicherbereich in Referenzen auf physische Seiten umwandeln
- Die Zeit innerhalb von
iov_iter_get_pageswird zum Großteil inget_user_pages_fastverbracht- Bei einem 128-KiB-Puffer und 4-KiB-Seiten müssen insgesamt 32 Seiten geholt werden
- Der Pipe-Code ruft die Funktion implementationsbedingt jeweils mit
nr_pages = 16auf und wiederholt das bei Bedarf, die Gesamtzahl der gesplice’ten Seiten beträgt aber 32
get_user_pages_fastläuft ähnlich wie die CPU softwareseitig durch die Page Tables und sammeltstruct page-Objekte ein- Damit physische Seiten nicht wiederverwendet werden, während der Aufrufer sie nutzt, muss der Referenzzähler von
struct pageerhöht werden- Später muss der Referenzzähler mit
put_pagewieder verringert werden
- Später muss der Referenzzähler mit
- Wenn der Puffer beim Start mit
memsetgefüllt wird, werden die Page-Table-Einträge vorab angelegt, wodurch der langsame Pfad vonget_user_pages_fastvermieden werden kann- Ohne
memsetsinkt der Durchsatz im Beispiel auf 25,0 GiB/s - Bei Verwendung von Huge Pages tritt dieses Phänomen nicht in gleicher Weise auf
- Ohne
Seitenverarbeitungskosten mit Huge Pages senken
- x86-64 unterstützt neben normalen 4-KiB-Seiten auch 2-MiB- und 1-GiB-Huge-Pages
- Die weiteren Experimente behandeln nur 2-MiB-Huge-Pages
- 1-GiB-Seiten sind relativ selten und gelten für diese Aufgabe als überdimensioniert
- Huge Pages stellen denselben Speicherbereich mit weniger Seiten dar und senken so den Verwaltungsaufwand
- Bei der Übersetzung virtueller in physische Adressen entfällt außerdem eine Page-Table-Stufe
- Das kann auch helfen, den Druck auf die TLB der CPU zu reduzieren
- Der unmittelbare Flaschenhals in diesem Experiment ist nicht der Hardware-Page-Table-Walk, sondern der Softwarepfad des Kernels,
get_user_pages_fast - Unter Linux kann man die Verwendung von Huge Pages anfordern, indem man auf 2 MiB ausgerichteten Speicher allokiert und
madvise(..., MADV_HUGEPAGE)aufruft - Mit Huge Pages steigt der Durchsatz auf 51,0 GiB/s
- Der Grund für die Leistungsverbesserung ist nicht, dass
struct pagedirekt auf eine einzelne 2-MiB-Seite zeigt- Kernel-Code geht im Allgemeinen davon aus, dass
struct pageauf die Standardseitengröße der aktuellen Architektur verweist - Eine Huge Page wird durch eine Head-
struct pageund mehrere Tail-struct page-Objekte dargestellt - Eine 2-MiB-Huge-Page kann bei 4-KiB-Basisgröße durch bis zu 512
struct page-Objekte dargestellt werden
- Kernel-Code geht im Allgemeinen davon aus, dass
- Trotzdem lassen sich nach dem Finden des ersten Eintrags die folgenden
struct page-Objekte in einer einfachen Schleife erzeugen, wodurch die Kosten für wiederholte Page-Table-Walks sinken - Seit Linux 5.17 enthält der Kernel
struct folio, das Head Pages explizit identifiziert und damit die Notwendigkeit von Head/Tail-Prüfungen zur Laufzeit reduziert
Synchronisationskosten mit einer Busy Loop reduzieren
- Nach Anwendung von Huge Pages fallen in
perfbesonders Zeiten inwait_for_spaceund__wake_up_common_lockauf- Kosten für das Warten auf beschreibbaren Platz
- Kosten für das Aufwecken der Leseseite
- Um diese Synchronisationskosten zu vermeiden, kann man
SPLICE_F_NONBLOCKfürvmspliceundspliceverwenden- Wenn nicht in die Pipe geschrieben werden kann, wird sofort
EAGAINzurückgegeben - Der Aufrufer läuft in einer Busy Loop, bis die Pipe bereit ist
- Wenn nicht in die Pipe geschrieben werden kann, wird sofort
- Mit Busy Loop steigt der Durchsatz auf 62,5 GiB/s
- Die Kosten sind ebenfalls klar
- Während auf Bereitschaft von
vmspliceodersplicegewartet wird, wird ein CPU-Kern vollständig belegt - Man tauscht also höhere CPU-Nutzung gegen geringere Latenz oder höheren Durchsatz
- Während auf Bereitschaft von
- Am Ende verbessert sich dieser synthetische Benchmark von etwa 3,5 GiB/s auf rund 65 GiB/s
Verbleibende Details und praktische Themen
- Der Optimierungsprozess erfolgte durch gemeinsames Betrachten der
perf-Ausgabe und des Linux-Quellcodes - Die behandelten Themen gehen über Pipes und Splicing selbst hinaus und berühren allgemeinere Themen der Hochleistungsprogrammierung
-
Kopierfreie Operationen
- Ringpuffer
- Paging und virtueller Speicher
- Synchronisations-Overhead
- Im echten Code werden die beiden Puffer getrennt allokiert, um Konflikte auf Page Tables zu reduzieren
get_user_pageserhöht den Referenzzähler von Page-Table-Einträgen,put_pagesenkt ihn- Wenn die beiden Puffer unterschiedliche Page-Table-Einträge nutzen, sinken Konflikte beim Ändern der Referenzzähler
- Der Test wird mit
tasksetausgeführt, um die Prozesse./writeund./readan zwei CPU-Kerne zu binden - Das Repository enthält auch einen synthetischen Benchmark für
get_user_pages_fast - Damit lässt sich der Geschwindigkeitsunterschied mit und ohne Huge Pages messen
- Splicing bleibt ein schwammiges und riskantes Konzept, und die zugehörigen Probleme belasten Kernel-Entwickler weiterhin
-
1 Kommentare
Meinungen auf Hacker News
Wenn ich es richtig verstanden habe, wirkt
vmsplice, wenn man es gleichzeitig an beiden Enden – der Lese- und der Schreibseite – verwendet, eher wie ein kleiner Shared-Memory-Mechanismus zwischen zwei Prozessen.Das heißt, beide Prozesse müssen extrem vorsichtig damit umgehen, wann sie den Puffer lesen und schreiben und wie sie ihn nach der Nutzung zurückgeben. Es ist schnell, aber zugleich eine beängstigende Methode, und es ist auch schade, dass die naive Implementierung, die wohl jeder schreiben würde, 20-mal langsamer ist als die mögliche Performance.
vmspliceein kleiner Shared-Memory-Mechanismus zwischen zwei Prozessen. Es unterstützt nur Zero-Copy vom Userspace-Speicher in die Pipe; in die Gegenrichtung wird kopiert.Details siehe https://mazzo.li/posts/fast-pipes.html#fn10
Ich frage mich, ob es eine Bibliothek zur Datenverarbeitung gibt, die Pipes, Sockets, Dateien und Speicher abstrahiert und dabei auch solche Optimierungen übernimmt.
Ich würde gern wissen, ob es so eine Bibliothek für C, C++, Rust oder andere Systemsprachen gibt. Da ich mit APIs wie
splice()undvmsplice()aus dem Artikel nicht vertraut bin, frage ich mich, ob es beim Bau von Low-Level-Anwendungen eine Bibliothek gibt, die solche Optimierungen automatisch nutzt, wenn das möglich ist. Ich frage mich auch, oblibuv,tokiooderNettydas unter Linux automatisch erledigen; nach einer kurzen Suche sieht es so aus, als könnte das vielleicht der Fall sein.Höherer Code nutzt solche Funktionen nur selten, weil sie ziemlich speziell sind und auf Linux zugeschnitten werden müssen. Wenn man Daten unter Linux nur verschiebt, ohne hineinzuschauen, ist
splicenützlich. Für Anwendungen wie TCP/UDP-Proxys braucht man das definitiv, für einen gewöhnlichen HTTP-Server passt es eher nicht. Wenn man solche Apps baut, begegnet man häufig Stichworten wie zero copy, undspliceist eines der ersten Ergebnisse, auf die man stößt.tokio. Nicht automatisch, aber vielleicht interessant: https://lib.rs/crates/tokio-spliceAußerhalb des Forschungsumfelds scheint es nicht sehr bekannt zu sein, und eine effiziente Cosh-Implementierung zu schreiben, dürfte ziemlich viel Zeit kosten. Kurz gesagt gibt es drei Übertragungsmodi: move, share und copy. Bei einer move-Übertragung etwa übergibt der Sender Daten, für die er Lese-/Schreibrechte hat, vollständig an den Empfänger; das kann durch Remapping des virtuellen Speichers in den Seitentabellen implementiert werden. Außerdem gibt es strong/weak-Eigenschaften, die ausdrücken, ob man darauf vertrauen kann, dass Sender und Empfänger kooperieren, oder ob sie durch Remapping der virtuellen Speicherrechte strikt isoliert werden müssen. Ehrlich gesagt weiß ich nicht, ob sich das zuverlässig so gut optimieren lässt, dass es mit etwas wie einer extrem hochoptimierten Pipe mithalten kann; es könnte auch zu einem „hinreichend cleverer Compiler“-Problem werden. Trotzdem halte ich es für einen Versuch wert.
[1] https://barrelfish.org/publications/trios14-baumann-cosh.pdf
Frühere Diskussion von vor 2022: https://news.ycombinator.com/item?id=31592934
Eine erstaunliche Erkenntnis, auf die ich vor vier Jahren zufällig gestoßen bin: Die Verwendung von Linux-Pipes kann zu nichtdeterministischem Verhalten führen
https://www.gibney.org/the_output_of_linux_pipes_can_be_inde...
echoausgegebenen Daten(echo red; echo green 1>&2) | echo blueerzeugt zwei Subshells, getrennt durch das Zeichen|. Subshells sind Kindprozesse der aktuellen Shell und erben wichtige Eigenschaften wie die Tabelle der offenen Dateideskriptoren. Die beiden Subshells laufen gleichzeitig, und die Eltern-Shell macht lediglichwait(), bis alle Kindprozesse beendet sind. Welches Kind zuerst läuft, ist im Großen und Ganzen nicht vorhersagbar; auf Multicore-Systemen können sie buchstäblich gleichzeitig laufen. Die Standardausgabe der linken Subshell ist mit dem Schreibende der Pipe verbunden, die Standardeingabe der rechten Subshell mit dem Leseende.echo blueliest aber keine Eingabe, sondern gibt nur etwas aus, daher wird aus der Pipe nichts gelesen.echo green >&2schickt die Standardausgabe nicht in die Pipe, sondern dorthin, wohin Standardfehler zeigt. Am Ende schreibenecho greenundecho bluein dieselbe Datei, vermutlich direkt ins Terminal, wodurch eine Race Condition entsteht; die Reihenfolge hängt davon ab, wer zuerst geschedult wirdAndernfalls wären Pipelines nicht nützlich. Wenn man zum Beispiel eine Pipeline hat, die mit
curleine tar-Datei herunterlädt und sie sofort entpackt, würde es Probleme geben, etwa wo die große temporäre tar-Datei gespeichert werden soll, wenn man erst auf das Ende voncurlwartet und danntarstartet.tarmuss während der Ausführung voncurlmitlaufen, damit der Puffer klein bleibt und alles schnell läuft. Der einzige Kontrollfluss zwischen Programmen in einer Pipeline läuft über Standardeingabe und Standardausgabe. Im Beispiel wird auf Standardfehler geschrieben, also ist das selbstverständlich nicht Teil eines deterministischen KontrollflussesNebenbei: Um Verwirrung zu vermeiden: „Indeterministic“ ist ein philosophischer Begriff; der Begriff aus der Informatik lautet „nondeterministic“
0. https://blog.superpat.com/zero-copy-in-linux-with-sendfile-a...
Dieser Befehl sieht wahrscheinlich absichtlich ungewöhnlich aus, und ein Code-Reviewer hätte dabei sicher den Kopf schiefgelegt. Es gibt
echo red, aber es wird nirgendwohin weitergeleitet. Vielleicht ist es auch ein „red herring“-Witz.echo greengeht an Standardfehler und ist daher nur dann vorecho bluezu sehen, wenn es vorher fertig wird. Die genaue Reihenfolge hängt vom Output-Buffering ab, und das wiederum davon, welcher Time Slice zuerst zugewiesen wird; das variiert je nach CPU-Zahl und Last. Es ist also nichtdeterministisch, aber auf dieselbe Weise wietopnichtdeterministisch istKurz gesagt: Wenn man annimmt, dass beide Programme möglichst optimal geschrieben sind, liegt die Maximalgeschwindigkeit einer Pipe nahe an der Geschwindigkeit, mit der ein Kern des Systems lesen und schreiben kann
Im Kern mappt der Kernel dieselben physischen Speicherseiten von der Standardausgabe eines Programms auf die Standardeingabe eines anderen Programms; die Arbeit ist also Zero-Copy oder, in weniger optimalen Fällen, nahe an einer schnellen Einzelkopie. Wenn man das weiß, ist es lohnend und auch witzig, mit Shell-Skripten, die zwei oder mehr Tools per Pipe verbinden, sehr performante Aufgaben zu erledigen. Es ist eines der nützlichsten Werkzeuge im Werkzeugkasten
spliceodervmspliceverwendet. Diese Linux-spezifischen Systemaufrufe sind schwer zu benutzen, besondersvmspliceDie meisten Programme und Shell-Filter verwenden sie nicht, abgesehen von auffälligen Ausnahmen wie
pv, und zahlen daher die Kosten dafür, in Kernel-Speicher zu kopieren und wieder herauszukopierenJe nach Lastprofil lässt sich die Anwendung, die man baut, möglicherweise sauberer mit Pipes+Prozessen oder mit Green-/User-Space-Threads umsetzen. Es kann weniger bequem sein, aber Message Passing ist meistens besser als die Deadlock-Hölle
Dieser Artikel behandelt, wie man Linux-Pipes schneller macht, aber andere Verfahren wie Shared Memory oder Message Queues können weiterhin schneller sein
In Systemen, die große Datenmengen schnell bewegen müssen, können die zusätzlichen Schritte einer Pipe bremsen. Auch wenn mehrere Threads Daten gemeinsam nutzen, können Pipes mehr Probleme verursachen als andere Ansätze. Daher helfen die Verbesserungen aus dem Artikel in realen, geschwindigkeitskritischen Situationen möglicherweise nicht viel
io_uringwähltBei bidirektionaler Kommunikation braucht jedoch beide Seiten eine Benachrichtigung, dass Daten bereitstehen. Vielleicht will man nicht CPU-Zeit mit Polling verbrennen, und ich sehe nicht ganz, wie solche Alternativen diese Synchronisierung schneller als Pipes erledigen
Dinge wie Seitentabellen kannte ich schon, aber sie mit Performance-Analyse über
perfzu verbinden, macht deutlich, wie zentral sie für den Durchsatz sindPipes sind großartig. Ehrlich gesagt ist es ziemlich egal, ob der andere Prozess auf einer anderen CPU oder auf einer anderen Maschine läuft
https://github.com/nathants/s4/blob/master/examples/nyc_taxi...
Pipes sind schnell genug, um
cat,sed,awk,cut,grep,uniq,jqusw. wiederholt miteinander zu kombinieren