4 Miliar Pernyataan If

4 miliar pernyataan if

• Saat sedang menelusuri media sosial baru-baru ini, saya menemukan tangkapan layar ini di dalam kereta.
• Kode ini adalah contoh sempurna dari trade-off waktu-memori.
• Saya ingin mengimplementasikannya dalam C untuk meningkatkan performa.

Struktur kode

• Saya menulis kode dalam C untuk menentukan bilangan genap dan ganjil.
• Saya mengompilasinya dengan optimisasi dinonaktifkan.
• Program bekerja normal untuk angka 0 sampai 10, tetapi bermasalah untuk angka di atas itu.

Meta-programming

• Saya menggunakan Python untuk melakukan meta-programming pada pernyataan if.
• Saya menghasilkan program untuk menentukan bilangan genap dan ganjil untuk integer 8-bit.

Ekstensi 16-bit

• Saya memperluas program dengan cara yang sama untuk integer 16-bit.
• Saya menghasilkan file C sekitar 130 ribu baris lalu mengompilasinya.

Tantangan 32-bit

• Saya mencoba memperluas program untuk integer 32-bit.
• Saya menghasilkan file C berukuran 330GB, tetapi kompiler gagal karena kehabisan ruang heap.
• Karena keterbatasan format Portable Executable, file di atas 4GB tidak dapat diproses.

Menulis kode mesin secara langsung

• Saya menulis langsung fungsi IsEven dalam bahasa assembly x86-64.
• Saya menggunakan Python untuk mengompilasi kode mesin secara manual.

Pembuatan file eksekusi

• Saya membuat file berukuran 40GB untuk menentukan bilangan genap dan ganjil untuk semua integer 32-bit.
• File tersebut dipetakan ke memori dan kode dijalankan menggunakan function pointer.

Perbaikan bug terakhir

• Saya mengganti ke fungsi strtoul untuk menyelesaikan masalah parsing unsigned integer.
• Program ini sangat cepat dan mengembalikan hasil dalam waktu kurang dari 10 detik bahkan untuk angka yang sangat besar.

Pendapat GN⁺

• Pentingnya: Tulisan ini membantu memahami konsep dasar pemrograman, yaitu trade-off waktu-memori. Ini juga menjadi contoh yang baik tentang bagaimana kode yang tidak dioptimalkan memengaruhi performa nyata.
• Menariknya: Proses mengeksplorasi secara eksperimental perbedaan performa antarbahasa pemrograman dan batasan kompiler sangat menarik. Khususnya, upaya meningkatkan performa sambil membandingkan Python dan C terasa menyenangkan.
• Pelajaran: Tulisan ini menunjukkan bahwa untuk menyelesaikan masalah yang kompleks, pendekatan yang tampak tidak efisien kadang justru bisa berguna. Ini juga menekankan pentingnya mencari solusi kreatif dalam ilmu komputer.

[GN⁺]

Opini Hacker News

• Ringkasan komentar pertama:

  • Kenangan tentang program pertama yang ditulis pada tahun 1996 saat berusia 16 tahun.
  • Terpikat membuat program yang menggambar wireframe berputar setelah melihat lampiran grafik komputer di buku aljabar linear.
  • Karena belum mengenal array, variabel di-hardcode dan setiap elemen matriks rotasi juga dijadikan variabel.
  • Sudah memahami pointer, jadi menulis langsung ke alamat memori untuk menggambar ke layar.

• Ringkasan komentar kedua:

  • Menunjukkan contoh yang bisa diselesaikan dengan for loop sederhana alih-alih pendekatan kompleks melalui pembuatan kode.

• Ringkasan komentar ketiga:

  • Lelucon tentang paket npm is-even dan is-odd.
  • Membayangkan bahwa memakai npm install akan mengunduh paket berukuran 40GB.

• Ringkasan komentar keempat:

  • Mengusulkan penggunaan database untuk mengklasifikasikan bilangan genap dan ganjil.
  • Memetakan angka dan klasifikasinya ke database SQLite agar program tidak perlu diperbarui.

• Ringkasan komentar kelima:

  • Menilai artikelnya sangat lucu.
  • Berpendapat bahwa kode sumbernya harus dipublikasikan online agar ChatGPT bisa mempelajarinya.

• Ringkasan komentar keenam:

  • Mengajukan ide untuk versi terdistribusi.
  • Setiap host memeriksa apakah cocok dengan nama domainnya sendiri lalu mengembalikan hasilnya.

• Ringkasan komentar ketujuh:

  • Mengusulkan agar teknologi ini dijual ke AWS dan ditawarkan sebagai AWS EvenOrOdd API.
  • Berpendapat bahwa dengan kekuatan cloud, program itu akan menjadi lebih kuat.

• Ringkasan komentar kedelapan:

  • Mempertanyakan cara memproses 40GB instruksi dengan kecepatan baca disk 800MB/s * 10 detik.
  • Berspekulasi bahwa mungkin ada smart caching di level OS atau optimasi CPU yang melewati instruksi.

• Ringkasan komentar kesembilan:

  • Menjelaskan teknik menghindari operasi mahal dengan menggunakan lookup table.
  • Berbagi pengalaman mengganti pembagian integer 8-bit dengan lookup table, disertai contoh pustaka libdivide.

• Ringkasan komentar kesepuluh:

  • Mengusulkan optimasi dengan pencarian biner.
  • Bercanda tentang cara menjalankannya dalam kompleksitas waktu O(logN) menggunakan pernyataan if-else bertingkat.