Jadikan Java cepat: Optimalkan!

Menurut ilmuwan komputer perintis Donald Knuth, "Pengoptimalan dini adalah akar dari segala kejahatan." Setiap artikel tentang pengoptimalan harus dimulai dengan menunjukkan bahwa biasanya ada lebih banyak alasan untuk tidak mengoptimalkan daripada mengoptimalkan.

  • Jika kode Anda sudah berfungsi, mengoptimalkannya adalah cara yang pasti untuk memperkenalkan bug baru, dan mungkin tidak kentara

  • Pengoptimalan cenderung membuat kode lebih sulit untuk dipahami dan dipertahankan

  • Beberapa teknik yang disajikan di sini meningkatkan kecepatan dengan mengurangi ekstensibilitas kode

  • Mengoptimalkan kode untuk satu platform sebenarnya dapat memperburuknya di platform lain

  • Banyak waktu dapat dihabiskan untuk pengoptimalan, dengan sedikit peningkatan kinerja, dan dapat mengakibatkan kode dikaburkan

  • Jika Anda terlalu terobsesi dengan pengoptimalan kode, orang akan menyebut Anda nerd di belakang Anda

Sebelum mengoptimalkan, Anda harus mempertimbangkan dengan cermat apakah Anda perlu mengoptimalkan sama sekali. Pengoptimalan di Java bisa menjadi target yang sulit dipahami karena lingkungan eksekusi bervariasi. Menggunakan algoritme yang lebih baik mungkin akan menghasilkan peningkatan kinerja yang lebih besar daripada sejumlah pengoptimalan tingkat rendah dan lebih cenderung memberikan peningkatan dalam semua kondisi eksekusi. Sebagai aturan, pengoptimalan tingkat tinggi harus dipertimbangkan sebelum melakukan pengoptimalan tingkat rendah.

Jadi, mengapa harus mengoptimalkan?

Jika itu ide yang buruk, mengapa harus mengoptimalkannya? Nah, di dunia yang ideal Anda tidak akan melakukannya. Tetapi kenyataannya adalah terkadang masalah terbesar dengan sebuah program adalah program tersebut membutuhkan terlalu banyak sumber daya, dan sumber daya ini (memori, siklus CPU, bandwidth jaringan, atau kombinasinya) mungkin terbatas. Fragmen kode yang muncul beberapa kali di seluruh program cenderung peka ukuran, sedangkan kode dengan banyak iterasi eksekusi mungkin peka terhadap kecepatan.

Jadikan Java cepat!

Sebagai bahasa yang ditafsirkan dengan bytecode yang ringkas, kecepatan, atau kekurangannya, adalah yang paling sering muncul sebagai masalah di Java. Kami terutama akan melihat bagaimana membuat Java berjalan lebih cepat daripada membuatnya sesuai dengan ruang yang lebih kecil - meskipun kami akan menunjukkan di mana dan bagaimana pendekatan ini memengaruhi memori atau bandwidth jaringan. Fokusnya akan pada bahasa inti daripada pada Java API.

Omong-omong, satu hal yang tidak akan kita bahas di sini adalah penggunaan metode asli yang ditulis dalam C atau assembly. Meskipun menggunakan metode asli dapat memberikan peningkatan kinerja tertinggi, hal itu dilakukan dengan mengorbankan independensi platform Java. Dimungkinkan untuk menulis versi Java dari suatu metode dan versi asli untuk platform yang dipilih; ini mengarah pada peningkatan kinerja pada beberapa platform tanpa melepaskan kemampuan untuk berjalan di semua platform. Tapi ini semua yang akan saya katakan tentang masalah mengganti Java dengan kode C. (Lihat Tip Java, "Menulis metode asli" untuk informasi lebih lanjut tentang topik ini.) Fokus kami dalam artikel ini adalah tentang cara membuat Java cepat.

90/10, 80/20, hut, hut, hike!

Sebagai aturan, 90 persen waktu eksusi program dihabiskan untuk mengeksekusi 10 persen kode. (Beberapa orang menggunakan aturan 80 persen / 20 persen, tetapi pengalaman saya menulis dan mengoptimalkan game komersial dalam beberapa bahasa selama 15 tahun terakhir menunjukkan bahwa rumus 90 persen / 10 persen adalah tipikal untuk program yang haus kinerja karena beberapa tugas cenderung dilakukan dengan frekuensi tinggi.) Mengoptimalkan 90 persen program lainnya (di mana 10 persen dari waktu eksekusi dihabiskan) tidak memiliki efek yang nyata pada kinerja. Jika Anda dapat membuat 90 persen kode itu dieksekusi dua kali lebih cepat, programnya hanya akan menjadi 5 persen lebih cepat. Jadi, tugas pertama dalam mengoptimalkan kode adalah mengidentifikasi 10 persen (seringkali kurang dari ini) program yang menghabiskan sebagian besar waktu eksekusi. Ini bukant selalu seperti yang Anda harapkan.

Teknik pengoptimalan umum

Ada beberapa teknik pengoptimalan umum yang berlaku terlepas dari bahasa yang digunakan. Beberapa dari teknik ini, seperti alokasi register global, adalah strategi canggih untuk mengalokasikan sumber daya mesin (misalnya, register CPU) dan tidak berlaku untuk bytecode Java. Kami akan fokus pada teknik yang pada dasarnya melibatkan restrukturisasi kode dan mengganti operasi yang setara dalam suatu metode.

Pengurangan kekuatan

Pengurangan kekuatan terjadi saat operasi diganti dengan operasi setara yang dijalankan lebih cepat. Contoh paling umum dari pengurangan kekuatan adalah menggunakan operator shift untuk mengalikan dan membagi bilangan bulat dengan pangkat 2. Misalnya, x >> 2dapat digunakan sebagai pengganti x / 4, dan x << 1menggantikan x * 2.

Penghapusan sub ekspresi umum

Penghapusan sub ekspresi umum menghapus penghitungan yang berlebihan. Alih-alih menulis

double x = d * (lim / max) * sx; double y = d * (lim / max) * sy;

sub ekspresi umum dihitung sekali dan digunakan untuk kedua penghitungan:

double depth = d * (lim / max); double x = depth * sx; double y = depth * sy;

Gerakan kode

Kode gerak bergerak kode yang melakukan operasi atau menghitung ekspresi yang hasilnya tidak berubah, atau invarian . Kode dipindahkan sehingga hanya dieksekusi ketika hasilnya mungkin berubah, daripada mengeksekusi setiap kali hasilnya diperlukan. Ini paling umum terjadi pada loop, tetapi juga dapat melibatkan kode yang diulangi pada setiap pemanggilan metode. Berikut ini adalah contoh gerakan kode invarian dalam satu lingkaran:

for (int i = 0; i < x.length; i++) x [i] * = Math.PI * Math.cos (y); 

menjadi

picosy ganda = Math.PI * Math.cos (y); for (int i = 0; i < x.length; i++)x [i] * = picosy;

Loop membuka gulungan

Unrolling loop mengurangi overhead kode kontrol loop dengan melakukan lebih dari satu operasi setiap kali melalui loop, dan akibatnya mengeksekusi iterasi yang lebih sedikit. Bekerja dari contoh sebelumnya, jika kita tahu bahwa panjang x[]selalu merupakan kelipatan dua, kita mungkin menulis ulang loop sebagai:

picosy ganda = Math.PI * Math.cos (y); for (int i = 0; i < x.length; i += 2) {x [i] * = picosy; x [i + 1] * = picosy; }

Dalam praktiknya, membuka gulungan loop seperti ini - di mana nilai indeks loop digunakan dalam loop dan harus ditambah secara terpisah - tidak menghasilkan peningkatan kecepatan yang cukup besar dalam Java yang ditafsirkan karena bytecode tidak memiliki instruksi untuk menggabungkan " +1"ke dalam indeks larik.

Semua kiat pengoptimalan dalam artikel ini mencakup satu atau beberapa teknik umum yang tercantum di atas.

Menggunakan kompiler untuk bekerja

Kompiler C dan Fortran modern menghasilkan kode yang sangat dioptimalkan. Kompiler C ++ umumnya menghasilkan kode yang kurang efisien, tetapi masih berada di jalur yang tepat untuk menghasilkan kode yang optimal. Semua penyusun ini telah melewati banyak generasi di bawah pengaruh persaingan pasar yang kuat dan telah menjadi alat yang terasah untuk memeras setiap penurunan kinerja dari kode biasa. Mereka hampir pasti menggunakan semua teknik pengoptimalan umum yang disajikan di atas. Tetapi masih banyak trik tersisa untuk membuat kompiler menghasilkan kode yang efisien.

javac, JIT, dan kompiler kode asli

Tingkat pengoptimalan yang javacdilakukan saat menyusun kode pada titik ini minimal. Secara default melakukan hal berikut:

  • Pelipatan konstan - kompilator menyelesaikan ekspresi konstan apa pun yang i = (10 *10)dikompilasi ke i = 100.

  • Pelipatan cabang (sebagian besar waktu) - gotobytecode yang tidak perlu dihindari.

  • Penghapusan kode mati terbatas - tidak ada kode yang dihasilkan untuk pernyataan seperti if(false) i = 1.

Tingkat pengoptimalan yang disediakan javac harus meningkat, mungkin secara dramatis, seiring dengan kematangan bahasa dan vendor compiler mulai bersaing dengan sungguh-sungguh berdasarkan pembuatan kode. Java sekarang mendapatkan kompiler generasi kedua.

Lalu ada kompiler just-in-time (JIT) yang mengubah bytecode Java menjadi kode native pada saat dijalankan. Beberapa sudah tersedia, dan meskipun mereka dapat meningkatkan kecepatan eksekusi program Anda secara dramatis, tingkat pengoptimalan yang dapat mereka lakukan dibatasi karena pengoptimalan terjadi pada waktu proses. Kompiler JIT lebih mementingkan pembuatan kode dengan cepat daripada menghasilkan kode tercepat.

Kompiler kode native yang mengompilasi Java langsung ke kode native harus menawarkan performa terbaik tetapi dengan mengorbankan independensi platform. Untungnya, banyak trik yang disajikan di sini akan dicapai oleh kompiler masa depan, tetapi untuk saat ini dibutuhkan sedikit usaha untuk mendapatkan hasil maksimal dari kompilator.

javacmemang menawarkan satu opsi kinerja yang dapat Anda aktifkan: menjalankan -Oopsi untuk menyebabkan compiler menyebariskan panggilan metode tertentu:

javac -O MyClass

Menyebariskan panggilan metode menyisipkan kode untuk metode secara langsung ke dalam kode yang membuat panggilan metode. Ini menghilangkan overhead panggilan metode. Untuk metode kecil, biaya tambahan ini dapat mewakili persentase yang signifikan dari waktu pelaksanaannya. Perhatikan bahwa metode hanya dinyatakan sebagai baik private, staticatau finaldapat dipertimbangkan untuk inlining, karena hanya metode ini statis diselesaikan oleh kompilator. Selain itu, synchronizedmetode tidak akan sebaris. Kompilator hanya akan menyebariskan metode kecil yang biasanya hanya terdiri dari satu atau dua baris kode.

Sayangnya, compiler javac versi 1.0 memiliki bug yang akan menghasilkan kode yang tidak dapat melewati pemverifikasi bytecode saat -Oopsi tersebut digunakan. Ini telah diperbaiki di JDK 1.1. (Pemverifikasi bytecode memeriksa kode sebelum diizinkan untuk dijalankan untuk memastikan bahwa kode tidak melanggar aturan Java apa pun.) Ini akan menyebariskan metode yang mereferensikan anggota kelas yang tidak dapat diakses ke kelas pemanggil. Misalnya, jika kelas berikut dikompilasi bersama menggunakan -Oopsi

kelas A {private static int x = 10; public static void getX () {return x; }} kelas B {int y = A.getX (); }

panggilan ke A. getX () di kelas B akan disisipkan di kelas B seolah-olah B telah ditulis sebagai:

kelas B {int y = Ax; }

Namun, ini akan menyebabkan pembuatan bytecode mengakses variabel private Axe yang akan dibuat dalam kode B. Kode ini akan dijalankan dengan baik, tetapi karena melanggar batasan akses Java, kode ini akan ditandai oleh pemverifikasi IllegalAccessErrorsaat pertama kali kode dijalankan.

Bug ini tidak membuat -Oopsi menjadi tidak berguna, tetapi Anda harus berhati-hati dalam menggunakannya. Jika dipanggil pada satu kelas, itu bisa menyebariskan panggilan metode tertentu dalam kelas tanpa risiko. Beberapa kelas dapat menjadi inline bersama selama tidak ada potensi pembatasan akses. Dan beberapa kode (seperti aplikasi) tidak tunduk pada verifikator bytecode. Anda dapat mengabaikan bug jika Anda tahu kode Anda hanya akan dijalankan tanpa tunduk pada pemverifikasi. Untuk informasi tambahan, lihat FAQ javac-O saya.

Profiler

Untungnya, JDK dilengkapi dengan profiler bawaan untuk membantu mengidentifikasi di mana waktu dihabiskan dalam sebuah program. Ini akan melacak waktu yang dihabiskan di setiap rutinitas dan menulis informasi ke file java.prof. Untuk menjalankan profiler, gunakan -profopsi saat memanggil interpreter Java:

java -prof myClass

Atau untuk digunakan dengan applet:

java -prof sun.applet.AppletViewer myApplet.html

Ada beberapa peringatan untuk menggunakan profiler. Output profiler tidak mudah diuraikan. Selain itu, di JDK 1.0.2 ia memotong nama metode menjadi 30 karakter, jadi beberapa metode mungkin tidak dapat dibedakan. Sayangnya, dengan Mac tidak ada cara untuk memanggil profiler, jadi pengguna Mac kurang beruntung. Di atas semua ini, halaman dokumen Java Sun (lihat Sumber) tidak lagi menyertakan dokumentasi untuk -profopsi tersebut). Namun, jika platform Anda mendukung -profopsi tersebut, HyperProf Vladimir Bulatov atau ProfileViewer Greg White dapat digunakan untuk membantu menafsirkan hasil (lihat Sumberdaya).

Ini juga memungkinkan untuk "membuat profil" kode dengan memasukkan waktu eksplisit ke dalam kode:

long start = System.currentTimeMillis(); // do operation to be timed here long time = System.currentTimeMillis() - start;

System.currentTimeMillis()mengembalikan waktu dalam 1/1000 detik. Namun, beberapa sistem, seperti PC Windows, memiliki timer sistem dengan resolusi kurang (jauh lebih kecil) dari 1/1000 detik. Bahkan 1/1000 detik tidak cukup lama untuk menghitung waktu banyak operasi secara akurat. Dalam kasus ini, atau pada sistem dengan pengatur waktu resolusi rendah, mungkin perlu menghitung waktu berapa lama untuk mengulangi operasi n kali dan kemudian membagi total waktu dengan n untuk mendapatkan waktu sebenarnya. Meskipun pembuatan profil tersedia, teknik ini dapat berguna untuk mengatur waktu tugas atau operasi tertentu.

Berikut beberapa catatan penutup tentang pembuatan profil:

  • Selalu tentukan waktu kode sebelum dan setelah membuat perubahan untuk memverifikasi bahwa, setidaknya pada platform pengujian, perubahan Anda meningkatkan program

  • Cobalah untuk membuat setiap tes waktu dalam kondisi yang sama

  • Jika memungkinkan, buat pengujian yang tidak bergantung pada masukan pengguna apa pun, karena variasi dalam respons pengguna dapat menyebabkan hasil berfluktuasi

Applet Benchmark

Applet Tolok Ukur mengukur waktu yang diperlukan untuk melakukan operasi ribuan (atau bahkan jutaan) kali, mengurangi waktu yang dihabiskan untuk melakukan operasi selain pengujian (seperti overhead loop), lalu menggunakan informasi ini untuk menghitung berapa lama setiap operasi mengambil. Ini menjalankan setiap tes selama kurang lebih satu detik. Dalam upaya untuk menghilangkan penundaan acak dari operasi lain yang mungkin dilakukan komputer selama pengujian, komputer menjalankan setiap pengujian tiga kali dan menggunakan hasil terbaik. Ini juga mencoba untuk menghilangkan pengumpulan sampah sebagai faktor dalam pengujian. Karena itu, semakin banyak memori yang tersedia untuk benchmark, semakin akurat hasil benchmark tersebut.