Hari ini saya menemukan link ke sebuah pertanyaan menarik di Stack Overflow. Sebuah pertanyaan sederhana: mengapa menjumlahkan elemen yang nilainya kurang dari nilai tertentu dalam array yang terurut, lebih cepat dari melakukan operasi yang sama pada array yang tidak terurut. Lebih jelasnya silakan baca pertanyaan dan jawabannya di sini:
Why is processing a sorted array faster than an unsorted array?
Ada beberapa hal menarik dari jawaban pertanyaan tersebut.
Pertama: meskipun Anda memprogram high level sekalipun (menggunakan Java/Ruby/Python, atau bahasa lain yang menggunakan JIT), Anda akan tetap dibatasi oleh hardware. Anda tetap perlu mengerti hardware untuk membuat aplikasi yang performasinya tinggi.
Kedua: perhatikan bahwa dengan mengetahui sebab dari masalah, kita bisa mempercepat program, tanpa menggunakan sorting. Cukup dengan menggunakan manipulasi bit yang menghilangkan branching. Kita ingin menghilangkan sorting, karena sorting sendiri butuh waktu.
Ketiga: dalam kasus tertentu, compiler bisa mengoptimasi jika diberi flag yang tepat. Tapi kita tidak bisa menggantungkan diri pada compiler saja. Compiler yang berbeda menghasilkan kode yang berbeda, dan hasilnya bisa sangat jauh berbeda. Misalnya disebutkan bahwa compiler Visual C++ 2010 tidak bisa mengoptimasi kodenya, sedangkan compiler Intel bisa melakukannya dengan sangat baik.
Keempat: Perhatikan juga bahwa optimasi compiler dibatasi oleh hardware. Hardware tertentu (misalnya Intel sejak Pentium Pro) mendukung instruksi conditional move (di assembly Intel, instruksi ini disebut dengan CMOV) yang tadinya perlu manipulasi bit manual (AND, OR, dsb). Anda tidak bisa menggunakan optimasi ini di semua hardware, apalagi jika Anda menargetkan CPU model lama (banyak digunakan di embedded device).
Mungkin sebagian dari Anda mengira pertanyaan tersebut agak mengada-ada: untuk apa mencari jumlah bilangan yang kurang dari N dan dilakukan berulang-ulang, kalau sekali saja kan hanya butuh beberapa milidetik. Dan berbeda beberapa milidetik saja kan harusnya tidak berpengaruh bagi user.
Saya terpikir beberapa aplikasi dalam dunia nyata yang mungkin membutuhkan penjumlahan secara cepat tapi berulang-ulang. Saya berikan contoh kecil: Misalnya Anda punya aplikasi interactive data viewer, dengan slider yang bisa diubah nilainya dengan mouse (sangat cepat)
- Anda punya array yang berisi daftar jumlah gaji semua orang pegawai di sebuah kota (arraynya tidak terurut)
- Kita ingin menampilkan secara interaktif: jika saya set slider ke nilai 1 juta, maka saya akan melihat bahwa total gaji semua orang yang dibawah satu juta adalah X
- saya bisa mengubah nilai di slider, dan menghitung ulang total semua orang yang gajinya di bawah 2 juta. Saya bisa menaik turunkan slider dengan sangat cepat, ratusan kali per detik nilai slider bisa berubah.
Perhatikan bahwa meskipun contoh ini hanya menyatakan kurang dari X, tapi sebenarnya berlaku juga untuk operasi lebih dari X, atau X dalam range tertentu.
Dalam contoh ini: perbedaan interaksi antara beberapa milidetik dan beberapa puluh milidetik bisa sangat terasa. Jadi mengerti untuk mengurutkan data (atau menggunakan trik manipulasi bit) sebelum menjumlahkan bisa membuat interaksi semakin smooth. Menggunakan database untuk tujuan animasi yang sangat smooth seperti itu tidak akan berhasil (latensinya sangat tinggi), apalagi misalnya devicenya kemampuannya processing/komputasinya rendah (misalnya tablet atau smartphone).
Sebenarnya saya bisa menunjukkan contoh yang lebih kompleks lagi (misalnya dalam hal komputasi piksel grafik), tapi nanti pembahasannya akan ngelantur ke mana-mana. Hal yang ingin saya tekankan adalah: ada banyak persoalan serupa dalam dunia nyata semacam ini. Ini adalah penyederhanaan, supaya inti masalah bisa dilihat lebih jelas.
Seringkali jika ada yang menunjukkan bahwa optimasi seperti ini diperlukan, jawaban programmer yang malas adalah: beli saja hardware yang lebih cepat, masalahnya kan beres. Perlu dicatat juga: bahwa membeli hardware yang lebih cepat tidak selalu menjadi solusi.
Misalnya Anda menjual aplikasi Anda di Apple appstore, Anda harus mendukung hardware terlambat sampai tercepat. Jika Anda bandingkan iPad generasi pertama dan kedua, maka perbedaan hardwarenya sangat jauh: memori menjadi 2x lipat, prosessor menjadi jauh lebih cepat (dari single menjadi dual core). Anda bisa mengabaikan 14.8 juta pengguna iPad 1, tapi penjualan aplikasi Anda bisa menurun jauh.
Mungkin Anda terpikir untuk melakukan komputasi di server saja. Tapi berapa delay karena latensi jaringan? apakah kecepatannya cukup acceptable untuk membuat interaksi yang smooth?
Jika saya rangkum, semua hal tersebut menunjukkan: betapa perlunya kita belajar ilmu informatika atau computer science secara baik dan menyeluruh. Misalnya dalam contoh yang sangat kecil ini:
- Dalam arsitektur komputer, kita belajar mengenai batasan hardware, bagaimana arsitektur CPU superscalar bekerja.
- Dalam pelajaran algoritma, kita belajar mengenai kompleksitas algoritma. Bagaimana memilih algoritma yang baik.
- Dalam pelajaran compiler, kita bisa tahu optimasi apa yang bisa (dan tidak bisa) dilakukan oleh compiler
- Dalam pelajaran networking, kita bisa tahu mengenai latensi jaringan (jika ingin memindahkan komputasi ke server)
Jadi menurut saya, orang-orang yang ingin membatasi pelajaran komputer hanya dengan materi yang praktis saja, tidak akan berhasil.
terima kasih infonya, sangat bergunan terutama untuk orang yang sedang belajar informatika seperti saya.