Halo, Habr! Saya mempersembahkan untuk Anda terjemahan artikel "Lubang Cacing dalam JavaScript" oleh Mathius Buus.
Komputer adalah mesin yang menarik. Secara teori, mereka bagi kita adalah ahli matematika mekanik ideal yang bekerja dengan angka dan operasi penambahan, perkalian, dan pengurangan yang berkinerja baik.
Namun, abstraksi semacam itu cukup menyesatkan. Ini menjauhkan kita dari pemahaman bahwa komputer memproses operasi matematika yang berbeda dengan kecepatan yang berbeda. Jika Anda menulis dalam JavaScript (atau bahasa lain apa pun) dan peduli dengan kinerja algoritme yang Anda tulis, sangat penting untuk memahami cara kerja komputer di bawah tenda.
Jika kita tahu apa yang mampu dilakukan komputer, kita dapat menggunakan jalur terpendek atau lubang cacing untuk membuat program kita lebih cepat dari yang kita harapkan.
Lubang cacing dalam operasi memperoleh sisa divisi
Apa sebenarnya artinya ini? Mari kita lihat sebuah contoh: bayangkan kita ingin menerapkan daftar cincin . Daftar dering adalah daftar ukuran tetap di mana sisipan yang lebih besar dari ukuran daftar dipindahkan ke bagian atas daftar dan dalam lingkaran. Daftar dering sangat nyaman untuk banyak hal - seperti mengumpulkan statistik untuk interval waktu tertentu, buffering data, dan banyak lagi, tetapi lihat implementasi ini:
const list = new Array(15000) function set (i, item) {
Seberapa cepat kode ini dijalankan? Mari kita jalankan tes kecepatan sederhana
console.time() for (var i = 0; i < 1e9; i++) { set(i, i) } console.timeEnd()
Di komputer saya, butuh ~ 4 detik untuk 1 miliar sisipan. Tidak buruk.
Namun, mari kita terapkan lubang cacing komputasi dan ubah ukuran array menjadi angka ajaib:
// 15000 16384 const list = new Array(16384) function set (i, item) { // % - , // // , i list[i % list.length] = item }
Mari kita coba jalankan tes kinerja lagi. Di komputer saya, tes selesai dalam ~ 1,5 detik. Lebih dari dua kali lipat peningkatan karena ukuran sederhana. Untuk memahami mengapa ini terjadi, kita harus memahami yang berikut, di bawah tenda, komputer bekerja dengan angka dengan basis 2. Penting untuk mengetahui apakah kita mendapatkan sisa pembagian (% operasi). Perhitungan seperti itu jauh lebih sederhana jika jumlahnya adalah kelipatan dari 2 (2 ^ n) b 16384 itu adalah 2 ^ 14. Sebenarnya, komputer melihat angka dalam bentuk biner dan hanya mengambil n bit terakhir.
Sebagai contoh: apa yang akan terjadi ketika operasi seperti itu dilakukan 353 500% 16 384? 353 500 dalam representasi biner akan terlihat seperti 1010110010011011100. Sejak 16384 == 2 ^ 14 - kita perlu mengambil 14 bit terakhir - 10101 (10010011011100) atau 9 346.
Kita bisa menggunakan pengetahuan ini dalam kaitannya dengan lubang cacing lain. Untuk komputer, sangat sederhana dan cepat untuk mengambil n bit terakhir. Bahkan, hanya diperlukan untuk menghasilkan biner dan (operasi &) dengan nomor (2 ^ n) - 1
const list = new Array(16384) function set (i, item) {
Menjalankan tes kinerja lagi di komputer saya, kita akan melihat bahwa waktu eksekusi akan berkurang hingga ~ 1s atau akan ada peningkatan kinerja empat kali lipat dibandingkan dengan yang dijalankan pertama. Dan semua ini karena pemahaman tentang cara kerja komputer.
Smart compiler atau VM dapat melakukan optimasi semacam ini dengan mengubah operasi untuk mendapatkan sisanya di belakang layar menjadi operasi bitwise dan sebaliknya. Bahkan, V8 Javascript VM terbaru (tidak diimplementasikan di NodeJS) melakukan hal itu.
Lubang Cacing Numerik
Millill lain yang bermanfaat adalah memahami cara kerja membaca dan menulis angka. Ingat bagaimana kami menggunakan komputer 32-bit dan bagaimana kami mendapat 64 bit? Dan hingga 32 bit kami memiliki 16 bit. Apa sebenarnya artinya ini? Biasanya kita berpikir seperti ini - berapa banyak RAM yang kita miliki di komputer. 2 ^ 32 = 4294967296 atau 4 GB, yang berarti bahwa kita hanya dapat mengakses 4 GB memori pada komputer 32-bit. Ketika kami menulis program JS, kami biasanya tidak perlu memikirkannya, karena kami biasanya tidak menggunakan banyak memori.
Namun, sangat penting untuk memahami perbedaan antara komputer 32-bit dan 64-bit. Karena prosesor menerima register 64-bit pada komputer 64-bit, operasi menjadi 2 kali lebih cepat daripada pada komputer 32-bit, di mana Anda hanya memiliki register 32-bit.
Bagaimana kita dapat menggunakan informasi tentang lubang cacing ini?
Mari kita menulis sebuah program sederhana yang menyalin satu Uint8Array ke yang lain. Jika Anda tidak terbiasa dengan Unit8Arrays, mereka sangat mirip dengan Buffer di NodeJS, atau hanya "bersihkan" memori.
function copy (input, output) { // input.length <= output.length for (var i = 0; i < input.length; i++) { // 8- (byte) output[i] = input[i] } }
Sekali lagi, mari kita mengukur kecepatan dengan menjalankan tes kinerja.
// 1MB Uint8Arrays const input = new Uint8Array(1024 * 1024) const output = new Uint8Array(1024 * 1024) console.time() for (var i = 0; i < 1e4; i++) { copy(input, output) } console.timeEnd()
Di komputer saya, program diselesaikan dalam ~ 7,5 detik. Bagaimana kita bisa menggunakan lubang cacing untuk mempercepat? Menggunakan Uint8Array, kami hanya menyalin 8 bit pada satu waktu, tetapi dengan komputer 64-bit kami dapat menyalin informasi 64 bit sekaligus. Kita dapat melakukan ini dalam JavaScript dengan mengonversi Uint8Array ke Float64Array sebelum menyalin, yang tidak akan dikenakan biaya apa pun.
function copy (input, output) { // input.length <= output.length // 64- // , // 64- // BigInts JavaScript, BigInt64Array. const input64 = new Float64Array(input.buffer, input.byteOffset, input.length / 8) const output64 = new Float64Array(output.buffer, output.byteOffset, output.length / 8) for (var i = 0; i < input64.length; i++) { // 64- output64[i] = input64[i] } }
Menjalankan tes kinerja lagi, kami mendapatkan runtime 1 detik, yang memberikan peningkatan kecepatan 8 kali lipat.
Untuk menyalin, solusi yang dapat diterima adalah dengan menggunakan metode array.set (otherArray) untuk Uint8Array, yang memberi kita menyalin dalam kode asli - yang jauh lebih cepat daripada lubang cacing lainnya. Sebagai referensi, ini akan memberikan hasil ~ 0,2 detik eksekusi dalam pengujian kami di komputer saya, yang 5 kali lebih cepat dari solusi sebelumnya.
Galaksi JavaScript penuh lubang cacing
Menggunakan lubang cacing di atas akan membantu Anda membuat banyak algoritma dunia nyata jauh lebih cepat. Ada banyak lubang cacing seperti itu. Favorit saya adalah Math.clz32 , sebuah metode yang mengembalikan jumlah bit nol terdepan dalam representasi biner 32-bit dari sebuah angka. Kita dapat menggunakan metode ini untuk banyak algoritma yang menarik. Saya menggunakannya untuk mempercepat implementasi bidang bit sebanyak 4 kali, yang menyebabkan penurunan konsumsi memori sebesar 4 kali dan memungkinkan saya untuk mengurutkan angka dalam beberapa situasi jauh lebih cepat.
Memahami prinsip-prinsip dasar komputer memungkinkan Anda untuk menulis program tercepat yang kami butuhkan. Pengetahuan ini penting bahkan ketika Anda menulis dalam bahasa tingkat tinggi seperti JavaScript.
PS:
Terima kasih khusus untuk bantuan dalam menerjemahkan dan menyesuaikan terjemahan ke Olga Pereverzeva