Menulis kode Javascript berkinerja tinggi tanpa menjadi tidak optimal

10

Saat menulis kode sensitif kinerja dalam Javascript yang beroperasi pada array numerik besar (pikirkan paket aljabar linier, beroperasi pada bilangan bulat atau angka floating-point), orang selalu ingin JIT membantu sebanyak mungkin. Secara kasar ini berarti:

  1. Kami selalu ingin agar array kami dikemas IKM (bilangan bulat kecil) atau dikemas ganda, tergantung pada apakah kita melakukan perhitungan bilangan bulat atau mengambang.
  2. Kami selalu ingin meneruskan jenis hal yang sama ke fungsi, sehingga tidak diberi label "megamorphic" dan dioptimalkan. Sebagai contoh, kami selalu ingin melakukan panggilan vec.add(x, y)dengan keduanya xdan ydikemas array SMI, atau keduanya dikemas array ganda.
  3. Kami ingin fungsi sebaris mungkin.

Ketika seseorang tersesat di luar kasus ini, penurunan kinerja yang tiba-tiba dan drastis terjadi. Ini dapat terjadi karena berbagai alasan yang tidak berbahaya:

  1. Anda dapat mengubah array SMI yang dikemas menjadi Double array yang dikemas melalui operasi yang tampaknya tidak berbahaya, seperti yang setara dengan myArray.map(x => -x). Ini sebenarnya adalah kasus buruk "terbaik", karena paket array ganda masih sangat cepat.
  2. Anda dapat mengubah array yang dikemas menjadi array kotak umum, misalnya dengan memetakan array di atas fungsi yang (atau tidak terduga) dikembalikan nullatau undefined. Kasus buruk ini cukup mudah untuk dihindari.
  3. Anda dapat menonaktifkan seluruh fungsi seperti vec.add()dengan memasukkan terlalu banyak jenis benda dan mengubahnya menjadi megamorphic. Ini bisa terjadi jika Anda ingin melakukan "pemrograman generik", di mana vec.add()digunakan baik dalam kasus di mana Anda tidak berhati-hati tentang jenis (sehingga terlihat banyak jenis masuk) dan dalam kasus di mana Anda ingin meningkatkan kinerja maksimal (Misalnya, hanya menerima ganda kotak).

Pertanyaan saya lebih merupakan pertanyaan lunak, tentang bagaimana seseorang menulis kode Javascript berkinerja tinggi dengan mempertimbangkan pertimbangan-pertimbangan di atas, sambil tetap menjaga kodenya bagus dan mudah dibaca. Beberapa sub-pertanyaan spesifik sehingga Anda tahu jawaban seperti apa yang saya tuju:

  • Apakah ada seperangkat pedoman di suatu tempat tentang cara memprogram sementara tetap di dunia array SMI dikemas (misalnya)?
  • Apakah mungkin untuk melakukan pemrograman umum berkinerja tinggi di Javascript tanpa menggunakan sesuatu seperti sistem makro untuk vec.add()menyejajarkan hal-hal seperti ke dalam callsites?
  • Bagaimana cara modularisasi kode kinerja tinggi menjadi perpustakaan dalam hal-hal seperti situs panggilan megamorphic dan deoptimisasi? Misalnya, jika saya dengan senang hati menggunakan paket Aljabar Linier Adengan kecepatan tinggi, dan kemudian saya mengimpor paket Byang tergantung A, tetapi Bmemanggilnya dengan tipe lain dan mendeoptimisasinya, tiba-tiba (tanpa kode saya berubah) kode saya berjalan lebih lambat.
  • Apakah ada alat pengukuran yang baik dan mudah digunakan untuk memeriksa apa yang dilakukan mesin Javascript secara internal dengan tipe?
Joppy
sumber
1
Itu topik yang sangat menarik, dan posting yang ditulis dengan sangat baik yang menunjukkan Anda telah melakukan bagian riset dengan benar. Namun saya khawatir pertanyaan (s) terlalu luas untuk format SO, dan juga bahwa itu pasti akan menarik lebih banyak pendapat daripada fakta. Optimasi kode adalah masalah yang sangat rumit, dan dua versi mesin mungkin tidak berlaku sama. Saya pikir ada salah satu orang yang bertanggung jawab untuk V8 JIT yang kadang-kadang bergaul, jadi mungkin mereka bisa memberikan jawaban yang tepat untuk mesin mereka, tetapi bahkan bagi mereka, saya pikir itu akan menjadi subjek yang terlalu luas untuk satu Q / A .
Kaiido
"Pertanyaan saya lebih merupakan pertanyaan lunak, tentang bagaimana seseorang menulis kode Javascript berkinerja tinggi ..." Sebagai tambahan, perhatikan bahwa javascript menyediakan untuk pemunculan proses latar belakang (pekerja web), dan ada juga perpustakaan yang memanfaatkan penawaran GPU (tensorflow.js dan gpu.js) selain berarti hanya mengandalkan kompilasi untuk meningkatkan throughput komputasi aplikasi berbasis javascript ...
Jon Trent
@ JonTrent Sebenarnya saya berbohong sedikit di posting saya, saya tidak terlalu peduli untuk aplikasi aljabar linear klasik, tetapi lebih untuk aljabar komputer di atas bilangan bulat. Ini berarti bahwa banyak paket numerik yang ada segera dikesampingkan, karena (misalnya) sementara pengurangan baris matriks mereka dapat membaginya dengan 2, yang "tidak diizinkan" di dunia tempat saya bekerja sejak (1/2) bukan bilangan bulat. Saya telah mempertimbangkan pekerja web (terutama untuk beberapa komputasi lama yang ingin saya batalkan), tetapi masalah yang saya bahas di sini adalah menurunkan latensi yang cukup untuk responsif pada interaksi.
Joppy
Untuk aritmatika integer dalam JavaScript, Anda mungkin melihat kode gaya asm.js, kira-kira "meletakkan di |0belakang setiap operasi". Ini tidak cantik, tetapi yang terbaik yang dapat Anda lakukan dalam bahasa yang tidak memiliki bilangan bulat yang tepat. Anda juga bisa menggunakan BigInts, tetapi pada hari ini mereka tidak terlalu cepat di salah satu mesin umum (kebanyakan karena kurangnya permintaan).
jmrk

Jawaban:

8

Pengembang V8 di sini. Mengingat besarnya minat pada pertanyaan ini, dan kurangnya jawaban lain, saya bisa mencoba ini; Saya khawatir itu tidak akan menjadi jawaban yang Anda harapkan.

Apakah ada seperangkat pedoman di suatu tempat tentang cara memprogram sementara tetap di dunia array SMI dikemas (misalnya)?

Jawaban singkat: itu di sini: const guidelines = ["keep your integers small enough"].

Jawaban yang lebih panjang: memberikan serangkaian pedoman yang komprehensif sulit karena berbagai alasan. Secara umum, pendapat kami adalah bahwa pengembang JavaScript harus menulis kode yang masuk akal bagi mereka dan kasus penggunaannya, dan pengembang mesin JavaScript harus mengetahui cara menjalankan kode itu dengan cepat di mesin mereka. Di sisi lain, jelas ada beberapa batasan untuk ideal itu, dalam arti bahwa beberapa pola pengkodean akan selalu memiliki biaya kinerja yang lebih tinggi daripada yang lain, terlepas dari pilihan implementasi mesin dan upaya optimasi.

Ketika kita berbicara tentang saran kinerja, kita mencoba mengingatnya, dan dengan hati-hati memperkirakan rekomendasi apa yang memiliki kemungkinan tinggi untuk tetap berlaku di banyak mesin dan bertahun-tahun, dan juga cukup idiomatis / tidak mengganggu.

Kembali ke contoh yang ada: menggunakan Smis secara internal seharusnya merupakan detail implementasi yang tidak perlu diketahui oleh kode pengguna. Ini akan membuat beberapa kasus lebih efisien, dan tidak boleh sakit dalam kasus lain. Tidak semua mesin menggunakan Smis (misalnya, AFAIK Firefox / Spidermonkey secara historis belum; Saya pernah mendengar bahwa untuk beberapa kasus mereka menggunakan Smis hari ini, tapi saya tidak tahu detailnya dan tidak dapat berbicara dengan otoritas apa pun tentang masalah). Dalam V8, ukuran Smis adalah detail internal, dan sebenarnya telah berubah seiring waktu dan versi. Pada platform 32-bit, yang dulunya adalah case penggunaan terbanyak, Smis selalu menjadi bilangan bulat bertanda 31-bit; pada platform 64-bit, mereka dulunya adalah integer bertanda 32-bit, yang baru-baru ini tampak seperti kasus yang paling umum, sampai di Chrome 80 kami mengirimkan "kompresi pointer" untuk arsitektur 64-bit, yang membutuhkan penurunan ukuran Smi menjadi 31 bit yang dikenal dari platform 32-bit. Jika Anda kebetulan telah mendasarkan implementasi pada asumsi bahwa Smis biasanya 32 bit, Anda akan mendapatkan situasi yang kurang menguntungkan sepertiini .

Untungnya, seperti yang Anda perhatikan, array ganda masih sangat cepat. Untuk kode numerik-berat, mungkin masuk akal untuk menganggap / menargetkan array ganda. Mengingat prevalensi ganda dalam JavaScript, masuk akal untuk mengasumsikan bahwa semua mesin memiliki dukungan yang baik untuk ganda dan array ganda.

Apakah mungkin untuk melakukan pemrograman umum berkinerja tinggi dalam Javascript tanpa menggunakan sesuatu seperti sistem makro untuk menyejajarkan hal-hal seperti vec.add () ke dalam callsites?

"generik" umumnya bertentangan dengan "kinerja tinggi". Ini tidak terkait dengan JavaScript, atau implementasi mesin tertentu.

Kode "Generik" berarti bahwa keputusan harus dibuat saat runtime. Setiap kali Anda menjalankan suatu fungsi, kode harus dijalankan untuk menentukan, katakanlah, "adalah xbilangan bulat? Jika demikian, ambil jalur kode itu. Apakah xsebuah string? Lalu lompat ke sini. Apakah itu sebuah objek? Apakah itu memiliki .valueOf? Tidak? Lalu mungkin .toString()? Mungkin di rantai prototipe? Sebut itu, dan mulai ulang dari awal dengan hasilnya ". Kode yang dioptimalkan "berkinerja tinggi" pada dasarnya dibangun di atas ide untuk membatalkan semua pemeriksaan dinamis ini; itu hanya mungkin ketika mesin / kompiler memiliki beberapa cara untuk menyimpulkan jenis sebelumnya: jika itu dapat membuktikan (atau berasumsi dengan probabilitas cukup tinggi) yang xselalu akan menjadi bilangan bulat, maka hanya perlu menghasilkan kode untuk kasus tersebut ( dijaga oleh tipe cek jika asumsi yang tidak terbukti terlibat).

Inlining adalah ortogonal untuk semua ini. Fungsi "generik" masih bisa disorot. Dalam beberapa kasus, kompiler mungkin dapat menyebarkan informasi tipe ke dalam fungsi inline untuk mengurangi polimorfisme di sana.

(Sebagai perbandingan: C ++, menjadi bahasa yang dikompilasi secara statis, memiliki template untuk menyelesaikan masalah terkait. Singkatnya, mereka membiarkan programmer secara eksplisit menginstruksikan kompiler untuk membuat salinan fungsi khusus (atau seluruh kelas), parameter pada jenis yang diberikan. Itu adalah solusi yang bagus untuk beberapa kasus, tetapi bukan tanpa kekurangannya sendiri, misalnya waktu kompilasi yang panjang dan biner yang besar. JavaScript, tentu saja, tidak memiliki template. Anda dapat menggunakan evaluntuk membangun sistem yang agak mirip, tetapi kemudian Anda akan mengalami kekurangan serupa: Anda harus melakukan yang setara dengan pekerjaan kompiler C ++ saat runtime, dan Anda harus khawatir tentang banyaknya jumlah kode yang Anda hasilkan.)

Bagaimana cara modularisasi kode kinerja tinggi menjadi perpustakaan dalam hal-hal seperti situs panggilan megamorphic dan deoptimisasi? Misalnya, jika saya dengan senang hati menggunakan paket Aljabar Linier A dengan kecepatan tinggi, dan kemudian saya mengimpor paket B yang bergantung pada A, tetapi B menyebutnya dengan tipe lain dan mendeoptimisasinya, tiba-tiba (tanpa kode saya berubah) kode saya berjalan lebih lambat .

Ya, itu masalah umum dengan JavaScript. V8 digunakan untuk mengimplementasikan builtin tertentu (hal-hal seperti Array.sort) dalam JavaScript secara internal, dan masalah ini (yang kami sebut "ketik umpan balik pencemaran") adalah salah satu alasan utama mengapa kami telah sepenuhnya beralih dari teknik itu.

Yang mengatakan, untuk kode numerik, tidak ada semua jenis yang banyak (hanya Smis dan dobel), dan seperti yang Anda catat mereka harus memiliki kinerja yang sama dalam prakteknya, jadi sementara polusi umpan balik jenis memang merupakan masalah teoritis, dan dalam beberapa kasus dapat memiliki dampak signifikan, juga kemungkinan besar dalam skenario aljabar linier Anda tidak akan melihat perbedaan yang terukur.

Juga, di dalam mesin ada lebih banyak situasi daripada "satu jenis == cepat" dan "lebih dari satu jenis == lambat". Jika operasi yang diberikan telah melihat baik Smis maupun ganda, itu sama sekali tidak masalah. Memuat elemen dari dua jenis array juga baik-baik saja. Kami menggunakan istilah "megamorphic" untuk situasi ketika suatu beban telah melihat begitu banyak tipe berbeda sehingga ia dilacak untuk melacaknya secara individu dan sebagai gantinya menggunakan mekanisme yang lebih umum yang dapat menskala dengan lebih baik ke sejumlah besar jenis - fungsi yang mengandung beban seperti itu dapat masih bisa dioptimalkan. "Deoptimisasi" adalah tindakan yang sangat spesifik karena harus membuang kode yang dioptimalkan untuk suatu fungsi karena jenis baru terlihat yang belum pernah dilihat sebelumnya, dan oleh karena itu kode yang dioptimalkan tidak diperlengkapi untuk menangani. Tetapi itu pun tidak masalah: cukup kembali ke kode yang tidak dioptimalkan untuk mengumpulkan lebih banyak jenis umpan balik, dan optimalkan lagi nanti. Jika ini terjadi beberapa kali, maka tidak ada yang perlu dikhawatirkan; itu hanya menjadi masalah dalam kasus patologis yang buruk.

Jadi ringkasan dari semua itu adalah: jangan khawatir tentang hal itu . Cukup tulis kode yang masuk akal, biarkan mesin menanganinya. Dan dengan "masuk akal", maksud saya: apa yang masuk akal untuk use case Anda, dapat dibaca, dipelihara, menggunakan algoritma yang efisien, tidak mengandung bug seperti membaca di luar array. Idealnya, hanya itu yang ada, dan Anda tidak perlu melakukan hal lain. Jika itu membuat Anda merasa lebih baik untuk melakukan sesuatu , dan / atau jika Anda benar-benar mengamati masalah kinerja, saya dapat menawarkan dua ide:

Menggunakan TypeScript dapat membantu. Peringatan besar: tipe-tipe TypeScript ditujukan untuk produktivitas pengembang, bukan kinerja eksekusi (dan ternyata, kedua perspektif tersebut memiliki persyaratan yang sangat berbeda dari sistem tipe). Yang mengatakan, ada beberapa tumpang tindih: misalnya jika Anda secara konsisten membubuhi keterangan hal-hal sebagai number, maka kompiler TS akan memperingatkan Anda jika Anda secara tidak sengaja dimasukkan nullke dalam array atau fungsi yang seharusnya hanya berisi / beroperasi pada angka. Tentu saja, disiplin masih diperlukan: number_func(random_object as number)pintu keluar tunggal dapat secara diam-diam merusak segalanya, karena kebenaran jenis anotasi tidak ditegakkan di mana pun.

Menggunakan TypedArrays juga dapat membantu. Mereka memiliki overhead yang lebih kecil (konsumsi memori dan kecepatan alokasi) per array dibandingkan dengan array JavaScript biasa (jadi jika Anda memerlukan banyak array kecil, maka array reguler mungkin lebih efisien), dan mereka kurang fleksibel karena mereka tidak dapat tumbuh atau menyusut setelah alokasi, tetapi mereka memberikan jaminan bahwa semua elemen memiliki tepat satu jenis.

Apakah ada alat pengukuran yang baik dan mudah digunakan untuk memeriksa apa yang dilakukan mesin Javascript secara internal dengan tipe?

Tidak, dan itu disengaja. Seperti yang dijelaskan di atas, kami tidak ingin Anda secara khusus menyesuaikan kode Anda dengan pola apa pun yang dapat dioptimalkan dengan baik oleh V8 hari ini, dan kami juga tidak percaya bahwa Anda benar-benar ingin melakukannya juga. Seperangkat hal itu dapat berubah di kedua arah: jika ada pola yang ingin Anda gunakan, kami dapat mengoptimalkannya dalam versi yang akan datang (kami sebelumnya bermain-main dengan gagasan menyimpan bilangan bulat 32-bit tanpa kotak sebagai elemen larik .. (tetapi pekerjaan yang belum dimulai, jadi tidak ada janji); dan kadang-kadang jika ada pola yang kami optimalkan sebelumnya, kami mungkin memutuskan untuk membatalkannya jika itu menghalangi optimasi lain yang lebih penting / berdampak. Juga, hal-hal seperti inur heuristik terkenal sulit untuk diperbaiki, jadi membuat keputusan inlining yang tepat pada waktu yang tepat adalah bidang penelitian yang sedang berlangsung dan perubahan yang sesuai dengan perilaku engine / compiler; yang membuat ini kasus lain di mana itu akan disayangkan bagi semua orang (Andadan kami) jika Anda menghabiskan banyak waktu mengutak-atik kode Anda sampai beberapa versi browser saat ini melakukan keputusan yang menurut Anda (atau tahu?) adalah yang terbaik, hanya untuk kembali setengah tahun kemudian untuk menyadari bahwa browser saat itu telah mengubah heuristik mereka.

Anda dapat, tentu saja, selalu mengukur kinerja aplikasi Anda secara keseluruhan - itulah yang pada akhirnya penting, bukan pilihan apa yang dibuat mesin secara internal. Waspadalah terhadap microbenchmark, karena mereka menyesatkan: jika Anda hanya mengekstrak dua baris kode dan membandingkannya, maka kemungkinan skenario tersebut akan cukup berbeda (misalnya, umpan balik tipe yang berbeda) sehingga mesin akan membuat keputusan yang sangat berbeda.

jmrk
sumber
2
Terima kasih atas jawaban yang luar biasa ini, itu menegaskan banyak kecurigaan saya tentang bagaimana segala sesuatu bekerja, dan yang penting bagaimana mereka dimaksudkan untuk bekerja. Omong-omong, apakah ada posting blog dll tentang masalah "ketik umpan balik" yang Anda sebutkan Array.sort()? Saya ingin membaca sedikit tentang itu.
Joppy
Saya tidak berpikir kami telah membuat blog tentang aspek tertentu. Ini pada dasarnya adalah apa yang Anda jelaskan dalam pertanyaan Anda sendiri: ketika builtin diimplementasikan dalam JavaScript, mereka "seperti perpustakaan" dalam arti bahwa jika potongan kode yang berbeda memanggil mereka dengan tipe yang berbeda, maka kinerjanya dapat menurun - terkadang hanya sedikit, terkadang lebih. Itu bukan satu-satunya, dan bahkan bisa dibilang bukan masalah terbesar dengan teknik itu; Saya kebanyakan hanya ingin mengatakan bahwa saya akrab dengan masalah umum.
jmrk