Jangan jatuh ke dalam perangkap optimasi prematur

Donald Knuth pernah mengatakan kata-kata yang kemudian menjadi terkenal: "Masalah sebenarnya adalah bahwa programmer, bukan di mana mereka perlu, dan bukan ketika mereka perlu, menghabiskan terlalu banyak waktu untuk merawat efisiensi. Optimalisasi prematur adalah akar dari semua kejahatan (atau setidaknya sebagian besar dari mereka) dalam pemrograman. "



Penulis bahan, terjemahan yang kami terbitkan hari ini, ingin berbicara tentang bagaimana ia pernah jatuh ke dalam perangkap optimasi prematur, dan bagaimana ia memahami dari pengalaman pahitnya sendiri bahwa optimasi prematur adalah akar dari semua kejahatan.

Game GeoArena Online

Beberapa tahun yang lalu saya mengerjakan game web GeoArena Online (kemudian saya menjualnya , pemilik baru mempostingnya di geoarena.io ). Itu adalah permainan multipemain dengan gaya "selamat terakhir". Di sana, pemain mengendalikan kapal, bertarung satu lawan satu melawan pemain lain.


Game GeoArena Online


Game GeoArena Online

Sebuah permainan yang dinamis, dunia yang penuh dengan partikel dan efek, membutuhkan sumber daya komputasi yang serius. Akibatnya, permainan di beberapa komputer lama "melambat" di saat-saat menegangkan. Saya, seorang pria yang tidak acuh terhadap masalah produktivitas, mengambil solusi untuk masalah ini dengan penuh minat. “Bagaimana cara mempercepat bagian JavaScript sisi klien GeoArena,” saya bertanya pada diri sendiri.

Perpustakaan Fast.js

Setelah mencari sedikit di Internet, saya menemukan perpustakaan fast.js. Itu adalah "kumpulan optimasi mikro yang bertujuan menyederhanakan pengembangan program JavaScript yang sangat cepat." Pustaka ini dipercepat oleh ketersediaan implementasi yang lebih cepat dari metode standar bawaan seperti Array.prototype.forEach () .

Saya menemukan ini sangat menarik. GeoArena menggunakan banyak array, melakukan banyak operasi dengan array, jadi menggunakan fast.js bisa sangat membantu saya dalam mempercepat permainan. Hasil studi kinerja forEach() berikut dimasukkan dalam README untuk fast.js.

 Native .forEach() vs fast.forEach() (10 items)  ✓ Array::forEach() x 8,557,082 ops/sec ±0.37% (97 runs sampled)  ✓ fast.forEach() x 8,799,272 ops/sec ±0.41% (97 runs sampled)  Result: fast.js is 2.83% faster than Array::forEach(). 

Bagaimana metode yang diterapkan di beberapa perpustakaan eksternal menjadi lebih cepat daripada versi standarnya? Masalahnya adalah bahwa ada satu trik (mereka, trik ini, ditemukan di mana pun Anda melihat). Perpustakaan hanya cocok untuk bekerja dengan array yang tidak jarang.

Berikut adalah beberapa contoh sederhana dari array tersebut:

 //  -  :   1  . const sparse1 = [0, , 1]; console.log(sparse1.length); // 3 //  -   const sparse2 = []; // ...   - .   0 - 4    . sparse2[5] = 0; console.log(sparse2.length); // 6 

Untuk memahami mengapa perpustakaan tidak dapat bekerja secara normal dengan array jarang, saya melihat ke dalam kode sumbernya. Ternyata implementasi forEach() di fast.js didasarkan pada for loop. Implementasi cepat metode forEach() akan terlihat seperti ini:

 //     . function fastForEach(array, f) {  for (let i = 0; i < array.length; i++) {    f(array[i], i, array);  } } const sparseArray = [1, , 2]; const print = x => console.log(x); fastForEach(sparseArray, print); //  print() 3 . sparseArray.forEach(print); //  print()  2 . 

Panggilan ke metode fastForEach() tiga nilai:

 1 undefined 2 

Memanggil sparseArray.forEach() hanya mengarah pada kesimpulan dari dua nilai:

 1 2 

Perbedaan ini disebabkan oleh fakta bahwa spesifikasi JS mengenai penggunaan fungsi panggilan balik menunjukkan bahwa fungsi tersebut tidak boleh dipanggil pada indeks array jarak jauh atau tidak diinisialisasi (juga disebut "lubang"). fastForEach() tidak memeriksa array untuk lubang. Hal ini menyebabkan peningkatan kecepatan dengan biaya kerja yang benar dengan array yang jarang. Ini sempurna bagi saya, karena array jarang tidak digunakan di GeoArena.

Pada titik ini, saya harus melakukan tes cepat pada fast.js. Saya harus menginstal perpustakaan, mengubah metode standar objek Array ke metode dari fast.js dan menguji kinerja permainan. Tetapi sebaliknya, saya bergerak ke arah yang sama sekali berbeda.

Perkembangan saya disebut fast.js

Manik perfeksionis yang hidup dalam diri saya ingin benar-benar memeras segalanya dari mengoptimalkan kinerja permainan. Perpustakaan fast.js bagi saya sepertinya bukan solusi yang cukup baik, karena penggunaannya secara tersirat memanggil metode-metodenya. Kemudian saya berpikir: “Bagaimana jika saya mengganti metode standar array dengan hanya menanamkan implementasi baru yang lebih cepat dari metode ini dalam kode? Itu akan menyelamatkan saya dari kebutuhan akan panggilan metode perpustakaan. ”

Ide inilah yang membawa saya ke ide cerdik, yaitu untuk membuat kompiler, yang saya sebut dengan lebih cepat . Saya berencana untuk menggunakannya daripada fast.js. Misalnya, berikut ini cuplikan kode sumber:

 //   const arr = [1, 2, 3]; const results = arr.map(e => 2 * e); 

Compiler fast.js akan mengonversi kode ini ke yang berikut - lebih cepat, tetapi terlihat lebih buruk:

 //      faster.js const arr = [1, 2, 3]; const results = new Array(arr.length); const _f = (e => 2 * e); for (let _i = 0; _i < arr.length; _i++) {  results[_i] = _f(arr[_i], _i, arr); } 

Penciptaan fast.js didorong oleh ide yang sama yang mendukung fast.js. Yaitu, kita berbicara tentang optimasi mikro kinerja karena penolakan dukungan untuk array jarang.

Pada pandangan pertama, lebih cepat. Saya melihat perkembangan yang sangat sukses bagi saya. Berikut adalah beberapa hasil dari studi kinerja fast.js:

   array-filter large    ✓ native x 232,063 ops/sec ±0.36% (58 runs sampled)    ✓ faster.js x 1,083,695 ops/sec ±0.58% (57 runs sampled) faster.js is 367.0% faster (3.386μs) than native  array-map large    ✓ native x 223,896 ops/sec ±1.10% (58 runs sampled)    ✓ faster.js x 1,726,376 ops/sec ±1.13% (60 runs sampled) faster.js is 671.1% faster (3.887μs) than native  array-reduce large    ✓ native x 268,919 ops/sec ±0.41% (57 runs sampled)    ✓ faster.js x 1,621,540 ops/sec ±0.80% (57 runs sampled) faster.js is 503.0% faster (3.102μs) than native  array-reduceRight large    ✓ native x 68,671 ops/sec ±0.92% (53 runs sampled)    ✓ faster.js x 1,571,918 ops/sec ±1.16% (57 runs sampled) faster.js is 2189.1% faster (13.926μs) than native 

Hasil tes lengkap dapat ditemukan di sini . Mereka ditahan di Node v8.16.1, pada MacBook Pro 2018 15-inci.

Apakah perkembangan saya 2000% lebih cepat dari implementasi standar? Peningkatan produktivitas yang serius seperti itu, tanpa diragukan lagi, adalah sesuatu yang dapat memiliki dampak positif terkuat pada program apa pun. Benar?
Tidak, tidak benar.

Pertimbangkan contoh sederhana.

• Bayangkan bahwa rata-rata game GeoArena membutuhkan 5.000 milidetik (ms) perhitungan.
• Compiler fast.js mempercepat eksekusi metode array dengan rata-rata 10 kali (ini adalah perkiraan perkiraan, apalagi, itu terlalu tinggi; dalam sebagian besar aplikasi nyata bahkan tidak ada akselerasi ganda).

Dan inilah pertanyaan yang sangat menarik bagi kita: “Bagian mana dari 5000 ms yang dihabiskan untuk implementasi metode array?”.

Misalkan setengah. Artinya, 2500 ms dihabiskan untuk metode array, sisanya 2500 ms untuk yang lainnya. Jika demikian, maka menggunakan fast.js akan memberikan peningkatan kinerja yang sangat besar.


Contoh bersyarat: waktu pelaksanaan program sangat berkurang

Hasilnya, ternyata total waktu komputasi telah berkurang sebesar 45%.

Sayangnya, semua argumen ini sangat, sangat jauh dari kenyataan. GeoArena, tentu saja, menggunakan banyak metode array. Tetapi distribusi aktual dari waktu eksekusi kode untuk tugas yang berbeda terlihat seperti berikut ini.


Realitas yang keras

Sedihnya, apa yang bisa saya katakan.

Ini persis kesalahan yang Donald Knuth ingatkan. Saya tidak berusaha untuk menerapkannya, dan saya tidak melakukannya saat itu layak dilakukan.

Di sini matematika sederhana ikut berperan. Jika sesuatu hanya membutuhkan 1% dari waktu pelaksanaan program, maka mengoptimalkannya akan memberikan, dalam kasus terbaik, hanya peningkatan 1% dalam produktivitas.

Ini persis seperti apa yang ada dalam benak Donald Knuth ketika dia berkata "tidak di tempat yang dibutuhkan." Dan jika Anda berpikir tentang apa "di mana Anda membutuhkannya", ternyata ini adalah bagian dari program yang mewakili hambatan kinerja. Ini adalah potongan-potongan kode yang memberikan kontribusi signifikan terhadap kinerja keseluruhan program. Di sini konsep "produktivitas" digunakan dalam arti yang sangat luas. Ini mungkin termasuk runtime program, ukuran kode yang dikompilasi, dan sesuatu yang lain. Peningkatan 10% pada bagian program yang sangat memengaruhi kinerja lebih baik daripada peningkatan 100% dalam beberapa hal kecil.

Knut juga berbicara tentang penerapan upaya "tidak bila perlu." Intinya adalah Anda perlu mengoptimalkan sesuatu hanya saat diperlukan. Tentu saja, saya punya alasan yang bagus untuk memikirkan pengoptimalan. Tapi ingat saya mulai berkembang lebih cepat. Saya dan sebelum itu saya bahkan tidak mencoba menguji perpustakaan fast.js di GeoArena? Menit dihabiskan untuk menguji fast.js dalam game saya akan menghemat saya minggu kerja. Saya harap Anda tidak jatuh ke dalam perangkap yang sama dengan yang saya alami.

Ringkasan

Jika Anda tertarik untuk bereksperimen dengan fast.js, Anda dapat melihat demo ini . Hasil apa yang Anda dapatkan tergantung pada perangkat dan browser Anda. Di sini, misalnya, apa yang terjadi di Chrome 76 pada MacBook Pro 2018 15-inci.


Hasil tes Faster.js

Anda mungkin tertarik untuk mempelajari tentang hasil aktual menggunakan fast.js di GeoArena. Saya, ketika permainan masih milik saya (seperti yang saya katakan, saya menjualnya), melakukan beberapa penelitian dasar. Hasilnya, ternyata yang berikut ini:

• Menggunakan fast.js mempercepat eksekusi siklus game utama dalam game tipikal sekitar 1%.
• Karena penggunaan fast.js, ukuran bundel game meningkat sebesar 0,3%. Ini sedikit memperlambat pemuatan halaman game. Ukuran bundel telah tumbuh karena fakta bahwa fast.js mengubah kode pendek standar menjadi lebih cepat, tetapi juga kode yang lebih panjang.

Secara umum, fast.js memiliki pro dan kontra, tetapi pengembangan tambang ini tidak memiliki banyak dampak pada kinerja GeoArena. Saya akan mengerti ini jauh sebelumnya jika saya repot-repot untuk menguji permainan menggunakan fast.js.

Semoga kisah saya menjadi peringatan bagi Anda.

Pembaca yang budiman! Apakah Anda jatuh ke dalam perangkap optimasi prematur?