Linux pipe'larının hızı ne kadar yüksek? (2022)

 (mazzo.li)
1 puan yazan GN⁺ 2023-10-06 | 1 yorum | WhatsApp'ta paylaş
  • Linux pipe throughput'unu perf ve çekirdek yol analiziyle izleyerek, basit write/read tabanlı 3.7GiB/s uygulamasını sonunda 62.5GiB/s seviyesine çıkardı
  • Darboğazın başlangıç noktası, pipe'ın 4KiB sayfa referanslarını tutan bir ring buffer olarak çalışırken kopyalama, sayfa ayırma, kilit, bekleme-uyandırma maliyetlerini birlikte ödemesi
  • vmsplice ve splice, kullanıcı belleği ile çekirdek tamponu arasındaki kopyaları azaltarak throughput'u sırasıyla 12.7GiB/s ve 32.8GiB/s seviyelerine yükseltiyor
  • Sonrasında sanal adres aralığını struct page'e dönüştürme maliyeti öne çıkıyor; 2MiB huge page kullanıldığında sayfa tablosu yürüyüşü yükü azalıyor ve hız 51.0GiB/s'ye ulaşıyor
  • Son optimizasyon olan SPLICE_F_NONBLOCK ve busy loop, throughput'u daha da artırıyor; ancak hazır olma durumunu beklerken CPU çekirdeğini sürekli meşgul ediyor

Deneyin amacı ve referans performans

  • Amaç, Linux'ta Unix pipe'larının nasıl uygulandığını incelemek ve pipe'a veri yazıp okuyan test programını adım adım optimize etmek
  • Deney ortamı Intel Skylake i7-8550U CPU ve Linux 5.17; Linux'un iç uygulaması sürekli değiştiği için sayılar ortama göre farklılık gösterebilir
  • Başlangıç noktası, write ve read sistem çağrılarıyla 256KiB tamponu tekrar tekrar pipe'tan geçiren bir program
    • write, aynı 256KiB tamponu sürekli yazar
    • read, toplam 10GiB okur ve throughput'u yazdırır
    • Kod pipes-speed-test içinde yer alıyor
  • Karşılaştırma için alınan, yoğun biçimde optimize edilmiş FizzBuzz programı pv ölçümünde yaklaşık 36.2GiB/s çıktı veriyor
    • FizzBuzz, L2 önbellek boyutuyla aynı olan 256KiB bloklar kullanıyor
    • Bu deney de aynı 256KiB blokları kullanıyor; ancak çıktı içeriğini hesaplamadan, pipe IO üst sınırına yakın bir değer görmek istiyor
  • İlk uygulamanın sonucu şöyle
    • ./write | ./read
    • 3.7GiB/s, 256KiB tampon, 40960 yineleme, toplam 10GiB aktarım

write ve read neden yavaş?

  • perf record -g ve perf report ile bakıldığında write tarafındaki sürenin yaklaşık %47'si pipe_write içinde harcanıyor
  • pipe_write içinde copy_page_from_iter ve __alloc_pages büyük pay alıyor
    • veri kopyalama
    • sayfa ayırma
    • zamanlama
    • bekleme-uyandırma
    • kilit alma-bırakma
  • Linux pipe'ı, sayfa referanslarını tutan bir ring buffer
    • pipe_inode_info, head, tail, pipe_buffer dizisini içerir
    • pipe_buffer, struct page *page, offset, len alanlarını içerir
    • x86-64'te normal sayfa boyutu 4KiB'dir
    • Varsayılan ring buffer yuva sayısı 16'dır; örnekteki 8 yuvalı pipe en fazla 32KiB taşıyabilir
  • head yazma sonunu, tail ise okuma sonunu gösterir
    • pipe dolarsa write bloklanır
    • pipe boşsa read bloklanır
  • pipe_write kabaca şu sırayla ilerler
    • pipe zaten doluysa yer açılana kadar bekler
    • Mevcut head'in gösterdiği tamponda yer varsa önce onu doldurur
    • Boş yuva ve kalan veri varsa yeni sayfa ayırır, doldurur ve head'i günceller
  • pipe_read ise tersine sayfaları tüketir, tamamen okunan sayfaları serbest bırakır ve tail'i günceller
  • Bu yolda her sayfa iki kez kopyalanır
    • kullanıcı belleğinden çekirdeğe bir kez
    • çekirdekten kullanıcı belleğine bir kez daha
  • Kopyalama 4KiB sayfa birimleriyle yapılır; araya eşzamanlama ve sayfa ayırma-serbest bırakma karışır
  • Aynı makinede tek iş parçacıklı sıralı RAM okuması yaklaşık 16GiB/s idi; pipe yolunun karmaşıklığı düşünülünce write/read'in yaklaşık 4 kat daha yavaş olması şaşırtıcı değil

vmsplice ve splice ile kopyalamayı azaltmak

  • Hızlı IO'da, kullanıcı belleği ile çekirdek tamponu arasındaki kopyalama maliyeti darboğaz olabilir
  • Linux, pipe ile ilgili olarak kopyasız taşıma için sistem çağrıları sunar
    • splice: veriyi pipe ile dosya tanıtıcısı arasında taşır
    • vmsplice: veriyi kullanıcı belleğinden pipe'a taşır
  • vmsplice, pipe'a konacak tamponları struct iovec dizisiyle belirtir
    • Dönüş değeri, gerçekten pipe'a giren bayt sayısıdır
    • Pipe ring buffer boyut sınırı nedeniyle istenen toplam boyut tek seferde sığmayabilir
  • vmsplice, kullanıcı belleğini kopyalamadan pipe'a bağladığı için, okuma tarafı veriyi tüketmeden önce tamponun yeniden kullanılmamasına dikkat etmek gerekir
  • FizzBuzz programı bunun için double buffering kullanır
    • 256KiB tamponu iki adet 128KiB yarıya böler
    • Pipe boyutunu 128KiB yaparak 4KiB sayfa bazında 32 yuva oluşturur
    • İki yarım tamponu sırayla doldurur ve vmsplice ile pipe'a verir
  • Test programı gerçekte tampon içeriğini yeniden yazmasa da, gerçek çıktı üreten programlarda gereken yapıya benzer biçimde double buffering'i korur
  • write yerine vmsplice kullanıldığında throughput 12.7GiB/s'ye çıkar
    • kopya miktarı yarıya iner
    • write/read'e göre 3 kattan fazla iyileşme sağlar
  • Okuma tarafı da splice ile değiştirildiğinde tüm kopyalar kaldırılır ve hız 32.8GiB/s'ye ulaşır
  • Ancak vmsplice'ın güvenliği konusunda dikkat gerekir
    • sayfa yeniden splice edilirse ömrü uzayabilir
    • SPLICE_F_GIFT olmadan da güvenli olup olmadığı net değildir
    • kopyasız (zero-copy) pipe'ları güvenli kullanmak için özel dikkat gerekir

iov_iter_get_pages ve sayfa dönüştürme maliyeti

  • vmsplice ve splice uygulandıktan sonra perf, vmsplice yolunda belirgin süre gösteriyor
    • iov_iter_get_pages
    • __mutex_lock.constprop.0
    • add_to_pipe
  • iov_iter_get_pages, vmsplice'a verilen struct iovec içindeki sanal bellek aralığını, pipe'ın taşıyabileceği struct page listesinə dönüştürür
  • Süreçler fiziksel bellek adreslerini değil sanal adresleri kullanır
    • CPU, sanal adresleri sayfa tabloları üzerinden fiziksel adreslere çevirir
    • x86-64'te normal sayfa boyutu 4KiB'dir
    • x86-64 sayfa tablosu, her seviyesi 512 kollu ağaç olan 4 seviyeli bir yapı olarak açıklanır
  • Pipe'ın pipe_buffer yapısı struct page'e referans verir
    • struct page, çekirdeğin fiziksel sayfalarla ilgili metaveriyi yönettiği temel yapıdır
    • Bu nedenle vmsplice, giriş sanal bellek aralığını fiziksel sayfa referanslarına çevirmek zorundadır
  • iov_iter_get_pages içindeki sürenin çoğu get_user_pages_fast içinde harcanır
    • 128KiB tampon ve 4KiB sayfa temelinde toplam 32 sayfa alınmalıdır
    • Pipe kodu uygulama gereği bir seferde nr_pages = 16 ile çağırır ve gerekirse tekrarlar; ancak splice edilen toplam sayfa sayısı 32'dir
  • get_user_pages_fast, CPU'nun yaptığına benzer şekilde sayfa tablosunu yazılımla yürüyerek struct page toplar
  • Çağıran taraf sayfayı kullanırken fiziksel sayfanın yeniden kullanılmaması için struct page referans sayısını artırmak gerekir
    • sonrasında put_page ile referans sayısı düşürülmelidir
  • Başta tamponu memset ile doldurmak, sayfa tablosu girdilerini önceden oluşturarak get_user_pages_fast'in yavaş yolundan kaçınabilir
    • memset yapılmazsa örnekte throughput 25.0GiB/s'ye düşer
    • huge page kullanıldığında aynı etki görülmez

huge page ile sayfa işleme maliyetini azaltmak

  • x86-64, 4KiB normal sayfaların yanında 2MiB ve 1GiB huge page'i destekler
    • Sonraki deneyler yalnızca 2MiB huge page üzerinde duruyor
    • 1GiB sayfalar nispeten nadir ve bu iş için fazla büyük görülüyor
  • huge page, aynı bellek aralığını daha az sayfayla temsil ederek yönetim maliyetini düşürür
    • sanal adresten fiziksel adrese çeviride sayfa tablosu seviyesi de bir azalır
    • CPU'nun TLB yükünü azaltmaya da yardımcı olabilir
  • Bu deneydeki doğrudan darboğaz, donanımın sayfa tablosu yürüyüşü değil; çekirdekteki yazılım yolu get_user_pages_fast
  • Linux'ta 2MiB hizalı bellek ayırıp madvise(..., MADV_HUGEPAGE) çağırarak huge page kullanımı istenebilir
  • huge page uygulandığında throughput 51.0GiB/s'ye çıkar
  • Performans artışının nedeni, struct page'in 2MiB sayfayı tek başına doğrudan göstermesi değildir
    • Çekirdek kodu genel olarak struct page'in mevcut mimarinin standart sayfa boyutunu gösterdiğini varsayar
    • huge page, bir head struct page ve birden çok tail struct page ile temsil edilir
    • 2MiB huge page, 4KiB temelinde en fazla 512 struct page ile temsil edilebilir
  • Yine de ilk giriş bulunduktan sonra ardışık struct page'ler basit bir döngüyle üretilebilir; böylece sayfa tablosunu tekrar tekrar yürütme maliyeti azalır
  • Linux 5.17 sonrası çekirdekte, head page'i açıkça tanımlayan struct folio bulunur; bu da çalışma zamanında head/tail kontrolü ihtiyacını azaltan bir iyileştirmedir

busy loop ile eşzamanlama maliyetini azaltmak

  • huge page sonrasında perf, wait_for_space ve __wake_up_common_lock sürelerinin öne çıktığını gösteriyor
    • yazılabilir alan bekleme maliyeti
    • okuma tarafını uyandırma maliyeti
  • Bu eşzamanlama maliyetinden kaçınmak için vmsplice ve splice ile SPLICE_F_NONBLOCK kullanılabilir
    • Pipe'a yazılamazsa hemen EAGAIN döner
    • Çağıran taraf hazır olana kadar busy loop yapar
  • busy loop uygulandığında throughput 62.5GiB/s'ye kadar çıkar
  • Bunun bedeli de açık
    • vmsplice veya splice hazır olana kadar beklerken CPU çekirdeği tamamen meşgul edilir
    • Daha fazla CPU kullanımı karşılığında gecikme ya da throughput kazanılır
  • Sonuç olarak bu sentetik benchmark yaklaşık 3.5GiB/s seviyesinden yaklaşık 65GiB/s seviyesine kadar iyileştirilmiş olur

Kalan ayrıntılar ve pratik konular

  • Optimizasyon süreci, perf çıktısı ile Linux kaynak koduna birlikte bakılarak yürütüldü
  • Ele alınan konular, pipe ve splicing'in ötesinde daha geniş yüksek performanslı programlama başlıklarıyla bağlantılı

    • kopyasız işlemler

      • ring buffer
      • sayfalama ve sanal bellek
      • eşzamanlama overhead'i
      • Gerçek kodda iki tampon ayrı ayrı ayırılarak sayfa tablosu çekişmesi azaltılır
      • get_user_pages, sayfa tablosu girdilerinin referans sayısını artırır ve put_page bunu azaltır
      • İki tampon farklı sayfa tablosu girdileri kullanırsa referans sayısı güncelleme çekişmesi azalır
      • Test, taskset ile ./write ve ./read süreçleri iki çekirdeğe sabitlenerek çalıştırıldı
      • Depoda, get_user_pages_fast için bir sentetik benchmark da yer alıyor
      • huge page kullanımına göre hız farkı ölçülebilir
      • splicing hâlâ muğlak ve riskli bir kavram olarak kalıyor; ilgili sorunlar çekirdek geliştiricileri için yük olmaya devam ediyor

İlgili okumalar

1 yorum

 
GN⁺ 2023-10-06
Hacker News yorumları

  • Doğru anladıysam, vmsplice okuyan ve yazan uçların ikisi de aynı anda kullandığında iki süreç arasında küçük bir paylaşımlı bellek mekanizmasına daha yakın görünüyor
    Yani her iki sürecin de tamponun ne zaman okunup yazılacağına ve kullanımdan sonra nasıl iade edileceğine son derece dikkat etmesi gerekiyor. Hızlı ama aynı zamanda ürkütücü bir yöntem; herkesin yazabileceği naif uygulamanın mümkün performanstan 20 kat yavaş olması da üzücü

    • 20 kat hızlı sürümü yazmaya kalkarsanız, iş arkadaşlarınız bunu aşırı karmaşıklaştırdığınızı ve takım oyuncusu gibi davranmadığınızı düşünecektir
    • vmspliceın iki süreç arasında küçük bir paylaşımlı bellek mekanizması olduğunu sanmıyorum. Yalnızca kullanıcı belleğinden pipe'a doğru sıfır kopyayı destekliyor; ters yönde kopyalama gerçekleşiyor
      Ayrıntılar için bkz. https://mazzo.li/posts/fast-pipes.html#fn10

  • Pipe, soket, dosya ve belleği soyutlayıp bu tür optimizasyonları da yapan bir veri işleme kütüphanesi olup olmadığını merak ediyorum
    C, C++, Rust ya da başka sistem dillerinde böyle bir kütüphane var mı bilmek isterim. Yazıda geçen splice() ve vmsplice() gibi API'lere aşina olmadığım için, düşük seviyeli uygulamalar geliştirirken mümkün olduğunda bu optimizasyonları otomatik olarak kullanan bir kütüphane var mı diye merak ettim. libuv, tokio, Nettynin Linux'ta bunu otomatik halledip halletmediğini de merak ediyorum; kısa bir aramada belki öyle olabileceği izlenimine kapıldım

    • Genel akışa uymayabilir ama bu taşınabilir olmadığı için soyutlamaya çok değmez. Büyük olasılıkla ihtiyaç duyulan yerlerde doğrudan uygulanacaktır
      Üst seviye kod bu özellikleri nadiren kullanır; çünkü oldukça özel amaçlıdır ve Linux'a göre özelleştirilmesi gerekir. Veriye bakmadan onu Linux üzerinde sadece taşıyorsanız splice kullanışlıdır. TCP/UDP proxy gibi uygulamalarda kesinlikle gereklidir, ama sıradan bir HTTP sunucusuna pek uymaz. Böyle bir uygulama geliştiriyorsanız zero copy gibi anahtar kelimelerle sık karşılaşırsınız ve splice göreceğiniz ilk sonuçlardan biri olur
    • tokio için bir crate var. Otomatik değil ama ilginizi çekebilir: https://lib.rs/crates/tokio-splice
    • Cosha bakmaya değer. Şu anda makalesini okuyup üzerine düşünüyorum; optimizasyona izin verirken mesaj iletimi soyutlaması da sunan bir model
      Araştırma ortamı dışında pek bilinmiyor gibi ve verimli bir Cosh uygulaması yazmak muhtemelen epey zaman alır. Özetle aktarım modları üç tane: move, share, copy. Örneğin move aktarımı, gönderenin okuma/yazma yetkisine sahip olduğu veriyi alıcıya tamamen devreder ve sayfa tablosunda sanal bellek yeniden eşlemesiyle uygulanabilir. Ayrıca gönderen ve alıcının iş birliği yapacağına güvenilip güvenilemeyeceğini ya da sanal bellek izinlerinin yeniden eşlenmesiyle katı biçimde yalıtılmaları gerekip gerekmediğini belirten strong/weak özellikleri de var. Açıkçası, aşırı optimize edilmiş bir pipe gibi şeylerle güvenilir biçimde boy ölçüşecek kadar iyi optimize edilip edilemeyeceğini bilmiyorum; bu, “yeterince akıllı derleyici” problemine de dönüşebilir. Yine de denemeye değer olduğunu düşünüyorum
      [1] https://barrelfish.org/publications/trios14-baumann-cosh.pdf

  • 2022 öncesi tartışma: https://news.ycombinator.com/item?id=31592934

  • 4 yıl önce tesadüfen öğrendiğim şaşırtıcı bir gerçek: Linux pipe kullanmak nondeterministic davranış doğurabiliyor
    https://www.gibney.org/the_output_of_linux_pipes_can_be_inde...

    • Aslında şaşırtıcı değil. Oluşturulan pipe, echo edilen verinin hiçbirini gerçekten aktarmıyor
      (echo red; echo green 1>&2) | echo blue, | işaretinin iki yanında iki subshell oluşturur. Subshell, mevcut shell’in çocuk süreci olduğundan açık dosya tanımlayıcıları tablosu gibi önemli özellikleri miras alır. İki subshell aynı anda çalışır; ebeveyn shell ise yalnızca tüm çocuk süreçlerin bitmesini wait() eder. Hangi çocuğun önce çalışacağı çoğunlukla tahmin edilemez; çok çekirdekli sistemlerde kelimenin tam anlamıyla aynı anda da çalışabilirler. Soldaki subshell’in standart çıktısı pipe’ın yazma ucuna, sağdaki subshell’in standart girdisi okuma ucuna bağlanır. Ama echo blue girdi okumaz, yalnızca çıktı verir; dolayısıyla pipe’tan hiçbir şey okunmaz. echo green >&2, standart çıktıyı pipe’a değil, standart hatanın işaret ettiği yere gönderir. Sonuçta echo green ile echo blue aynı dosyaya, muhtemelen doğrudan terminale yazar ve bir yarış durumu oluşur; sıra, hangisinin önce zamanlandığına göre değişir
    • Biraz daha derin düşününce tamamen doğal. Pipeline’daki programlar eşzamanlı çalışır
      Aksi halde pipeline kullanışlı olmazdı. Örneğin curl ile bir tar dosyasını indirip hemen açan bir pipeline’da, curl bitene kadar bekleyip sonra tar çalıştırılsa büyük ara tar dosyasının nereye kaydedileceği gibi sorunlar çıkar. tar, curl çalışırken onunla birlikte çalışmalı ki tampon küçük kalsın ve işlem hızlı yürüsün. Pipeline programları arasındaki tek denetim akışı standart girdi ve standart çıktı üzerinden olur. Örnekte standart hataya yazıldığı için bunun belirleyici denetim akışına dahil olmaması doğal
    • Linux’ta hızlı sıfır kopya G/Ç seviyorsanız bu yazı da görülmeye değer
      Ek olarak, karışıklığı önlemek için: “Indeterministic” bir felsefe terimi, bilgisayar bilimi terimi ise “nondeterministic”tir
      0. https://blog.superpat.com/zero-copy-in-linux-with-sendfile-a...
    • Bu gerçekten o kadar şaşırtıcı mı? Hangi çıktının beklendiğini ve neden öyle düşünüldüğünü bilsek kafa karışıklığını gidermek daha kolay olurdu
      Bu komut muhtemelen bilerek tuhaf yazılmış; bir kod gözden geçireni kesinlikle durup düşünürdü. echo red var ama hiçbir yere aktarılmıyor. “red herring” şakası da olabilir. echo green standart hataya gittiği için ancak echo bluedan önce biterse görünür. Kesin sıra çıktı tamponlamasına bağlıdır; bu da hangi zaman diliminin önce verildiğine göre değişir ve CPU sayısı ile yüke bağlıdır. Yani nondeterministic, ama topun nondeterministic olmasıyla aynı şekilde
    • Bunun gerçek sorunlara yol açtığı durumlar var mı? Açıkçası bu örnek epey yapay görünüyor

  • Özetle, iki programın mümkün olduğunca en iyi şekilde yazıldığını varsayarsak pipe’ın azami hızı, sistemdeki tek bir çekirdeğin okuyup yazabildiği hıza yakındır
    Esasen çekirdek, bir programın standart çıktısından diğer programın standart girdisine aynı fiziksel bellek sayfasını eşlediği için işlem sıfır kopya olur; ya da daha az ideal durumlarda hızlı tek kopyaya yakınsar. Bunu öğrendikten sonra, iki veya daha fazla aracı pipe ile bağlayan shell script’leriyle çok yüksek performanslı işler yapmak hem tatmin edici hem de biraz komik geliyor. Araç kutusundaki en kullanışlı araçlardan biri

    • Pipe’ın sıfır kopya olması yalnızca splice veya vmsplice kullanıldığında geçerlidir. Bu Linux’a özgü sistem çağrılarını kullanmak zordur; özellikle vmsplice böyledir
      Programların ve shell filtrelerinin büyük çoğunluğu, pv gibi göze çarpan istisnalar dışında bunları kullanmaz; bu yüzden veriyi çekirdek belleğine kopyalayıp sonra tekrar dışarı alma maliyetini öder
    • Pipe’ın ciddi bir sınırı, x86 Linux’ta bildiğim kadarıyla yalnızca 64KB / 16 sayfa tamponlayabilmesidir. Genellikle çekirdek-bellek bant genişliğinden daha yavaş olması muhtemeldir
    • Bu yüzden çok thread kullanan programcıların düşündüğü kadar önemli değil
      Geliştirmekte olduğunuz uygulama, yük karakteristiğine bağlı olarak pipe+süreçler ya da green/kullanıcı alanı thread’leriyle daha temiz uygulanabilir. Daha az konforlu olabilir ama mesaj iletimi çoğu zaman deadlock cehenneminden iyidir
    • Komik olan, insanların veya ekiplerin daha kötü sonuçlar almak için haftalar ve büyük paralar harcaması
    • Bu tür sistem sihirlerini pek bilmiyorum; verinin tamamen belleğe kadar çıkması mı gerekiyor? Yoksa cache bu gidiş dönüşü engelliyor mu?

  • Bu yazı Linux pipe’larını hızlandırma yöntemlerini ele alıyor, ancak paylaşımlı bellek veya mesaj kuyrukları gibi başka yöntemler hâlâ daha hızlı olabilir
    Çok miktarda veriyi hızlı taşımak gereken sistemlerde pipe’ın ek adımları hızı düşürebilir. Birden çok thread veri paylaştığında da pipe başka yöntemlere göre daha fazla sorun çıkarabilir. Bu yüzden yazıdaki iyileştirmeler, hızın önemli olduğu gerçek durumlarda çok yardımcı olmayabilir

    • Örnek verebilir misin? Veriyi toplu işlediğinde io_uring gibi bir şeyi seçmenin avantajı olur
      Ama çift yönlü iletişimde iki taraftan hangisi olursa olsun verinin hazır olduğuna dair bir bildirim gerekir. CPU yakarak polling yapmak istemeyebilirsin; bu seçeneklerin söz konusu senkronizasyonu pipe’dan nasıl daha hızlı yaptığı da bana pek açık değil
    • Mesaj kuyruğu kütüphanesi kullanmanın bir avantajı da birden çok platform arasındaki uyumsuzluklarla daha az uğraşmaktır

  • Sayfa tabloları gibi şeyleri biliyordum, ama bunu perf üzerinden performans analizi ile ilişkilendirince throughput açısından ne kadar merkezi olduğu netleşti

  • Pipe’lar harika. Diğer sürecin başka bir CPU’da mı yoksa başka bir makinede mi olduğu açıkçası pek fark etmiyor
    https://github.com/nathants/s4/blob/master/examples/nyc_taxi...

  • Pipe’lar cat, sed, awk, cut, grep, uniq, jq vb. araçları tekrar tekrar birleştirmek için yeterince hızlıdır