Pemrosesan string serde_json 20% lebih cepat

 (purplesyringa.moe)
2 poin oleh GN⁺ 2024-08-25 | 1 komentar | Bagikan ke WhatsApp
  • serde_json, yang digunakan layaknya parser JSON default di ekosistem Rust, memperoleh peningkatan performa 10%, 23%, 32% pada benchmark yang banyak berisi string hanya dengan optimisasi internal kecil
  • Perhitungan posisi error diubah agar tidak lagi memindai langsung bagian awal string, melainkan menggunakan memchr untuk menemukan jumlah baris dan newline terakhir, sehingga selisih jalur error yang sebelumnya lebih dari 2x lebih lambat dibanding jalur sukses menjadi berkurang
  • Loop inti parsing string tidak lagi mencari \, ", dan karakter kontrol secara terpisah, tetapi memeriksanya sekaligus dengan SWAR, sehingga latensi rendah pada string pendek dapat dicapai tanpa SIMD sungguhan
  • Decode escape \u mengurangi biaya branch dan shift dengan LUT, integer bertanda, dan tabel pra-shift; parsing JSON War and Peace berbahasa Rusia menjadi lebih cepat dari 284 MB/s menjadi 344 MB/s
  • Bottleneck berikutnya, encoding UTF-8, ditangani dengan pembuatan UTF-8 manual yang menghindari biaya inisialisasi dan penyalinan dari char::encode_utf8 serta Vec::extend_from_slice, sehingga benchmark yang sama naik hingga 374 MB/s

Mengapa optimisasi serde_json memberi dampak besar

  • serde adalah framework serialisasi dan deserialisasi representatif di Rust, dan serde_json banyak digunakan sebagai pasangan resmi untuk pemrosesan JSON
  • Pada saat publikasi, jumlah reverse dependency serde_json adalah 26.916, sedangkan simd-json 66
  • Dengan tingkat penggunaan sebesar ini, perbaikan kecil di internal serde_json pun dapat memberi efek akumulatif di seluruh ekosistem Rust
  • Dalam situasi ketika banyak pengguna tidak mudah beralih ke parser JSON lain, optimisasi berisiko rendah di dalam library yang sudah ada menjadi praktis

Perhitungan posisi error: dari loop sederhana ke memchr

  • Pada benchmark jalur error, serde_json lebih dari 2x lebih lambat dibanding jalur sukses untuk data yang sama
    • Pada dataset canada, citm_catalog, dan twitter, jalur error -48% hingga -77% lebih lambat dibanding jalur sukses
  • Bottleneck-nya adalah fungsi position_of_index() yang mengubah indeks menjadi line/column untuk memformat pesan error
    • Implementasi sebelumnya menelusuri self.slice[..i] per byte dan memperbarui line serta column setiap kali bertemu \n
  • Jika perhitungan dibagi menjadi dua tahap, memchr dapat diterapkan
    • Hitung jumlah \n di dalam self.slice[..i] untuk mendapatkan nomor line berbasis 0
    • Cari posisi \n terakhir, lalu kurangkan dari i untuk mendapatkan nomor column
  • memchr menyediakan implementasi yang dioptimalkan untuk pencarian satu karakter dan penghitungan jumlah, serta menggunakan SIMD secara internal
  • Setelah PR #1160 digabung, performa jalur error meningkat besar
    • Pada DOM canada, jalur error naik dari 122 MB/s menjadi 216 MB/s
    • Pada struct citm_catalog, naik dari 195 MB/s menjadi 736 MB/s
    • Jalur error masih lebih lambat daripada jalur sukses, tetapi selisihnya berkurang

Pencarian escape string: menemukan tiga kondisi sekaligus

  • Loop inti lama untuk parsing string melewati byte yang bukan escape dengan melihat tabel ESCAPE
    • Target escape yang perlu ditangani dalam string JSON adalah \, ", dan karakter kontrol ASCII 0x1F ke bawah
    • Menurut spesifikasi JSON, kode kontrol di dalam string tidak diperbolehkan
  • Percobaan pertama menggunakan memchr2 untuk mencari \ atau " terlebih dahulu, lalu memeriksa karakter kontrol secara terpisah
    • Akibatnya string dilalui dua kali: sekali dengan cepat, sekali dengan lambat, sehingga lebih lambat daripada sebelumnya
    • Memvektorisasi hanya separuh bagian sederhana dan membiarkan sisanya tetap skalar tidak menghasilkan peningkatan menyeluruh
  • Percobaan kedua memakai struktur memchr2 dan SIMD manual untuk memastikan tidak ada karakter kontrol
    • Pada string pendek, biaya pemanggilan fungsi pilihan runtime menjadi beban
    • Pada string panjang, masalah membaca memori dua kali masih tersisa
  • Implementasi akhir dirapikan ke arah menemukan \, ", dan karakter kontrol dalam satu pass

Mengimplementasikan pemrosesan mendekati SIMD dengan SWAR

  • Untuk menghindari penambahan kode SIMD khusus per platform, digunakan teknik SWAR(SIMD Within A Register)
    • Alih-alih SIMD 128-bit, word 64-bit diperlakukan seperti 8 byte
    • Dengan operasi bit, tiap byte diperiksa secara bersamaan apakah memenuhi kondisi
  • Pemeriksaan karakter kontrol mengubah kondisi c >= 0 && c < 0x20 menjadi bentuk operasi bit
    • Dalam kelompok 8 byte, pemeriksaan dilakukan dengan mask berbentuk !c & (c - 0x2020202020202020) & 0x8080808080808080
    • Borrow dari pengurangan 64-bit dapat merambat ke byte yang lebih tinggi, tetapi tidak menjadi masalah untuk tujuan menemukan karakter kontrol pada posisi terendah
  • \ dan " juga diperiksa dengan cara serupa lalu digabung menjadi satu ekspresi
    • Seluruh ekspresi terdiri dari 9 operasi bit
    • Jika memakai SIMD x86, dibutuhkan 7 operasi, sehingga throughput lebih rendah, tetapi pada string pendek latensi lebih penting
  • Dalam json-benchmark, kode SWAR ini lebih efisien daripada kode SIMD sungguhan
  • Pada string yang terlalu pendek, SWAR bisa lebih lambat daripada kode skalar
    • Regresi muncul pada string sekitar 5 karakter
    • Untuk melindungi pola umum seperti string kosong "" serta escape beruntun \r\n, \uD801\uDC37, karakter pertama diperiksa apakah escape sebelum masuk ke loop SWAR
  • Hasil optimisasi pencarian string berbeda-beda menurut dataset
    • struct twitter naik dari 638 MB/s menjadi 785 MB/s, yaitu +23%
    • DOM twitter naik dari 305 MB/s menjadi 335 MB/s, yaitu +10%
    • struct citm_catalog naik dari 865 MB/s menjadi 905 MB/s, yaitu +5%
    • String kosong masih melambat dalam batas 2% pada microbenchmark tertentu

Optimisasi decode escape Unicode

  • serde_json menangani string Unicode mentah maupun escape \u
    • Contoh: "🥺" dan "\ud83e\udd7a"
  • Decode hex lama menggunakan LUT 256 entri untuk memetakan tiap karakter ke nilai 0–15
    • Menangani '0'..='9', 'A'..='F', 'a'..='f'
    • Karakter yang tidak valid ditandai dengan nilai sentinel
  • Escape \u membaca 4 digit hex, sehingga cara lama memasukkan shift, add, perbandingan, dan branch bersyarat di setiap iterasi
  • Implementasi yang diperbaiki tidak mengembalikan error pada setiap iterasi, melainkan memproses keempat digit terlebih dahulu lalu memeriksa validitasnya
  • Implementasi akhir memakai LUT [i8; 256] dengan digit yang tidak valid bernilai -1, lalu menghitungnya sebagai integer 32-bit
    • Jika berhasil, hasilnya tidak negatif; jika gagal, hasilnya negatif
    • Di x86, load memori dan sign extension dapat digabung menjadi movsx
  • Untuk mengurangi latensi shift, digunakan dua tabel
    • HEX0: nilai asli
    • HEX1: tabel yang nilainya sudah di-shift 4 bit ke kiri
  • Implementasinya dirapikan menjadi decode_four_hex_digits() dengan loop yang di-unroll secara jelas
  • Dengan optimisasi ini, performa parsing War and Peace berbahasa Rusia dalam bentuk JSON-encoded naik dari 284 MB/s menjadi 344 MB/s, meningkat 21%

Bottleneck encoding UTF-8 dan pembuatan manual

  • Setelah decode escape Unicode, bottleneck berpindah ke encoding UTF-8
  • UTF-8 meng-encode codepoint menjadi 1–4 byte sesuai panjangnya
    • 1 byte: 0xxxxxxx
    • 2 byte: 110xxxxx 10xxxxxx
    • 3 byte: 1110xxxx 10xxxxxx 10xxxxxx
    • 4 byte: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
  • char::encode_utf8 di library standar Rust menulis ke buffer &mut [u8], sehingga buffer harus sudah berisi nilai u8 yang valid
    • Tidak bisa langsung menulis ke buffer yang belum diinisialisasi
    • Karena UTF-8 adalah encoding panjang variabel, LLVM sulit menghapus zeroization yang tidak perlu
  • serde_json menanganinya dengan cara scratch.extend_from_slice(c.encode_utf8(&mut [0u8; 4]).as_bytes())
    • Menggunakan buffer lokal [0u8; 4] secara teori dapat dibantu oleh alias analysis
    • Namun dalam praktiknya, karena penyalinan panjang variabel 1–4 byte, LLVM menghasilkan pemanggilan memcpy
  • UTF-8 dibuat langsung untuk menghindari pemanggilan memset dan memcpy
    • Algoritmenya sendiri sederhana, tetapi membutuhkan unsafe
    • Bersama beberapa perubahan kecil, benchmark War and Peace meningkat lagi +9%, dari 344 MB/s menjadi 374 MB/s

Hasil akhir

  • Pada benchmark JSON yang banyak berisi string, performa serde_json masing-masing meningkat 10%, 23%, 32%
  • Karena banyak data JSON berisi banyak string, optimisasi ini dapat berdampak pada berbagai kode Rust yang menggunakan serde_json
  • Perbaikan dilakukan dengan menghilangkan berbagai bottleneck secara berurutan, seperti perhitungan posisi error, pencarian escape string, decode escape Unicode, dan encoding UTF-8

Bacaan terkait

1 komentar

 
GN⁺ 2024-08-25
Komentar Hacker News

  • Trik UTF-8 terasa cukup mengkhawatirkan karena saya sudah terlalu sering melihat serangan yang membingungkan parser
    serde dipakai karena ketepatan-nya, bukan karena kecepatan, jadi semoga mereka sudah mem-fuzz habis-habisan dengan banyak string UTF-8 yang rusak sampai mentok

    • Untungnya struktur UTF-8 sangat sederhana dibanding parser pada umumnya
      Bukan berarti tidak ada bug, tapi state internal parser seharusnya tidak besar, dan exhaustive test juga tampaknya memungkinkan
    • Justru untuk area seperti ini saya ingin melihat hasil dari menjalankan fuzzer
    • Kalau ada contoh yang langsung teringat untuk jenis bug seperti ini, boleh dibagikan?

  • Keren melihat serde bergerak secepat ini
    Saya baru saja melihat simdutf8, lalu sadar bahwa PR untuk parsing UTF-8 dengan dukungan SIMD sudah hampir 5 tahun
    https://github.com/rust-lang/rust/issues/68455

  • Tulisan blog orang ini terasa sangat jart-ish, jadi seru dibaca
    Bagian “kita harus menemukan kembali roda, tapi kalau dipikir-pikir itu cukup keren” saya tidak tahu itu sungguh-sungguh atau ironis
    Saya mulai tertawa sambil menertawakan penulisnya, tapi sisa halamannya tampak cukup kuat unsur merendahkan dirinya sendiri

    • Maksudnya sepertinya bukan fakta bahwa kita harus menemukan kembali roda, melainkan pendekatannya yang cukup keren
    • jart itu maksudnya apa?

  • Kalimat “mengajarkan cara berpikir sama pentingnya dengan mengajarkan coding, tapi hampir tidak pernah dilakukan” terdengar
    Saya merasakan kesombongan yang menganggap lawan bicara tidak berpikir

    • Menurut saya tidak ada kesombongan dalam kalimat itu
      Itu bukan asumsi bahwa orang lain tidak berpikir, melainkan lebih seperti pengamatan bahwa kebanyakan tulisan blog dan panduan hanya menunjukkan hasil akhir, bukan langkah-langkah untuk sampai ke sana
    • Penulisnya bukan membuat klaim seperti itu
      Mengajarkan cara berpikir berarti harus melakukan investigasi dan tidak bisa melewati tahap itu, dan walaupun investigasi sudah dilakukan, itu juga tidak menghapus tanggung jawab untuk menarik kesimpulan sendiri
      Mudah untuk melewatkan salah satunya, tapi itu cara yang keliru

  • serde_json memakan 3GB dependensi kalau melakukan build debug dan release masing-masing sekali
    Kalau memakai serde di beberapa proyek aktif, ruang disk bisa habis
    Saya tidak paham kenapa parsing JSON butuh dependensi 3GB, dan saya setuju dengan reuse kode, tapi dependensi di sisi JSON milik serde kelihatan cukup berantakan
    Kalau salah satu dependensi itu punya exploit, setengah ekosistem Rust jadi rentan
    Rust seharusnya punya JSON bawaan

    • Dependensinya cuma 5, salah satunya opsional, dan satu lagi adalah serde sendiri: https://github.com/serde-rs/json/blob/master/Cargo.toml
      indexmap = { version = "2.2.3", optional = true }
      itoa = "1.0"
      memchr = { version = "2", default-features = false }
      ryu = "1.0"
      serde = { version = "1.0.194", default-features = false }
      Saat menyebut dependensi 3GB, kemungkinan besar yang benar-benar diukur bukan itu
      Saya tidak bisa yakin karena ini disampaikan sebagai fakta tanpa bukti, tapi dugaan saya mereka banyak memakai #[derive(Serialize, Deserialize)] sehingga banyak kode yang dihasilkan, lalu mengukur ukuran seluruh direktori target
      Build sederhana hasilnya ada di kisaran puluhan MB seperti ditunjukkan komentar lain
    • Saya rasa memasukkan JSON ke Rust bukan pendekatan yang masuk akal
      Itu hanya cara untuk membawa pembengkakan masuk, dan standard library tidak punya kelebihan dibanding crate lain selain jaminan stabilitas
      Hasil akhirnya hanya membuat siklus rilis library terikat ke siklus rilis compiler
      Dulu rustc-serialize memang nyaris seperti bawaan, jadi Rust sebenarnya sudah pernah mencoba arah itu
      Dan dalam keadaan default, serde_json tidak besar
      serde_json maupun serde tidak besar, dan keduanya juga mempertahankan MSRV yang sangat rendah yang tidak didukung baik oleh crate lain, jadi praktis mereka juga tidak bisa punya banyak dependensi
    • Pembengkakan dependensi memang masalah Rust secara umum
      Pohon dependensi proyek Rust yang ukurannya lumayan cepat sekali jadi mengerikan, mengaudit semua dependensi ini secara realistis mustahil, dan tingkat kepercayaan terhadap cukup banyak di antaranya juga rendah
      Setelah beberapa tahun bekerja dengan Rust, saya rasa saya tidak akan menyentuh Rust lagi sampai ekosistemnya jauh lebih matang
      Kematangan itu mungkin baru datang lewat adopsi perusahaan besar, atau kalau tidak ya hanya dipakai untuk proyek no-std, no-deps, pengganti C murni
      Tapi jika Zig sudah stabil, bahkan di use case ini pun Rust bisa tersingkir
    • Rust mengeluarkan informasi debug dalam jumlah yang tidak normal
      Besarnya begitu aneh sampai saya menduga itu cuma bug
      Apa pun yang dikompilasi akan menumpuk hingga ukuran gigabyte di folder target, tapi itu tidak mewakili artefak akhir setelah informasi debug dibuang atau setidaknya dikurangi detailnya
    • Untuk proyek yang ukurannya lumayan, rasanya folder target memang secara harfiah hampir selalu minimal beberapa GB