Seberapa cepat pipa Linux? (2022)

 (mazzo.li)
1 poin oleh GN⁺ 2023-10-06 | 1 komentar | Bagikan ke WhatsApp
  • Dengan menelusuri throughput pipa Linux menggunakan perf dan analisis jalur kernel, implementasi sederhana berbasis write/read yang awalnya 3.7GiB/s akhirnya ditingkatkan hingga 62.5GiB/s
  • Titik awal bottleneck adalah pipa bekerja sebagai ring buffer yang menyimpan referensi halaman 4KiB, sehingga harus menanggung biaya salin, alokasi halaman, lock, serta tunggu-bangun
  • vmsplice dan splice mengurangi penyalinan antara memori pengguna dan buffer kernel, sehingga throughput naik masing-masing ke sekitar 12.7GiB/s dan 32.8GiB/s
  • Setelah itu, biaya mengubah rentang alamat virtual menjadi struct page menjadi menonjol, dan penggunaan 2MiB huge page mengurangi beban penelusuran page table hingga performa naik ke 51.0GiB/s
  • Optimasi terakhir, SPLICE_F_NONBLOCK dan busy loop, mendorong throughput lebih jauh, tetapi membuat core CPU terus terpakai saat menunggu status siap

Tujuan eksperimen dan performa acuan

  • Tujuannya adalah melihat bagaimana Unix pipe diimplementasikan di Linux, lalu mengoptimalkan program uji yang menulis dan membaca data ke pipe secara bertahap
  • Lingkungan eksperimen menggunakan CPU Intel Skylake i7-8550U dan Linux 5.17; karena implementasi internal Linux terus berubah, angka dapat berbeda tergantung lingkungan
  • Titik awalnya adalah program yang berulang kali mengalirkan buffer 256KiB ke pipe dengan system call write dan read
    • write terus menulis buffer 256KiB yang sama
    • read membaca total 10GiB dan mencetak throughput
    • Kodenya ada di pipes-speed-test
  • Sebagai pembanding, program FizzBuzz yang sangat dioptimalkan menghasilkan sekitar 36.2GiB/s pada pengukuran pv
    • FizzBuzz memakai blok 256KiB, sama dengan ukuran cache L2
    • Eksperimen ini juga memakai blok 256KiB, tetapi tanpa menghitung isi output agar bisa melihat nilai yang mendekati batas atas pipe IO
  • Hasil implementasi pertama adalah sebagai berikut
    • ./write | ./read
    • 3.7GiB/s, buffer 256KiB, 40960 iterasi, total transfer 10GiB

Mengapa write dan read lambat

  • Dari perf record -g dan perf report, sekitar 47% waktu di sisi write dihabiskan di pipe_write
  • Di dalam pipe_write, copy_page_from_iter dan __alloc_pages mengambil porsi besar
    • penyalinan data
    • alokasi halaman
    • penjadwalan
    • tunggu-bangun
    • akuisisi dan pelepasan lock
  • Pipe Linux adalah ring buffer yang menyimpan referensi halaman
    • pipe_inode_info memiliki head, tail, dan array pipe_buffer
    • pipe_buffer memiliki struct page *page, offset, dan len
    • Ukuran halaman normal pada x86-64 adalah 4KiB
    • Jumlah slot ring buffer bawaan adalah 16, dan pipe 8 slot pada contoh bisa menampung maksimum 32KiB
  • head menandai ujung tulis, dan tail menandai ujung baca
    • Jika pipe penuh, write akan terblokir
    • Jika pipe kosong, read akan terblokir
  • pipe_write pada umumnya berjalan dalam urutan berikut
    • Jika pipe sudah penuh, ia menunggu sampai ada ruang
    • Jika masih ada ruang di buffer yang ditunjuk head saat ini, ruang itu diisi lebih dulu
    • Jika ada slot kosong dan data tersisa, halaman baru dialokasikan dan diisi, lalu head diperbarui
  • pipe_read melakukan kebalikannya: mengonsumsi halaman, membebaskan halaman yang sudah selesai dibaca, lalu memperbarui tail
  • Dalam jalur ini, setiap halaman disalin dua kali
    • sekali dari memori pengguna ke kernel
    • sekali lagi dari kernel ke memori pengguna
  • Penyalinan terjadi per halaman 4KiB, bercampur dengan sinkronisasi serta alokasi dan pembebasan halaman
  • Pada mesin yang sama, pembacaan RAM sekuensial single-thread sekitar 16GiB/s, jadi mengingat kompleksitas jalur pipe, tidak mengherankan jika write/read sekitar 4 kali lebih lambat

Mengurangi penyalinan dengan vmsplice dan splice

  • Dalam IO cepat, biaya penyalinan antara memori pengguna dan buffer kernel bisa menjadi bottleneck
  • Linux menyediakan system call terkait pipe untuk perpindahan tanpa salin
    • splice: memindahkan data antara pipe dan file descriptor
    • vmsplice: memindahkan data dari memori pengguna ke pipe
  • vmsplice menentukan buffer yang akan dimasukkan ke pipe melalui array struct iovec
    • Nilai kembalian adalah jumlah byte yang benar-benar masuk ke pipe
    • Karena batas ukuran ring buffer pipe, seluruh ukuran yang diminta mungkin tidak masuk sekaligus
  • vmsplice menghubungkan memori pengguna ke pipe tanpa menyalin, jadi buffer tidak boleh dipakai ulang sebelum sisi pembaca mengonsumsi data tersebut
  • Program FizzBuzz memakai double buffering untuk itu
    • Buffer 256KiB dibagi menjadi dua bagian 128KiB
    • Ukuran pipe diatur ke 128KiB untuk membuat 32 slot berbasis halaman 4KiB
    • Kedua setengah buffer diisi bergantian lalu dimasukkan ke pipe dengan vmsplice
  • Program uji sebenarnya tidak menulis ulang isi buffer, tetapi tetap mempertahankan double buffering agar mirip dengan struktur yang dibutuhkan program pembuat output nyata
  • Saat write diganti dengan vmsplice, throughput meningkat menjadi 12.7GiB/s
    • Jumlah penyalinan berkurang setengah
    • Peningkatan lebih dari 3 kali dibanding write/read
  • Jika sisi baca juga diganti dengan splice, seluruh penyalinan dihapus dan throughput naik ke 32.8GiB/s
  • Namun, keamanan vmsplice perlu diperhatikan
    • Halaman bisa memiliki masa hidup lebih panjang jika di-splice lagi
    • Tidak jelas apakah tetap tidak aman tanpa SPLICE_F_GIFT
    • Perlu kehati-hatian khusus untuk memakai pipe zero-copy secara aman

iov_iter_get_pages dan biaya konversi halaman

  • Setelah menerapkan vmsplice dan splice, perf menunjukkan waktu besar pada jalur vmsplice
    • iov_iter_get_pages
    • __mutex_lock.constprop.0
    • add_to_pipe
  • iov_iter_get_pages mengubah rentang memori virtual dari struct iovec yang diberikan ke vmsplice menjadi daftar struct page yang bisa ditampung pipe
  • Proses menggunakan alamat virtual, bukan alamat memori fisik
    • CPU menerjemahkan alamat virtual ke alamat fisik melalui page table
    • Ukuran halaman normal x86-64 adalah 4KiB
    • Page table x86-64 dijelaskan sebagai struktur pohon 4 tingkat dengan fan-out 512 di tiap tingkat
  • pipe_buffer pada pipe mereferensikan struct page
    • struct page adalah struktur inti yang dipakai kernel untuk menangani metadata terkait halaman fisik
    • Karena itu, vmsplice harus mengubah rentang memori virtual input menjadi referensi halaman fisik
  • Sebagian besar waktu di dalam iov_iter_get_pages dihabiskan di get_user_pages_fast
    • Dengan buffer 128KiB dan halaman 4KiB, total ada 32 halaman yang harus diambil
    • Secara implementasi, kode pipe memanggilnya dengan nr_pages = 16 per kali dan mengulang jika perlu, tetapi total halaman yang di-splice tetap 32
  • get_user_pages_fast mengumpulkan struct page dengan menelusuri page table lewat software, mirip dengan yang dilakukan CPU
  • Pemanggil harus menaikkan reference count struct page agar halaman fisik tidak dipakai ulang selama halaman itu sedang ditulis
    • Setelahnya reference count harus diturunkan lagi dengan put_page
  • Jika buffer diisi lebih dulu dengan memset saat awal, entri page table sudah dibuat sebelumnya sehingga jalur lambat get_user_pages_fast bisa dihindari
    • Tanpa memset, throughput pada contoh turun menjadi 25.0GiB/s
    • Gejala yang sama tidak muncul dengan cara yang sama saat memakai huge page

Menurunkan biaya penanganan halaman dengan huge page

  • Selain halaman normal 4KiB, x86-64 mendukung huge page 2MiB dan 1GiB
    • Eksperimen setelah ini hanya membahas huge page 2MiB
    • Halaman 1GiB relatif jarang dan dianggap berlebihan untuk pekerjaan ini
  • Huge page merepresentasikan rentang memori yang sama dengan jumlah halaman lebih sedikit, sehingga biaya pengelolaan turun
    • Saat menerjemahkan alamat virtual ke fisik, satu tingkat page table juga berkurang
    • Ini juga bisa membantu mengurangi beban TLB CPU
  • Bottleneck langsung pada eksperimen ini bukan page table walk perangkat keras, melainkan jalur software kernel get_user_pages_fast
  • Di Linux, penggunaan huge page bisa diminta dengan mengalokasikan memori yang rata ke 2MiB lalu memanggil madvise(..., MADV_HUGEPAGE)
  • Setelah huge page diterapkan, throughput meningkat menjadi 51.0GiB/s
  • Alasan peningkatan performa bukan karena satu struct page langsung menunjuk seluruh halaman 2MiB
    • Kode kernel pada umumnya mengasumsikan struct page menunjuk ukuran halaman standar arsitektur saat ini
    • Huge page direpresentasikan sebagai head struct page dan beberapa tail struct page
    • Satu huge page 2MiB dapat direpresentasikan oleh hingga 512 struct page berdasarkan ukuran 4KiB
  • Meski begitu, setelah entri pertama ditemukan, struct page berikutnya bisa dibuat lewat loop sederhana, sehingga biaya penelusuran page table berulang berkurang
  • Sejak Linux 5.17, kernel juga memiliki struct folio yang secara eksplisit mengidentifikasi head page, sehingga perbaikan ini mengurangi kebutuhan pengecekan head/tail saat runtime

Mengurangi biaya sinkronisasi dengan busy loop

  • Setelah huge page diterapkan, perf menunjukkan waktu yang menonjol pada wait_for_space dan __wake_up_common_lock
    • biaya menunggu ruang yang bisa ditulis
    • biaya membangunkan sisi pembaca
  • Untuk menghindari biaya sinkronisasi ini, vmsplice dan splice bisa memakai SPLICE_F_NONBLOCK
    • Jika pipe tidak bisa ditulisi, ia langsung mengembalikan EAGAIN
    • Pemanggil lalu melakukan busy loop sampai siap
  • Dengan busy loop, throughput meningkat hingga 62.5GiB/s
  • Namun biayanya juga jelas
    • Saat menunggu vmsplice atau splice siap, core CPU terpakai penuh
    • Ini adalah pertukaran: memakai lebih banyak CPU demi latensi atau throughput
  • Pada akhirnya, benchmark sintetis ini meningkat dari sekitar 3.5GiB/s ke sekitar 65GiB/s

Detail yang tersisa dan topik praktis

  • Proses optimasi dilakukan dengan melihat keluaran perf bersama source code Linux
  • Topik yang dibahas terhubung ke isu pemrograman performa tinggi yang lebih luas daripada sekadar pipe dan splicing

    • Operasi tanpa salin

      • ring buffer
      • paging dan memori virtual
      • overhead sinkronisasi
      • Dalam kode nyata, dua buffer dialokasikan terpisah untuk mengurangi kontensi page table
      • get_user_pages menaikkan reference count entri page table dan put_page menurunkannya
      • Jika dua buffer memakai entri page table yang berbeda, kontensi saat mengubah reference count berkurang
      • Pengujian dijalankan dengan taskset untuk mengikat proses ./write dan ./read ke dua core
      • Repositori juga menyertakan benchmark sintetis untuk get_user_pages_fast
      • Perbedaan kecepatan bisa diukur berdasarkan apakah huge page dipakai atau tidak
      • Splicing tetap menjadi konsep yang ambigu dan berisiko, dan isu terkait terus menjadi beban bagi para pengembang kernel

Bacaan terkait

1 komentar

 
GN⁺ 2023-10-06
Komentar Hacker News

  • Jika saya memahaminya dengan benar, vmsplice tampaknya lebih mirip mekanisme memori bersama kecil di antara dua proses jika digunakan secara bersamaan di kedua ujung, baik sisi pembaca maupun penulis
    Artinya, kedua proses harus sangat berhati-hati soal kapan membaca dan menulis buffer, serta bagaimana mengembalikannya setelah digunakan. Ini cara yang cepat, tetapi sekaligus menakutkan, dan sayangnya implementasi naif yang mungkin ditulis semua orang ternyata 20 kali lebih lambat daripada performa yang sebenarnya mungkin dicapai

    • Kalau mencoba menulis versi yang 20 kali lebih cepat, rekan kerja akan menganggap Anda membuatnya terlalu rumit dan tidak bersikap seperti pemain tim
    • Sepertinya vmsplice bukan mekanisme memori bersama kecil di antara dua proses. Ia hanya mendukung zero-copy dari memori pengguna ke pipe, sedangkan arah sebaliknya tetap terjadi penyalinan
      Untuk detailnya, lihat https://mazzo.li/posts/fast-pipes.html#fn10

  • Saya penasaran apakah ada pustaka pemrosesan data yang mengabstraksikan pipe, socket, file, dan memori sekaligus melakukan optimisasi seperti ini
    Saya ingin tahu apakah ada pustaka semacam itu di C, C++, Rust, atau bahasa sistem lainnya. Karena saya tidak familier dengan API seperti splice() dan vmsplice() yang disebutkan dalam tulisan, saya jadi bertanya-tanya apakah ada pustaka yang secara otomatis memanfaatkan optimisasi seperti ini bila memungkinkan saat membuat aplikasi level rendah. Saya juga penasaran apakah libuv, tokio, dan Netty menanganinya secara otomatis di Linux; dari pencarian singkat, sepertinya mungkin saja begitu

    • Ini mungkin berbeda dari alur umum, tetapi karena tidak portabel, nilainya untuk diabstraksikan tidak terlalu besar. Kemungkinan besar Anda akan mengimplementasikannya sendiri di tiap tempat yang membutuhkan
      Kode level tinggi jarang memakai fitur semacam ini, karena cukup khusus untuk tujuan tertentu dan harus dispesialisasikan untuk Linux. Jika Anda hanya memindahkan data di Linux tanpa melihat isinya, splice berguna. Untuk aplikasi seperti proxy TCP/UDP jelas dibutuhkan, tetapi kurang cocok untuk server HTTP biasa. Jika Anda sedang membuat aplikasi seperti ini, Anda akan sering menjumpai kata kunci seperti zero copy, dan splice adalah salah satu hasil pertama yang akan Anda lihat
    • Ada crate untuk tokio. Tidak otomatis, tetapi mungkin menarik: https://lib.rs/crates/tokio-splice
    • Cosh patut dilihat. Saya sedang membaca makalahnya dan memikirkannya; ini adalah model yang menyediakan abstraksi pengiriman pesan sambil tetap memungkinkan optimisasi
      Tampaknya tidak terlalu dikenal di luar lingkungan riset, dan menulis implementasi Cosh yang efisien kemungkinan akan memakan cukup banyak waktu. Ringkasnya, ada tiga mode transfer: move, share, dan copy. Misalnya, transfer move sepenuhnya menyerahkan data yang sebelumnya dapat dibaca/ditulis oleh pengirim kepada penerima, dan dapat diimplementasikan dengan remapping memori virtual pada page table. Ada juga atribut strong/weak yang menunjukkan apakah pengirim dan penerima dapat dipercaya untuk bekerja sama, atau harus diisolasi secara ketat melalui remapping hak akses memori virtual. Sejujurnya, saya tidak tahu apakah ini bisa dioptimalkan dengan cukup baik hingga secara andal menandingi sesuatu seperti pipe yang dioptimalkan habis-habisan, dan ini bisa saja menjadi masalah “compiler yang cukup pintar”. Meski begitu, menurut saya layak dicoba
      [1] https://barrelfish.org/publications/trios14-baumann-cosh.pdf

  • Diskusi sebelum 2022: https://news.ycombinator.com/item?id=31592934

  • Fakta mengejutkan yang saya ketahui secara kebetulan 4 tahun lalu adalah bahwa penggunaan pipe Linux bisa menimbulkan perilaku nondeterministik
    https://www.gibney.org/the_output_of_linux_pipes_can_be_inde...

    • Ini bukan hal yang mengejutkan. Pipe yang dibuat sama sekali tidak benar-benar meneruskan data yang di-echo
      (echo red; echo green 1>&2) | echo blue membuat dua subshell yang dipisahkan oleh simbol |. Subshell adalah proses anak dari shell saat ini, sehingga mewarisi properti penting seperti tabel file descriptor yang terbuka. Kedua subshell berjalan bersamaan, dan shell induk hanya wait() sampai semua proses anak selesai. Anak mana yang berjalan lebih dulu umumnya tidak bisa diprediksi, dan pada sistem multicore bisa benar-benar berjalan bersamaan. Standard output subshell kiri terhubung ke ujung tulis pipe, sedangkan standard input subshell kanan terhubung ke ujung baca. Namun echo blue tidak membaca input dan hanya menghasilkan output, jadi tidak ada yang dibaca dari pipe. echo green >&2 mengirim standard output ke tempat yang ditunjuk standard error, bukan ke pipe. Pada akhirnya echo green dan echo blue menulis langsung ke file yang sama, kemungkinan terminal, sehingga terjadi race condition, dan urutannya bergantung pada siapa yang dijadwalkan lebih dulu
    • Kalau dipikir sedikit lebih dalam, ini sepenuhnya wajar. Program dalam pipeline berjalan bersamaan
      Kalau tidak begitu, pipeline tidak akan berguna. Misalnya dalam pipeline yang mengunduh file tar dengan curl lalu langsung mengekstraknya, jika harus menunggu curl selesai baru menjalankan tar, akan muncul masalah seperti di mana menyimpan file tar perantara yang besar. tar harus berjalan bersama saat curl berjalan agar buffer tetap kecil dan eksekusi cepat. Satu-satunya alur kontrol di antara program-program pipeline adalah melalui standard input dan standard output. Dalam contoh ini, penulisan dilakukan ke standard error, jadi wajar saja tidak termasuk dalam alur kontrol yang deterministik
    • Kalau Anda menyukai I/O zero-copy yang cepat di Linux, tulisan ini juga layak dibaca
      Tambahan, untuk menghindari kebingungan, “Indeterministic” adalah istilah filsafat, sedangkan istilah ilmu komputer adalah “nondeterministic”
      0. https://blog.superpat.com/zero-copy-in-linux-with-sendfile-a...
    • Apakah itu memang begitu mengejutkan? Sepertinya akan lebih mudah meluruskan kebingungan kalau tahu output apa yang diharapkan dan mengapa berpikir begitu
      Perintah ini mungkin sengaja dibuat terlihat aneh, dan seorang code reviewer pasti akan mengernyit. Ada echo red, tetapi tidak diteruskan ke mana pun. Mungkin juga lelucon “red herring”. echo green pergi ke standard error, jadi hanya terlihat jika selesai sebelum echo blue. Urutan pastinya bergantung pada buffering output, yang bergantung pada time slice mana yang diberikan lebih dulu, dan berubah sesuai jumlah CPU serta beban. Jadi memang nondeterministik, tetapi dengan cara yang sama seperti top bersifat nondeterministik
    • Apakah ada kasus nyata di mana hal seperti ini menyebabkan masalah? Jujur saja, contoh ini terlihat cukup dibuat-buat

  • Ringkasnya, dengan asumsi dua program ditulis seoptimal mungkin, kecepatan maksimum pipe mendekati kecepatan satu core sistem dalam membaca dan menulis
    Pada dasarnya, karena kernel memetakan halaman memori fisik yang sama dari standard output satu program ke standard input program lain, operasi menjadi zero-copy, atau pada situasi yang kurang optimal mendekati satu kali copy yang cepat. Setelah mengetahui hal ini, melakukan pekerjaan berkinerja sangat tinggi dengan skrip shell yang menyambungkan dua atau lebih tool lewat pipe terasa memuaskan sekaligus lucu. Ini salah satu alat paling berguna di toolbox

    • Pipe bersifat zero-copy hanya ketika menggunakan splice atau vmsplice. System call khusus Linux ini sulit digunakan, terutama vmsplice
      Sebagian besar program dan filter shell tidak menggunakannya, kecuali contoh mencolok seperti pv, sehingga tetap membayar biaya menyalin ke memori kernel lalu mengeluarkannya lagi
    • Setahu saya, keterbatasan serius pipe adalah pada x86 Linux ia hanya bisa melakukan buffering 64KB / 16 halaman. Secara umum kemungkinan lebih lambat daripada bandwidth core-ke-memori
    • Jadi ini tidak sepenting yang dipikirkan banyak programmer yang memakai banyak thread
      Aplikasi yang sedang dibuat, tergantung karakteristik bebannya, kemungkinan bisa diimplementasikan lebih rapi dengan pipe+proses atau thread green/user-space. Mungkin kurang nyaman, tetapi message passing biasanya lebih baik daripada neraka deadlock
    • Yang lucu adalah orang atau tim menghabiskan berminggu-minggu dan banyak uang untuk mendapatkan hasil yang lebih buruk
    • Saya tidak begitu paham sihir sistem seperti ini, tetapi apakah data harus benar-benar naik sampai ke memori? Atau cache mencegah perjalanan bolak-balik itu?

  • Tulisan ini membahas cara membuat pipe Linux lebih cepat, tetapi metode lain seperti shared memory atau message queue masih bisa lebih cepat
    Pada sistem yang harus memindahkan banyak data dengan cepat, langkah tambahan pada pipe bisa memperlambat. Saat beberapa thread berbagi data, pipe juga bisa menimbulkan lebih banyak masalah dibanding cara lain. Jadi perbaikan dalam tulisan ini mungkin tidak banyak membantu dalam situasi nyata yang sensitif terhadap kecepatan

    • Bisa beri contoh? Saat memproses data secara batch, memilih sesuatu seperti io_uring memang ada keuntungannya
      Namun dalam komunikasi dua arah, kedua sisi tetap butuh notifikasi bahwa data sudah siap. Anda mungkin tidak ingin membakar CPU dengan polling, dan saya kurang tahu bagaimana opsi seperti itu menangani sinkronisasi tersebut lebih cepat daripada pipe
    • Menggunakan library message queue juga punya keuntungan karena tidak perlu terlalu memikirkan inkompatibilitas lintas platform

  • Saya sudah tahu hal-hal seperti page table, tetapi ketika menghubungkannya dengan analisis performa lewat perf, menjadi jelas betapa sentralnya hal itu bagi throughput

  • Pipe itu hebat. Sejujurnya tidak terlalu penting apakah proses lain berada di CPU lain atau di mesin lain
    https://github.com/nathants/s4/blob/master/examples/nyc_taxi...

  • Pipe cukup cepat untuk berulang kali menggabungkan cat, sed, awk, cut, grep, uniq, jq, dan sebagainya