{fmt} diperkecil: ukuran biner turun menjadi 14k dan runtime C++ dihapus

• {fmt} adalah library formatting C++ yang selama ini mengurangi pembengkakan template lewat type erasure; dalam eksperimen ini, executable sederhana yang menjalankan fmt::print diperkecil dari 75kB menjadi 14kB
• Struktur intinya adalah format mendelegasikan ke vformat yang bukan template, dan tipe output juga disembunyikan melalui API buffer, sehingga ukuran biner dan waktu build dapat dikurangi sekaligus
• Di aarch64 Ubuntu 22.04 dan GCC 11.4.0, executable stripped dari {fmt} 11.0.2 berukuran 75kB; dengan menonaktifkan locale, mengurangi tipe bawaan, dan memakai makro optimasi ukuran, ukurannya turun 71kB → 31kB → 27kB → 23kB
• Penghapusan runtime C++ dimungkinkan dengan menangani exception melalui FMT_THROW sebagai abort, melakukan build dengan -fno-exceptions, -nodefaultlibs, -lc, lalu mengganti allocator default basic_memory_buffer menjadi berbasis malloc/free
• Executable akhir berukuran 14kB; mengingat main C kosong pada sistem yang sama berukuran 6kB, ukuran tambahan dari {fmt} kurang dari 10kB, dan ldd juga tidak menunjukkan dependensi runtime C++

---

Cara {fmt} menghasilkan biner kecil

• {fmt} formatting library sering menghasilkan kode per pemanggilan fungsi yang beberapa kali lebih kecil dibanding alternatif seperti IOStreams, Boost Format, dan tinyformat
• Kuncinya ada pada struktur yang menerapkan type erasure di beberapa lapisan untuk mengurangi pembengkakan template
• Argumen formatting dihapus tipenya menjadi format_args
  • Fungsi template format mendelegasikan pekerjaan sebenarnya ke vformat yang bukan template
  • Output iterator dan tipe output lain juga dihapus tipenya melalui API buffer terpisah
• Penggunaan template dibatasi pada lapisan tipis di level paling atas, dan struktur ini berkontribusi pada biner yang lebih kecil serta waktu kompilasi C++ yang lebih cepat

Ukuran kode mendekati printf dengan keamanan yang lebih kuat

• Program contoh hanya memanggil fmt::print("The answer is {}.", 42);
• Hasil kompilasinya jauh lebih kecil daripada IOStreams, dan berada pada level yang mirip dengan contoh printf
  • Contoh {fmt} di Godbolt: godbolt
  • Contoh printf di Godbolt: godbolt
• Berbeda dari printf, {fmt} menyediakan keamanan tipe saat runtime
  • Kesalahan string format dapat ditangkap pada compile time
  • Meski string format ditentukan saat runtime, error ditangani dengan exception sehingga perilaku tak terdefinisi, kerusakan memori, dan potensi crash dapat dihindari
• Saat memakai argumen posisional (positional arguments) yang tidak cocok dengan baik dengan argumen variadik C, pemanggilan {fmt} umumnya lebih efisien

Ukuran dasar dan penghapusan locale

• Dalam optimasi ukuran library pada 2020, {fmt} pernah diperkecil hingga di bawah 100kB, sekitar 57kB dengan -Os -flto
• Setelah itu, {fmt} mulai menggunakan algoritme Dragonbox yang dikontribusikan oleh Junekey Jeon untuk formatting floating-point
• Pengukuran kali ini didasarkan pada ukuran executable yang dirasakan pengguna akhir, dan dilakukan di aarch64 Ubuntu 22.04 dengan GCC 11.4.0
• Build dasar {fmt} 11.0.2 berukuran 75kB setelah -Os -flto -DNDEBUG dan strip
  • Meski ada berbagai perubahan selama 4 tahun terakhir, ukurannya tidak banyak mengalami kemunduran
• Jika dukungan locale dinonaktifkan dengan FMT_STATIC_THOUSANDS_SEPARATOR, ukuran biner turun menjadi 71kB
  • Formatting {fmt} secara default independen dari locale
  • Locale dapat digunakan secara opsional dengan specifier format L

Pengurangan tipe bawaan dan model “tidak membayar untuk yang tidak dipakai”

• Analisis Bloaty menunjukkan bahwa formatting angka, khususnya formatting floating-point, mengambil porsi besar dari ukuran biner
  • Formatting floating-point juga memakai tabel, dan tabel tersebut tidak tampak dalam output Bloaty
• Beban mendasar muncul karena fungsi formatting harus mengetahui semua tipe yang bisa diformat
  • Pendekatan ini cocok untuk printf dalam standar C, tetapi bukan syarat wajib bagi {fmt}
  • {fmt} mendukung API ekstensi yang dapat memformat tipe arbitrer tanpa perlu mengetahui seluruh kumpulan tipe sebelumnya
• Dalam implementasi eksperimental, FMT_BUILTIN_TYPES=0 disetel agar hanya int yang ditangani secara khusus, sementara tipe lain dikirim ke API ekstensi umum
  • int diperlukan untuk pemrosesan lebar dan presisi dinamis
  • Contoh: fmt::print("{:{}}\n", "hello", 10); mencetak "hello "
• Pendekatan ini menyediakan model tidak membayar biaya tipe yang tidak dipakai, tetapi ukuran biner per pemanggilan sedikit meningkat
  • Jika floating-point atau tipe lain benar-benar diformat, kode terkait tetap akan disertakan dalam build
• Setelah menerapkan FMT_BUILTIN_TYPES=0, biner contoh turun menjadi 31kB
• Setelah jejak terkait locale yang tersisa dihapus pada e582d37 dan b3ccc2d, serta bisa dimatikan lebih jelas melalui makro FMT_USE_LOCALE, ukurannya menjadi 27kB

Pilihan antara kecepatan dan ukuran, serta penghapusan runtime C++

• Di dalam library ada beberapa bagian yang mengorbankan ukuran demi kecepatan
• do_count_digits, yang menghitung jumlah digit desimal, menggunakan tabel 256 byte
  • Mengubah implementasi ini secara tanpa syarat dapat berdampak negatif pada use case lain
  • Implementasi fallback untuk kasus seperti constexpr yang tidak dapat memakai __builtin_clz juga sudah ada
• Makro FMT_OPTIMIZE_SIZE ditambahkan agar pengguna dapat mengontrol apakah implementasi fallback digunakan
  • Dengan penyesuaian ini dan beberapa perubahan serupa, ukuran biner menjadi 23kB
• Untuk menghilangkan dependensi pada C++ standard library, exception dapat dinonaktifkan melalui FMT_THROW
  • Contohnya memakai FMT_THROW(s)=abort() dan -fno-exceptions
  • Ini umumnya tidak direkomendasikan, tetapi bisa dapat diterima untuk sebagian use case ketika sebagian besar error tertangkap saat compile time
• Jika build dilakukan dengan -nodefaultlibs -lc, dependensi runtime C++ yang tersisa berasal dari fmt::basic_memory_buffer
  • Buffer ini adalah buffer kecil yang dialokasikan di stack dan diperluas ke memori dinamis jika diperlukan
  • fmt::print umumnya dapat menulis langsung ke buffer FILE, sehingga alokasi dinamis tidak diperlukan
• Sebagai solusi yang lebih umum, allocator default diganti dari new/delete menjadi berbasis malloc/free
  • Setelah perubahan ini, ukuran biner akhir menjadi 14kB
  • Karena program main C kosong pada sistem yang sama berukuran 6kB, ukuran tambahan dari {fmt} kurang dari 10kB
• Hasil ldd a.out hanya menunjukkan libc.so.6 dan loader, tanpa dependensi runtime C++
• Hasil akhir menunjukkan bahwa {fmt} dapat digunakan dengan ukuran lebih kecil di lingkungan embedded dan yang memiliki keterbatasan memori

[GN⁺]

Pendapat di Hacker News

• Ini sebenarnya lebih merupakan masalah kecenderungan komite, jadi saya tidak berharap fmt, sebagai pustaka pihak ketiga, sengaja punya default yang buruk
  Yang mengejutkan, ketika fitur ini distandardisasi sebagai std::format di C++20, komite tidak memasukkan kembali kesalahan ini yang ada di banyak bagian lain standar
  Jadi masih ada sedikit harapan bagi para pengusul yang memohon agar C++ tidak dibuat lebih buruk tanpa perlu hanya demi membuatnya “konsisten”

• Kalau melihat jumlah kode yang dibutuhkan untuk pemformatan floating-point, cukup mengejutkan
  Proyek Dragonbox [1] yang ditautkan juga layak dibaca, dan bahkan cabang yang hampir tidak pernah dipakai pun cukup dioptimalkan
  [1] https://github.com/jk-jeon/dragonbox

  • Saat belakangan mengerjakan Zig, saya jadi tahu betapa banyaknya kode yang diperlukan untuk pemformatan floating-point
    Biasanya compiler Zig tidak bergantung pada C runtime di Windows, sehingga bisa membuat biner yang lebih kecil daripada MSVC, tetapi kali ini binernya anehnya besar dibandingkan pekerjaan yang dilakukan tool tersebut
    Setelah membukanya dengan Binary Ninja, ternyata sebagian besar kodenya untuk dukungan pemformatan floating-point, dan setelah saya meng-cast angka floating-point ke integer sebelum output, ukurannya turun ke ukuran yang saya harapkan
  • https://github.com/jk-jeon/dragonbox/discussions/57#discussioncomment-9340182
    Saya sedang bereksperimen dengan optimasi ukuran, dan saat ini bisa diperkecil hingga sekitar 3k di AVR 8-bit
    Itu hanya mencakup implementasi dan tabel untuk binary32 presisi tunggal, dan presisi ganda akan membutuhkan jauh lebih banyak, tetapi pada saat yang sama sebagian besar pembengkakan itu disebabkan oleh keterbatasan AVR
    Di platform seperti x64 ukurannya bisa jauh lebih kecil, tetapi 3k pun masih bisa dibilang besar
  • Kalau ingin membuatnya cepat, perlu banyak kode
    Implementasi acuan pada akhirnya juga merupakan implementasi aritmetika presisi arbitrer, tetapi tidak terlalu buruk
    [1] https://research.swtch.com/ftoa
    [2] https://go.dev/src/strconv/ftoa.go
  • {fmt} punya implementasi opsional dari algoritma Dragon4 yang lebih lama; ukuran kodenya lebih kecil, tetapi lebih lambat
  • Kebanyakan kasus penggunaan sepertinya akan membatasi jumlah digit desimal yang dicetak
    Saya penasaran apakah pendekatan mengalikan sesuai jumlah digit desimal, lalu mengubahnya ke integer, melewatkannya ke itoa(), kemudian menyisipkan titik desimal di posisi yang tepat akan lebih efisien

• Dari sudut pandang pemula C++, saya penasaran: apakah allocator default libc++, yakni implementasi new/delete default, secara internal melakukan sesuatu yang benar-benar berbeda dari memanggil malloc/free milik libc? Kalau ya, mengapa?

  • Saya bukan orang yang sangat kuat di C++, tetapi new[] akan memanggil operator new untuk mendapatkan memori lalu menjalankan konstruktor tiap elemen
    delete[] akan menjalankan destruktor tiap elemen sebelum membebaskan memori
    Agar delete[] bisa bekerja, C++ harus melacak ukuran alokasi di suatu tempat, dan informasi ini bisa diletakkan di dekat area alokasi atau di struktur terpisah
    Jika memakai struktur terpisah, kemungkinan informasi itu tertimpa saat memori setelah objek disalahgunakan akan lebih kecil, tetapi butuh biaya lookup dan kode tambahan
    Pustaka C++ yang benar akan melakukan lebih banyak hal, tetapi dari sini bisa terasa bahwa new/delete tidak sama dengan malloc/free
  • ISO C++ tidak mewajibkan implementasi default new/delete untuk memanggil malloc()/free()
    Banyak implementasi melakukannya hanya karena sudah ada dan mudah digunakan
  • Selain overload alokasi berpenyelarasan, pada dasarnya tidak berbeda
    Namun aplikasi bisa mengganti operator new pustaka standar default dengan implementasinya sendiri, bahkan di platform yang tidak punya fitur setara interposisi simbol ELF
  • Alasan utama menggantinya dengan malloc adalah karena new melempar std::bad_alloc, sehingga jika memakainya harus menautkan C++ runtime

• Untuk pustaka pemformatan yang dirancang kecil dan bisa mencetak string serta integer, saya sempat berharap ukurannya kira-kira 50 byte
  Untuk string, cukup sekitar 4 instruksi: cek karakter terminator null, cetak karakter, lalu branch mundur dua langkah
  Untuk integer, sekitar 20 instruksi: cek negatif lalu cetak '-' dan balik tanda, masukkan 1000000000 ke R1, bagi dan simpan sisa, tambahkan ASCII '0', cetak karakter, bagi R1 dengan 10, masukkan sisa sebagai input, ulangi sampai R1=0
  Floating-point tidak dipakai di banyak program, jadi semestinya hanya dikompilasi saat dibutuhkan; begitu juga heksadesimal, pointer, dan padding nol di depan
  Saat menulis kode untuk mikrokontroler dengan ruang kode 2KB, saya tidak akan memasukkan pustaka pemformatan string berukuran 14KB

  • Ini bukan pustaka output integer/string lambat tanpa modifier, melainkan pustaka pemformatan yang kaya fitur
    Tidak mungkin membuat pustaka yang sekaligus kaya fitur, cepat, dan kecil
  • Desain pustaka untuk mikrokontroler dan desain pustaka yang “setara” untuk aplikasi pengguna akhir umum berbeda di hampir semua titik penting
    Saya tidak begitu melihat apa bedanya ini dari keluhan umum yang disampaikan di ruang publik, bukan sesuatu yang khusus untuk fmt
    Kode algoritma seperti Dragonbox atau Dragon4 saja sudah melampaui anggaran ukuran, jadi fitur “opsional” tidak terlalu penting
    Dan itu baru salah satu dari sekitar 20 fitur yang orang-orang inginkan
  • Kalau begitu, sepertinya lebih tepat untuk membuka pustaka yang benar-benar Anda pakai dan mendokumentasikan fitur pemformatan apa saja yang didukungnya
    Dengan begitu orang lain mungkin bisa menemukan cara yang lebih cerdas untuk memasukkan lebih banyak fitur
    Kalau tidak, saya kurang paham poinnya
  • Menurut saya kebutuhan dari niche pemrograman tertentu tidak semestinya memengaruhi bahasa dengan cara seperti itu
    Kebutuhan itu valid, tetapi itu urusan compiler mikrokontroler berspesifikasi minimum, bukan spesifikasi bahasa
  • Tujuan utama pustaka ini bukan membuatnya kecil, melainkan membuat pustaka pemformatan string yang lengkap dengan ukuran sebagai tujuan sekunder yang penting
    Kalau yang dibutuhkan adalah sesuatu yang sangat kecil dengan mengorbankan dukungan fitur dasar, jelas ada pilihan yang lebih baik
    Jika ruang kode hanya 2KB, jangan gunakan ini
    Untungnya kebanyakan mikrokontroler modern jauh lebih besar dari itu; misalnya esp32 mulai dari 1MB, jadi memakai pustaka pemformatan 14KB juga cukup masuk akal

• Sekadar promosi sedikit, bahkan dengan menyertakan libc yang punya buffering output, printf(Hello, World!\n"); bisa menjadi executable 1008 byte: https://github.com/pts/minilibc686
  Tentu saja, perbandingan langsungnya seperti membandingkan apel dan jeruk

  • Itu karena compiler mengubahnya menjadi fputs

• Bagian “Jika program C dengan fungsi main kosong berukuran 6kB di sistem ini, {fmt} sekarang hanya menambahkan kurang dari 10kB ke biner” menarik
  Saya belum pernah melakukan tes seperti ini

  • Ini sangat bergantung pada apakah C library ditautkan secara dinamis atau statis, serta bagaimana aplikasi dan C library tersebut dibangun
    C library mana yang dipakai juga penting, dan apakah memakai ELF atau container lain juga sedikit berpengaruh

• Selalu saja fmt yang jadi masalah
  Lucu sekali bahwa ketika menyentuh cukup banyak angka, khususnya pemformatan/parsing floating-point dan decimal, linker menarik banyak kode terkait floating-point dan BigInt sehingga ukuran biner membengkak; hal yang sama sekarang juga terjadi di .NET

  • Di Native AOT, saya masih mengharapkan pengalaman seperti Delphi, dan untungnya makin lama makin membaik

• Sangat menarik
  Saya suka optimasi dengan perubahan cara berpikir seperti ini

• Entah saya yang lambat, tapi butuh beberapa saat bagi saya untuk menyadari bahwa “14k” di judul berarti 14kB

  • Memangnya bisa berarti apa lagi
    Setidaknya secara historis, k adalah singkatan umum untuk kB