simdjson - Mengurai JSON pada skala GB/detik

• Menggunakan instruction set SIMD untuk parsing 2,5 kali lebih cepat dibanding parser yang ada

• Secara otomatis memilih parser yang dioptimalkan untuk tiap CPU saat runtime: Haswell (AVX2)/Westmere (SSE4.2)/ARM64/lainnya 64-bit

• Mendukung validasi penuh JSON & UTF-8

• Satu file .h + .cpp

• Hanya menggunakan 25% instruction set dibanding RapidJSON, dan 50% dibanding sajson

[novemberoscar]

Tampaknya ada berbagai binding / port.

• ZippyJSON: binding Swift untuk proyek simdjson.

• libpy_simdjson: binding Python berkecepatan tinggi untuk simdjson menggunakan libpy.

• pysimdjson: binding Python untuk proyek simdjson.

• simdjson-rs: port Rust.

• simdjson-rust: wrapper Rust (binding).

• SimdJsonSharp: versi C# untuk .NET Core (binding dan port penuh).

• simdjson_nodejs: binding Node.js untuk proyek simdjson.

• simdjson_php: binding PHP untuk proyek simdjson.

• simdjson_ruby: binding Ruby untuk proyek simdjson.

• fast_jsonparser: binding Ruby untuk proyek simdjson.

• simdjson-go: port Go yang menggunakan assembly Golang.

rcppsimdjson: binding R.

[xguru]

Versi Rust - https://github.com/simd-lite/simd-json

Presentasi pengembang di QCon, "Parsing JSON Really Quickly: Lessons Learned"

https://www.youtube.com/watch?v=wlvKAT7SZIQ

[kunggom]

Transkrip kuliah video yang ditautkan:

https://www.infoq.com/presentations/simdjson-parser/

Saya membacanya karena penasaran bagaimana bisa mencapai kecepatan setinggi ini, dan rasanya ini benar-benar bisa disebut kristalisasi dari segala macam ilmu hitam. Kalau poin-poin utamanya dirangkum secara kasar, jadinya seperti berikut.

---

[Pendahuluan]

Sebagian besar library parsing JSON lebih lambat daripada kecepatan sequential read drive

• Di system drive saya (pembicara Daniel Lemire), kecepatan membaca file teks besar secara berurutan adalah 2.2 GB/s, tetapi kecepatan parsing library JSON utama tidak mampu menyusulnya.

• Karena jarang ada library yang kecepatan parsing-nya menembus 1 GB/s, kami memutuskan untuk membuatnya sendiri.

• Hasilnya, kami mencapai throughput yang bisa memakai seluruh bandwidth drive. Jika dihitung, CPU hanya memakai 1.5 cycle per 1 byte input. Bagaimana ini bisa dicapai?

[Berbagai prinsip]

Menghindari branch statement semaksimal mungkin

• Misalnya, pada kode sederhana yang memasukkan angka acak ke dalam array, hanya dengan menambahkan satu if untuk memeriksa apakah angkanya ganjil, program bisa jadi 5 kali lebih lambat. Ini karena biaya saat prediksi branch CPU gagal sangat besar.

• Jika if dihapus dengan operasi bit pada kode yang dicontohkan di atas, kecepatannya hampir pulih seperti semula.

• Jika kode dijalankan berulang kali, akurasi branch prediction memang bisa naik sehingga penurunan performa berkurang, tetapi pada akhirnya ini perilaku non-deterministik, jadi ketika branch prediction ikut berperan, performa jadi sulit diprediksi atau diukur.

Menggunakan SIMD secara agresif untuk memakai word yang lebih lebar

• Dengan instruksi SIMD, kita bisa memakai register dengan word yang lebih lebar dari 64 bit, sehingga lebih banyak data dapat diproses dalam 1 cycle. (Misalnya SSE atau NEON adalah 128 bit, AVX adalah 256 bit.) Karena itu, SIMD dipakai secara agresif sebisa mungkin. Inilah rahasia mengapa hanya 1.5 cycle yang dipakai untuk tiap 1 byte data input.

• Untuk memakai SIMD, digunakan intrinsic function yang bergantung pada prosesor tertentu. Tidak disarankan memakai assembly secara langsung.

Menghindari alokasi memori/objek

• Di simdjson, data JSON diperlakukan seperti satu tape panjang, dan datanya didaur ulang. Dengan kata lain, memori tidak dialokasikan terpisah untuk string atau angka; semuanya diproses secara linear. Ini trik yang umum dipakai.

Terus mengukur performa

• Pengembangan dilakukan secara benchmark-driven. CI kami memasukkan benchmark performa.

• Sebagai catatan, saat melakukan pekerjaan yang CPU-intensive, perlu diingat bahwa frekuensi kerja CPU terus berubah-ubah.

[Contoh nyata]

Contoh 1: Memvalidasi apakah UTF-8 benar

• Tugas memvalidasi apakah data arbitrer yang dimasukkan merupakan code point UTF-8 yang valid pada umumnya melibatkan banyak branch statement.

• Kami membuat cara untuk memvalidasi 32 byte data sebagai UTF-8 yang benar dalam maksimal 20 cycle tanpa branch statement dengan SIMD.

• Karena byte UTF-8 sebagai nilai integer tidak bisa melebihi 244, data dimasukkan ke register 256 bit dengan instruksi SIMD, lalu integer 244 dikurangkan secara saturating dari tiap byte, dan setelah itu cukup diperiksa apakah tidak ada nilai nonzero.

• Cara ini lebih dari 20 kali lebih cepat daripada metode yang memakai branch statement!

Contoh 2: Mengklasifikasikan jenis karakter

• Untuk mem-parsing JSON, berbagai karakter seperti koma, titik dua, tanda kurung, dan spasi harus diklasifikasikan menurut jenisnya.

• Pada x86-64 dan ARM NEON ada instruksi untuk melihat lookup table berukuran 16 byte sekaligus.

• Satu byte dibagi menjadi 4 bit atas dan 4 bit bawah, dua lookup table yang sudah disiapkan sebelumnya diterapkan masing-masing, lalu hasilnya di-AND.

• Kodenya memang tampak kotor, tetapi dengan hanya 5 instruksi, 16 karakter bisa diklasifikasikan tanpa branch.

Contoh 3: Mendeteksi escape character

• Apakah escape character yang dinyatakan dengan menambahkan karakter backslash (\) di depan bisa dideteksi tanpa branch statement? Terutama, kasus backslash yang muncul beruntun untuk meng-escape backslash itu sendiri juga harus ditangani.

• Dalam kasus seperti ini, ada trik bahwa cukup melihat backslash pada posisi ganjil saja.

• Dengan menjadikan bitmask yang menunjukkan posisi genap dan posisi ganjil sebagai konstanta, lalu melewati operasi bit yang kompleks, escape character bisa disaring tanpa branch.

• Setelah tanda kutip yang di-escape disaring, yang tersisa adalah tanda kutip yang menandai string.

• Jika posisi tanda kutip yang diperoleh dengan cara ini dijadikan bitmask lalu operasi bit xor diterapkan berulang, kita bisa memperoleh bitmask yang menunjukkan posisi string. Bagian ini pada kebanyakan prosesor bisa diproses dengan satu instruksi saja.

• Ada juga trik dalam cara mencocokkan himpunan bit dengan posisi string, tetapi karena keterbatasan waktu, bagian itu dilewati.

Contoh 4: Mem-parsing angka

• Mem-parsing angka adalah pekerjaan yang sangat mahal. Saat benchmark parsing floating point dengan fungsi C yang sudah dioptimalkan dengan baik, kecepatannya hanya 0.09 GB/s yang benar-benar mengerikan. Jelas ini adalah bottleneck.

• Sebagian besar kode untuk mem-parsing angka biasanya bekerja per byte sekaligus. Ini sama sekali tidak cepat.

• Jika kita mengambil 8 karakter, menjadikannya satu integer 64 bit, lalu memasukkannya ke rumus tertentu yang ditemukan pembicara pada Sabtu malam larut, kita bisa tahu apakah 8 karakter itu adalah 8 digit angka yang berurutan. Ini penting terutama karena makin banyak digit suatu angka, makin lama waktu parsing-nya.

• Saya juga melihat di Stack Overflow ada snippet kode untuk mem-parsing integer 8 digit dengan cepat. Dengan SIMD ini masih bisa sedikit ditingkatkan, tetapi yang penting adalah mendapatkan ide tentang strategi memproses banyak data sekaligus seperti ini.

[Selain itu]

Runtime dispatch

• Karena banyak kode yang bergantung pada hardware, muncul fungsi-fungsi yang dioptimalkan untuk tiap prosesor, dan membuat agar saat dijalankan fungsi yang sesuai dengan jenis prosesor dipilih ternyata cukup sulit.

• Mungkin sulit dipahami apa yang susah dari itu, tetapi masalahnya adalah mengimplementasikan hal seperti ini dengan kode portabel yang tidak tergantung pada jenis compiler. Ada compiler yang punya bug, dan bahasa itu sendiri juga tidak mendukung hal seperti ini di level bahasa.

• Hal ini penting karena simdjson adalah library open source single-header yang bisa dengan mudah diintegrasikan ke proyek lain.

Lain-lain

• Ada wrapper untuk berbagai bahasa agar bisa digunakan dari banyak bahasa pemrograman.

• Ada versi porting Rust, dan porting Go serta C# sedang dipersiapkan, tetapi tidak ada porting Java.

• Berbagai rumus matematika yang dipakai dalam proyek ini dirancang bersama rekan penulis Geoff Langdale, dan paper terkait dipublikasikan di VLDB Journal. ( https://doi.org/10.1007/s00778-019-00578-5 )

[xguru]

Wah, enak sekali dibaca. Terima kasih!