55 GiB/s FizzBuzz (2021)

 (codegolf.stackexchange.com)
5 poin oleh GN⁺ 2023-07-04 | 1 komentar | Bagikan ke WhatsApp
  • High throughput Fizz Buzz di Code Golf Stack Exchange adalah eksperimen performa yang mengadu seberapa cepat keluaran FizzBuzz dapat dihasilkan dan dialirkan melalui pipe, dengan skor diukur berdasarkan throughput <program> | pv > /dev/null
  • Keluaran yang valid harus berupa ASCII sederhana, baris baru \n, Fizz/Buzz/FizzBuzz yang tepat, setidaknya hingga 2^58 atau secara praktis tak terbatas, dan trik null byte yang hanya tertangkap oleh pv dilarang
  • Implementasi papan atas membuang loop % 3, % 5, dan printf, lalu mengurangi bottleneck dengan unroll pola 15 baris, pemrosesan angka lebar tetap, buffer besar, paralelisasi, dan output zero-copy
  • Jawaban assembly x86-64+AVX2 yang ditampilkan mengasumsikan Linux dan AVX2, lalu menggabungkan vmsplice, cache L2, huge page, dan interpreter bytecode FizzBuzz untuk mencatat sekitar 61GiB/s
  • Hasil sangat dipengaruhi oleh CPU, buffer pipe, versi pv, CPU affinity, dan pengaturan mitigasi, sementara skor tertinggi pada mesin penanya dirangkum sebagai implementasi C++ David Frank sekitar 1.7Tb/s

Mendorong batas throughput dengan FizzBuzz

  • Intinya bukan soal masalah FizzBuzz itu sendiri, melainkan memeriksa apakah pada pembuatan teks yang sangat sederhana, bottleneck pertama muncul di komputasi CPU, penyalinan memori, pipe I/O, atau batas kernel
  • Implementasi C naif yang dijadikan acuan memakai % 3, % 5, dan printf, dan pada mesin rata-rata menghasilkan sekitar 170MiB/s
  • Penanya pernah melihat implementasi di mesin yang sama menembus lebih dari 3GiB/s, dan ingin komunitas mengeksplorasi batas throughput yang lebih tinggi
  • Skor diukur pada desktop milik penanya
    • AMD 5950x, 16C/32T
    • RAM 64GB 3200MHz
    • mitigasi CPU dinonaktifkan
  • Tabel per bahasa mencakup 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, dan lainnya
  • Jawaban assembly x86-64+AVX2 oleh ais523 menargetkan performa maksimum single-thread, mencatat sekitar 31GiB/s pada mesin penulis dan sekitar 61GiB/s dalam rekap penanya
  • Implementasi C++ David Frank adalah skor tertinggi saat ini menurut isi pertanyaan, dengan sekitar 1.7 Terrabit/s, dan disebutkan pula implementasi C++20 terpisah yang mencapai 283GB/s pada AMD Ryzen 9 7700X

Aturan keluaran dan kondisi benchmark

  • Syarat keluaran valid cukup ketat
    • Keluaran harus berupa FizzBuzz yang tepat
    • Setiap karakter ASCII harus 1 byte
    • Baris baru hanya boleh \n
    • \r\n tidak diperbolehkan
    • Keluaran harus berlanjut hingga setidaknya 2^58 atau angka yang sangat besar
  • Cara benchmark sendiri juga memengaruhi throughput
    • pv dan buffer pipe Linux dibahas menggunakan buffer 64K secara default
    • Penempatan sibling core CPU dapat mengubah jalur cache L2 antara program penghasil dan program konsumen
    • Perbandingan dapat dipaksakan dengan taskset untuk mengatur penempatan CPU

Cara optimasi implementasi assembly

  • Inti implementasi assembly adalah mengurangi biaya penyalinan output lebih daripada biaya komputasi
    • Menggunakan write menambah biaya penyalinan dari ruang pengguna ke ruang kernel
    • Penulis menyebut performa turun menjadi seperlima bila diubah ke basis write
    • Dengan vmsplice, pipe dibuat mereferensikan buffer program sehingga penyalinan berkurang
  • Perhitungan FizzBuzz dibagi menjadi 3 tahap
    • Tahap pertama meng-hardcode string awal
    • Tahap kedua menangani angka 2 hingga 5 digit dengan rutin AVX2 yang relatif langsung
    • Tahap ketiga menangani rentang 6 hingga 18 digit dengan interpreter bytecode FizzBuzz
  • Loop utama tahap ketiga menargetkan keluaran 64 byte tiap 4 siklus clock
    • 1 byte bytecode menghasilkan 1 byte keluaran
    • Bytecode 32 byte dimuat lalu dengan vpshufb, vpsubb, dan lainnya diubah menjadi 32 byte keluaran
    • Nomor baris ditangani dengan nilai perkiraan dan koreksi bytecode, sehingga tidak melakukan konversi angka umum pada setiap baris
  • Implementasi ini sangat bergantung pada platform
    • Membutuhkan Linux yang cukup baru
    • Membutuhkan prosesor x86-64 yang mendukung AVX2
    • Akan memunculkan error saat startup jika stdout bukan pipe
    • Disebutkan bahwa pada konfigurasi pipe yang melibatkan splice, ada kasus yang bisa menghasilkan keluaran salah

Strategi umum yang dipilih implementasi bahasa lain

  • Implementasi C, Go, Java, Rust, Python, Julia, Ruby, dan C# juga mengulang arah optimasi serupa
    • Melakukan unroll pola FizzBuzz 15 baris
    • Mengurangi jumlah konversi angka ke string
    • Menulis secara terkumpul ke buffer besar
    • Memparalelkan pekerjaan generasi dengan thread atau goroutine
    • Menggunakan barrier, channel, queue, atau mutex untuk menjaga urutan keluaran
  • Hasil ini sulit dipandang sebagai perbandingan sederhana tentang “performa bahasa”
    • Versi pv, ukuran pipe, ketersediaan vmsplice, CPU affinity, huge page, optimasi compiler, dan apakah memcpy di-inline sangat mengubah throughput
    • Beberapa jawaban cepat pada mesin tertentu, tetapi menurut komentar, angka yang sama tidak dapat direproduksi di lingkungan lain

Cakupan yang tidak dibahas

  • Catatan input menyebut sebagian source chunk dihilangkan karena batas panjang dan biaya, sehingga tidak mencakup seluruh 46 jawaban beserta semua kode dan komentar secara lengkap
  • Cakupan yang dihilangkan bisa mencakup sebagian kiriman per bahasa, isi kode yang panjang, log tuning terperinci, dan diskusi komentar

Bacaan terkait

1 komentar

 
GN⁺ 2023-07-04
Komentar Hacker News

  • Hal yang paling mengesankan adalah bahwa Linux bisa menjaga data yang dipipe dari satu program ke program lain tetap hanya berada di cache L2 dan tidak menyentuh memori utama
    Menurut saya, luar biasa bahwa berbagai bagian dari kernel Linux yang biasa bisa saling berpadu sehingga jalur cepat seperti ini menjadi mungkin; ini menunjukkan rancangan arsitektur sistem yang menakjubkan
    Saya jadi penasaran apakah hal seperti ini juga mungkin di Mach ports milik Mac OSX atau Named Pipes di Windows

    • Jika cache CPU memakai tag alamat fisik, dan tabel halaman dari dua proses berbagi halaman fisik yang sama, maka selama sistem operasi tidak secara eksplisit mengosongkan atau membatalkan cache saat pergantian konteks, CPU akan mengizinkan salah satu proses menggunakan isi cache tersebut
    • Ini adalah salah satu dari banyak alasan mengapa seluruh industri high-frequency trading berjalan di Linux

  • Sesuai dengan nama pengguna “ais523 - high effort answers”, dia meninggalkan komentar yang sangat serius bahkan untuk orang yang tidak bisa menjalankan programnya, dan kesimpulannya seperti ini
    “Kemungkinan programnya entah bagaimana dikompilasi dengan ASLR aktif. Dalam kasus ini, dynamic linker tidak menghormati alignment 4MiB dari segmen BSS, sehingga .align saya praktis diabaikan, dan itu tampaknya menjadi penyebab bug tersebut”

    • Saya jadi tahu satu hal: kalau orang ini melamar pekerjaan yang sama dengan saya, saya tidak punya peluang. Dia benar-benar leet coder tingkat akhir

  • Setiap kali tulisan ini muncul lagi, saya tertawa melihat komentar ini
    “@chx: Saya sudah punya tesis master. Ini lebih sulit. – ais523 - high effort answers Oct 29, 2021 at 1:17”

  • Saya mencoba implementasi sederhana tanpa optimasi dalam Rust, Python3, dan C. Hanya memakai if/else/while sederhana dan output ke stdout
    Rust -> 23.2MiB/s
    Python3 -> 28.6MiB/s
    C -> 238MiB/s
    Saya penasaran apakah ada yang tahu kenapa performa Rust ada di kisaran yang mirip dengan Python3. Saya kira akan lebih dekat ke C

    • Fungsi print di Rust secara default mengambil lock. Itu demi keamanan, sedangkan C tidak. Lihat dokumentasi Rust untuk detailnya: https://doc.rust-lang.org/std/macro.print.html
      Untuk mendapatkan performa yang mirip C, kemungkinan besar Anda harus menangani lock ini sendiri
      let mut lock = stdout().lock();
      write!(lock, "hello world").unwrap();
      Dan ukuran buffer stdout juga perlu disamakan dengan C
    • Ini tulisan lama yang saya buat, mungkin membantu
      https://ismailmaj.github.io/tinkering-with-fizz-buzz-and-con...
    • C dan Python memakai buffering adaptif pada stdout. Jika target output adalah terminal, buffer dikosongkan setiap kali ada newline; kalau bukan, buffer internal hanya dikosongkan saat sudah penuh
      Dalam program C yang menghitung angka dengan jeda 1ms, kolom kedua adalah waktu yang berlalu sejak read() sebelumnya
      $ ./out | rtss
      4.7ms 4.7ms | 1
      4.7ms | 2
      4.7ms | 3
      4.7ms | 4
      4.8ms exit status: 0
      Terlihat bahwa semuanya ditulis sekaligus. Jika terminal dialokasikan, hasilnya muncul per baris
      $ 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 tidak punya perilaku adaptif seperti ini untuk output, jadi ia selalu bertindak seperti hasil kedua terlepas dari apakah targetnya terminal atau bukan
      Secara teknis, stdout selalu dibungkus dengan LineWriter(https://doc.rust-lang.org/std/io/struct.LineWriter.html), dan setiap kali melihat penulisan yang mengandung newline, buffer akan langsung dikosongkan. Untuk memaksimalkan throughput, Anda perlu membungkusnya dengan BufWriter agar beberapa baris bisa ditulis sekaligus
    • Rust harus dikompilasi dengan --release, dan C dengan -O3
    • Hampir pasti bottleneck-nya ada pada output. Kemungkinan besar ini soal buffering atau lock

  • Jadi penasaran seberapa cepat jadinya kalau semuanya ditulis dalam assembly
    Dalam pengembangan audio, menulis kode DSP dalam assembly adalah hal yang sangat umum

    • Alasan ini cepat bukan semata-mata karena menggunakan assembly. Itu memang perlu untuk solusi ini, tetapi sama sekali bukan syarat yang cukup
      Ini hanya mungkin dengan gabungan riset algoritme yang ekstrem, pengetahuan mendalam tentang system call Linux, dan optimasi spesifik per platform. Meminjam kata-kata penulisnya sendiri, Alex Smith:
      “@chx: Saya sudah punya tesis master. Ini lebih sulit.”
      Ini benar-benar berada di dimensi yang berbeda dari sekadar “pakai assembly saja”
    • Bahkan kalau semuanya ditulis hanya dengan Java, itu mungkin tetap lebih baik daripada cara sekarang yang menjalankan server web JavaScript di dalam Chrome di dalam sebuah instance Python untuk merender dokumen
    • Pada akhirnya, ini akan jadi seperti kisah Geoworks dari Steve Yegge
      “Baiklah. Saya kuliah di University of Washington lalu bekerja di sebuah perusahaan bernama Geoworks, dan selama 5 tahun saya melakukan pemrograman bahasa assembly. Kami para Geoworker menulis seluruh sistem operasi, library, driver, aplikasi, pokoknya seluruh desktop operating system, dalam assembly. Assembly 8086! Bahkan bukan assembly yang bagus! Hanya ada empat register! Kalau menghitung sampai 386, ada juga register si. Itu mengerikan.
      Sebenarnya kami cukup menyukainya. Itu assembly berorientasi objek. Sungguh menakjubkan bagaimana seseorang bisa meyakinkan dirinya sendiri untuk menyukai sesuatu; itulah ironi sebenarnya dari semua ini. Bagi kami, C++ adalah puncak dekadensi Romawi. Seperti muntah supaya bisa makan lebih banyak. Mereka punya IF! Kami punya jump CX zero! Mereka punya ‘objek’. Kami juga punya, tetapi mereka punya sintaks untuk itu. Terlihat sangat lemah. Dan pada saat itu kami tahu kami bisa membuat kode yang lebih cepat daripada compiler mana pun, dan memang begitu!
      Jadi apa yang terjadi? Perusahaannya bangkrut. Kenapa? Mungkin saya akan berbeda pendapat dengan semua Geoworker. Bahkan saya tahu sayalah satu-satunya yang benar-benar percaya ini. Tetapi alasannya adalah karena kami menulis 15 juta baris bahasa assembly 8086. Kami punya alat yang sangat bagus, alat kelas dunia, percayalah. Itu memang mutlak diperlukan. Tetapi pada suatu titik…
      Masalahnya, bayangkan seekor semut yang mencoba berjalan lurus melintasi jok mobil dan lantai. Ia tidak bisa berjalan lurus. Kita tahu itu karena pandangan kita lebih luas. Kita bisa melihat semut itu berputar-putar, melakukan optimasi lokal terhadap batu ini, lalu kini bergerak ke arah sana.
      Persis itulah yang terjadi ketika kami menulis sistem bahasa assembly yang sangat besar. Pada akhirnya Microsoft merilis platform perangkat mobile yang jauh lebih cepat daripada milik kami. Saya masuk dengan debugger dan berkata, ‘Apa ini? Kenapa begini? Rendering-nya sangat lambat, tersendat-sendat.’ Ketika saya masuk lebih dalam, ternyata setiap kali layar disegarkan, suatu title bar dirender 140 kali. Dan bukan hanya title bar. Segalanya dipanggil berkali-kali.
      Karena kami tak lagi bisa melihat bagaimana sistem itu bekerja!
      Sistem kecil bukan hanya lebih mudah dioptimalkan, tetapi memang bisa dioptimalkan. Maksudnya, optimasi global itu mungkin dilakukan.”
      http://steve-yegge.blogspot.com/2008/05/dynamic-languages-st...
    • Assembly sudah terlalu jauh dari source code yang ditulis saat ini, jadi bahkan memikirkannya pun tidak realistis. Namun tetap menarik membayangkan seberapa cepat semuanya bisa jadi kalau perusahaan pembuat software benar-benar peduli pada kinerja
      Rasanya sekitar 99% website dan software saat ini bisa mencapai peningkatan kecepatan minimal 50% hanya dengan perubahan dasar, asal sedikit saja memperhatikan kinerja aplikasi. Hal-hal seperti caching yang benar, optimasi aset, mengganti library pihak ketiga yang gemuk dengan pemanggilan native bawaan yang melakukan hal yang sama, dan konfigurasi server serta database yang tepat
      Mungkin dalam beberapa tahun, AI akan memberi optimasi satu klik pada repositori untuk menerapkan best practice atau menulis ulang kode asli menjadi assembly yang cepat
    • Detail yang sering terlewat dalam anggapan bahwa bahasa yang lebih primitif menghasilkan program yang lebih cepat adalah bahwa jika membuat sedikit kemajuan saat coding saja sudah menyakitkan, orang akan berusaha keras untuk mengimplementasikan sesedikit mungkin
      Keterbatasan sumber daya dapat memberi kejelasan fokus

  • Eksperimen ini memang menyenangkan dan informatif, tetapi tampaknya agak cacat. Alih-alih menilai seberapa cepat masalah yang kompleks diselesaikan, ini terutama menguji masalah sampingan berupa efisiensi mengambil memori dari satu proses dan menyerahkannya ke proses lain
    Jadi proses kedua itu tampak seperti terus menulis ke konsol atau file, tetapi secara teknis tidak demikian. Menjalankan pv >/dev/null pada dasarnya hampir sama seperti tidak melakukan apa-apa, dan pemanggilan sistem write hampir langsung kembali
    vmsplice adalah fungsi yang setara dengan shared memory yang memungkinkan proses lain mengakses buffer/memori milik satu proses. Kemungkinan besar persyaratan awal kompetisinya ambigu, jadi tidak jelas apakah ini sah menurut aturannya

    • Apakah persyaratan awalnya ambigu bisa dicek dengan menggulir ke atas ke pertanyaan aslinya, dan dari riwayat edit juga bisa dilihat bahwa itu tidak berubah setelah tantangan dimulai
      “Tulislah program FizzBuzz. Jalankan. Pipe output-nya ke | pv > /dev/null. Semakin tinggi throughput, semakin baik.”
      “Output program harus berupa fizzbuzz yang benar-benar valid. Trik seperti menyisipkan null byte di antara output yang valid tidak diperbolehkan. Misalnya null byte yang tidak terlihat di konsol tetapi tetap terhitung dalam throughput pv.”
      Dan vmsplice(2) memang benar-benar membuat aliran byte pada pipe keluaran standar, lalu pv(1) bisa men-splice itu ke /dev/null atau cat(1) bisa menyalinnya ke terminal
      Bukan hanya kiriman ini yang memakai vmsplice(2). Peserta lain juga mengetahui bahwa ini sama sekali bukan solusi ajaib. Bahkan setelah melewati hambatan I/O, masih banyak pekerjaan tersisa untuk menghasilkan halaman output secepat mungkin
    • Kurasa “efisiensi mengambil memori dari satu proses dan menyerahkannya ke proses lain” hampir selalu memang merupakan keseluruhan masalahnya
      Kebanyakan kode mengalami bottleneck pada memori dan I/O. Bahkan masalah yang kompleks pun biasanya terhambat oleh kecepatan memindahkan data dari satu tempat ke tempat lain; jarang sekali terhambat oleh perhitungan datanya. Bahkan sebagai orang yang menghabiskan hari mengoptimalkan assembly GPU, dalam kasus langka ketika komputasi memang menjadi bottleneck, setelah itu dioptimalkan bottleneck-nya berubah menjadi memori
    • Saya tidak setuju. Tanpa terlebih dahulu melakukan optimisasi yang sangat spesifik untuk FizzBuzz, bottleneck-nya tidak akan pernah mencapai “efisiensi mengambil memori dari satu proses dan menyerahkannya ke proses lain”
      Misalnya ada representasi bit yang cerdas agar carry digit desimal terjadi secara alami
      Persyaratan awal kompetisi juga tidak terlalu ambigu pada titik ini. Mereka secara eksplisit mengatakan untuk mengukur throughput dengan | pv > /dev/null, dan juga mengatakan ini:
      “Optimisasi khusus arsitektur / assembly juga diperbolehkan. Ini bukan kompetisi sungguhan. Kami hanya ingin melihat orang-orang mendorong fizz buzz sampai batasnya, bahkan jika itu hanya berjalan pada lingkungan/platform yang sangat khusus.”
    • I/O secara harfiah adalah sesuatu yang harus dilakukan semua program. Pada perangkat keras modern, 99% kode justru mengalami bottleneck di sini. Memindahkan byte dari satu tempat ke tempat lain itu wajib dan relatif lambat
      Memahami cara menangani I/O memori dan I/O file dengan performa baik adalah keterampilan yang relevan bagi semua program dan semua programmer

  • Tertulis harus disimpan sebagai fizzbuzz.S, dan saya jadi penasaran apa bedanya ekstensi .S dan .s

    • Huruf S kapital akan menjalankan preprocessor terlebih dahulu
      Menurut manual page:
      file.s
      Kode assembler
      file.S
      file.sx
      Kode assembler yang memerlukan preprocessing
    • Sepanjang ingatan saya, secara tradisional bedanya adalah apakah input diteruskan ke preprocessor (.S) atau tidak (.s)
      Saya kurang tahu apakah masih ada perbedaan dalam toolchain modern
    • Dalam konvensi yang saya kenal, .S dipakai untuk file assembly yang ditulis manusia, biasanya file yang dilacak di git, sedangkan .s dipakai untuk assembly hasil mesin yang boleh ditimpa bila perlu
    • GCC dan sejenisnya tidak akan menimpa .S, tetapi jika diminta menghasilkan assembly (misalnya gcc -S xyz.c), maka .s akan ditimpa

  • Tulisan sebelumnya:
    https://news.ycombinator.com/item?id=29031488
    https://news.ycombinator.com/item?id=29413656

  • Awalnya saya membacanya sebagai 55 GiB/s FritzBox. FritzBox adalah router yang populer di wilayah Eropa berbahasa Jerman
    ISP saya juga men-tweet minggu lalu tentang box OPNSense dengan dukungan 60 GiB/s yang akan segera tersedia[1]
    [1] https://twitter.com/init7/status/1674920410889043973

    • Saya memakai DEC750 dengan memori ditingkatkan menjadi 16GB. Router dengan dukungan 10GbE dan kemampuan WireGuard 2.3GbE yang hening serta daya idle hanya 8W—kurang lebih setara modem kabel—adalah perangkat yang luar biasa, dan saya tidak berniat menggantinya sebelum 2030~2035
      Saya juga memasang adaptor USB WiFi, jadi jika kabel putus maka VLAN tertentu akan failover, dan saya bisa memakai ponsel untuk menjaga konektivitas penting untuk pekerjaan
      Memang tidak murah, tetapi jika Anda ingin perangkat yang benar sambil mendukung proyek OPNSense secara finansial, perangkat Deciso sulit dibantah. Efisien daya, menggunakan komponen yang berfokus pada daya tahan, dan benar-benar bekerja dengan baik
      Senang melihat lini produk komersialnya menjadi lebih kuat