4 miliar pernyataan if

 (andreasjhkarlsson.github.io)
3 poin oleh GN⁺ 2023-12-29 | 1 komentar | Bagikan ke WhatsApp
  • Ide iseng untuk menentukan bilangan genap/ganjil tanpa %, hanya dengan daftar perbandingan, diperluas dari 8-bit hingga 32-bit dan akhirnya menyingkap batas compiler serta format file eksekusi
  • Saat generator kode Python dipakai untuk membuat if (number == n) secara otomatis, rentang 8-bit dan 16-bit berjalan, tetapi pada 32-bit jumlah target perbandingan meledak menjadi sekitar 4,2 miliar
  • Versi C 32-bit setelah 48 jam menghasilkan file C sekitar 330GB, dan MSVC gagal mengompilasinya karena batas nomor baris dan kehabisan heap space
  • Untuk menghindari batas 4GB pada file executable PE, penulis langsung menghasilkan instruksi x86-64 dan membuat biner 40GB bernama isEven.bin, lalu memanggilnya seperti kode eksekusi melalui memory mapping Windows
  • Program akhirnya dapat membedakan nilai 32-bit besar dengan benar setelah atoi diganti ke strtoul, dan input besar pun kembali dalam sekitar 10 detik pada Core i5 12600K, memori 32GB, dan SSD M.2

Menentukan genap/ganjil hanya dengan pernyataan perbandingan

  • Titik awalnya adalah tangkapan layar kode yang dilihat di media sosial, berupa cara menyelesaikan masalah klasik penentuan genap/ganjil tanpa operasi modulus
  • Strukturnya menaruh if (number == n) untuk setiap angka, lalu mencetak dengan printf apakah angka itu genap atau ganjil
  • Contoh C pertama memakai uint8_t number = atoi(argv[1]); dan menulis langsung pernyataan perbandingan dari 0 sampai 10
  • Dikompilasi dengan /Od untuk mematikan optimisasi agar compiler tidak mengubah algoritmanya
    • 0, 4 menghasilkan even
    • 3, 7 menghasilkan odd
    • 50, 11, 99 tidak menghasilkan output apa pun
  • Penyebabnya adalah setelah if terakhir tidak ada lagi perbandingan yang menangani nilai berikutnya, sehingga dibutuhkan lebih banyak pernyataan if

Membuat pernyataan if dengan Python

  • Alih-alih menulis semua perbandingan secara manual, dipakai pendekatan metaprogramming dengan Python untuk menghasilkan kode C
  • Skrip Python membuat pernyataan perbandingan dari 0 sampai 255 dengan for i in range(2**8)
    • jika i % 2 == 0, cetak printf("even\n");
    • jika tidak, cetak printf("odd\n");
  • Program C yang dihasilkan bekerja untuk seluruh rentang 8-bit
    • 99 adalah odd
    • 50 adalah even
    • 240 adalah even
    • 241 adalah odd

Sampai 16-bit masih berhasil dikompilasi sebagai C

  • Cara yang sama diperluas ke uint16_t dan range(2**16)
  • File C yang dihasilkan berukuran sekitar 130 ribu baris
  • Setelah dikompilasi dengan MSVC, program berjalan normal untuk berbagai nilai
    • 21000 adalah even
    • 3475 adalah odd
    • 3 adalah odd
    • 65001 adalah odd
    • 65532 adalah even
  • Ukuran file executable sekitar 2MB, dan pada PC dengan memori 31,8GB ini tidak menimbulkan masalah

File C 32-bit dan batas compiler

  • Target berikutnya adalah menangani seluruh rentang 32-bit dengan uint32_t dan range(2**32) menggunakan pernyataan perbandingan
  • Jumlah angka pada 32-bit 65.536 kali lebih banyak daripada 16-bit
  • Setelah generator Python berjalan 48 jam, terbentuk file C sekitar 330GB
  • Kompilasi MSVC segera menabrak batas
    • warning C4049: compiler mencapai batas nomor baris dan menghentikan line number emission
    • batas nomor baris adalah 16777215
    • fatal error C1060: compiler is out of heap space
  • Format Windows Portable Executable(.exe) juga punya keterbatasan untuk melewati 4GB, sehingga jalur kompilasi C untuk memasukkan lebih dari 4 miliar perbandingan ke dalam executable menjadi buntu
  • Sebagai rujukan, disebutkan batas terkait ukuran maksimum file PE

Membuat machine code secara langsung lalu menjalankannya

  • Untuk menghindari batas compiler dan format file executable, pendekatannya diubah menjadi langsung menulis instruksi x86-64 ke dalam biner
  • Fungsi target berbentuk IsEven, menerima argumen di ECX dan mengembalikan nilai di EAX
    • XOR EAX, EAX menetapkan nilai balik dasar 0 untuk kasus ganjil
    • untuk setiap angka dipakai CMP ECX, i
    • jika genap, lakukan INC EAX lalu RET
    • jika ganjil, langsung RET
  • Digunakan x86-64 assembly dan opcode, dan opcode tiap instruksi ditanyakan ke ChatGPT
  • Skrip Python membuka isEven.bin sebagai biner dan menulis instruksi perbandingan untuk semua angka dari 0 sampai 2**32 - 1
  • isEven.bin yang dihasilkan berukuran sekitar 40GB dan memuat sekitar 4,2 miliar perbandingan yang dibutuhkan untuk seluruh angka 32-bit

Memanggil kode 40GB dengan memory mapping Windows

  • Program C host membuka isEven.bin dan alih-alih membaca seluruh file, menggunakan memory mapping lewat Windows API
  • Alur eksekusinya sebagai berikut
    • membuka isEven.bin dengan CreateFileA menggunakan hak akses GENERIC_READ | GENERIC_EXECUTE
    • memeriksa ukuran file 64-bit dengan GetFileSizeEx
    • memanggil CreateFileMapping dengan PAGE_EXECUTE_READ
    • membuat mapping yang bisa dieksekusi dan dibaca dengan MapViewOfFile
    • melakukan cast pointer hasil mapping ke pointer fungsi int (*isEven)(int) lalu memanggilnya
  • Cara ini memperlakukan file 40GB seolah-olah seluruhnya sudah ada di memori, sementara penempatan aktualnya diserahkan ke virtual memory sistem operasi
  • Pada pengujian awal, sebagian besar hasil benar, tetapi 4200000000 menghasilkan odd, jadi hasilnya salah
  • Penyebabnya adalah atoi tidak dapat menangani nilai unsigned besar dengan benar; setelah diganti menjadi strtoul(argv[1], NULL, 10), 4200000000 menghasilkan even dan 4200000001 menghasilkan odd

Pengamatan performa

  • Untuk angka kecil, hasil keluar seketika, dan untuk angka besar yang mendekati batas 2^32 pun hasil kembali dalam sekitar 10 detik
  • Lingkungan pengujiannya adalah Core i5 12600K, memori 32GB, dan SSD M.2
  • Kecepatan baca maksimum SSD yang teramati selama pengujian sekitar 800MB/s
  • Meski harus membaca data 40GB dari disk, memetakannya ke memori fisik, dan CPU hampir tidak bisa memanfaatkan keuntungan cache, hasil kecepatan ini tetap terasa mengejutkan

Bacaan terkait

1 komentar

 
GN⁺ 2023-12-29
Komentar Hacker News

  • Andai saja aku masih menyimpan salah satu program pertama yang pernah kutulis. Pada 1996, saat berusia 16 tahun, aku melihat bagian grafik komputer di lampiran buku aljabar linear, lalu terobsesi membuat program yang menggambar wireframe berputar dari beberapa bentuk dengan pemrograman yang baru kupelajari semester sebelumnya
    Gara-gara itu aku nyaris gagal kelas, dan saat itu aku bahkan belum tahu array, jadi semua titik sudut dan elemen matriks rotasi ditulis sebagai variabel yang di-hardcode masing-masing, dan perkalian matriks pun harus disalin-tempel serta diubah untuk tiap titik sudut sebagai daftar rumus panjang tanpa loop
    Untuk menggambar ke layar, aku tahu pointer karena harus menulis ke memori mulai dari alamat tertentu, dan aku juga punya loop untuk merasterisasi garis di antara titik-titik sudut. Jadi pada akhirnya aku sebenarnya sudah punya konsep array dan indexing, hanya saja belum tahu cara membuatnya sendiri

    • Aku juga mirip. Sekitar umur 12 tahun aku mencoba membuat game Pac-Man dalam BASIC, dan kupikir aku harus menulis logika untuk keempat hantu secara terpisah dari (x1,y1) sampai (x4,y4), jadi terasa buntu
      Aku berkata pada ayahku bahwa aku ingin bisa menulis sesuatu seperti xn, yn di dalam loop for, dan n menunjukkan hantu yang mana, lalu beliau mengambil buku BASIC dan menunjukkan bahwa x(n) memang benar-benar bisa dilakukan
      Hal ini selalu kuingat saat membicarakan pendidikan. Konsep abstrak paling mudah dipahami ketika murid benar-benar membutuhkannya, dan hal yang tampak membingungkan meski dijelaskan seharian bisa langsung klik dalam hitungan detik atau menit ketika itu menyelesaikan masalah mereka sendiri
    • Solusi yang jelas adalah memakai bagian bawah layar sebagai working memory sambil menggambar bagian atasnya. Saat mencapai bagian bawah, hampir tak akan ada komputasi yang tersisa, dan karena memakai memori GPU yang cepat, ini terasa seperti CUDA dan sangat bernuansa AI
    • Ini mengingatkanku pada masa-masa awal freelance. Yang kupunya hanya VPS kecil yang bisa menjalankan PHP, dan aku harus memproses spreadsheet 5 ribu hingga 10 ribu baris, yang pada 2002/2003 tergolong cukup besar
      Aku bukan lulusan ilmu komputer, jadi aku membaca file dengan cara paling bodoh yang bisa dibayangkan, dan karena loop bersarang, penggunaan memorinya terus meledak dan error kehabisan ruang terus muncul. Jadi aku menaruh $variable = null di semua tempat yang memungkinkan, dan ternyata benar-benar jalan
    • Snake untuk TI-83 buatanku saat SMP, yang sempat jadi hit, juga mirip. Koordinat x dan y tiap ruas ular kusimpan dalam variabel terpisah, dan karena jumlah variabel yang bisa dipakai di TI-83 BASIC terbatas, panjang ularnya juga tidak bisa melebihi itu
    • Setelah belajar sendiri print, input, if, dan goto dari dokumentasi, fitur GWBasic pertama yang kupelajari dari meminta bantuan orang lain adalah chain

  • Ini terasa terlalu overengineered. Aku tidak paham kenapa sampai perlu code generation, padahal bisa diselesaikan dengan loop for yang sederhana
    Di isOdd, cukup ulangi odd = !odd dari 0 sampai n, lalu kembalikan hasilnya
    Tautan Playground: https://go.dev/play/p/8TIfzGrdWDF
    Aku belum memprofilkannya, tapi berdasarkan intuisi dan pengalaman industri, ini cepat

    • Implementasi kualitas production yang sesungguhnya tentu harus selalu memakai rekursi. Jika n == 0, kembalikan false; jika positif, kembalikan !isOdd(n-1); jika negatif, kembalikan !isOdd(n+1)
    • Bisa dipastikan versi Rust dari pendekatan ini cepat
      Assembly-nya keluar seperti testq %rdi, %rdi, setg %al, andb %dil, %al, retq
      Tekan ... di samping build untuk melihat assembly: https://play.rust-lang.org/?version=stable&mode=release&edit...
      Sayangnya, Go Playground tampaknya tidak mendukung output assembly
    • Jangan lupakan fungsi genap juga. isEven(n int64) bool { return !isOdd(n) }
    • Kalau n = tak hingga, maka ini akan berulang tanpa akhir
    • Ini bisa diperbaiki dengan tail recursion

  • Pendekatan ini sangat cocok untuk paket npm is-even[1] dengan 196.023 unduhan mingguan atau paket npm is-odd[2] dengan 285.501 unduhan. Akan keren kalau setelah mengetik npm install, malah mulai mengunduh is-even 40GB dan is-odd 40GB
    [1] https://www.npmjs.com/package/is-even
    [2] https://www.npmjs.com/package/is-odd

    • Selalu layak disebut bahwa paket-paket ini adalah hasil dari satu spammer npm yang sangat berdedikasi[1] yang berusaha masuk ke sebanyak mungkin direktori node_modules
      ansi-colors pun bukan satu paket warna lengkap, melainkan ada paket per warna, dan selain itu masih banyak lagi hal semacam itu. Paket-paket seperti ini disisipkan ke alat CLI atau paket yang tampak masuk akal lalu saling merujuk, sehingga proyek nyata pun bisa menarik puluhan paket jonschlinkert hanya dari satu dependensi yang tampaknya tidak berbahaya
      [1] https://www.npmjs.com/~jonschlinkert
    • Anehnya, hasil paling murni dari mengikuti prinsip “jangan mengulang diri sendiri” adalah bahwa is-even bergantung pada is-odd
      Setelah var isOdd = require('is-odd');, isinya cuma module.exports = function isEven(i) { return !isOdd(i); };
    • Orang ini mungkin tidak tahu, tetapi setelah memeriksa source tree dari dua aplikasi frontend kami, paket is-number yang menjadi dependensi is-odd ternyata juga dipakai oleh cukup banyak paket lain
      Jika memang sangat merepotkan untuk menentukan apakah suatu nilai bertipe angka di JS, mungkin paket ini ada gunanya, tetapi rasanya pasti ada paket yang lebih umum yang juga menangani tipe bawaan lain
      Namun isNumber memperlakukan string yang bisa dikonversi menjadi angka sebagai angka, jadi hasilnya bisa aneh. Misalnya const a = '1'; isNumber(a); // true, tetapi const b = a + a; akan menjadi string '11'
      Tentu saja ini kebodohan JS standar di mana 2*a menjadi 2 dan 1+'1' serta '1'+1 sama-sama menjadi '11', tetapi karena itu jawaban bahwa '1' adalah angka belum tentu tepat. Namun paket ini diunduh 46 juta kali minggu lalu, dan itu malah rendah karena minggu Natal; minggu-minggu sebelumnya rata-ratanya sekitar 70 juta. Seperti proyek kami, sebagian besar mungkin adalah dependensi
    • Saya pernah membuat paket nullll[1] yang hanya mengekspor satu null tetapi memakai memori 400MB, dan entah bagaimana itu ditandai di HN[2]
      Dengan 41 bintang GitHub dan cakupan pengujian 100%[3], jelas itu sudah siap produksi
      [1]: https://github.com/mickael-kerjean/nulll
      [2]: https://news.ycombinator.com/item?id=17072675
      [3]: https://github.com/mickael-kerjean/nulll/blob/master/test.js
    • Sebenarnya angka JavaScript adalah f64, bukan u32, jadi sebesar itu pun masih kurang. Bahkan jika hanya mendukung rentang bilangan bulat aman, itu sudah 2⁵⁴, lebih dari 4 juta kali lebih besar daripada 2³²
      Ukuran kode mesin tampaknya hanya akan bertambah 4 byte per cabang, jadi sekitar 40% saja, sehingga kasarnya naik menjadi 224 exbibyte. Itu pun jika 10 bit terakhir dilewati secara malas
      Jika ingin melakukannya dengan benar, mungkin masih perlu dikalikan 1.000 lagi, dan saya belum benar-benar memikirkan pola NaN, jadi bisa juga sedikit lebih kecil. Jika sampai mendukung bigint, mungkin jadinya tak terbatas

  • Saya tidak paham kenapa harus repot-repot begini. Database memang diciptakan untuk hal seperti ini. Tinggal simpan pemetaan angka ke klasifikasi even/odd di database SQLite
    Metode ini juga punya keuntungan bahwa program tidak perlu diperbarui setiap kali klasifikasi suatu angka berubah dari ganjil menjadi genap

    • Database juga perlu pemeliharaan dan pembaruan. Lebih baik buat saja kontrak Ethereum, lalu beri insentif ekonomi agar orang lain bertindak sebagai oracle dan selalu mengembalikan jawaban yang benar kapan saja
    • Ini tampak seperti jenis data yang seharusnya ada di Wikidata. Dengan begitu tidak perlu punya database lokal, cukup lakukan permintaan HTTPS yang cepat
      Satu-satunya masalah mungkin jika TLS sendiri bergantung pada fungsi genap/ganjil, tetapi sepertinya tidak begitu
    • Tabelnya cukup dibuat sebagai even_or_odd, lalu diberi kolom seperti is_odd, is_even, is_zero, is_one, is_two, is_three. 1 dimasukkan sebagai is_odd,is_one, 2 sebagai is_even,is_two
    • Benar, tetapi tentu saja harus memakai database XML
      Ini juga membantu portabilitas data, dan saat harus diperiksa manual, formatnya tetap mudah dibaca manusia
    • AWS sudah punya Elastic Cloud Parity, dan skalabilitasnya jauh lebih baik

  • Ini salah satu tulisan paling lucu yang pernah saya baca di sini. Source code-nya harus dipasang online agar ChatGPT bisa “belajar”

    • Dengan begitu dia pasti melanggar lisensi ketatnya
      /* Copyright 2023. All unauthorized distribution of this source code will be persecuted to the fullest extent of the law*/
      Untuk kode seanggun ini, siapa yang bisa menyalahkannya?

  • Saya sama sekali tidak paham letak lucunya. Kalaupun orang yang membuat ini memang seperti itu, yang membingungkan adalah 1198 rekomendasi yang ada sekarang
    Tabel lookup untuk nilai yang bisa dihitung bukan hal baru dan juga bukan lelucon. Itu solusi nyata untuk trade-off waktu/memori, dan penulisnya juga tahu itu
    Masalahnya sendiri konyol tetapi sangat primitif, jadi sejak awal tidak ada keraguan bahwa ini mungkin dilakukan, dan selain pengamatan bahwa dia memproses program 40GB di komputernya selama sekitar 10 detik, tidak ada pengukuran nyata
    Jadi apa yang dipelajari? Bahwa file exe tidak bisa melebihi 4GB? Bahwa jika ada 2^32 buah if, programnya sekitar 300GB? Saya tidak tahu kenapa 1198 orang menganggap ini menarik
    Tidak seperti “Hexing the technical interview” atau tulisan SIGBOVIK, ini tampaknya bukan gila, hanya tidak bermakna

    • Leluconnya adalah bahwa dia benar-benar melakukannya. Selama puluhan tahun orang membuat lelucon seperti ini, lalu orang sinting ini benar-benar berhasil
      Ini terlalu ekstrem sampai tidak ada compiler yang bisa menanganinya, bahkan assembler yang dikenal pun tidak bisa. Jadi untuk membuatnya berjalan, dia harus menghasilkan biner bahasa mesin sendiri, dan itu benar-benar berfungsi. Gila
    • Benar bahwa tabel lookup untuk nilai yang bisa dihitung bukan hal baru, tetapi jika optimisasi dimatikan, 4 miliar pernyataan if tidak akan dikompilasi menjadi tabel lookup
      Setiap if akan dievaluasi satu per satu untuk memeriksa apakah cocok dengan input, dan keluaran program pada tulisan asli yang selesai jauh lebih cepat untuk angka kecil juga mendukung hal ini. Karena angka kecil berada di bagian depan kode
      Sebaliknya, jika itu switch dengan 4 miliar case, saya memperkirakan itu akan dikompilasi menjadi semacam tabel lookup. Hanya saja saya tidak tahu seperti apa kode hasil kompilasi tanpa optimisasi ketika tipe datanya integer unsigned
    • Kadang orang melakukan sesuatu hanya karena lucu
    • Saya memahaminya sebagai parodi terhadap tulisan blog yang menyindir betapa tidak bergunanya perlawanan terhadap kebijaksanaan konvensional. Lelucon yang cukup kering

  • Ini pencapaian teknis yang menakjubkan. Harus dijual ke AWS lalu disajikan sebagai Enterprise-ready AWS EvenOrOdd API untuk semua orang yang tidak tahu cara meng-host executable 40GB dengan benar
    Dengan kekuatan cloud, program ini tak akan bisa dihentikan

    • Ini benar-benar terlihat seperti sedang menunggu untuk dijadikan fungsi Lambda

  • Menakjubkan bahwa tidak ada yang menyoroti bahwa program itu “memproses” instruksi 40GB hanya dengan pembacaan disk sekitar 800 MB/s * 10 detik
    Dugaan saya, ada caching cerdas di level sistem operasi, tetapi kalau begitu berarti benchmark dengan n mendekati 2^32 tidak benar-benar dijalankan dengan layak
    Atau mungkin CPU cukup pintar untuk melompati ratusan juta instruksi

    • Jika itu “perangkat gaming bertenaga dengan memori 31.8GB”, maka kalau caching file system cukup kuat untuk pemindaian berulang/berurutan, saat dijalankan ulang mungkin hanya perlu membaca sekitar 8GB
      Awalnya saya kira hitungannya pasti salah, tetapi setelah dihitung kasar ternyata cukup masuk akal. Angkanya juga semuanya dibulatkan secara agak samar, dan nilai inputnya juga bukan maksimum mutlak melainkan hanya nilai yang tinggi, jadi makin masuk akal
    • Kemungkinan karena kompresi atau data yang masih tertinggal di RAM. CPU tidak bisa bersikap pintar di sini karena ia tidak tahu seperti apa if di masa depan
      Ia tidak tahu apakah kode-kode itu berurutan, unik, atau bahkan instruksi yang valid. Secara teori, saat program berjalan, salah satu if itu bisa saja diubah menjadi loop tak hingga. Walau sistem operasinya mungkin tidak akan mengizinkan
    • Ada juga paging prediktif. Sistem operasi bisa menebak halaman yang akan diminta berikutnya
    • Tidak mungkin karena CPU. Pada praktiknya ini adalah kode yang dimemory-map, dan branch predictor tidak mungkin memicu page fault untuk memuat halaman kode berikutnya
      Saya benar-benar penasaran. Pola akses linear memang akan membantu, tapi 800 MiB/s?
    • Karena programnya di-mmap, halaman yang tidak dipakai hanya memakan entri page table dan tidak dimuat. Yang benar-benar dimuat hanyalah halaman yang dilompati secara langsung. Trik yang rapi

  • Jenius visioner Ross van der Gussom sekarang adalah makhluk mitologi favorit saya

    • Lihat saja Python sebagai cara menskrip C dan lewati sebagian besar atau seluruh proses kompilasi. Jika Python terasa lambat, mungkin Anda memakainya dengan salah
      Saya merekomendasikan tulisan ini: https://cerfacs.fr/coop/fortran-vs-python
    • Saya sempat mencari di web untuk melihat apakah “Ross van der Gussom” itu lelucon internal, tetapi dua hasil teratas justru tulisan asli dan komentar induk ini

  • Seluruh tulisan ini terasa seperti alegori tentang pengembangan LLM. Jika ditulis oleh pengkritik, ini bisa disebut sebagai solusi yang “menghafal” dengan sumber daya dan “data pelatihan” dalam jumlah luar biasa besar
    Saya jadi penasaran apakah itu memang maksud penulisnya

    • Hanya dari judulnya saya mengira ini tulisan pengumuman model 4B baru, jadi mungkin benar
    • Saya membaca judulnya dan langsung mengira ini pasti tulisan tentang LLM
    • Betul. Ini tampak seperti model LLM 40B yang menjalankan loop for. Alegori ini terasa seperti motivasi sebenarnya dari tulisan itu, dan seperti tulisan yang membahas absurditas yang akan segera datang, bukan sekadar cerita rekayasa teknik