SWAR ajaib merykitty di 1brc: kode 8 baris yang dijelaskan dalam 3.000 kata

• Bottleneck 1BRC adalah mem-parsing 1 miliar nilai suhu CSV dengan sangat cepat, dan kode SWAR merykitty dari Quân Anh Mai menarik perhatian karena mengubah suhu menjadi bilangan bulat lewat operasi ALU tetap tanpa if
• Kode ini menggunakan pendekatan SWAR (SIMD Within A Register), yang menangani 8 byte dalam satu long sekaligus, memproses beberapa karakter seolah-olah paralel di register CPU biasa
• Alur pemrosesannya meliputi deteksi tanda minus, penghapusan tanda, pencarian posisi titik desimal, penyelarasan XY.Z, konversi digit ASCII, perkalian ajaib, lalu penerapan tanda
• Format input ada empat: -XX.X, -X.X, X.X, XX.X; berdasarkan posisi titik desimal, byte digeser agar panjang yang berbeda cocok ke tata letak bit yang sama
• Alih-alih mengurangi percabangan dan perulangan, kode ini memanfaatkan secara rapat karakteristik kode ASCII, komplemen dua, bit mask, serta sifat shift-penjumlahan dari perkalian untuk mewujudkan parsing berkinerja tinggi

---

Parsing suhu yang menjadi bottleneck di 1BRC

• Dalam One Billion Row Challenge(1BRC), mem-parsing nilai suhu dari file CSV dengan sangat cepat muncul sebagai bottleneck utama
• Dengan optimasi sebelumnya saja, kode Java paralel yang idiomatis sudah dipercepat dari 71 detik menjadi 1,7 detik
• Format suhu memang sederhana, tetapi untuk mem-parsing 1 miliar nilai dalam kurang dari 1 detik, biaya kecil pun akan terakumulasi besar
  • Format yang mungkin adalah -XX.X, -X.X, X.X, XX.X
• Para peserta awal menggunakan Double.parseDouble(), tetapi kemudian muncul parser kustom tanpa loop
• Sebagian solusi @merykitty dari Quân Anh Mai memproses dengan pembacaan satu file tanpa if, dan menyebar seperti elemen standar dalam solusi papan atas 1BRC
• Pemenangnya, Thomas Wuerthinger, menyebut Quân Anh sebagai bagian dari tim yang berkontribusi pada solusinya

Apa yang dilakukan kode merykitty

• Kode menerima long berisi input CSV 8 byte dan mengembalikan nilai suhu bilangan bulat yang merupakan 10 kali suhu sebenarnya
• Input masuk dari file CSV yang di-mmap melalui pembacaan memori native secara langsung; bagian itu dipisahkan sebagai perhatian tersendiri
• Operasinya terdiri dari 18 operasi ALU dalam urutan tetap
  • Bit shift, AND, NOT, XOR
  • Penjumlahan, pengurangan, perkalian
  • Long.numberOfTrailingZeros()
• numberOfTrailingZeros() menggunakan instruksi CPU khusus melalui intrinsic compiler JDK
• Karena menangani beberapa byte dengan register dan instruksi CPU biasa, bukan instruksi khusus SIMD umum, pendekatan ini termasuk SWAR
• Kode contoh sedikit dimodifikasi dari aslinya agar lebih mudah dibaca, dan versi asli ada di CalculateAverage_merykitty.java

Tahapan pemrosesan lengkap

• Kode mem-parsing suhu dengan urutan berikut
  • Memeriksa apakah karakter pertama adalah - untuk mendeteksi apakah nilainya negatif
  • Jika ada karakter tanda, byte tersebut dibuat menjadi 0
  • Menemukan posisi titik desimal .
  • Menggeser bit di dalam long agar digit cocok dengan template XY.Z
  • Mengubah karakter ASCII menjadi nilai angka sebenarnya
  • Mengalikan tiap digit dengan bobot 1x, 10x, 100x lalu menjumlahkannya
  • Menerapkan tanda di akhir
• Secara permukaan ini terlihat seperti masalah parsing tingkat tinggi, tetapi setiap tahap diimplementasikan hanya dengan operasi ALU

Tahap 1: Deteksi tanda minus

• Deteksi tanda dimulai dengan kode berikut

long negatedInput = ~inputData;
long broadcastSign = (negatedInput << 59) >> 63;

• Jika urutan penjelasannya dibalik, ini dapat dilihat seperti ( ~(inputData << 59) ) >> 63
• Dalam ASCII, minus - memiliki bit 4 bernilai 0, sedangkan karakter digit memiliki bit tersebut bernilai 1; sifat ini dimanfaatkan
• Menggeser input 59 bit ke kiri memindahkan bit pembeda karakter pertama ke bit paling signifikan
• Setelah bit dibalik dengan NOT, melakukan arithmetic right shift 63 bit menyebarkan bit paling signifikan ke seluruh long
• Hasilnya, broadcastSign, menjadi semua bit 1 jika ada minus, dan semua bit 0 jika tidak ada

Tahap 2: Menghapus karakter tanda

• Karena informasi negatif sudah disimpan di broadcastSign, karakter tanda dihapus dari data input

long maskToRemoveSign = ~(broadcastSign & 0xFF);
long withSignRemoved = inputData & maskToRemoveSign;

• Jika broadcastSign semuanya 1, maka broadcastSign & 0xFF hanya membuat 8 bit terbawah menjadi 1
• Melakukan NOT terhadapnya menghasilkan mask yang hanya 8 bit terbawahnya 0
• Jika di-AND dengan inputData, - pada byte terbawah akan dihapus
• Jika tidak ada minus, broadcastSign adalah 0, sehingga mask menjadi semua bit 1 dan byte digit tetap dipertahankan

Tahap 3: Menemukan posisi titik desimal

• Posisi titik desimal dihitung dengan kode berikut

int dotPos = Long.numberOfTrailingZeros(negatedInput & DOT_DETECTOR);

• Karakter . juga, seperti minus, memiliki karakteristik bit 4 bernilai 0
• Untuk hanya memeriksa bit 4 pada kemungkinan posisi titik desimal, digunakan mask DOT_DETECTOR = 0x10101000
• Dalam negatedInput, yaitu input asli yang dibalik, bit terkait pada posisi titik desimal menjadi 1
• Long.numberOfTrailingZeros() mengembalikan posisi bit 1 ini
• Pada contoh -10.8, titik desimal berada di posisi bit 28, sehingga dotPos = 28

Tahap 4: Menyelaraskan ke template tetap

• Berdasarkan posisi titik desimal, input digeser ke kiri agar selalu cocok dengan template yang sama

long alignedToTemplate = withSignRemoved << (28 - dotPos);

• Template target adalah sebagai berikut

0 0 0 Z . Y X 0

• Di sini X adalah digit puluhan, Y adalah digit satuan, dan Z adalah digit pertama setelah desimal
• 0 berarti byte bernilai 0, bukan ASCII "0"
• Setelah tanda dihapus, input dapat berada dalam salah satu dari empat tata letak
  • 0 0 0 Z . Y X 0
  • 0 0 0 0 Z . Y 0
  • 0 0 0 0 Z . Y X
  • 0 0 0 0 0 Z . Y
• -10.8 sudah memiliki dotPos = 28, sehingga jumlah pergeserannya 0
• -7.7 memiliki titik desimal pada posisi bit 20, sehingga digeser 8 bit, yakni satu byte ke kiri, dan 0 ditempatkan pada posisi X

Tahap 5: Mengubah digit ASCII menjadi nilai

• Setelah penyelarasan, hanya nilai angka yang disisakan dari karakter ASCII

long digits = alignedToTemplate & ASCII_TO_DIGIT_MASK;

• Digit ASCII 0 sampai 9 adalah 0x30 sampai 0x39 dalam heksadesimal
• Jika hanya 4 bit bawah yang disisakan, kode karakter menjadi nilai angka sebenarnya
• Mask yang memiliki F hanya pada posisi digit di template diterapkan

0 0 0 Z . Y X 0
000000F000F0F00

• Pada contoh -10.8, setelah mask diterapkan, yang tersisa hanya nilai yang mewakili Z=8, Y=0, X=1

Tahap 6: Menjumlahkan nilai tempat dengan perkalian ajaib

• Nilai absolut akhir harus dihitung sebagai 100 * X + 10 * Y + Z
• Dengan memanfaatkan sifat bahwa perkalian adalah kombinasi shift dan penjumlahan, perhitungan bobot beberapa digit diproses dengan satu perkalian
• Pertama, jika membayangkan X + Y + Z, nilai digits yang digeser ke posisi 0, 16, dan 24 bit dapat dijumlahkan untuk mengumpulkan hasil di rentang bit tertentu
• Kombinasi shift-penjumlahan ini dapat direpresentasikan sebagai perkalian berikut

0x1 + 0x10000 + 0x1000000

• Pada praktiknya, bobot tiap digit berbeda, sehingga MAGIC_MULTIPLIER disusun seperti berikut

MAGIC_MULTIPLIER = 0x1 + 10 * 0x10000 + 100 * 0x1000000;

• Rumus perhitungannya adalah sebagai berikut

absValue = ((digits * MAGIC_MULTIPLIER) >>> 32) & 0x3FF;

• 0x3FF adalah mask untuk memisahkan hanya hasil selebar 10 bit
• 100 * X dapat membesar hingga 10 bit dan tumpang tindih dengan bit di sebelahnya, tetapi karena dua bit kanan dari Y * 100 menjadi 0, ruang bit yang diperlukan tetap tersedia
• merykitty meninggalkan komentar // That was close :) pada bagian ini

Tahap 7: Menerapkan tanda tanpa percabangan

• Pada titik ini terdapat nilai absolut absValue dan informasi tanda broadcastSign
• broadcastSign berperilaku sebagai 0 untuk positif dan -1 untuk negatif
• Dalam komplemen dua, nilai negatif dinyatakan dengan rumus berikut

-n = NOT(n) + 1

• XOR dapat digunakan seperti NOT bersyarat
  • n XOR -1 adalah NOT(n)
  • n XOR 0 adalah n
• +1 opsional ditangani dengan -broadcastSign

temperature = (absValue ^ broadcastSign) - broadcastSign;

• Hasilnya, tanpa if, nilai positif dibiarkan apa adanya, sedangkan nilai negatif dikonversi menjadi nilai negatif komplemen dua

Bonus: Menghitung posisi awal baris CSV berikutnya

• Dalam keseluruhan solusi 1BRC, posisi awal baris CSV berikutnya juga harus dihitung dengan murah
• Setelah titik desimal, selalu ada satu digit desimal dan karakter newline, sehingga posisi awal baris berikutnya dihitung berdasarkan posisi titik desimal
• Karena dotPos adalah posisi dalam bit, pembagian dengan 8 dilakukan menggunakan shift kanan 3 bit

nextLineStart = (dotPos >>> 3) + 3;

• +3 adalah nilai untuk menunjuk byte pertama setelah titik desimal, satu digit desimal, dan newline

Kesimpulan

• Kode SWAR merykitty mem-parsing empat format string suhu menjadi seragam hanya dengan operasi bit tetap
• Intinya adalah karakteristik bit kode ASCII, penyelarasan berdasarkan posisi titik desimal, ekstraksi digit melalui mask, penjumlahan nilai tempat menggunakan perkalian, dan penerapan tanda berbasis komplemen dua
• Jika dipecah tahap demi tahap, cara kerjanya dapat diikuti, tetapi fakta bahwa kombinasi ini dirangkai dalam beberapa hari selama tantangan online tetap menjadi bagian yang mengesankan

[GN⁺]

Komentar di Hacker News

• Penjelasan langkah demi langkahnya benar-benar bagus
  Lebih dari 2 tahun lalu saya mengetahui bahwa byte array view var handle cukup cocok untuk membuat rutin SWAR yang efisien di Java/Scala
  Ada banyak contoh penggunaan SWAR di sini juga, seperti parsing string Base16/64, java.time.*, dan parsing nilai angka langsung dari array byte: https://github.com/plokhotnyuk/jsoniter-scala/blob/master/js...
• Tulisannya bagus dan ini solusi yang sangat baik dalam konteks kodenya, tetapi pendekatan ini berasumsi bahwa datanya berformat benar
  Nilai besar dari parser yang teruji di dunia nyata ada pada pemeriksaan dan pemulihan kesalahan yang efisien
  • Akan menarik jika membedah bagaimana input yang salah dapat memengaruhi output
    Dan saya juga penasaran seberapa banyak pekerjaan yang diperlukan untuk mendeteksinya agar mengembalikan semacam nilai error sentinel seperti gaya kode saat ini
    Tidak cukup menarik untuk saya coba sendiri, sih ;-)
• Teknik mengalikan bitfield angka dengan pangkat 10 untuk setiap digit lalu melakukan shift/penjumlahan dengan MUL adalah metode yang cukup dikenal
  Lihat tulisan Lemire: https://lemire.me/blog/2023/11/28/parsing-8-bit-integers-qui...
• Menurut tulisan itu, SWAR adalah SIMD Within A Register
• Jika menyukai hal seperti ini, makalah simdjson juga memakai teknik serupa, tulisannya sangat baik, dan contohnya bagus
  Makalah: https://arxiv.org/abs/1902.08318
  Github: https://github.com/simdjson/simdjson
  • Ini memang bukan SWAR, tetapi saya mengerti mengapa ini menarik
• Bisa jelaskan mengapa BRC tidak terkena bottleneck input/output? Saya tidak paham mengapa CPU menjadi bottleneck
  • Pada sistem modern, input/output disk lokal bukan lagi bottleneck: https://benhoyt.com/writings/io-is-no-longer-the-bottleneck/
    Selain itu, 1BRC resmi menyatakan bahwa hasil dievaluasi dari RAM disk agar kecepatan input/output benar-benar dikecualikan: https://github.com/gunnarmorling/1brc?tab=readme-ov-file#eva...
    “Programs are run from a RAM disk (i.o. the IO overhead for loading the file from disk is not relevant)”
  • Sebagai latar belakang, ada wawancara dengan Daniel Lemire. Ia adalah orang yang membangun seluruh kariernya berdasarkan pengamatan bahwa input/output tidak selalu menjadi bottleneck: https://corecursive.com/frontiers-of-performance-with-daniel...
  • Saya belum melihat masalah ini secara detail, tetapi kita bisa mulai dari arah sebaliknya. Mengapa Anda berpikir input/output memori adalah bottleneck?
    Dari pemahaman saya yang terbatas, file teks besar diambil secara berurutan ke L1 dan setiap nilai dibaca sekali. Pada kebanyakan prosesor, pembacaan seperti ini bisa dilakukan dua kali per siklus. Bagian yang lambat adalah membawa data dari RAM ke L1, tetapi pembacaan berurutan cukup cepat
    Setelah itu, ada pemrosesan untuk setiap pembacaan. Sekilas, pada versi yang dioptimalkan tampaknya sekitar 4 siklus. Lalu hasilnya harus ditulis ke suatu tempat, dan mungkin sebelum itu diperlukan satu atau dua pembacaan acak. Apakah bagian ini yang Anda anggap sebagai bottleneck input/output?
    Saya tidak mengatakan bahwa batasan CPU itu jelas, tetapi tampaknya tidak jelas juga bahwa bukan begitu
    Edit: saya tidak mempertimbangkan bahwa yang dimaksud mungkin “input/output disk”. Seperti dikatakan orang lain, di sini itu pada dasarnya bukan faktor
  • Pengujian dijalankan dengan memfs. File dan semuanya sudah ada di RAM sejak awal
  • Dataset cukup kecil untuk masuk ke page cache kernel Linux, dan benchmark diulang 5 kali berturut-turut, jadi iterasi pertama bisa saja bottleneck pada input/output disk, tetapi 4 sisanya tidak
    Dengan kata lain, semua data berada di RAM, lebih tepatnya di page cache
• Dulu saya cukup efektif memakai SWAR di 68000. Satu instruksi memproses 4 byte secara paralel
  Kalau ingatan saya benar, penanganan overflow cukup rumit. Saya sangat menyukai tulisan ini
• Katanya, “misteri sebenarnya adalah bagaimana satu orang yang bekerja sendirian bisa membuat semua ini sambil santai mengikuti tantangan online selama beberapa hari dengan hadiah kaus dan mug kopi.” Mengapa itu misteri?
  Masih ada orang yang benar-benar tahu cara memprogram CPU dan memahami apa yang mereka lakukan
  Misteri sebenarnya adalah kebanyakan orang yang menyebut diri programmer kurang memiliki pemahaman mendalam, dan bahkan tampaknya tidak menyadari bahwa mereka sangat kekurangan hal itu
• Di C#, trik SWAR seperti ini tidak diperlukan. Sebagai gantinya, ia menyediakan API SIMD lintas platform kelas satu
  Bahwa ini benar-benar bekerja dapat dilihat dari solusi C# yang tampaknya paling cepat di antara 1BRC yang sudah dipublikasikan sejauh ini: https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-...
• Bisakah ini divektorisasi dengan SSE? Sebagian besar pemrosesan intinya tampak bisa dilakukan dengan vektor berisi empat integer 32-bit
  Masalahnya adalah apakah biaya menyusun vektor awal dan mengekstrak hasilnya tidak berlebihan
  • Bisa, dan beberapa implementasi 1BRC lain juga melakukannya
    Namun saya ragu HotSpot akan melakukannya sendiri, dan secara terpisah, kebanyakan submission 1BRC dijalankan dengan Graal untuk mengurangi overhead startup
    SSE2 dasar tidak memiliki perkalian 32-bit atau 64-bit, jadi perkalian 32×32→64-bit menjadi masalah, tetapi SSE4.1 menambahkan pmuldq yang persis dibutuhkan. Namun hasilnya 64-bit, sehingga untuk memproses seluruh vektor integer 32-bit, operasi seperti ini diperlukan dua kali
  • Karena field suhu tercampur dengan field nama, tampaknya sulit mendapatkan keuntungan tambahan dengan SSE
    Selain itu, field suhu panjangnya variabel, jadi meskipun disimpan per kolom, mungkin tidak memberikan keuntungan
    Namun SSE berhasil diterapkan untuk mencari delimiter antara nama dan suhu
  • Kode seperti ini sepertinya akan mengalami auto-vectorization, entah sejak awal maupun setelah HotSpot mendeteksi hotspot