Pentingnya memahami Ilmu Informatika secara menyeluruh

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)

  1. Anda punya array yang berisi daftar jumlah gaji semua orang pegawai di sebuah kota (arraynya tidak terurut)
  2. 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
  3. 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:

  1. Dalam arsitektur komputer, kita belajar mengenai batasan hardware, bagaimana arsitektur CPU superscalar bekerja.
  2. Dalam pelajaran algoritma, kita belajar mengenai kompleksitas algoritma. Bagaimana memilih algoritma yang baik.
  3. Dalam pelajaran compiler, kita bisa tahu optimasi apa yang bisa (dan tidak bisa) dilakukan oleh compiler
  4. 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.

Manipulasi bit bagian 1: representasi biner

Kemarin buku yang saya tunggu-tunggu akhirnya tiba juga: The Art of Computer Programming, Volumes 1-4A Boxed Set (Box Set). Dulu waktu kuliah, saya sudah membaca sebagian buku ini, tapi buku ini berat di matematika, jadi kebanyakan saya hanya membaca bagian algoritmanya saja, sambil mencoba-coba sedikit latihannya. Terinspirasi dari banyak programmer di buku Coders at work yang menyukai buku ini, dan minimal memakai buku ini sebagai referensi, maka saya sekarang berusaha membaca ulang koleksi buku Knuth, plus membaca volume yang baru: Volume 4a.

Sebagai catatan: dalam wawancara Knuth sendiri tidak menyarankan seseorang membaca buku ini dari sampul ke sampul sampai habis. Saya membaca buku ini pertama skimming dulu, mencari topik menarik, setelah itu baru saya baca teliti bagian-bagian yang saya perlukan. Jadi jika Anda merasa berat membaca buku ini: coba langsung skip ke bagian yang menarik.
Continue reading Manipulasi bit bagian 1: representasi biner

Tools untuk debugging

Di posting ini saya sekedar ingin sharing metode dan tools yang biasa saya pakai untuk debugging program. Di lingkungan yang ideal, kita seharusnya punya debugger yang canggih, cepat dan reliable, tapi sayangnya sering kali ini tidak tersedia. Ini contoh beberapa lingkungan pengembangan yang “mengesalkan” yang pernah saya jumpai:

  • Symbian versi awal (versi 6): untuk bisa mendebug, perlu IDE khusus dengan license khusus yang mahal. Symbian versi terbaru sudah semakin baik (tapi sekarang ini Symbian sudah akan berakhir).
  • BlackBerry: startup time debugger sangat lama, dan debugger sering error. Setiap kali menginstall versi program baru di BlackBerry, perlu restart (butuh sekitar 5 menit tiap kali restart).
  • Mendebug aplikasi Android di emulator. Startup emulator sangat lambat (bahkan di processor AMD quad core 3 ghz memori 16 GB) , lebih cepat mencoba langsung di HP. Masalahnya adalah ketika ada laporan: ada bug kecil di Android versi 2.2, tapi HP saya memakai Android 2.3
  • Debugging PHP di web hosting. Kadang ada masalah yang hanya muncul di web hosting, tapi tidak muncul ketika dicoba di server sendiri. Beberapa kemungkinan adalah karena versi PHP yang tidak sama, versi library yang tidak sama. Di server sendiri bisa mudah menginstall Xdebug, tapi tidak tersedia di tempat hosting.
  • Nurit Point Of Sales. Device ini banyak bugnya, tidak tersedia debugger, dan jika crash, akan memprint isi memori di atas kertas thermal sekitar 1/2 meter.
  • Kernel FreeBSD. Ketika porting tahap awal, sangat sulit mendebug apa yang terjadi di level CPU. Masalahnya karena saya tidak menggunakan development board yang memiliki JTAG.

Sebenarnya tidak semua lingkungan itu benar-benar mengesalkan jika kita punya uang, contohnya: jika saya punya uang beberapa ribu dollar, saya akan bisa mendebug Symbian dengan mudah. Jika saya punya beberapa HP Android berbagai versi, debugging Android juga lebih mudah. Jika saya punya development board resmi dengan JTAG, porting kernel akan lebih mudah. Jika saya hosting VPS dengan versi PHP saya sendiri, maka tidak akan ada masalah dengan PHP, dan andaikan ada masalah, saya bisa menginstall XDebug. Pada kenyataannya seringkali tidak tersedia dana untuk menyelesaikan berbagai masalah tersebut.
Continue reading Tools untuk debugging

Berpikir Ketika Memprogram dan Menguji Program

Setelah membaca posting reddit ini, saya teringat kembali pada buku Programming Pearl, terutama bagian yang dibahas dalam posting itu yaitu mengenai binary search. Dalam buku programming pearl dinyatakan bahwa para programmer professional yang diberi waktu 2 jam untuk menulis binary search, 90% memiliki bug (terutama di *boundary* condition). Penulis blog memberi tantangan pada pembacanya untuk membuat binary search, boleh beberapa jam, tapi *tanpa testing* sama sekali.

Respon kebanyakan orang bisa dirangkum menjadi tiga kubu. Kubu pertama: ah di dunia nyata kan orang pasti testing, keahlian buat memprogram dengan benar tanpa testing itu tidak berguna. Kubu kedua menyatakan: kalau program sependek itu tidak bisa dibuat tanpa testing, bagaimana mungkin bisa membuat program besar yang rumit, apakah tiap baris program harus ditest?. Kubu terakhir menyatakan: buat apa sih membuat binary search, kan sudah ada di library/API?

Untuk kubu terakhir, jawabannya sederhana: ada kasus di mana hal tersebut masih diperlukan. Misalnya fungsi binary search di library kebanyakan tidak menyatakan elemen mana yang akan dikembalikan jika ada lebih dari 1 data yang cocok, dan tidak akan mengembalikan lokasi di mana data bisa disisipkan jika data belum ada. Contohnya di fungsi bsearch di C (POSIX):

The bsearch() function returns a pointer to a matching member of the array, or NULL if no match is found. If there are multiple elements that match the key, the element returned is unspecified.

Kadang diperlukan fungsi yang mengembalikan elemen pertama yang cocok, atau terakhir yang cocok, atau bahkan elemen random dari antara semua elemen yang cocok. Tentu saja salah satu solusinya adalah membungkus fungsi bsearch, lalu mencari ke depan atau belakang sampai tidak cocok lagi. Tapi dalam hal ini Anda juga tetap perlu memperhatikan batas index ketika mencari, jadi Anda tetap perlu menulis kode (yang perlu testing dan perlu dipikirkan).

Jika Anda mengimplementasikan fungsi binary search sendiri, Anda bisa membuat fungsi yang sekaligus mengembalikan posisi elemen di mana kita harus menyisipkan elemen tersebut jika elemen tidak ditemukan (ini bisa didapat dari lokasi perbandingan terakhir), dalam kasus ini kita tidak bisa membungkus fungsi bsearch, karena fungsi tersebut hanya mengembalikan NULL jika elemen tidak ditemukan.

Beberapa Pelajaran yang bisa dipetik dari posting dan diskusi adalah: testing itu perlu, bahkan untuk program kecil sekalipun. Pelajaran kedua adalah: kita tetap harus teliti dan berpikir ketika memprogram. Pelajaran ketiga adalah: meski isi library di berbagai bahasa sudah cukup lengkap, mengerti algoritma sederhana itu perlu, dan kadang kita perlu mengimplementasikan algoritma tersebut atau variannya.

Sebagian orang berpikir: ah tidak perlu terlalu teliti ketika memprogram, nanti akan ketauan salahnya ketika testing. Sebagian lagi berpikir: program ini sudah saya pikirkan, jadi gak perlu ditest. Sikap yang benar adalah: kedua hal tersebut berhubungan, kita harus teliti ketika memprogram, dan harus teliti juga dalam membuat testing. Mengapa tidak menggantungkan diri pada testing saja? ada beberapa masalah dengan testing, pertama testing itu sulit, untuk membuat test case yang baik perlu kasus yang sangat besar dan kedua testing tidak selalu bisa dilakukan.
Continue reading Berpikir Ketika Memprogram dan Menguji Program

Kritik PHP

PHP merupakan bahasa yang kurang bagus, designnya tidak dipikirkan dengan matang. Banyak sekali keanehan PHP dibanding bahasa lain, dan meskipun PHP sudah mulai agak membaik di versi 5.3 (yang baru dirilis 3 minggu yang lalu), saya masih menunggu PHP6 untuk mencoba lagi.

Kebanyakan orang tidak menyadari bahwa mereka butuh sesuatu, atau bahwa sesuatu itu jelek, sampai mereka diberikan sesuatu yang lebih baik. Di artikel ini saya ingin mengkritik PHP, tapi sebelumnya akan saya contohkan apa yang saya maksud dengan melihat sejarah MySQL.

Awalnya MySQL tidak mendukung transaksi. Komentar pendukung MySQL waktu itu: transaksi itu tidak perlu, yang penting cepat (Bahkan pembuat mysql pun berpikir demikian, coba lihat http://www.genome.ou.edu/mysql_manual.html#Bugs, bagian ” Some things we don’t have any plans to do”). Tapi kemudian transaksi ditambahkan, dengan catatan: kalau mau cepat jangan pakai transaksi. Lalu berikutnya: transaksi adalah salah satu fitur yang kami banggakan.

Nah, saya cukup yakin, isi kritik saya ini kemungkinan akan banyak ditolak oleh orang yang cinta buta pada PHP, setidaknya saat ini. Tapi ketika PHP sudah berkembang, baru akan bisa diterima. Memang begitulah sifat penggemar sesuatu, jadi saya bisa memakluminya.

Saya sendiri pernah memprogram PHP dari sejak PHP3, lalu PHP4, dan sampai awal PHP5. Semakin lama saya mempelajari dan memakai PHP, saya semakin merasakan keterbatasannya. Saya tidak menyangkal bahwa PHP merupakan bahasa yang sangat populer. Namun tidak semua yang populer itu bagus (ingat DBase? Ingat Visual Basic 6? dsb). Bagi pencinta PHP, Anda mungkin bisa berbangga PHP semakin membaik, meski caranya dengan “tambal sulam”, dan meski Anda harus sering menyesuaikan program agar berjalan di PHP terbaru. Mungkin saya akan mencoba lagi PHP di versinya yang keenam, tapi saat ini mari kita bahas satu persatu kelemahan PHP.

Continue reading Kritik PHP

DataStore di Google AppEngine (RDBMS bukan segalanya)

Google AppEngine adalah sebuah layanan Google, di mana kita bisa membuat aplikasi dalam Python atau Java (atau bahasa lain yang memakai virtual machine Java) di infrastruktur milik Google. Secara teori, Anda akan bisa melayani 5 juta pengunjung per bulan secara gratis. Anda bisa membayar ekstra jika ingin mendapatkan resource yang lebih banyak.

Saya akan menceritakan salah satu pengalaman development dengan google appengine, yaitu mengenai bagian pembuatan aplikasi yang scalable, dengan fokus pada DataStore. Menurut saya DataStore merupakan implementasi penyimpanan data yang menarik, yang berbeda dari database relasional yang umum dipakai saat ini.

Ilmu relational database dan SQL hampir tidak dipakai sama sekali di sini. Bahkan operasi Join yang sangat lazim di basis data tidak bisa dilakukan dengan DataStore. Lalu apa kelebihan DataStore? datastore memiliki aneka batasan yang memungkinan Google mendistribusikan data di berbagai server di seluruh dunia. DataStore diiimplementasikan di atas teknologi google yang sudah terbukti, yaitu BigTable.

Continue reading DataStore di Google AppEngine (RDBMS bukan segalanya)