Tantangan Memproses 1 Miliar Baris dengan Go: 9 Cara Memangkas Waktu dari 1 Menit 45 Detik menjadi 4 Detik

• 1BRC: tantangan menulis kode untuk membaca nilai pengukuran suhu dari file teks berisi 1 miliar baris dan menghitung suhu minimum/rata-rata/maksimum per stasiun pengamatan
• Berlangsung dari 1 Januari 2024 hingga 31 Januari 2024, dengan tujuan memanfaatkan Java terbaru semaksimal mungkin
• Hal ini kemudian menarik perhatian banyak orang, yang mulai menantangnya dengan berbagai bahasa (Rust, Go, C++, SQL)
• Pengenalan mendetail terhadap 9 solusi yang ditulis dengan Go (dari yang paling lambat hingga yang paling cepat)

Tolok ukur dasar

• Waktu yang dibutuhkan untuk membaca data teks 1 miliar baris (13GB) menggunakan perintah cat adalah 1.052 detik.
• Perintah wc yang benar-benar memproses file memerlukan hampir 1 menit (55.710 detik).
• Menyelesaikan masalah dengan solusi AWK memerlukan 7 menit 35 detik.

Solusi 1: Go yang sederhana dan idiomatis

• Solusi pertama yang menggunakan pustaka standar Go memerlukan 1 menit 45 detik.
• Membaca baris dengan bufio.Scanner, lalu memisahkannya berdasarkan ';' dengan strings.Cut.
• Mem-parsing suhu dengan strconv.ParseFloat dan mengakumulasi hasilnya menggunakan map Go.

Solusi 2: Map dengan nilai pointer

• Menggunakan map[string]*stats untuk menghindari hashing dua kali pada map.
• Dengan nilai pointer, waktu dipangkas dari 1 menit 45 detik menjadi 1 menit 31 detik.

Solusi 3: Menghindari strconv.ParseFloat

• Mem-parsing suhu dengan kode kustom alih-alih strconv.ParseFloat.
• Waktu dipangkas dari 1 menit 31 detik menjadi 55.8 detik.

Solusi 4: Menggunakan bilangan bulat fixed-point

• Merepresentasikan suhu sebagai bilangan bulat untuk menghindari operasi floating-point.
• Waktu dipangkas dari 55.8 detik menjadi 51.0 detik.

Solusi 5: Menghindari bytes.Cut

• Alih-alih memindai seluruh nama stasiun untuk mencari ';', parsing dilakukan dari belakang.
• Waktu dipangkas dari 51.0 detik menjadi 46.0 detik.

Solusi 6: Menghindari bufio.Scanner

• Menghapus bufio.Scanner dan membaca file dalam chunk besar.
• Waktu dipangkas dari 46.0 detik menjadi 41.3 detik.

Solusi 7: Tabel hash kustom

• Mengimplementasikan tabel hash kustom alih-alih map bawaan Go.
• Waktu dipangkas dari 41.3 detik menjadi 25.8 detik.

Solusi 8: Pemrosesan chunk secara paralel

• Memparalelkan kode yang sederhana dan idiomatis sehingga waktu turun dari 1 menit 45 detik menjadi 24.3 detik.

Solusi 9: Semua optimasi dan pemrosesan paralel

• Menggabungkan semua optimasi dengan pemrosesan paralel, memangkas waktu dari 24.3 detik menjadi 3.99 detik.

Tabel hasil

• Menyediakan tabel perbandingan semua solusi Go serta solusi Go dan Java tercepat.
• Versi Go tercepat memproses dalam 2.90 detik, sedangkan versi Java dalam 0.953 detik.
• Versi Java yang bahkan tidak sampai 1 detik dibuat oleh Thomas Wuerthinger (pembuat GraalVM), dan tampaknya itu dimungkinkan karena ia memang ahli di bidang ini.

Komentar akhir

• Dalam tugas pemrograman sehari-hari, kode yang sederhana dan idiomatis adalah titik awal yang baik.
• Jika Anda membangun pipeline pemrosesan data, membuat kode 4 kali atau 26 kali lebih cepat dapat meningkatkan kepuasan pengguna dan menghemat biaya komputasi.
• Jika Anda membangun runtime atau interpreter, peningkatan performa adalah hal yang penting.

Opini GN⁺

• Artikel ini memberikan studi kasus yang menarik tentang optimasi performa dengan mengeksplorasi berbagai cara mengoptimalkan pemrosesan data skala besar menggunakan bahasa Go.
• Artikel ini menunjukkan bahwa, dalam proses optimasi, implementasi struktur data seperti tabel hash kustom di luar pustaka standar Go memainkan peran penting.
• Artikel ini menekankan efektivitas pemrosesan paralel, dan menunjukkan bahwa penggabungan optimasi single-core dengan paralelisasi dapat menghasilkan peningkatan performa yang luar biasa.
• Artikel ini memberikan insight yang berguna bagi software engineer yang mengembangkan aplikasi yang sensitif terhadap performa.
• Seberapa berguna optimasi semacam ini di lingkungan produksi nyata dapat berbeda-beda tergantung use case. Tidak semua aplikasi memerlukan tingkat optimasi seperti ini.

[cosine20]

Saya penasaran pekerjaan spesifik apa yang dilakukan pada langkah 7. Itu bagian dengan peningkatan performa yang sangat besar wkwk

[sddsdd94]

Menarik melihat waktu peningkatan performa yang ditunjukkan terpisah untuk tiap langkah, haha.

[galadbran]

Bahkan dengan wc pun cuma 1 menit.... memang yang terbaik itu tidak menulis kode... haha

[jhbaek]

Terima kasih sudah membagikan tulisan yang bagus. Ini mengingatkan saya pada masa ketika saya sempat sangat tergila-gila pada optimisasi sistem, haha.
Seiring bertambahnya pengalaman pengembangan, saya jadi sering mengalami bahwa kode yang dioptimalkan sampai maksimal itu sulit dirawat, sehingga susah dijalankan di lingkungan organisasi. Karena itu, saya perlahan menjauh dari jalan optimisasi. (Tiba-tiba jadi refleksi pribadi)

[misolab]

Kode yang dioptimalkan untuk organisasi!!

[GN⁺]

Komentar Hacker News

• Pengguna pertama menyebut bahwa karena tidak memiliki pengalaman dalam optimasi kode untuk manipulasi data, bagian pertama yang menggunakan cat, wc, dan sebagainya untuk mendapatkan tolok ukur dasar terasa sangat menarik. Ia menganggap metode seperti ini sebagai cara mudah untuk mendapatkan kisaran yang "masuk akal".
• Pengguna kedua menyebut bahwa waktu pemrosesan saat menggunakan pustaka Polars adalah 33 detik, dan menyatakan ketertarikannya pada solusi paling sederhana yang mendekati solusi optimasi manual tercepat.
• Pengguna ketiga mengatakan bahwa laporan analisis performa bahasa Go membingungkan, dan menjelaskan bahwa jika waktu eksekusi pada baris kode tertentu terasa tidak intuitif, bisa jadi datanya sulit diprediksi dan branch predictor melakukan prediksi yang keliru.
• Pengguna keempat membagikan hasilnya menjalankan 1BRC (1 Billion Row Challenge) dengan bahasa Go, dan mengatakan bahwa ia mempelajari berbagai teknik optimasi khas Go. Contohnya termasuk pembacaan memori tanpa pemeriksaan batas menggunakan unsafe.Pointer, fakta bahwa fungsi-fungsi dalam paket bytes dan bits di pustaka standar ditulis dalam assembly, pengaturan untuk mematikan garbage collector, serta cara mengikat goroutine ke thread.
• Pengguna kelima berpendapat bahwa seorang pengembang shell script mungkin sudah lebih dulu menyelesaikan pemrosesan 1 miliar baris tertentu itu sementara pengembang bahasa lain masih bersiap-siap.
• Pengguna keenam berpendapat bahwa basis data lebih cepat, kurang kompleks, dan lebih tangguh terhadap pembaruan data dibandingkan kode aplikasi, sambil menekankan bahwa lebih banyak pekerjaan seharusnya dilakukan di basis data.
• Pengguna ketujuh membagikan pengalaman bahwa pada tahun 2010 ia mengembangkan aplikasi web yang menggunakan PostgreSQL untuk mengueri 270 juta baris data iklim Environment Canada, dan perangkat lunak itu memenangkan penghargaan. Aplikasi tersebut dioptimalkan agar dapat menghasilkan laporan dalam waktu kurang dari satu menit.
• Pengguna kedelapan menyebut bahwa keren melihat kode paralel di bahasa Go tetap mempertahankan gaya penulisan kode yang idiomatis khas Go.
• Pengguna kesembilan mengatakan bahwa saat menangani file teks berukuran besar di CLI, melewati parsing Unicode membuat awk, grep, dan lainnya menjadi jauh lebih cepat, serta mengklaim bahwa menambahkan LC_ALL=C pada solusi awk dapat memangkas waktu pemrosesan menjadi kurang dari satu menit.
• Pengguna terakhir mengatakan bahwa menarik melihat versi Java tercepat lebih cepat daripada versi Go tercepat, dan menilai performa Java Virtual Machine (JVM) memang sangat baik.