Tantangan 1 Miliar Baris

 (morling.dev)
2 poin oleh GN⁺ 2024-01-05 | 2 komentar | Bagikan ke WhatsApp
  • One Billion Row Challenge (1BRC), yang berlangsung sepanjang Januari 2024, adalah tantangan performa untuk memproses file teks berisi 1 miliar baris dan menguji seberapa cepat Java bisa berjalan
  • Input berupa teks sederhana dalam format station;temperature, tetapi program harus menghitung suhu minimum, rata-rata, dan maksimum per stasiun pengamatan serta mencetaknya secara akurat berdasarkan urutan nama
  • Implementasi hanya boleh menggunakan Java; distribusi SDKMan dan build Early Access dari openjdk.net boleh digunakan, tetapi dependensi eksternal dilarang
  • Peserta mengirimkan solusi melalui pull request ke repositori 1brc di GitHub, dan dapat membandingkan format jawaban serta performa dengan implementasi dasar yang disediakan
  • Penilaian dilakukan di lingkungan Hetzner Cloud CCX33 yang sama, dijalankan 5 kali, lalu peringkat leaderboard ditentukan berdasarkan rata-rata 3 kali eksekusi setelah catatan tercepat dan terlambat dikeluarkan

Tugas Java untuk Mengagregasi 1 Miliar Baris Secepat Mungkin

  • One Billion Row Challenge adalah tantangan performa Java yang berlangsung dari 1 Januari hingga 31 Januari 2024
  • Peserta menulis program Java yang membaca pengukuran suhu dari file teks dan menghitung suhu minimum, rata-rata, dan maksimum untuk setiap stasiun cuaca
  • Inti tingkat kesulitannya adalah ukuran file input yang mencapai 1.000.000.000 baris
  • Input memiliki struktur sederhana, dengan satu nilai pengukuran di setiap baris
    • Contoh: Hamburg;12.0
    • Contoh: Bulawayo;8.9
    • Contoh: Palembang;38.8
  • Output harus mengurutkan nama stasiun pengamatan secara alfabetis dan menampilkan nilai min/mean/max untuk masing-masing stasiun
    • Contoh: {Abha=5.0/18.0/27.4, Abidjan=15.7/26.0/34.1, ...}

Aturan Pengiriman dan Lingkungan Eksekusi

  • Tujuannya adalah membuat implementasi Java tercepat yang melakukan tugas yang sama
  • Optimisasi dapat memanfaatkan virtual thread, Vector API dan SIMD, optimisasi GC, kompilasi AOT, dan sebagainya
  • Aturan dasarnya adalah sebagai berikut
    • Kiriman harus ditulis dalam Java
    • Distribusi Java yang tersedia di SDKMan dan build Early Access dari openjdk.net boleh digunakan
    • Build EA dari proyek OpenJDK seperti Valhalla juga diizinkan
    • Dependensi eksternal tidak boleh digunakan
  • Peserta melakukan clone repositori 1brc dan mengirimkan implementasinya sesuai instruksi README
  • Implementasi dasar disediakan sebagai acuan pembanding dan untuk memeriksa format jawaban yang benar
  • Pengiriman dilakukan dengan membuka pull request ke repositori upstream

Metode Perhitungan Leaderboard dan Berbagi di Komunitas

  • Evaluasi dilakukan pada instans Hetzner Cloud CCX33
    • Spesifikasinya adalah 8 dedicated vCPU, 32 GB RAM
    • Waktu eksekusi end-to-end diukur dengan program time
    • Setiap kiriman dijalankan 5 kali berturut-turut
    • Eksekusi paling lambat dan paling cepat dikeluarkan
    • Rata-rata waktu eksekusi dari 3 kali yang tersisa menjadi hasil untuk kiriman tersebut
    • Hasil ditambahkan ke leaderboard
  • Diskusi tentang teknik optimisasi berlanjut di discussion pada repositori GitHub
  • Tersedia juga Show & Tell untuk berbagi implementasi dalam bahasa selain Java, dan implementasi 1BRC dalam Rust, Go, C++, dan lainnya dibagikan di sana

Bacaan terkait

2 komentar

 
GN⁺ 2024-01-05
Komentar Hacker News

  • Solusi yang saat ini tampak berkinerja terbaik [0] sepertinya tidak mempertimbangkan tabrakan hash, jadi jika dataset memiliki cukup banyak kota yang berbeda, hasilnya kemungkinan bisa salah
    Saya penasaran apakah ada yang saya lewatkan
    [0] https://github.com/gunnarmorling/1brc/blob/main/src/main/jav...

    • Benar. Masalah ini muncul kemarin, dan sebenarnya ada dua solusi yang bergantung pada fungsi hash yang disesuaikan untuk dataset tertentu sehingga melanggar aturan bahwa solusi harus bekerja untuk semua nama stasiun pengamatan, tetapi itu terlewat saat evaluasi
      Untuk sementara entri-entri tersebut sudah dihapus dari papan peringkat, dan kedua penulis sedang memperbaiki submission mereka sehingga nantinya akan ditambahkan kembali
      [0] https://twitter.com/mtopolnik/status/1742652716919251052

  • Saya rasa dengan pendekatan berikut seluruhnya bisa diproses dalam 0,3 detik
    Karena suhu memiliki satu angka desimal, dalam kasus umum sekitar 400 nilai sudah cukup, dan nama tempat juga terbatas sekitar 400, jadi kita bisa membuat lookup table sekitar 160 ribu kombinasi suhu×nama tempat
    Buat otomatis sebuah state machine yang memetakan 160 ribu kombinasi ini ke bucket unik dalam hash table, apa pun posisi rotasinya di register 4 byte, lalu pada register status 32-bit lakukan lookup tabel transisi status dan XOR 4 byte berikutnya di setiap siklus
    Cukup telusuri seluruh data pada kecepatan memori sambil menaikkan counter per status, dan karena statusnya hanya 65K, counter akan masuk cache
    Dengan AVX512, per core bisa menjalankan 512 state machine 32-bit semacam ini secara paralel, jadi komputasi tidak akan menjadi bottleneck
    Suhu tinggi/rendah atau nama tempat tak dikenal yang tidak terpetakan ke bucket valid dialihkan ke kode lambat, dan penanganan nilai minimum/maksimum juga bisa ditangani lewat escape seperti ini sehingga hanya terjadi beberapa ribu kali
    Menurut saya metode ini bisa berjalan pada kecepatan memori hanya dengan satu core AVX512, jadi tidak ada keuntungan membaginya ke banyak core

    • Lookup table tidak diperlukan. Yang diminta hanya nilai minimum/rata-rata/maksimum, jadi semuanya bisa dihitung dalam satu kali traversal tanpa menyimpan data
      Yang diperlukan hanyalah hash table berisi 400 entri, tiga nilai floating point untuk minimum·rata-rata·maksimum yang sedang berjalan, dan satu integer counter untuk memperbarui rata-rata
      Bahkan memakai 16 byte untuk nama, semuanya akan muat dalam 16KB
      Waktu eksekusi akan didominasi I/O, lalu kemungkinan berikutnya parsing JSON
    • Satu core tidak bisa menjenuhkan bandwidth memori. Core dibatasi oleh paralelisme memori dan latensi
      Sebagian besar chip server x86 modern bisa me-retire 2 SIMD load per clock, jadi dengan AVX2 pada 1GHz kira-kira bisa mencapai 32GB/s, sehingga AVX-512 tidak mutlak diperlukan untuk memaksimalkan bandwidth per core
      Namun jika membaca dari DRAM, batasnya akan jauh lebih cepat tercapai, di server umumnya kemungkinan tertahan di sekitar 10–16GB/s
      Selama sebagian besar data meluap ke RAM, throughput satu core akan turun tajam, dan pada pekerjaan streaming besar, paralelisme multicore hampir selalu menguntungkan
      Ini mudah dibuktikan dengan mengalokasikan blok memori yang jauh lebih besar daripada cache L3, melakukan page fault terlebih dahulu, lalu menjalankan vector load yang di-unroll (AVX2/AVX-512) dalam loop ketat
    • Status berikutnya selalu bergantung pada status sebelumnya, jadi saya tidak paham bagaimana state machine itu bisa dijalankan paralel
      Saya juga ragu bagaimana register statusnya akan ditafsirkan. Jika di-XOR dengan input 4 byte, untuk nama tempat yang tidak terduga nilainya pada dasarnya bisa menjadi sembarang dari sekitar 4,7 miliar kemungkinan nilai
      Bahkan untuk nama tempat yang diharapkan, jika lebih panjang dari 4 byte, bukankah masing-masing membutuhkan beberapa status agar bisa dibedakan dari nama lain yang memiliki prefiks sama?
    • Sepertinya interpretasi aturannya perlu dipastikan. Tidak jelas apakah kode yang dioptimalkan khusus untuk 400 nama tempat yang diketahui tetapi mendukung nama tambahan lewat jalur lambat itu valid
      Aturannya menyebut bahwa meskipun generator data memakai kumpulan nama stasiun pengamatan tetap, solusi apa pun harus bekerja untuk nama stasiun pengamatan UTF-8 arbitrer
    • Untuk menemukan nama tempat, pada akhirnya tetap harus membaca dan mem-parse seluruh file

  • Daripada membuang eksekusi paling lambat dan paling cepat lalu memakai rata-rata dari tiga eksekusi sisanya, menurut saya lebih baik membuang dua yang lambat atau cukup mengakui nilai tercepat
    Saya tidak melihat alasan kuat untuk membuang hasil eksekusi yang bagus

    • Ini adalah metode pengukuran yang cukup standar bernama trimmed mean (rata-rata terpangkas): https://statisticsbyjim.com/basics/trimmed-mean/
    • Ada alasan untuk membuang eksekusi terbaik. Jika kita menganggap sistem berperilaku dapat diprediksi dan hanya melambat karena pekerjaan latar belakang, memakai eksekusi terbaik memang masuk akal
      Namun jika ada sedikit saja sumber nondeterminisme di dalam program—dan ini lebih umum daripada yang dikira—waktu terbaik kemungkinan kurang representatif
      Terkait hal ini, https://tratt.net/laurie/blog/2019/minimum_times_tend_to_mis... adalah tulisan yang bagus
    • Kalau membuang eksekusi tercepat tidak bisa diterima, saya bertanya-tanya mengapa membuang eksekusi terlambat justru disetujui

  • Dari sudut pandang yang memperdebatkan aturan, pada eksekusi pertama rasanya ingin menjalankan daemon latar belakang, memuat seluruh file ke memori dan mem-pinning-nya, lalu menarik cache lebih dulu supaya eksekusi berikutnya pada dasarnya hanya melakukan pemindaian linear
    Menghitung hasil lebih dulu pada eksekusi pertama juga tampaknya bisa dilakukan, tergantung seberapa jauh aturan ditafsirkan secara longgar; angka-angka juga bisa di-parse lebih dulu ke format yang lebih padat lalu pada eksekusi berikutnya langsung dibaca sebagai akumulasi jumlah
    Ini sama sekali tidak sesuai dengan tujuan kompetisi, tetapi dari aturan yang terlihat tampaknya tidak dilarang
    Jika tidak suka prakalkulasi, masih ada trik seperti mengurutkan input lebih dulu, mem-parse lebih dulu, atau kompresi·pengurutan·tata letak memori yang sudah terurut
    Secara ekstrem, bisa saja mem-patch skrip calculate_time agar mengembalikan 0 detik dan mengembalikan 9999 untuk pesaing

    • Jika peserta diberi file persis yang akan benar-benar dipakai dalam kompetisi, masalah nyata akan muncul
      Mulai dari meng-hardcode jawaban dalam satu baris tanpa membaca input sama sekali, sampai pemrosesan dengan asumsi tidak mengetahui isi file, ada kira-kira satu miliar tingkat area abu-abu prakalkulasi
      Kompetisinya bisa berubah menjadi kompetisi menentukan mana prakalkulasi yang adil dan mana yang tidak
      Karena itu kompetisi machine learning tidak memperlihatkan data final kepada peserta
    • Sepertinya ini akan melanggar aturan
      Disebutkan bahwa komputasi harus terjadi saat aplikasi dijalankan, dan file pengukuran tidak boleh diproses pada waktu build lalu hasilnya dipanggang ke dalam binary
    • Menurut saya aturan harus menyatakan bahwa setiap eksekusi dijalankan di tmpfs terpisah, dan semua proses serta page cache dihapus di antara eksekusi

  • Sepertinya ini sekadar masalah yang terikat pada kecepatan disk. Saya ragu optimasi seperti SIMD atau multithreading akan berarti
    Memang tergantung pada jumlah stasiun observasi yang berbeda dan cara lookup hash, tetapi saya skeptis apakah dampaknya bisa terukur dibandingkan I/O

    • Akses disk bisa diparalelkan dan NVMe sangat cepat, jadi bottleneck bisa jadi ada di sisi CPU, bukan disk
      Sistem yang dirancang dengan asumsi hardware modern memanfaatkan hal ini, dan redpanda.com tempat saya bekerja juga salah satu contohnya
      Parsing adalah bagian besar dari waktu komputasi, dan teknik SIMD seperti SWAR untuk menemukan delimiter bisa membantu
      Jika ingin melihat implementasi algoritma seperti ini yang rapi, Stringzilla bagus: https://github.com/ashvardanian/StringZilla
      Mengenai fakta bahwa setelah eksekusi pertama file sepenuhnya di-cache di memori, saya sudah menjawabnya di sini: https://news.ycombinator.com/item?id=38864034
    • Sepenuhnya bergantung pada workload dan hardware. SSD konsumen biasa pun jika hanya memakai 700GB dari 2TB dapat dengan mudah mempertahankan 7GB/s (56Gbps)
      Server umumnya punya cukup lane PCIe untuk memasang 15 SSD seperti ini, sehingga bandwidth I/O server berada pada level yang mirip dengan bandwidth memori
      Server yang lebih mahal punya lane yang lebih cepat dan lebih banyak, seperti PCIe 5.0
      File ini berisi 1 miliar baris, sekitar 1GB jika dikompresi, dan setelah eksekusi pertama yang dibuang file akan berada di memori, jadi dalam skenario ini bandwidth I/O tidak penting
      Repositori GitHub menyebutkan ukurannya 12GB tanpa kompresi, tetapi itu tetap menegaskan bahwa bandwidth I/O tidak penting
    • Presentasi Daniel Lemire ini menarik: https://www.youtube.com/watch?v=wlvKAT7SZIQ
      Intinya, disk jarang menjadi bottleneck
    • Tergantung pada sistem operasi dan filesystem. File input sekitar 12GB dan dijalankan 5 kali pada mesin dengan memori 32GB, jadi setelah eksekusi pertama seluruh file bisa saja di-cache di memori
      Misalnya di Linux dengan ext2, besar kemungkinan seluruh file di-cache setelah eksekusi pertama, tetapi belum tentu demikian di ZFS
    • Untuk parsing secepat mungkin, tampaknya jelas bahwa semuanya harus dimuat ke RAM dan diproses mundur dari akhir
      Dengan begitu angka muncul dari digit rendah ke digit tinggi, lalu delimiter dan string muncul, dan proses dapat dilanjutkan sampai bertemu EOF atau newline

  • Menurut aturan, submission harus bekerja benar untuk semua input, tetapi tampaknya boleh, dan mungkin memang sebaiknya, di-tuning untuk input tertentu yang dihasilkan oleh create_measurements.sh
    Misalnya bisa dibayangkan submission yang memakai fungsi hash sempurna yang disesuaikan dengan himpunan stasiun observasi yang diberikan

    • Jika ada persyaratan ini, akan bijak membuat data uji berbeda dari data contoh
      Dengan begitu optimasi yang overfit bisa dicegah
    • UTF-8 membuatnya jauh lebih sulit. Tetapi jika mengikuti teks aturan saja dan bukan semangatnya, cukup alihkan ke implementasi lambat begitu mendeteksi byte yang lebih besar dari 127
      Byte yang lebih besar dari 127 berarti karakter UTF-8 multibyte

  • Untuk iseng, saya membandingkan kecepatan awk vs Java
    Ini skrip yang dengan awk -F';' mengakumulasi jumlah, hitungan, nilai minimum, dan maksimum per stasiun observasi, lalu menghitung dan mencetak rata-rata di END

    • Saya ingin melihat perbandingan kecepatannya dengan file foreign data wrapper PostgreSQL: https://www.postgresql.org/docs/current/file-fdw.html
      Caranya adalah membuat file CSV sebagai tabel eksternal dengan file_fdw, lalu menghitung MIN, AVG, MAX dengan GROUP BY station_name
    • Jika dijalankan dengan ClickHouse local, hasilnya sekitar 15,2 detik
      Di clickhouse local, membaca file('measurements.txt', 'CSV', 'station String, t Float32'), mengelompokkan min, max, avg per stasiun observasi, dan menjalankannya dengan max_threads = 8
      Sebagian besar waktu dihabiskan untuk parsing file
    • Karena variabel sum bisa menjadi cukup besar, sebaiknya gunakan rata-rata streaming
      Misalnya dengan cara seperti new_mean = ((n*old_mean)+temp)/(n+1)

  • Tantangan yang menarik, tapi sayang hanya untuk Java. Saya menantikan saat orang-orang mulai membuat bytecode JVM langsung dengan tangan

    • Dari diskusinya, sepertinya ada kiriman dalam berbagai bahasa. Ada Go, Rust, Python, C++, dan lain-lain
      [0] https://github.com/gunnarmorling/1brc/discussions
    • Atau “harus ditulis dalam Java” juga bisa ditafsirkan sebagai “harus memakai JVM saat mulai berjalan”, dan menjalankan proses lain dari Java jelas memungkinkan

  • Menarik. Rasanya seperti afterparty Advent of Code
    Kalau ingin perbandingan yang adil antarbahasa, make dan waktu build juga harus dimasukkan. Saya sudah beberapa tahun tidak memakai Java/Maven, dan melihat unduhan ./mvnw clean verify masih berlanjut sampai menit kedua membuat saya kembali ingat alasannya

    • Waktu build Java sangat cepat. Yang sedang diukur sekarang adalah kecepatan internet
      Dan untuk alat build kompilasi inkremental, Gradle lebih cepat
    • Kalau waktu build dimasukkan, waktu pemrograman juga harus dimasukkan, lalu keduanya dibagi dengan jumlah kali kode itu akan dijalankan selama masa pakainya
      Proporsi yang layak dari waktu yang dibutuhkan untuk belajar pemrograman juga harus ditambahkan
      Dalam tantangan seperti ini, versi yang sangat naif kemungkinan besar akan menang, dan menurut saya itu bukan hanya tidak realistis, tetapi juga bertentangan dengan maksud tantangan
    • Saya tidak tahu kenapa harus clean
      Itu sama saja membuang cache lalu mengatakan lambat
    • Maven tidak diperlukan
      Disebutkan bahwa dependensi eksternal tidak boleh digunakan

  • Di mata kuliah C di Czech Technical University ada tugas yang sangat mirip
    Semua kiriman mahasiswa terus dinilai di papan peringkat, dan banyak mahasiswa menghabiskan puluhan jam untuk optimasi demi mendapatkan poin tambahan untuk nilai yang lebih baik—pada dasarnya poin status
 
dlehals2 2024-01-10

Peringkat pertama 6 detik ya.. luar biasa.