55 GiB/s FizzBuzz (2021)

 (codegolf.stackexchange.com)
5 puan yazan GN⁺ 2023-07-04 | 1 yorum | WhatsApp'ta paylaş
  • Code Golf Stack Exchange’deki High throughput Fizz Buzz, FizzBuzz çıktısını ne kadar hızlı üretip pipe üzerinden akıtabildiğinizi yarıştıran bir performans deneyi; puanlama <program> | pv > /dev/null aktarım hızına göre yapılıyor
  • Geçerli çıktı için düz ASCII, \n satır sonu, tam olarak doğru Fizz/Buzz/FizzBuzz, en az 2^58’e kadar ya da fiilen sonsuz çıktı gerekiyor; yalnızca pv tarafından görülen null byte hilesi yasak
  • Üst sıralardaki uygulamalar % 3, % 5, printf döngülerini bırakıp 15 satırlık desen açma, sabit genişlikli sayı işleme, büyük buffer’lar, paralelleştirme ve zero-copy çıktı ile darboğazları azaltıyor
  • Gösterilen x86-64+AVX2 assembly cevabı Linux ve AVX2 varsayımıyla vmsplice, L2 cache, huge page ve bir FizzBuzz bytecode yorumlayıcısını birleştirerek yaklaşık 61GiB/s elde ediyor
  • Sonuçlar CPU, pipe buffer, pv sürümü, CPU affinity ve mitigation ayarlarına göre ciddi biçimde değişiyor; soru sahibinin makinesinde en yüksek skorun David Frank’in C++ uygulamasıyla yaklaşık 1.7Tb/s olduğu özetleniyor

FizzBuzz ile zorlanan aktarım hızı sınırları

  • Buradaki asıl mesele FizzBuzz sorusunun kendisi değil; çok basit bir metin üretiminde CPU hesaplaması, bellek kopyalama, pipe I/O ve çekirdek sınırı içinden hangisinin önce darboğaz olduğunu görmek
  • Referans alınan saf C uygulaması % 3, % 5 ve printf kullanıyor; ortalama bir makinede yaklaşık 170MiB/s seviyesine ulaşıyor
  • Soru sahibi aynı makinede 3GiB/s üstü uygulamalar görmüştü ve topluluğun daha yüksek aktarım hızı sınırlarını keşfetmesini istiyordu
  • Puanlama soru sahibinin masaüstünde ölçülüyor
    • AMD 5950x, 16C/32T
    • 64GB 3200MHz RAM
    • CPU mitigations devre dışı
  • Dillere göre tabloda asm 60.8GiB/s, C 20.9GiB/s, Julia 15.5GiB/s, Go 6.8GiB/s, Java 5.8GiB/s, Rust 3.4GiB/s, Ruby 1.7GiB/s, Python 0.5GiB/s gibi sonuçlar yer alıyor
  • ais523’ün x86-64+AVX2 assembly cevabı tek iş parçacığında azami performansı hedefliyor; yazarın makinesinde yaklaşık 31GiB/s, soru sahibinin derlemesinde ise yaklaşık 61GiB/s görülüyor
  • David Frank’in C++ uygulaması, soru metnine göre mevcut en yüksek skor olarak yaklaşık 1.7 Terrabit/s değerine ulaşıyor; ayrıca ayrı bir C++20 uygulamasının AMD Ryzen 9 7700X üzerinde 283GB/s verdiği belirtiliyor

Çıktı kuralları ve benchmark koşulları

  • Geçerli çıktı koşulları oldukça sıkı
    • Çıktı tam olarak doğru FizzBuzz olmalı
    • Her ASCII karakter 1 bayt olmalı
    • Satır sonu olarak yalnızca \n kabul ediliyor
    • \r\n kabul edilmiyor
    • Çıktı en az 2^58 gibi çok büyük bir sayıya kadar sürmeli
  • Benchmark yönteminin kendisi de aktarım hızını etkiliyor
    • pv ve Linux pipe buffer’ının varsayılan olarak 64K buffer kullandığı tartışılıyor
    • CPU sibling core yerleşimine göre üreten program ile tüketen program arasındaki L2 cache yolu değişebiliyor
    • taskset ile CPU yerleşimi zorlanarak karşılaştırma yapılabiliyor

Assembly uygulamasındaki optimizasyon yaklaşımı

  • Assembly uygulamasının özü, hesaplamadan çok çıktı kopyalama maliyetini azaltmak
    • write kullanıldığında kullanıcı alanından çekirdek alanına kopyalama maliyeti yüksek oluyor
    • Yazar, write tabanlı sürüme geçildiğinde performansın beşte bire düştüğünü yazıyor
    • vmsplice ile pipe’ın programın buffer’ına doğrudan başvurması sağlanarak kopyalama azaltılıyor
  • FizzBuzz hesaplaması üç aşamaya ayrılıyor
    • İlk aşama başlangıç dizgelerini sabit olarak içeriyor
    • İkinci aşama 2 ila 5 basamaklı sayıları nispeten doğrudan bir AVX2 rutiniyle işliyor
    • Üçüncü aşama 6 ila 18 basamak aralığını bir FizzBuzz bytecode yorumlayıcısıyla işliyor
  • Üçüncü aşamanın ana döngüsü her 4 clock cycle’da 64 bayt çıktı hedefliyor
    • 1 bayt bytecode, 1 bayt çıktı üretiyor
    • 32 bayt bytecode yüklenip vpshufb, vpsubb gibi talimatlarla 32 bayt çıktı oluşturuluyor
    • Satır numarası, her satırda genel amaçlı sayı dönüşümü yapmadan yaklaşık değerler ve bytecode düzeltmeleriyle ele alınıyor
  • Bu uygulama platforma güçlü biçimde bağımlı
    • Çok eski olmayan bir Linux gerekiyor
    • AVX2 destekleyen bir x86-64 işlemci gerekiyor
    • Standart çıktı pipe değilse başta hata veriyor
    • Araya splice giren pipe düzenlerinde bazı durumlarda hatalı çıktı üretebileceği belirtiliyor

Diğer dil uygulamalarının seçtiği ortak stratejiler

  • C, Go, Java, Rust, Python, Julia, Ruby ve C# uygulamaları da benzer optimizasyon yönelimlerini tekrar ediyor
    • 15 satırlık FizzBuzz deseni açılıyor
    • Sayıyı dizgeye çevirme sayısı azaltılıyor
    • Çıktı büyük buffer’larda biriktirilip yazılıyor
    • Üretim işi thread ya da goroutine ile paralelleştiriliyor
    • Çıktı sırasını korumak için barrier, channel, queue ve mutex kullanılıyor
  • Bu nedenle sonuçları basit bir “dil performansı” karşılaştırması olarak görmek zor
    • pv sürümü, pipe boyutu, vmsplice kullanılabilirliği, CPU affinity, huge page, derleyici optimizasyonu ve memcpy’nin inline edilip edilmemesi aktarım hızını ciddi biçimde değiştiriyor
    • Bazı cevaplarda, belirli bir makinede hızlı olan sonucun başka ortamlarda aynı şekilde yeniden üretilemediğine dair yorumlar bulunuyor

Kapsama dahil edilmeyen bölüm

  • Girdi notunda bazı source chunk’larının uzunluk ve maliyet sınırları nedeniyle atlandığı belirtiliyor; bu yüzden toplam 46 cevabın ve tüm kodların/yorumların eksiksiz kapsanmadığı ifade ediliyor
  • Atlanan kısımlar arasında bazı dillere özel gönderiler, uzun kod gövdeleri, ayrıntılı ince ayar kayıtları ve yorum tartışmaları bulunabiliyor

İlgili okumalar

1 yorum

 
GN⁺ 2023-07-04
Hacker News yorumları

  • En etkileyici nokta, Linux’un bir programdan diğerine pipe edilen veriyi L2 cache içinde tutup ana belleğe hiç dokunmadan aktarabilmesi
    Sıradan Linux çekirdeğinin çeşitli parçalarının birlikte çalışarak böyle hızlı bir yolu mümkün kılması, bence hayranlık uyandıran bir sistem mimarisi tasarımı
    Acaba Mac OSX’in Mach port’larında ya da Windows’un Named Pipes yapısında da böyle bir şey mümkün mü

    • Eğer CPU cache’i fiziksel adres etiketleri kullanıyorsa ve iki sürecin sayfa tabloları aynı fiziksel sayfayı paylaşıyorsa, işletim sistemi bağlam değişiminde cache’i açıkça temizleyip geçersiz kılmadığı sürece CPU, cache içeriğini hangi süreç olursa olsun kullanabilir
    • Yüksek frekanslı alım satım sektörünün büyük kısmının Linux üzerinde çalışmasının nedenlerinden biri de bu

  • “ais523 - high effort answers” kullanıcı adına yakışır biçimde, programı çalıştıramayan birine bile oldukça emek verilmiş bir yorum bırakmış ve şu sonuca varmış
    “Muhtemelen program yanlışlıkla ASLR açıkken derlenmiş. Bu durumda dinamik bağlayıcı BSS segmentinin 4MiB hizalamasına uymuyor ve benim .align direktifimi fiilen yok sayıyor; hatanın nedeni de bu gibi görünüyor”

    • Bu kişi benimle aynı işe başvursa hiç şansım olmadığını anladım. Tam bir ultimate leet coder

  • Bu yazı her yeniden gündeme geldiğinde şu yorumu görüp gülüyorum
    “@chx: Benim zaten bir yüksek lisans tezim var. Bu daha zordu. – ais523 - high effort answers Oct 29, 2021 at 1:17”

  • Rust, Python3 ve C ile optimizasyonsuz basit bir uygulama denemiştim. Sadece basit if/else/while ve standart çıktıya yazdırma kullandım
    Rust -> 23.2MiB/s
    Python3 -> 28.6MiB/s
    C -> 238MiB/s
    Neden Rust performansı Python3 ile benzer aralıkta, bilen var mı? C’ye daha yakın olmasını beklerdim

    • Rust’ın print fonksiyonu varsayılan olarak kilit alır. Bu güvenlik içindir; C böyle yapmaz. Ayrıntılar için Rust dokümanı: https://doc.rust-lang.org/std/macro.print.html
      C’ye benzer performans almak için bu kilidi kendiniz yönetmeniz gerekebilir
      let mut lock = stdout().lock();
      write!(lock, "hello world").unwrap();
      Ayrıca standart çıktının buffer boyutunu da C ile eşleştirmeniz gerekir
    • Yıllar önce yazdığım bir yazı, belki yardımcı olur
      https://ismailmaj.github.io/tinkering-with-fizz-buzz-and-con...
    • C ve Python, standart çıktı için uyarlamalı buffering kullanır. Çıktı hedefi terminal ise her satır sonunda flush eder, değilse yalnızca iç buffer dolunca flush eder
      1ms gecikmeyle sayı sayan bir C programında ikinci sütun, bir önceki read() çağrısından beri geçen süredir
      $ ./out | rtss
      4.7ms 4.7ms | 1
      4.7ms | 2
      4.7ms | 3
      4.7ms | 4
      4.8ms exit status: 0
      Her şeyin tek seferde yazıldığını görebilirsiniz. Bir terminal ayırırsanız satır satır gelir
      $ rtss --pty ./out
      0.8ms 0.8ms | 1
      1.9ms 1.1ms | 2
      3.0ms 1.1ms | 3
      4.1ms 1.1ms | 4
      4.3ms exit status: 0
      Rust’ta çıktıda böyle uyarlamalı bir davranış yok; terminal olup olmamasına bakmaksızın her zaman ikinci sonuçtaki gibi davranıyor
      Teknik olarak standart çıktıyı koşulsuz olarak bir LineWriter ile sarıyor (https://doc.rust-lang.org/std/io/struct.LineWriter.html) ve yazıda satır sonu görürse her seferinde flush ediyor. Aktarım hızını en üst düzeye çıkarmak için BufWriter ile sarıp birden fazla satırı birlikte yazmak gerekir
    • Rust’ı --release, C’yi -O3 ile derlemek gerekir
    • Neredeyse kesin olarak darboğaz çıktı tarafında. Muhtemelen buffering ya da kilitleme sorunu

  • Her şey assembly ile yazılsaydı ne kadar hızlı olurdu diye insan merak ediyor
    ses geliştirmede DSP kodunu assembly ile yazmak çok yaygındır

    • Bunun hızlı olmasının nedeni sadece assembly olması değil. Bu çözüm için gerekli ama asla tek başına yeterli bir koşul değil
      Bunu mümkün kılmak için uç düzey algoritma araştırması, Linux sistem çağrıları hakkında derin bilgi ve platforma özgü optimizasyonların birleşmesi gerekiyor. Yazar Alex Smith’in kendi sözleriyle:
      “@chx: Benim zaten bir yüksek lisans tezim var. Bu daha zordu.”
      Bu, basitçe “assembly ile yaparsın olur” denebilecek bir şeyden tamamen farklı bir düzey
    • Her şey yalnızca Java ile yazılmış olsaydı bile, Python instance’ının içine Chrome koyup JavaScript web sunucusu çalıştırarak belge render eden bugünkü yöntemden daha iyi olurdu
    • Sonunda Steve Yegge’nin Geoworks hikayesi gibi olurdu
      “Tamam. Ben University of Washington’a gittim, sonra Geoworks adlı bir şirkette işe girdim ve 5 yıl assembly dili programlama yaptım. Biz Geoworker’lar tüm işletim sistemini, kütüphaneleri, sürücüleri, uygulamaları, yani masaüstü işletim sisteminin tamamını assembly ile yazdık. 8086 assembly’ydi! Hem de iyi bir assembly bile değildi! Sadece dört register vardı! 386’yı sayarsanız si register’ı da vardı tabii. Berbattı.
      Aslında bayağı seviyorduk. Çünkü nesne yönelimli assembly’ydi. İnsanların kendilerini bir şeyi sevmeye ikna edebilmesi gerçekten şaşırtıcı; bütün bu işin asıl ironisi de bu. Bizim için C++, Roma usulü sefahatin zirvesiydi. Daha fazla yemek için kusmaya gitmek gibiydi. Onlarda IF vardı! Bizde ise jump CX zero vardı! Onlarda ‘object’ler vardı. Bizde de vardı ama onların bunun için sözdizimi vardı. Gerçekten zayıf görünüyorlardı. Ve o zamanlar herhangi bir derleyiciden daha hızlı kod üretebildiğimizi biliyorduk, gerçekten de öyleydi!
      Peki sonra ne oldu? Şirket battı. Neden mi? Muhtemelen bu konuda tüm Geoworker’larla aynı fikirde değilim. Hatta buna gerçekten inanan tek kişinin ben olduğumu da biliyorum. Ama sebep, 15 milyon satır 8086 assembly dili yazmış olmamızdı. Harika araçlarımız vardı, dünya çapında araçlar; bana güvenin. Bunlar kesinlikle gerekli. Ama bir noktadan sonra…
      Sorun şu: Garajın zeminini düz bir çizgide geçmeye çalışan bir karınca hayal edin. Düz gidemez. Biz daha geniş bir görüş alanına sahip olduğumuz için bunu biliyoruz. Karıncanın dolaşıp durduğunu, şu taşa göre yerel optimizasyon yaptığını ve sonra şimdi öbür tarafa yöneldiğini görürsünüz.
      Biz de devasa assembly dili sistemleri yazarken tam olarak bunu yapıyorduk. Sonunda Microsoft, bizimkinden çok daha hızlı bir mobil cihaz platformu çıkardı. Ben de debugger’la girip, ‘Bu ne? Neden böyle? Render gerçekten çok yavaş, takılıyor’ dedim. İçeri girdim ve ekran her yenilendiğinde bir title bar’ın 140 kez render edildiğini gördüm. Sadece title bar da değildi. Her şey defalarca çağrılıyordu.
      Çünkü artık sistemin nasıl çalıştığını göremiyorduk!
      Küçük sistemler sadece optimize etmesi daha kolay olduğu için değil, optimize edilebilir oldukları için de önemlidir. Yani küresel optimizasyon mümkündür.”
      http://steve-yegge.blogspot.com/2008/05/dynamic-languages-st...
    • Assembly, bugün yazılan kaynak koddan o kadar uzaklaştı ki bunu düşünmek bile artık gerçekçi değil. Yine de, yazılım yapan şirketler gerçekten performansa önem verse her şeyin ne kadar hızlanabileceğini hayal etmeye değer
      Bugün web siteleri ve yazılımların yaklaşık %99’unda, uygulama performansına biraz dikkat edilse yalnızca temel değişikliklerle en az %50 hız artışı sağlanabilir gibi görünüyor. Doğru caching, varlık optimizasyonu, şişkin üçüncü taraf kütüphaneleri aynı işi yapan yerleşik native çağrılarla değiştirmek, sunucu ve veritabanını düzgün yapılandırmak gibi şeyler
      Birkaç yıl içinde yapay zekanın depolarda tek tıkla optimizasyon sunup en iyi uygulamaları uygulaması ya da özgün kodu hızlı assembly’ye yeniden yazması da mümkün görünüyor
    • Daha ilkel bir dilin daha hızlı programlar ürettiği argümanında sık kaçırılan ayrıntı şu: Kod yazarken küçücük bir ilerleme kaydetmek bile acı veriyorsa, mümkün olduğunca az şey uygulamak için çok uğraşırsınız
      Kaynak kısıtları odağı berraklaştırabilir

  • Bu deney eğlenceli ve öğretici olsa da biraz kusurlu görünüyor. Karmaşık bir problemin ne kadar hızlı çözüldüğünü değerlendirmekten çok, belleği bir süreçten alıp başka bir sürece aktarmanın verimliliği gibi çevresel bir sorunu test ediyor.
    Bu yüzden ikinci sürecin sürekli konsola ya da dosyaya yazıyor gibi görünmesine rağmen, teknik olarak durum öyle değil. pv >/dev/null çalıştırmak özünde neredeyse hiçbir şey yapmamak gibidir ve write sistem çağrısı da neredeyse anında döner.
    vmsplice, bir sürecin tamponuna/belleğine başka bir sürecin erişmesini sağlayan, paylaşımlı belleğe denk bir işlevdir. İlk yarışma gereksinimlerinin muhtemelen belirsiz olması nedeniyle bunun kurallar açısından uygun olup olmadığı net görünmüyor.

    • İlk gereksinimlerin belirsiz olup olmadığını görmek için yukarı kaydırıp özgün soruya bakabilirsiniz; düzenleme geçmişi de challenge başladıktan sonra değişmediğini gösteriyor.
      “Bir FizzBuzz programı yazın. Çalıştırın. Çıktıyı | pv > /dev/null ile pipe edin. Verim ne kadar yüksekse o kadar iyidir.”
      “Program çıktısı tam olarak geçerli bir fizzbuzz olmalıdır. Geçerli çıktılar arasına null baytları serpiştirmek gibi hileler kabul edilmez. Konsolda görünmeyen ama pv veriminde sayılan null baytlar gibi.”
      Ve vmsplice(2) gerçekten de standart çıktı pipe'ında bir bayt akışı üretir; pv(1) bunu /dev/null'a splice edebilir ya da cat(1) terminale kopyalayabilir.
      vmsplice(2) kullanan tek gönderi de bu değildi. Başka katılımcılar da bunun kesinlikle sihirli bir çözüm olmadığını fark etti. G/Ç engelini aştıktan sonra bile, çıktı sayfalarını mümkün olan en hızlı şekilde üretmek için yapılacak çok iş kalıyor.
    • “Belleği bir süreçten alıp başka bir sürece aktarmanın verimliliği” neredeyse her zaman bütün problem değil mi?
      Kodların çoğu bellek ve G/Ç tarafında darboğaza girer. Karmaşık problemler bile genelde veriyi bir yerden başka bir yere taşıma hızına takılır; veriyi hesaplama hızına takılması daha nadirdir. GPU assembly optimizasyonuyla gün geçiren biri olarak, nadiren hesabın darboğaz olduğu durumlarda bile onu optimize ettikten sonra darboğazın belleğe kaydığını görüyorum.
    • Katılmıyorum. Önce kayda değer ölçüde FizzBuzz'a özgü optimizasyon yapmadan darboğaz “belleği bir süreçten alıp başka bir sürece aktarmanın verimliliği” noktasına ulaşmaz.
      Örneğin, 10'luk tabanda basamak elde taşımalarının doğal biçimde oluşmasını sağlayan akıllı bit gösterimleri var.
      İlk yarışma gereksinimleri de bu noktada pek belirsiz değil. Verimin | pv > /dev/null ile ölçüleceğini açıkça söylüyor ve şunu da ekliyor:
      “Mimariye özel optimizasyonlara / assembly'ye de izin vardır. Bu gerçek bir yarışma değil. Sadece insanların fizz buzz'ı sınırlarına kadar zorlamasını görmek istiyorum; özel bir ortamda/platformda çalışsa bile.”
    • G/Ç kelimenin tam anlamıyla her programın yapmak zorunda olduğu şeydir. Modern donanımda çalışan kodların %99'u bazen burada darboğaza girer. Baytları bir yerden başka bir yere taşımak zorunludur ve görece yavaştır.
      Bellek G/Ç ve dosya G/Ç'sini yüksek performansla ele almayı anlamak, tüm programlar ve programcılar için ilgili bir beceridir.

  • fizzbuzz.S olarak kaydedilmesi söyleniyor ama .S ile .s uzantıları arasındaki farkın ne olduğunu merak ediyorum.

    • Büyük S önce önişlemciyi çalıştırır.
      Man sayfasına göre:
      file.s
      Assembler kodu
      file.S
      file.sx
      Önişleme gerektiren assembler kodu
    • Hatırladığım kadarıyla geleneksel olarak fark, girdinin önişlemciden geçirilip geçirilmediğiydi (.S), geçirilmemesiydi (.s).
      Modern toolchain'lerde hâlâ fark var mı tam bilmiyorum.
    • Benim alışık olduğum kullanımda .S, insanlar tarafından elle yazılan ve genelde git tarafından izlenen assembly dosyaları için kullanılır; .s ise gerekirse üzerine yazılabilecek makine tarafından üretilmiş assembly için kullanılır.
    • GCC vb. .S dosyalarının üzerine yazmaz ama assembly üretmesi istenirse (ör. gcc -S xyz.c) .s dosyasının üzerine yazar.

  • Önceki yazılar:
    https://news.ycombinator.com/item?id=29031488
    https://news.ycombinator.com/item?id=29413656

  • İlk başta bunu 55 GiB/s FritzBox diye okudum. FritzBox, Avrupa'nın Almanca konuşulan bölgelerinde popüler bir router.
    Benim ISP'm de geçen hafta yakında sunulacak 60 GiB/s destekli bir OPNSense kutusunu[1] tweetledi.
    [1] https://twitter.com/init7/status/1674920410889043973

    • Belleği 16 GB'a yükseltilmiş bir DEC750 kullanıyorum. 10GbE destekli, WireGuard'da 2.3GbE yapabilen bir router'ın sessiz olması ve boşta güç tüketiminin kablo modemle benzer şekilde 8W civarında kalması onu harika bir cihaz yaptı; 2030~2035'ten önce değiştirmeyi düşünmüyorum.
      Ayrıca bir USB WiFi adaptörü de takılı; kablo kesilirse belirli VLAN'lar failover yapıyor ve telefon üzerinden iş için kritik bağlantıyı koruyorum.
      Ucuz değil ama OPNSense projesini finansal olarak desteklerken düzgün bir cihaz istiyorsanız Deciso donanımına itiraz etmek zor. Güç verimliliği iyi, dayanıklılık odaklı bileşenler kullanıyor ve sadece çalışıyor.
      Ticari ürün serisinin daha da güçlendiğini görmek güzel.