Seberapa cepat Kotlin mem-parsing dan apa bedanya? JavaCC atau ANTLR? Apakah kode sumber JetBrains cocok?

Bandingkan, berfantasi dan heran.

tl; dr

JetBrains terlalu sulit untuk diseret, ANTLR hype tetapi tiba-tiba lambat, dan JavaCC terlalu dini untuk dihapuskan.

Parsing file Kotlin sederhana dengan tiga implementasi berbeda:

1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8
1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8
1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8
1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8
1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8

Suatu hari yang cerah ...

Saya memutuskan untuk membangun penerjemah di GLSL dari beberapa bahasa yang nyaman. Idenya adalah untuk memprogram shader secara langsung dalam ide tersebut dan mendapatkan dukungan IDE "gratis" - sintaks, debug, dan tes unit. Ternyata sangat nyaman .

Sejak saat itu, gagasan untuk menggunakan Kotlin tetap ada - Anda dapat menggunakan nama vec3 di dalamnya, lebih ketat dan lebih nyaman dalam IDE. Selain itu, ini hype. Meskipun, dari sudut pandang manajer internal saya, ini semua adalah alasan yang tidak mencukupi, ide itu muncul berulang kali sehingga saya memutuskan untuk menyingkirkannya hanya dengan mengimplementasikannya.

Kenapa tidak Jawa? Tidak ada operator yang kelebihan, jadi sintaks dari aritmatika vektor akan terlalu berbeda dari yang biasa Anda lihat di game dev

Otak Jet

Orang-orang dari JetBrains mengunggah kode kompiler mereka ke github . Cara menggunakannya, Anda bisa mengintip di sini dan di sini .

Pada awalnya saya menggunakan parser mereka bersama dengan analyzer, karena untuk menerjemahkan ke bahasa lain, Anda perlu tahu apa jenis variabel itu tanpa secara eksplisit menentukan jenis val x = vec3() . Di sini jenis pembaca sudah jelas, tetapi dalam AST informasi ini tidak mudah diperoleh, terutama ketika variabel lain ada di sebelah kanan, atau pemanggilan fungsi.

Di sini saya kecewa. Peluncuran pertama pengurai pada file primitif membutuhkan waktu 3 detik (TIGA DETIK).

Kotlin JetBrains parser
first call elapsed : 3254.482ms
min time in next 10 calls: 70.071ms
min time in next 100 calls: 29.973ms
min time in next 1000 calls: 16.655ms
Whole time for 1111 calls: 40.888756 seconds

Waktu seperti itu memiliki ketidaknyamanan yang jelas berikut:

1. karena ditambah tiga detik untuk meluncurkan game atau aplikasi.
2. selama pengembangan, saya menggunakan kelebihan shader panas dan melihat hasilnya segera setelah mengubah kode.
3. Saya sering me-restart aplikasi dan senang bahwa itu dimulai cukup cepat (satu atau dua detik).

Ditambah tiga detik untuk memanaskan parser - ini tidak bisa diterima. Tentu saja, segera menjadi jelas bahwa selama panggilan berikutnya, waktu parsing turun menjadi 50 ms dan bahkan 20 ms, yang menghilangkan (hampir) ketidaknyamanan No. 2 dari ekspresi. Tetapi dua lainnya tidak pergi ke mana pun. Selain itu, 50ms per file ditambah 2500ms per 50 file (satu shader adalah 1-2 file). Bagaimana jika itu Android? (Di sini kita hanya berbicara tentang waktu.)

Yang perlu diperhatikan adalah karya gila JIT. Waktu parsing untuk file sederhana turun dari 70ms ke 16ms. Yang berarti, pertama, JIT itu sendiri menghabiskan sumber daya, dan kedua, hasil pada JVM yang berbeda bisa sangat berbeda.

Dalam upaya untuk mencari tahu dari mana angka-angka ini berasal, ada opsi - gunakan parser mereka tanpa penganalisa. Bagaimanapun, saya hanya perlu mengatur jenis dan ini dapat dilakukan dengan relatif mudah, sedangkan analisa JetBrains melakukan sesuatu yang jauh lebih kompleks dan mengumpulkan lebih banyak informasi. Dan kemudian waktu mulai turun setengah (tapi hampir satu setengah detik masih layak), dan waktu panggilan berikutnya sudah jauh lebih menarik - dari 8 ms dalam sepuluh pertama hingga 0,9 ms di suatu tempat dalam ribuan.

Kotlin JetBrains parser (without analyzer) ()
first call elapsed : 1423.731ms
min time in next 10 calls: 8.275ms
min time in next 100 calls: 2.323ms
min time in next 1000 calls: 0.974ms
Whole time for 1111 calls: 3.6884801 seconds
()
first call elapsed : 1423.731ms
min time in next 10 calls: 8.275ms
min time in next 100 calls: 2.323ms
min time in next 1000 calls: 0.974ms
Whole time for 1111 calls: 3.6884801 seconds

Saya harus mengumpulkan hanya angka-angka seperti itu. Waktu peluncuran pertama adalah penting saat memuat shader pertama. Ini penting, karena di sini Anda tidak dapat mengalihkan perhatian pengguna saat shader dimuat di latar belakang, ia hanya menunggu. Penurunan runtime penting untuk melihat dinamika itu sendiri, cara kerja JIT, seberapa efisien kita dapat memuat shader pada aplikasi yang hangat.

Alasan utama untuk melihat parser JetBrains terutama adalah keinginan untuk menggunakan pengetik mereka. Tetapi karena menolak itu menjadi opsi yang dibahas, Anda dapat mencoba menggunakan parser lain. Selain itu, non-JetBrains kemungkinan besar akan jauh lebih kecil, lebih sedikit menuntut lingkungan, lebih mudah dengan dukungan dan dimasukkannya kode dalam proyek.

ANTLR

Tidak ada parser di JavaCC, tetapi pada hype ANTLR, seperti yang diharapkan, ada ( satu , dua ).

Tapi yang tak terduga adalah kecepatan. 3s yang sama untuk memuat (panggilan pertama) dan 140ms fantastis untuk panggilan berikutnya. Di sini, bukan hanya peluncuran pertama yang berlangsung lama yang tidak menyenangkan, tetapi situasinya tidak diperbaiki. Rupanya, orang-orang dari JetBrains melakukan sihir dengan membiarkan JIT mengoptimalkan kode mereka seperti itu. Karena ANTLR tidak dioptimalkan sama sekali dari waktu ke waktu.

Kotlin ANTLR parser ()
first call elapsed : 3705.101ms
min time in next 10 calls: 139.596ms
min time in next 100 calls: 138.279ms
min time in next 1000 calls: 137.20099ms
Whole time for 1111 calls: 161.90619 seconds
()
first call elapsed : 3705.101ms
min time in next 10 calls: 139.596ms
min time in next 100 calls: 138.279ms
min time in next 1000 calls: 137.20099ms
Whole time for 1111 calls: 161.90619 seconds


Javacc

Secara umum, kami terkejut menolak layanan ANTLR. Parsing tidak harus selama itu! Tidak ada ambiguitas kosmis dalam tata bahasa Kotlin, dan saya memeriksanya pada file yang hampir kosong. Jadi, inilah saatnya untuk mengungkap JavaCC lama, menyingsingkan lengan baju Anda, dan masih "melakukannya sendiri dan bagaimana caranya."

Kali ini jumlahnya ternyata diharapkan, meskipun dibandingkan dengan alternatif - secara tak terduga menyenangkan.

Kotlin JavaCC parser ()
first call elapsed : 19.024ms
min time in next 10 calls: 1.952ms
min time in next 100 calls: 0.379ms
min time in next 1000 calls: 0.114ms
Whole time for 1111 calls: 0.38707677 seconds
()
first call elapsed : 19.024ms
min time in next 10 calls: 1.952ms
min time in next 100 calls: 0.379ms
min time in next 1000 calls: 0.114ms
Whole time for 1111 calls: 0.38707677 seconds

Pro tiba-tiba dari parser JavaCC Anda
Tentu saja, alih-alih menulis parser Anda sendiri, saya ingin menggunakan solusi yang sudah jadi. Tetapi yang sudah ada memiliki kerugian besar:

- kinerja (jeda saat membaca shader baru tidak dapat diterima, serta tiga detik pemanasan di awal)
- runtime kotlin besar, saya bahkan tidak yakin apakah mungkin untuk mengemas parser ke dalam produk akhir
- Omong-omong, dalam solusi saat ini dengan Groovy masalah yang sama - runtime membentang

Sedangkan parser JavaCC yang dihasilkan adalah

+ kecepatan luar biasa di awal dan di proses
+ hanya beberapa kelas parser itu sendiri

Kesimpulan

JetBrains terlalu sulit untuk diseret, ANTLR hype tetapi tiba-tiba lambat, dan JavaCC terlalu dini untuk dihapuskan.

Parsing file Kotlin sederhana dengan tiga implementasi berbeda:

1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8
1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8
1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8
1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8
1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8	1000 () JetBrains 3254 16,6 35.3 JetBrains (w/o analyzer) 1423 0,9 35.3 ANTLR 3705 137,2 1.4 JavaCC 19 0,1 0.8

Pada titik tertentu, saya memutuskan untuk melihat ukuran toples dengan semua dependensinya. JetBrains bagus seperti yang diharapkan, tetapi runtime ANTLR memukau dengan ukurannya .
UPDATE: Awalnya, saya menulis 15MB, tetapi seperti yang disarankan dalam komentar, jika Anda menghubungkan antlr4-runtime bukan antlr4, ukuran turun ke nilai yang diharapkan. Meskipun parser JavaCC itu sendiri tetap 10 kali lebih kecil dari ANTLR (jika Anda menghapus semua kode sama sekali, kecuali parser itu sendiri).
Ukuran tabung seperti itu penting, tentu saja, untuk ponsel. Tetapi itu juga penting untuk desktop, karena, pada kenyataannya, itu berarti jumlah kode tambahan yang dapat mengandung bug, yang harus diindeks oleh IDE, yang, pada kenyataannya, mempengaruhi kecepatan beban pertama dan kecepatan pemanasan. Selain itu, untuk kode kompleks, ada sedikit harapan untuk menerjemahkan ke bahasa lain.
Saya tidak mendesak Anda untuk menghitung kilobyte dan saya menghargai waktu dan kenyamanan programmer, tetapi tetap ada baiknya memikirkan penghematan, karena dengan begitu proyek menjadi canggung dan sulit dipertahankan.

Beberapa Kata Tentang ANTLR dan JavaCC

Fitur serius ANTLR adalah pemisahan tata bahasa dan kode. Akan lebih baik jika tidak harus membayar mahal. Ya, dan ini hanya penting untuk “pengembang serial tata bahasa,” dan untuk produk akhir ini tidak begitu penting, karena bahkan tata bahasa yang ada masih harus selesai untuk menulis kode Anda. Plus, jika kita menghemat uang dan mengambil tata bahasa "pihak ketiga" - itu mungkin tidak nyaman, masih perlu dipahami secara menyeluruh, itu akan mengubah pohon itu sendiri. Secara umum, JavaCC, tentu saja, mencampur lalat dan irisan daging, tetapi apakah itu benar-benar penting dan apakah itu sangat buruk?

Fitur lain dari ANTLR adalah banyak platform target. Tapi di sini Anda dapat melihat dari sisi lain - kode dari bawah JavaCC sangat sederhana. Dan sangat sederhana ... siaran! Tepat dengan kode khusus Anda - setidaknya dalam C #, setidaknya dalam JS.

PS

Semua kode ada di sini github.com/kravchik/yast

Hasil parsing adalah pohon yang dibangun di atas YastNode (ini adalah kelas yang sangat sederhana, pada kenyataannya - peta dengan metode yang mudah digunakan dan pengidentifikasi). Tapi YastNode sebenarnya bukan "simpul bulat dalam ruang hampa." Kelas inilah yang saya gunakan secara aktif, berdasarkan itu saya telah mengumpulkan beberapa alat - pengetik, beberapa penerjemah dan pengoptimal / inliner.

Parser JavaCC belum mengandung semua tata bahasa, masih ada 10 persen yang tersisa, tetapi sepertinya itu tidak dapat mempengaruhi kinerja - saya memeriksa kecepatan ketika aturan ditambahkan, dan itu tidak berubah secara nyata. Selain itu, saya sudah melakukan lebih dari yang saya butuhkan dan hanya mencoba untuk membagikan hasil yang tidak terduga yang ditemukan dalam proses.