Membangun Parser JSON Berkinerja Tinggi

 (dave.cheney.net)
1 poin oleh GN⁺ 2023-11-06 | 1 komentar | Bagikan ke WhatsApp
  • Presentasi GopherCon Singapore 2023 dari Dave Cheney membahas proses desain untuk membuat parser JSON streaming di Go yang mempertahankan API mirip encoding/json, tetapi meningkatkan throughput dan mengurangi alokasi
  • JSON tidak memiliki penanda panjang, sehingga input harus dibaca sampai akhir; batas bawah performanya minimal read(N)+parse(N), jadi kendala utamanya adalah mengurangi kunjungan ulang byte/token, penyalinan, alokasi, dan pemanggilan fungsi di hot path
  • encoding/json.Decoder.Token mengembalikan token sebagai interface{}, yang praktis, tetapi nilai konkret akan escape ke heap sehingga menghasilkan alokasi yang sebanding dengan jumlah token, dan bahkan untuk satu token "hello" terjadi 3 allocs/op
  • pkg/json mengurangi biaya hot path melalui NextToken yang mengembalikan sub-slice []byte dari input, sliding window pada byteReader, inlining manual, pemanggilan langsung metode state, dan penghapusan bounds check
  • Pada akhirnya, pkg/json.Scanner melakukan tokenisasi tanpa alokasi jika diberi buffer, Decoder.Token 2–3 kali lebih cepat daripada encoding/json.Decoder.Token, dan Decoder.NextToken yang alokasinya lebih sedikit menunjukkan performa 8–10 kali lebih cepat

Tujuan dan batasan dasar

  • Tujuannya adalah membuat parser JSON berkinerja tinggi sebagai studi desain paket Go
  • Sasaran desainnya ada tiga
    • Mendukung pemrosesan streaming tanpa memuat seluruh input ke memori
    • Memberikan throughput lebih tinggi dan alokasi lebih sedikit sambil tetap cukup kompatibel dengan API tingkat tinggi json.Decoder dari encoding/json
    • Menyediakan API yang lebih efisien, tanpa alokasi atau dengan batas alokasi, di luar API encoding/json
  • Jika seluruh input terlebih dahulu di-buffer ke memori, akan muncul risiko ketersediaan ketika ukuran input tidak diketahui atau tak terbatas, dan latensi sebelum pemrosesan juga meningkat
  • Pembacaan streaming memproses data segera saat tiba, dan dapat menumpangtindihkan pembacaan dengan pemrosesan

Kompleksitas waktu parsing JSON

  • JSON tidak memiliki penanda panjang, sehingga untuk mengetahui berapa banyak yang harus dibaca, seluruh input harus dibaca
  • Untuk mem-parse elemen ke-1.000 dalam array JSON, 999 elemen sebelumnya juga harus dibaca dan diproses, sehingga pemrosesan input tidak bisa dilewati
  • Batas bawah performa berbanding lurus dengan ukuran input; bukan hanya membaca sederhana, karena harus melewati state machine JSON untuk menemukan awal dan akhir token, sehingga minimal menjadi read(N)+parse(N)
  • Kriteria untuk mengurangi biaya tambahan adalah sebagai berikut
    • Jika N byte telah dibaca, setiap byte sebisa mungkin diproses hanya sekali
    • Token yang sama juga diproses hanya sekali
    • Di hot path Scanner atau Decoder, batasi jumlah pemanggilan fungsi menjadi O(tokens), bukan O(bytes)
    • Kurangi penyalinan untuk mengurangi jumlah kunjungan ulang ke byte yang sama
    • Kurangi alokasi untuk menurunkan biaya alokasi heap, akses struktur data bersama, lock, kontensi cache, dan GC

Tokenisasi dan desain API

  • Decoder JSON secara garis besar terbagi menjadi dua tahap
    • Scanner atau tokenizer yang mengubah stream byte menjadi stream token JSON
    • Unmarshaller yang menerapkan stream token JSON ke objek Go
  • encoding/json.Decoder.Token mengembalikan token sebagai interface{}
    • String direpresentasikan sebagai string, angka sebagai float64, boolean sebagai bool, null sebagai nil, dan delimiter sebagai json.Delim
    • Pendekatan ini nyaman digunakan karena merepresentasikan nilai dan tipe token sekaligus
  • Kenyamanan memiliki biaya
    • Brad Fitzpatrick menyebut Token API sebagai garbage factory
    • Karena desain API Decoder.Token, nilai konkret yang dialokasikan untuk tiap token escape ke heap
    • Jumlah alokasi terikat pada jumlah token dalam input
  • Dalam benchmark untuk satu token "hello", encoding/json menunjukkan 355ns/op, 19.7MB/s, 37.0B/op, 3.00 allocs/op
  • Desain API menentukan alokasi, dan alokasi dapat berdampak langsung pada performa

Token []byte dan informasi tipe implisit

  • Tipe token JSON dapat diketahui hanya dari karakter pertamanya
    • {, }: awal dan akhir objek
    • [, ]: awal dan akhir array
    • t: true
    • f: false
    • n: null
    • ": string
    • -, 0~9: angka
  • API Decoder.NextToken dari pkg/json tidak mengubah input []byte menjadi nilai Go, melainkan mengembalikan byte yang mewakili token langsung sebagai sub-slice dari input
  • Byte pertama dari []byte yang dikembalikan menunjukkan tipe token
  • API ini memiliki batasan
    • Output bukan salinan, melainkan sub-slice dari input, sehingga ada batasan masa berlaku
    • Ini mirip dengan API bufio.Scanner
    • Untuk menangani tipe token atau nilai string/angka aktual dengan lebih nyaman, diperlukan abstraksi tingkat lebih tinggi

Pembacaan efisien: byteReader

  • Pendekatan tradisional io.Reader.Read menyalin data dari reader ke buffer, dan penyalinan ini sendiri memiliki biaya
  • io.Reader.Read menyerahkan pengelolaan buffer kepada pemanggil
    • Jika membaca byte demi byte, mungkin diperlukan ruang untuk menyimpan atau memutar balik byte yang telah dilewati
    • Pendekatan membaca ke buffer besar lalu mencari awal dan akhir token membutuhkan banyak pengelolaan, penyalinan, dan perluasan buffer ketika akhir token tidak ada di dalam buffer
  • Sebagai alternatif, digunakan byteReader yang terinspirasi oleh iopipe dari Steven Schveighoffer dan ide Phil Pearl
  • byteReader menyediakan sliding window di atas io.Reader, mirip dengan bufio.Reader tetapi dengan API yang lebih efisien
    • window() mengembalikan jendela data yang saat ini belum dibaca
    • release(n) membuang n byte di bagian depan jendela
    • extend() membaca lebih banyak data dari reader di bawahnya untuk memperluas jendela
  • Benchmark pencarian whitespace adalah baseline yang mengunjungi setiap karakter dan hanya memeriksa apakah karakter tersebut whitespace; pada berbagai input hasilnya sekitar 2.04–2.07GB/s
  • Contoh kode penghitung whitespace ada di github.com/davecheney/whitespace

Optimasi scanner

  • Scanner.Next melewati whitespace di antara token, menentukan token dari karakter pertama pada jendela, lalu membaca hingga akhir token
  • Performa awal Scanner.Next sekitar 1/4 hingga 2/5 dari baseline whitespace
    • Contoh: Scanner/canada 510MB/s, citm_catalog 677MB/s, sample 837MB/s
  • Optimasi pertama adalah mengganti pembaruan field s.offset dengan variabel lokal offset
    • s.offset bernilai 0 saat masuk dan keluar fungsi, sehingga perubahan internal tidak terlihat dari luar
    • Dengan menggunakan variabel lokal, compiler menghindari penulisan memori sementara
    • citm_catalog turun dari 2.52ms menjadi 1.80ms, berkurang 28.46%; sample turun dari 828µs menjadi 528µs, berkurang 36.24%
  • Alasan efeknya berbeda untuk tiap input adalah perbedaan jumlah whitespace
    • canada hanya memiliki 33 whitespace
    • citm memiliki 1.227.563 whitespace
  • Optimasi kedua adalah manual inlining Scanner.token ke dalam Scanner.Next
    • Compiler Go tidak dapat meng-inline otomatis Scanner.token, parseString, parseNumber, Scanner.Next, dan lainnya karena loop for serta kompleksitas fungsi
    • Scanner.Next dan Scanner.token dipanggil untuk setiap token input, sehingga ada biaya dua pemanggilan fungsi per token
  • Setelah manual inlining, throughput meningkat 9–24%
    • canada naik dari 512MB/s menjadi 642MB/s, meningkat 24.50%
    • citm_catalog naik dari 960MB/s menjadi 1105MB/s, meningkat 15.16%
    • sample naik dari 1.33GB/s menjadi 1.46GB/s, meningkat 9.11%
  • Efek optimasi dapat dirangkum menjadi dua hal
    • Pembaruan s.offset dikurangi dari 1 kali per byte menjadi 1 kali per token
    • Menghindari pemanggilan fungsi di hot path dapat meningkatkan performa

Validasi dan Decoder.NextToken

  • Scanner saja dapat memisahkan token, tetapi pemrosesan JSON lengkap memerlukan validasi state
  • JSON adalah state machine, dan token yang dapat muncul berikutnya dibatasi oleh token saat ini
    • Misalnya, setelah membaca {, "username", hanya : yang valid
  • Decoder.NextToken menambahkan logika state di atas Scanner.Next untuk memastikan urutan token valid
  • State dibagi menjadi value, string key objek, kolon objek, value objek, koma objek, value array, koma array, state selesai, dan sebagainya
  • Bahkan pada implementasi validasi awal, pkg/json menunjukkan hasil 8–10 kali lebih cepat daripada encoding/json
    • canada: pkg/json 399MB/s, encoding/json 34.6MB/s
    • citm_catalog: pkg/json 713MB/s, encoding/json 87.1MB/s
    • sample: pkg/json 1.23GB/s, encoding/json 216MB/s

Optimasi transisi state

  • Di pusat Decoder.NextToken terdapat pernyataan switch
  • switch umum dapat diimplementasikan seperti serangkaian pernyataan if, sehingga rangkaian cabang yang panjang memecah instruction stream dan membebani branch predictor CPU
  • Ada juga cara menggunakan tabel untuk mencari metode state dari nilai state, tetapi contoh implementasinya tidak dikompilasi karena loop inisialisasi
  • Sebagai gantinya, digunakan method expression Go untuk menyimpan metode langsung di d.state, bukan enum state
    • Decoder.NextToken memanggil metode state saat ini secara langsung, seperti return d.state(d, tok)
  • Pendekatan computed goto ini saja tidak banyak meningkatkan performa
    • Beberapa input hampir tidak berubah, dan pada twitter, code, example justru sedikit lebih lambat
    • sample menjadi 1.15% lebih cepat
  • Perubahan ini memungkinkan optimasi berikutnya, yaitu outlining

Outlining dan penghapusan bounds check

  • Setelah outlining, Decoder.NextToken hanya melakukan return d.state(d), dan setiap metode state langsung memanggil d.scanner.Next()
  • Karena tok tidak diteruskan sebagai argumen metode state, call stack berkurang 3 words
  • Pemeriksaan len(tok) < 1 dan switch tok[0] berada dalam fungsi yang sama, sehingga penghapusan bounds check menjadi mungkin
    • Sebelumnya, pemeriksaan len(tok) berada di Decoder.NextToken, sedangkan metode state dipanggil melalui method expression dan tidak di-inline
    • Karena itu, tok[0] di metode state memerlukan bounds check
    • Jika pemeriksaan panjang dilakukan dalam fungsi yang sama, compiler dapat membuktikan bahwa panjang tok minimal 1
  • Decoder.NextToken sendiri juga menjadi sederhana sehingga bisa di-inline
    • Pemanggil pada dasarnya melihat pemanggilan langsung ke metode state saat ini, bukan dec.NextToken()
    • Biaya pemanggilan fungsi dihilangkan

Hasil benchmark akhir

  • pkg/json.Scanner level terendah melakukan tokenisasi streaming tanpa alokasi jika diberi buffer beberapa KB
    • canada: 638.78MB/s, 0 B/op, 0 allocs/op
    • citm_catalog: 1110.51MB/s, 0 B/op, 0 allocs/op
    • sample: 1471.01MB/s, 0 B/op, 0 allocs/op
  • pkg/json.Decoder.Token 2–3 kali lebih cepat daripada encoding/json.Decoder.Token
    • canada: 101.98MB/s vs 33.19MB/s
    • citm_catalog: 333.23MB/s vs 82.71MB/s
    • sample: 788.59MB/s vs 209.12MB/s
  • pkg/json.Decoder.NextToken memiliki alokasi jauh lebih sedikit dan 8–10 kali lebih cepat
    • canada: 466.52MB/s, 136 B/op, 3 allocs/op vs 34.42MB/s, 17.740.399 B/op, 889.106 allocs/op
    • citm_catalog: 798.58MB/s, 136 B/op, 3 allocs/op vs 86.08MB/s, 5.661.597 B/op, 324.692 allocs/op
    • sample: 1346.85MB/s, 1144 B/op, 9 allocs/op vs 217.44MB/s, 723.781 B/op, 26.095 allocs/op
  • Pada API level tertinggi, pkg/json dapat melakukan unmarshal ke objek Go dengan cara yang sama seperti encoding/json
    • canada: 82.08MB/s vs 58.70MB/s
    • citm_catalog: 215.66MB/s vs 104.00MB/s
    • sample: 615.99MB/s vs 128.04MB/s
  • Tautan presentasi ada di dave.cheney.net/paste/gophercon-sg-2023.html, dan kodenya ada di github.com/pkg/json

Topik yang didapat dari desain

  • Alokasi memengaruhi performa

    • Walaupun GC mengalokasikan dengan cepat dan mengumpulkan dengan efisien, tidak melakukan alokasi selalu lebih cepat
    • Desain API dapat menghilangkan alokasi
    • Sebagian besar peningkatan kecepatan paket ini berasal dari pengurangan alokasi
    • Waktu yang tidak dihabiskan pada jalur alokasi heap dan siklus GC digunakan untuk scanning
    • API encoding/json.Decoder membutuhkan alokasi karena mengembalikan nilai primitive sebagai interface{}
    • Nilai escape ke heap sehingga pada praktiknya menjadi pointer ke nilai
    • Dalam pemrosesan data, alokasi dapat menjadi biaya performa terbesar dalam algoritme
    • Mengurangi biaya per byte dan per token dengan cermat adalah faktor peningkatan performa terbesar kedua
    • Arah yang penting adalah mengubah pemanggilan fungsi per byte menjadi pemanggilan fungsi per token
    • Berangkat dari asumsi bahwa encoding/json bisa lebih lambat karena API-nya, dan jika API lain dapat diterima, performa 2–3 kali lipat dapat diperoleh pada beberapa jalur unmarshal, serta 8–10 kali lipat pada tokenisasi

Bacaan terkait

1 komentar

 
GN⁺ 2023-11-06
Komentar Hacker News

  • Kelihatannya cukup bagus. Sepanjang karier saya, saya sudah terlalu sering membuat parser JSON, tetapi sangat menyenangkan punya referensi yang menunjukkan langkah demi langkah bagaimana merancang parser JSON yang masuk akal dan cepat
    Namun, JSON tidak benar-benar membutuhkan tokenizer yang eksplisit. Konsep token bisa dihilangkan, lalu parsing dan tokenisasi bisa digabung sepenuhnya. Biasanya memang begitu, dan keseluruhannya jadi lebih sederhana
    Di bahasa seperti ECMAScript ini jauh lebih sulit, karena ada kasus yang tampak seperti subset dari tata bahasa ekspresi bertanda kurung, seperti arrow function, lalu baru dipastikan tergantung apakah => muncul, sehingga bisa memerlukan lookahead sepanjang arbitrer

    • Saya penasaran pekerjaan seperti apa yang membuat seseorang bisa bilang “saya terlalu sering membuat parser JSON” sepanjang kariernya

  • Ini tulisan yang enak diikuti, dan alurnya jelas soal bagaimana melakukannya jika ingin mengimplementasikannya sendiri
    Kalau yang dicari adalah performa murni di lingkungan produksi, Daniel Lemire punya https://github.com/simdjson/simdjson yang juga layak dilihat. Ada juga port Go dari MinIO, https://github.com/minio/simdjson-go

    • Jika bentuk JSON-nya selalu sama, hasilnya mungkin bisa lebih baik daripada parser JSON generik
    • Dulu saat membandingkan performa beberapa parser JSON, parser berbasis SIMD ternyata mengecewakan dan lebih lambat dari perkiraan
    • Library JSON tercepat di Go dibuat oleh perusahaan di balik TikTok
    • simdjson sudah lama sekali bukan yang paling cepat

  • Hal yang saya pelajari saat membuat parser JSON cepat memang banyak dipengaruhi karakteristik tiap bahasa, tetapi kalau digeneralisasi kira-kira begini
    Pada tokenisasi, alokasi heap harus dihindari. Lebih baik tokenizer mengembalikan struct yang dialokasikan di stack, atau fungsi yang mengembalikan token int64 yang memaketkan posisi awal token, panjang, offset tipe, dan sebagainya
    Pada parsing juga sebaiknya menghindari alokasi heap, dan untuk klien yang ingin bekerja dengan potongan buffer bisa didukung antarmuka seperti getString(key String)
    Saat melakukan deserialisasi ke objek yang field-nya diketahui saat kompilasi, biasanya dibuat switch berdasarkan panjang key sebelum membandingkan nilai string
    Di pipeline data yang banyak memproses JSON, hanya dari pemilihan library JSON saja perbedaan performa 3–10x bisa terjadi, dan parser utama umumnya cenderung mengalokasikan objek
    Jika kelas untuk serialisasi/deserialisasi sudah diketahui saat kompilasi, Jackson di Java bekerja cukup baik, tetapi dengan coding yang hati-hati dan profiling biasanya masih bisa didorong sekitar 2x lagi
    Sebaliknya, jika harus menangani JSON arbitrer, parser arus utama cenderung melakukan banyak alokasi, jadi parser yang ditulis sendiri dan lebih intrusif bisa menghindari itu, dan keuntungan performanya sangat besar saat memproses ribuan hingga jutaan objek per detik

  • Saya pernah membuat tokenizer dan parser GraphQL dengan pendekatan serupa, dan ini juga tanpa alokasi memori serta cukup cepat. Kalau penasaran dengan kodenya, lihat https://github.com/wundergraph/graphql-go-tools

    • Karya aneh saya juga mungkin menarik: https://github.com/graph-guard/gqlscan
      Saya juga pernah presentasi soal ini, sayangnya tidak direkam. Saya hampir gila saat mencoba memeras Go semaksimal mungkin :D
    • Saya penasaran seberapa besar masalah ini pada server GQL berbasis allowlist yang semua query-nya sudah diketahui sebelumnya. Hasil parsing AST bisa di-cache atau diingat, jadi rasanya ini cuma jadi masalah performa selama beberapa menit setelah container mulai berjalan
      Atau mungkin ada dampak lain juga?

  • Di n2[1] saya membutuhkan tokenizer cepat, dan mengalami masalah pembuat sampah yang sama. Pada dasarnya ada campuran kumpulan token konstan seperti json.Delim dan string yang memicu alokasi
    Solusi yang menurut saya cukup bagus adalah membuat tokenizer generik terhadap suatu T, lalu menerima fungsi yang mengubah slice byte menjadi T, sehingga yang dipakai adalah T, bukan string
    Dengan begitu pemanggil bisa memberikan representasi yang lebih efisien, misalnya yang lebih sedikit alokasinya, dan pada saat yang sama untuk unit test tokenizer tetap bisa diuji dengan nyaman memakai fungsi identitas
    Dalam arti tertentu ini mirip dengan menggabungkan tokenizer dan parser saat build, tetapi berkat generics, tokenizer tetap bisa menjaga lapisannya tanpa perlu tahu representasi parser
    [1] https://github.com/evmar/n2

  • Dengan desain API yang lebih baik, memang mungkin mengungguli standard library, tetapi saat membuat parser streaming yang benar-benar lengkap, pada praktiknya sulit untuk tidak meninggalkan struct dalam keadaan setengah terisi lalu keluar di tengah jalan sebelum menemukan error. Standard library tampaknya juga menjadikan ini sebagai batasan desain yang eksplisit

  • Mungkin saya melewatkan sesuatu, tetapi penulis berulang kali bilang dia membuat parser “streaming” tanpa menjelaskan apa sebenarnya maksudnya
    Secara khusus, tidak ada penjelasan tentang bagaimana key yang berulang ditangani di “hash table”. Saya penasaran, apakah kode sink dipanggil dua kali saat ada key berulang, atau apakah ia menunggu sampai seluruh “hash table” selesai dibaca baru memanggil kode sink
    Menurut saya JSON itu bersifat hierarkis, panjangnya tidak diketahui sebelumnya, dan yang paling penting ada key berulang, sehingga pada dasarnya tidak cocok untuk streaming
    Memang mungkin membuat sebagian subset JSON lebih ramah streaming, tetapi kalau begitu tidak ada alasan khusus untuk tetap memaksakan JSON. Jika solusinya adalah mengubah JSON, menurut saya format lain yang memang bukan JSON akan lebih baik

  • Senang melihat Phil Pearl disebut
    https://github.com/bytedance/sonic juga patut dilihat

  • Cukup mengejutkan bahwa tidak ada cara untuk mengatakan “tolong inline fungsi ini” pada fungsi yang terlalu besar sehingga tidak di-inline
    Operasi dasar menghitung dan mencari whitespace tampaknya akan jauh lebih cepat jika divektorkan dengan SIMD, tetapi saya paham itu di luar cakupan penulis

    • Tentu saja force inline itu memungkinkan

  • Pernyataan “tidak realistis mengharapkan seluruh input bisa dimuat ke memori” itu tidak benar untuk sebagian besar aplikasi

    • Sebagian besar aplikasi membaca JSON dari jaringan, dan itu adalah stream. Walaupun JSON-nya relatif kecil, jika seluruh request dibuffer ke memori lalu diutak-atik, latensi akan meningkat besar
    • Benar, tetapi untuk aplikasi yang perlu melakukan transformasi ala ETL pada dataset besar, streaming adalah strategi yang sangat berguna
      Mungkin orang bisa bilang Go bukan alat yang tepat untuk pekerjaan itu, tetapi dengan optimasi seperti ini saya rasa tidak ada alasan itu tidak bisa dilakukan
    • Kalau membuat library, kita harus secara eksplisit menyatakan batasannya atau mendukung streaming
      Saya pernah memasukkan data JSON berukuran gigabyte, jadi parser streaming sangat saya hargai. Lagi pula, dukungan streaming juga jadi sinyal bahwa penulis memahami berbagai use case dan punya engineering yang lebih baik
      Memori itu murah dan nyaris gratis hanya dalam teori, bukan di dunia nyata
    • Jika cukup puas dengan “datanya ada di disk”, apakah mmap() bukan juga pilihan yang layak? Itu terpisah dari kasus ketika benar-benar butuh streaming, misalnya saat data di bagian awal file JSON tunggal perlu diproses lebih cepat seperti aliran transaksi atau pekerjaan
    • Apakah body request HTTP juga dianggap sebagai bagian dari input?