jsongrep yang lebih cepat daripada jq

 (micahkepe.com)
17 poin oleh GN⁺ 24 hari lalu | 3 komentar | Bagikan ke WhatsApp
  • Alat CLI Rust untuk menelusuri dokumen JSON berbasis path, dengan kecepatan pencarian lebih tinggi daripada jq, jmespath, jsonpath-rust, dan jql
  • Mengungkapkan kueri sebagai bahasa reguler lalu mengompilasinya ke DFA, dan menelusuri pohon JSON dalam satu pass sehingga diproses dalam waktu O(n)
  • Menggunakan serde_json_borrow yang mendukung zero-copy parsing untuk meminimalkan alokasi memori, dan dirancang dengan mengacu pada filosofi performa ripgrep
  • Hasil benchmark menunjukkan performa end-to-end terbaik bahkan pada JSON berukuran besar, serta menyediakan bahasa kueri sederhana yang berfokus pada pencarian
  • Dirilis dengan lisensi MIT, dan mesin kueri berbasis DFA-nya dapat digunakan ulang sebagai library Rust

Gambaran umum jsongrep

  • jsongrep adalah alat CLI berbasis Rust untuk mencari nilai dalam dokumen JSON berdasarkan path, dengan target performa lebih cepat daripada jq, jmespath, jsonpath-rust, dan jql
  • Dokumen JSON dipandang sebagai pohon, lalu path diekspresikan sebagai bahasa reguler (regular language), dikompilasi menjadi DFA (Deterministic Finite Automaton), dan ditelusuri dalam satu pass
  • Bahasa kuerinya sederhana dan dirancang berfokus pada pencarian, tanpa fitur transformasi atau perhitungan
  • Meminimalkan alokasi memori melalui zero-copy parsing dengan serde_json_borrow
  • Dikembangkan dengan merujuk pada filosofi desain dan pendekatan performa ripgrep

Contoh penggunaan jsongrep

  • Perintah jg menerima kueri dan input JSON, lalu menampilkan semua nilai yang path-nya cocok dengan kueri
  • Akses field bertingkat dengan dot notation (dot path)
    • jg 'roommates[0].name' → "Alice"
  • Wildcard (*, [*]) untuk mencocokkan semua key atau indeks
  • Alternation (|) untuk memilih salah satu dari beberapa path
  • Pencarian rekursif ((* | [*])*) untuk mencari field pada kedalaman sembarang
  • Optional (?) mendukung pencocokan 0 atau 1 kali
  • Opsi -F memungkinkan pencarian nama field tertentu dengan cepat
  • Saat menggunakan pipe (| less, | sort), output path otomatis disembunyikan, dan dapat dipaksa tampil dengan --with-path

Konsep inti jsongrep

  • JSON adalah struktur pohon, dan key objek serta indeks array berperan sebagai edge
  • Kueri mendefinisikan kumpulan path dari root ke node tertentu
  • Bahasa kueri dirancang sebagai bahasa reguler sehingga dapat diubah menjadi DFA
  • DFA membaca input hanya sekali dan menelusuri dalam waktu O(n) tanpa backtracking
  • Alat yang sudah ada (jq, jmespath, dll.) meng-interpretasi kueri dan menelusuri secara rekursif, sedangkan jsongrep melakukan penelusuran satu pass dengan DFA yang telah dikompilasi sebelumnya

Struktur mesin kueri berbasis DFA

  • Pipeline terdiri dari 5 tahap
    1. Parse JSON menjadi pohon dengan serde_json_borrow
    2. Parse kueri menjadi AST
    3. Bangun NFA dengan algoritme Glushkov
    4. Ubah ke DFA dengan Subset Construction
    5. Telusuri pohon JSON dengan satu DFS mengikuti transisi DFA

  • Parsing kueri

    • Tata bahasa PEG (menggunakan library pest) mengubah kueri menjadi AST Query
    • Elemen sintaks utama: Field, Index, Range, FieldWildcard, ArrayWildcard, Optional, KleeneStar, Disjunction, Sequence
    • Contoh: roommates[*].name → Sequence(Field("roommates"), ArrayWildcard, Field("name"))

  • Model pohon JSON

    • Key objek dan indeks array adalah edge, nilai adalah node
    • Contoh: roommates[*].name menelusuri path roommates → [0] → name

  • Konstruksi NFA (algoritme Glushkov)

    • Membangun NFA tanpa transisi ε
    • Tahapan
      1. Memberi nomor posisi pada simbol kueri
      2. Menghitung himpunan First/Last/Follows
      3. Menyusun transisi antar posisi
    • Contoh kueri roommates[*].name menghasilkan NFA sederhana linear dengan 4 status

  • Konversi DFA (Subset Construction)

    • Membentuk DFA deterministik berdasarkan himpunan status NFA
    • Setiap status berkorespondensi dengan satu himpunan status NFA
    • Menambahkan simbol Other untuk melewati key yang tidak diperlukan secara efisien
    • Kueri sederhana dikonversi menjadi DFA dengan struktur yang sama seperti NFA

  • Penelusuran berbasis DFS

    • Mulai dari root dan melakukan transisi DFA di sepanjang setiap edge
    • Jika tidak ada transisi, subtree terkait akan dipangkas (prune)
    • Jika status DFA accepting, path dan nilainya dicatat
    • Setiap node dikunjungi paling banyak satu kali, sehingga seluruh penelusuran O(n)
    • serde_json_borrow mereferensikan buffer asli tanpa menyalin string

Metodologi benchmark

  • Benchmark berbasis statistik dilakukan dengan Criterion.rs

  • Dataset

    • simple.json (106B), kubernetes-definitions.json (~992KB), kestra-0.19.0.json (~7.6MB), citylots.json (~190MB)

  • Alat pembanding

    • jsongrep, jsonpath-rust, jmespath, jaq, jql

  • Grup benchmark

    1. document_parse: kecepatan parsing JSON
    2. query_compile: waktu kompilasi kueri
    3. query_search: hanya melakukan pencarian
    4. end_to_end: seluruh pipeline

  • Pertimbangan fairness

    • Keunggulan zero-copy parsing diukur secara terpisah
    • Biaya kompilasi DFA diukur secara terpisah
    • Alat yang tidak memiliki fitur terkait dikecualikan dari pengujian tersebut
    • Biaya duplikasi data ditangani secara terpisah

Hasil benchmark

  • Waktu parsing dokumen: serde_json_borrow adalah yang tercepat
  • Waktu kompilasi kueri: jsongrep menimbulkan biaya terbesar karena pembuatan DFA, sedangkan jmespath jauh lebih cepat
  • Waktu pencarian: jsongrep paling cepat di antara semua alat
  • Performa end-to-end: bahkan pada dataset 190MB, jauh lebih unggul daripada jq, jmespath, jsonpath-rust, dan jql
  • Hasil lengkap dapat dilihat di situs benchmark live

Lisensi dan pemanfaatan

  • Perangkat lunak open source dengan lisensi MIT
  • Tersedia di GitHub, Crates.io, dan Docs.rs
  • Mesin kueri berbasis DFA dapat digunakan ulang sebagai library, dan bisa diintegrasikan langsung ke proyek Rust

Referensi

  • Glushkov, V. M. (1961), The Abstract Theory of Automata
  • Rabin, M. O., & Scott, D. (1959), Finite Automata and Their Decision Problems

Bacaan terkait

3 komentar

 
roxie 18 hari lalu

Keren sekali.
 
lamanus 24 hari lalu

| Kenapa tanda pipe terlihat berbeda di isi teks? Menarik juga..
 
GN⁺ 24 hari lalu
Komentar Hacker News

  • Sintaks jq terlalu sulit dipahami, jadi setiap kali hanya ingin mengambil satu nilai JSON sederhana pun saya harus mencarinya lagi

    • Menarik. Buat saya, sintaks jq terasa intuitif, dan saya sudah terbiasa hanya memakai titik, pipe, dan tanda kurung siku seperti pipeline shell
      Saya biasanya menulis filter sekali pakai, jadi waktu menulis lebih banyak daripada waktu membaca
      Mungkin use case saya memang sederhana, atau jq memang cocok dengan cara berpikir saya
      Saya memimpikan dunia di mana semua alat CLI menerima dan mengeluarkan JSON lalu dirangkai dengan jq, tapi sepertinya itu akan terasa seperti mimpi buruk bagi Anda
    • Saya tidak cukup sering memakai jq, jadi ini adalah alat yang terus berada di "lembah pembelajaran"
      Setiap kali memakainya, saya harus belajar lagi dari awal, jadi tidak terasa intuitif
      Bahkan meski sed Turing complete, kebanyakan orang tetap hanya memakainya untuk substitusi regex sederhana
    • Saya merekomendasikan celq yang saya buat
      Saya suka jq, tetapi pernah ada saat saya sendiri tidak paham kueri yang pernah saya tulis sebelumnya
      celq memakai bahasa CEL yang terasa lebih familier
    • Saya juga membuat sendiri alat bernama dq karena alasan serupa
      Intinya hanya menangani JSON dengan JavaScript, dan anehnya justru lebih cepat daripada jq
      Dipakai seperti ini: $ cat package.json | dq 'Object.keys(data).slice(0, 5)'
    • JSON sendiri terasa merepotkan karena punya noise sintaksis yang tidak perlu
      Setelah belajar Clojure, sekarang saya memakai EDN alih-alih JSON
      Lebih ringkas, lebih mudah dibaca, dan lebih mudah ditangani secara struktural
      Akhir-akhir ini saya mengolah data dengan borkdude/jet atau babashka, lalu memvisualisasikannya dengan djblue/portal
      Saya tidak paham kenapa orang tetap bersikeras memakai operator jq yang rumit

  • Saya peduli pada performa, tetapi perbandingan di level nanodetik terasa seperti performance theater
    Dalam kebanyakan kasus, alat yang saya pakai sekarang sudah cukup
    Misalnya, saya hanya memakai rg alih-alih grep saat menangani file besar

    • Kalau Anda merasa seperti itu, cukup pikirkan saja, “Saya bukan target user-nya”
      Selisih antara 2ms dan 0,2ms mungkin tampak sepele, tetapi bagi orang yang memproses stream skala TB itu penting
    • Tapi kalau semua orang berpikir begitu, pada akhirnya inefisiensi kecil akan menumpuk dan membuat semuanya melambat
      Hardware makin cepat, tetapi software justru terasa makin lambat
    • Kalau jq ingin benar-benar menonjol, ia perlu sintaks yang intuitif dan lebih banyak contoh dunia nyata
    • Ucapan “sudah cukup cepat” selalu sedikit mengganggu saya
      Menolak optimisasi terasa seperti kemalasan dan kurangnya imajinasi
      Merasa aman hanya karena lebih cepat daripada latensi jaringan terdengar seperti alasan pembenaran
    • Saya juga lebih mementingkan usability dan fitur daripada kecepatan
      Jika JSON-nya terlalu besar, sebaiknya gunakan format biner alih-alih JSON
      Kalau di CLI sampai harus menyusun pipeline yang rumit, menurut saya lebih baik sekalian menulis program

  • Banyak alat CLI baru menjual diri dengan klaim “lebih cepat”, tetapi hampir tidak pernah saya merasa jq itu lambat

    • Saya menangani file ndjson skala TB
      Pekerjaan sederhana seperti hanya mengganti nama field dengan jq pun terlalu lambat, jadi saya memprosesnya langsung dengan skrip Node atau Rust
    • Saat menangani file log yang sangat besar, jq memang bisa terasa lambat
      Di lingkungan hyperscaler, orang mengunduh log beberapa TB lalu menganalisisnya langsung
    • Kami mem-parsing respons JSON dari ribuan node
      Tergantung resolusi monitoring, perbedaan performa bisa benar-benar terasa
    • Setiap kali alat baru muncul, polanya selalu berulang: “versi lebih cepat yang ditulis ulang dengan Rust”
      Biasanya hanya mengimplementasikan sebagian fitur lalu mengklaim menang lewat benchmark
      Proyek kali ini juga terlihat sebagai bagian dari tren "subset lebih cepat" itu
    • Anda baru sadar sebuah alat lambat ketika benar-benar mulai terasa lambat
      Setelah itu semuanya akan terasa lambat
      Seperti ripgrep, sekali Anda memakai alat yang cepat, sulit untuk kembali

  • Saya sudah memakai jq dan yq, tetapi meski yq jauh lebih lambat, saya tidak pernah merasa terganggu
    Kalau ada alat yang lebih cepat daripada jq, keren juga, tetapi itu hanya dibutuhkan oleh segmen pengguna tertentu
    Meski begitu, sebagai orang yang mencintai optimisasi, saya tetap menghormatinya

    • Saya penasaran yq yang mana — versi Go atau versi Python?
    • Di lingkungan integrasi server, performa memang penting, tetapi untuk CLI biasanya sudah cukup cepat
    • Saya memproses GeoJSON beberapa GB hasil ekspor ArcGIS dengan jq
      Pada tahap ETL, itu memang memakan waktu cukup lama
    • Tidak semua orang memakai alat dengan cara yang sama

  • Saat pertama membuka halaman, ada warna light mode yang rusak
    Kalau ganti ke dark mode lalu balik lagi, masalahnya hilang

    • Situsnya juga terasa seperti dibuat dengan gaya "vibe-coded"
    • Saya penulisnya, saya memang tidak memakai light mode jadi lupa mengetesnya, akan segera saya perbaiki
    • Ternyata masalahnya karena sebagian style dark mode bocor dari CSS
    • Di Android Firefox tampilannya baik-baik saja, tetapi skala chart tidak konsisten jadi sulit dibandingkan
    • Sekarang sudah diperbaiki

  • Saya pindah ke Jaq karena alasan akurasi
    Katanya performanya juga lebih baik daripada jq

    • Terima kasih atas rekomendasinya. jaq tampaknya berkembang lebih jauh ke arah yang benar dibanding jsongrep
    • Hanya saja, meski jaq 3.0 lebih cepat daripada jq versi distro, jq yang dibangun sendiri ternyata lebih cepat
      Reputasi jq sebagai alat yang lambat tampaknya lebih banyak disebabkan masalah packaging distribusi

  • Dalam pekerjaan saya, saya sering menangani newline-delimited JSON (jsonl)
    Tiap baris adalah objek JSON lengkap, dan saya penasaran apakah alat-alat CLI utama mendukung format ini

  • Saya sudah memakai berbagai alat CLI pemrosesan data seperti jq, mlr, htmlq, xsv, yq, dan lain-lain,
    tetapi sejak menemukan Nushell, semuanya tergantikan
    Rasanya segar bisa menangani semua format dengan satu sintaks yang sama

    • Saya juga sudah memakai Nushell sebagai shell utama sejak pertengahan 2023
      Saya hanya tetap memakai jq, yq, dan mlr saat perlu kolaborasi dengan rekan kerja
    • Saya juga mengganti hampir semuanya dengan Nushell
      Ada sedikit ketidaknyamanan pada konfigurasi autocomplete dan kemudahan pencarian perintah, tetapi jauh lebih baik daripada oh-my-zsh
      Kalau nanti ada enforcement anotasi tipe, kompilasi biner statis, dan library TUI, saya mungkin akan memakainya juga untuk menulis aplikasi kecil
    • Saya setuju. Nushell membuat otomasi jauh lebih mudah berkat sintaks yang intuitif dan konsisten

  • Alat yang keren! Hanya saja visualisasi benchmark-nya agak kurang
    Semua alat memakai warna yang sama, jadi sulit menemukan jsongrep di mana
    jq sendiri juga tidak ada di grafik, jadi agak membingungkan
    File xLarge berukuran 190MiB terasa masih kecil; saya sendiri sering menangani JSON 400MiB sampai 1GiB

    • Saya penulisnya. Saat ini cakupan benchmark sekitar 106B sampai 190MB
      Kalau ada dokumen JSON publik yang lebih besar, saya akan senang jika diberi tahu

  • Visualisasi benchmark-nya terasa agak kasar
    Akan lebih baik jika memakai warna atau bentuk untuk menyampaikan lebih banyak dimensi
    Harus membaca path file secara langsung untuk memahami hasilnya terasa kurang nyaman