SWAR ajaib 1brc merykitty: 8 baris kode yang dijelaskan dalam 3 ribu kata

 (questdb.io)
2 poin oleh GN⁺ 2024-03-11 | 1 komentar | Bagikan ke WhatsApp

Pengenalan kompetisi 1BRC

  • Dalam kompetisi 1BRC, ada prediksi bahwa setelah menangani "para tersangka biasa", bottleneck berikutnya adalah parsing suhu dari file CSV.
  • Suhu dapat muncul dalam empat bentuk: -XX.X, -X.X, X.X, XX.X, dan pada awalnya digunakan pemanggilan pustaka Double.parseDouble().
  • Namun, tak lama kemudian muncul solusi kustom, dan salah satunya tampak sebagai metode teroptimasi dengan hanya dua percabangan tanpa loop.
  • Lalu hadir solusi dari Quân Anh Mai(@merykitty) yang membuat tagar #1BRC di Twitter memanas. Solusi ini menggunakan hanya satu pembacaan file tanpa pernyataan if.

Analisis SWAR ajaib milik merykitty

  • Kode merykitty hanya terdiri dari 18 operasi ALU dan mencakup satu pemanggilan fungsi level rendah, yaitu numberOfTrailingZeros().
  • Angka long masukan berisi 8 byte dari CSV, dan keluarannya adalah suhu dalam bentuk bilangan bulat (10 kali suhu sebenarnya).
  • Teknik ini disebut "SIMD Within A Register"(SWAR), dan menggunakan register serta instruksi CPU standar.
  • Kode tersebut melewati langkah-langkah seperti mendeteksi apakah angkanya negatif, menghapus karakter tanda, mencari posisi titik desimal, menyelaraskan isi agar cocok dengan templat, mengubah karakter ASCII menjadi nilai angka, mengalikan tiap angka dengan bobotnya lalu menjumlahkan semuanya, dan menerapkan tandanya.
  • Langkah-langkah ini dilakukan hanya dengan operasi ALU.

Kesimpulan

  • Bagaimana merykitty sendirian bisa menyelesaikan semua ini hanya dalam beberapa hari adalah misteri sejati yang tidak bisa dijelaskan sepenuhnya lewat sebuah posting blog.
  • QuestDB bersifat open source dan menyediakan pemasukan data cepat serta analisis SQL di bawah lisensi Apache 2.0.

Pendapat GN⁺

  • Artikel ini menunjukkan kompleksitas dan kreativitas teknik SWAR yang dirancang untuk memecahkan masalah parsing suhu yang sederhana. Ini menekankan kekuatan operasi bit dalam pemrograman dan pentingnya optimasi.
  • Pendekatan seperti ini dapat menjadi contoh yang menarik terutama bagi insinyur perangkat lunak pemula yang tertarik pada pemrograman sistem atau pengembangan aplikasi yang sensitif terhadap performa.
  • Untuk meningkatkan pemahaman tentang operasi bit dan optimasi, akan membantu jika mencari kompetisi coding online atau tutorial yang membahas topik atau masalah terkait.
  • Diperlukan penelitian lebih lanjut tentang bagaimana teknik ini dapat diterapkan di lingkungan industri nyata, dan apakah ada basis data atau sistem lain yang menggunakan teknik optimasi serupa.
  • Saat mengadopsi sistem seperti QuestDB, selain peningkatan performa, faktor lain seperti kemudahan pemeliharaan, keterbacaan kode, dan dukungan teknis jangka panjang juga perlu dipertimbangkan.

Bacaan terkait

1 komentar

 
GN⁺ 2024-03-11
Komentar Hacker News

  • Ringkasan komentar Hacker News terkait makalah simdjson:

    • Makalah simdjson: Menggunakan teknik serupa, ditulis dengan sangat baik, dan menyertakan contoh-contoh yang sangat bagus.

  • Interpretasi terhadap konteks kode: Solusi yang diajukan memang luar biasa, tetapi perlu asumsi bahwa datanya tersusun dengan baik. Pemeriksaan kesalahan dan kemampuan pemulihan yang efisien sangat bernilai pada parser yang sudah matang.

  • Teknik parsing angka: Mengalikan bitfield angka dengan masing-masing pangkat 10 lalu menggunakan MUL untuk melakukan shift/penjumlahan adalah teknik yang sudah dikenal. Lihat blog Lemire.

  • Penjelasan tentang SWAR (SIMD Within A Register): Dalam Java/Scala, ada banyak contoh implementasi rutin SWAR yang efisien dengan menggunakan byte array view var handle.

  • Definisi singkat SWAR: "SIMD Within A Register" berarti melakukan operasi SIMD di dalam satu register.

  • Pertanyaan tentang bottleneck I/O pada BRC (Branchless Ray Casting): Sulit memahami mengapa CPU menjadi bottleneck.

  • Pengalaman menggunakan SWAR di 68000: Memproses 4 byte sekaligus secara paralel memang memungkinkan, tetapi penanganan overflow cukup rumit. Sangat menyukai artikel tersebut.

  • Ruang status dan superoptimizer: Karena ruang statusnya kecil, muncul pertanyaan apakah ada superoptimizer yang menghasilkan hasil serupa.

  • Instruksi AVX dan dukungan SIMD di Java: Algoritme ini bisa dijalankan dengan paralelisme 32x menggunakan instruksi AVX, tetapi sayangnya Java tidak benar-benar mendukung penggunaan CPU SIMD dengan baik kecuali pada kasus tertentu.

  • Pemahaman tentang manipulasi bit: Artikel ini membuat manipulasi bit jauh lebih mudah dipahami dibanding apa pun sebelumnya, dan menyampaikan terima kasih kepada penulis yang menyajikan solusi Java untuk tantangan 1BRC.