{fmt}の縮小: バイナリサイズを14kBに削減し、C++ランタイムを除去
(vitaut.net)- {fmt}は型消去によってテンプレートの肥大化を抑えてきたC++フォーマットライブラリであり、今回の実験では単純な
fmt::print実行ファイルを75kBから14kBまで縮小 - 中核となる構造は、
formatがテンプレートではないvformatに処理を委譲し、出力型もバッファAPIで隠蔽する方式で、バイナリサイズとビルド時間を同時に削減できる - aarch64 Ubuntu 22.04とGCC 11.4.0において、{fmt} 11.0.2のstrip後実行ファイルは75kBで、localeの無効化と組み込み型の縮小、サイズ最適化マクロにより71kB → 31kB → 27kB → 23kBまで減少
- C++ランタイムの除去は、例外を
FMT_THROWでabort処理し、-fno-exceptions、-nodefaultlibs、-lcでビルドした後、basic_memory_bufferのデフォルトアロケータをmalloc/freeベースに変更することで可能になった - 最終的な実行ファイルは14kBで、同じシステム上の空のC
mainが6kBであることを踏まえると、{fmt}が追加するサイズは10kB未満であり、lddでもC++ランタイム依存は見られない
{fmt}が小さなバイナリを実現する仕組み
- {fmt} formatting libraryは、IOStreams、Boost Format、tinyformatといった代替手段よりも、関数呼び出しごとに生成されるコードが何倍も小さいことが多い
- 核心は、複数の層で型消去(type erasure) を適用してテンプレートの肥大化を抑える構造にある
- フォーマット引数は
format_argsによって型消去されるformatテンプレート関数は実際の処理をテンプレートではないvformatに委譲する- 出力イテレータやその他の出力型も、別のバッファAPIを通じて型消去される
- テンプレートの使用は最上位の薄い層に限定されており、この構造がより小さなバイナリとより高速なC++コンパイル時間に貢献している
printfに近いコードサイズと、より強い安全性
- 例のプログラムは
fmt::print("The answer is {}.", 42);を呼び出すだけ - コンパイル結果はIOStreamsよりはるかに小さく、
printfの例と同程度の水準 printfと異なり、{fmt}は実行時の型安全性を提供する- フォーマット文字列の誤りはコンパイル時に検出できる
- フォーマット文字列が実行時に決まる場合でも、例外によってエラーを処理し、未定義動作、メモリ破損、潜在的なクラッシュを避けられる
- Cの可変引数と相性のよくない位置引数(positional arguments) を使う場合、{fmt}の呼び出しの方が一般的に効率的
基準サイズとlocaleの除去
- 2020年のライブラリサイズ最適化では、{fmt}を100kB未満、
-Os -flto基準で約57kBまで縮小していた - その後、{fmt}はJunekey Jeonが貢献したDragonboxアルゴリズムを浮動小数点フォーマットに使うようになった
- 今回の測定はエンドユーザーが体感する実行ファイルサイズを基準とし、aarch64 Ubuntu 22.04とGCC 11.4.0で実施された
- {fmt} 11.0.2の基準ビルドは
-Os -flto -DNDEBUGとstrip後で75kB- この4年間でさまざまな変更はあったが、サイズは大きく後退していない
- localeサポートを
FMT_STATIC_THOUSANDS_SEPARATORで無効化すると、バイナリサイズは71kBに減少- {fmt}のフォーマットはデフォルトでlocale非依存
- localeは
Lフォーマット指定子で任意に利用できる
組み込み型の縮小と「使わないものにはコストを払わない」モデル
- Bloatyの分析では、数値フォーマット、特に浮動小数点フォーマットがバイナリサイズの大きな部分を占めている
- 浮動小数点フォーマットではテーブルも使用しており、そのテーブルはBloatyの出力には現れない
- 根本的な負担は、フォーマット関数がフォーマット可能なすべての型を知っていなければならない点にある
- この方式はC標準の
printfには適しているが、{fmt}では必須条件ではない - {fmt}は、型集合全体を事前に把握していなくても任意の型をフォーマットできる拡張APIをサポートしている
- この方式はC標準の
- 実験的実装では、
FMT_BUILTIN_TYPES=0を設定してintだけを特別扱いし、その他の型は汎用の拡張APIに送るintは動的な幅と精度の処理に必要- 例:
fmt::print("{:{}}\n", "hello", 10);は"hello "を出力する
- この方式は使わない型にはコストを払わないモデルを提供するが、呼び出しごとのバイナリサイズはやや増える
- 浮動小数点や他の型を実際にフォーマットすれば、関連コードは依然としてビルドに含まれる
FMT_BUILTIN_TYPES=0適用後、例のバイナリは31kBまで減少- その後、残っていたlocale関連の痕跡をe582d37とb3ccc2dで除去し、
FMT_USE_LOCALEマクロでより明確に無効化できるようにした結果、サイズは27kBになった
速度とサイズの選択、そしてC++ランタイムの除去
- ライブラリ内には、速度のためにサイズを使っている箇所がいくつもある
- 10進の桁数を計算する
do_count_digitsは256バイトのテーブルを使う- この実装を無条件に変更すると、他のユースケースに悪影響を与える可能性がある
__builtin_clzを使えないconstexprのような場合に備えたfallback実装もすでにある
FMT_OPTIMIZE_SIZEマクロを追加し、ユーザーがfallback実装を使うかどうかを制御できるようにした- この調整といくつかの類似した変更により、バイナリサイズは23kBになった
- C++標準ライブラリへの依存をなくすため、例外は
FMT_THROWで無効化できる- 例では
FMT_THROW(s)=abort()と-fno-exceptionsを使用 - 一般には推奨されないが、ほとんどのエラーがコンパイル時に検出される一部のユースケースでは問題ない場合もある
- 例では
-nodefaultlibs -lcでビルドすると、残るC++ランタイム依存はfmt::basic_memory_bufferから発生する- このバッファは小さなスタック確保バッファで、必要に応じて動的メモリに拡張される
fmt::printは通常、FILEバッファへ直接書き込めるため、動的確保は不要
- より一般的な解決策として、デフォルトアロケータを
new/deleteではなくmalloc/freeベースに置き換えた- この変更後、最終的なバイナリサイズは14kBになった
- 同じシステム上の空のC
mainプログラムは6kBなので、{fmt}が追加するサイズは10kB未満
ldd a.outの結果にはlibc.so.6とローダーだけが表示され、C++ランタイム依存は現れない- 最終結果は、組み込み環境やメモリ制約のある環境で{fmt}をより小さく使えることを示している
1件のコメント
Hacker News のコメント
これは実のところ委員会の傾向に近い問題なので、サードパーティライブラリである fmt が必ずしも悪いデフォルトを持つとは期待していません。
驚いたことに、この機能が C++20 の std::format として標準化されたとき、委員会は標準の他の多くの部分にあるこの過ちを再び入れませんでした。
なので、C++を「一貫した」ものにするという理由で不必要に悪化させないでほしいと訴える提案者にも、少しは希望があります。
浮動小数点フォーマットに必要なコード量を見ると、かなり衝撃的です。
リンクされている Dragonbox [1] プロジェクトも読む価値があり、ほとんど使われない分岐までかなり最適化されています。
[1] https://github.com/jk-jeon/dragonbox
通常、Zig コンパイラは Windows で C ランタイムに依存しないため、MSVC より小さいバイナリを作れますが、今回はツールがしていることに比べてバイナリが妙に大きかったのです。
Binary Ninja で開いてみると、コードの大半が浮動小数点フォーマットのサポート用で、出力前に浮動小数点数を整数にキャストしたところ、期待していたサイズまで縮みました。
サイズ最適化の実験をしており、現在は 8ビット AVR で約 3k まで削減できます。
単精度 binary32 向けの実装とテーブルだけを含む状態で、倍精度にははるかに多くが必要ですが、同時に肥大化のかなりの部分は AVR の制約によるものです。
x64 のようなプラットフォームではずっと小さくできますが、それでも 3k はまだ大きいと言えます。
基準実装も結局は任意精度算術の実装ですが、そこまで悪くはありません。
[1] https://research.swtch.com/ftoa
[2] https://go.dev/src/strconv/ftoa.go
小数桁数分だけ掛けてから整数に変換し、itoa() を通した後、適切な位置に小数点を挿入する方式のほうが効率的なのか気になります。
C++初心者として気になるのですが、libc++ のデフォルトアロケータ、つまりデフォルトの new/delete 実装は、内部で libc の malloc/free を呼ぶのと実際に何か違うことをしているのでしょうか？ そうだとすれば、なぜですか？
delete[] はメモリを解放する前に各要素のデストラクタを実行しようとします。
delete[] が動作するには、C++ はどこかで割り当てサイズを追跡する必要があり、この情報は割り当て領域の近くに置くことも、別の構造に置くこともできます。
別構造を使えば、オブジェクトの後方メモリを誤って使った場合に情報が上書きされる可能性は低くなりますが、検索コストと追加コードが必要になります。
まともな C++ ライブラリならもっと多くのことをするでしょうが、new/delete が malloc/free と同じではないという感覚はつかめるはずです。
多くの実装がそうしているのは、すでに存在していて使いやすいからにすぎません。
ただしアプリケーションは、ELF シンボルインターポジションに相当する機能がないプラットフォームでも、標準ライブラリのデフォルト operator new を独自実装で置き換えられます。
小さく、文字列と整数を出力できるように設計されたフォーマットライブラリなら、およそ 50バイト 程度であるべきではないかと期待していました。
文字列はヌル終端文字の検査、文字出力、2段階戻る分岐くらいで、約4命令で済みます。
整数は、負数の確認後に '-' を出力して符号反転し、1000000000 を R1 に入れて除算と剰余の保存、ASCII '0' の加算、文字出力、R1 を 10 で割る、剰余を入力に入れる、R1=0 になるまで繰り返す程度なので、約20命令で済みます。
浮動小数点は多くのプログラムでは使わないので、必要なときだけコンパイルされるべきですし、16進数・ポインタ・前方ゼロ埋めも同様です。
コード空間が 2KB のマイクロコントローラ向けコードを書くとき、14KB の文字列フォーマットライブラリは入れません。
機能が多く、速く、しかも小さいライブラリを同時に作ることはできません。
これが fmt だけに当てはまる話というより、公の場での一般的な不満と何が違うのかよく分かりません。
Dragonbox や Dragon4 のようなアルゴリズムコードだけで、すでにサイズ予算を超えるため、「任意」機能はそれほど重要ではありません。
そしてそれは、人々が欲しがる20ほどの機能のうちの1つにすぎません。
そうすれば、他の人たちがより多くの機能をもっと賢く詰め込む方法を見つけられるかもしれません。
そうでなければ、要点がよく分かりません。
その要件は妥当ですが、言語仕様ではなく、最低スペックのマイクロコントローラ用コンパイラが解決すべきことです。
基本機能すらサポートしない代わりに極端に小さくなければならないなら、もっと良い選択肢は確実にあります。
コード空間が 2KB しかないなら、これを使うべきではありません。
幸い、現代のマイクロコントローラの多くはそれよりはるかに大きく、例えば esp32 は 1MB から始まるので、14KB のフォーマットライブラリを使うのも十分に合理的です。
少し宣伝すると、出力バッファリング付きの libc を含めても、1008バイトの実行ファイルで
printf(Hello, World!\n");が可能です: https://github.com/pts/minilibc686もちろん直接比較すれば、リンゴとオレンジを比べるようなものです。
「空の main 関数を持つ C プログラムがこのシステムで 6kB なら、{fmt} は今やバイナリに 10kB 未満しか追加しない」という部分が興味深いです。
こういうテストはしたことがありません。
どの C ライブラリを使うかも重要で、ELF を使うのか別のコンテナを使うのかも多少影響します。
いつも fmt が問題です。
十分な数の数値、特に浮動小数点と decimal のフォーマット/パースに触れると、リンカが浮動小数点と BigInt 関連のコードを大量に引き込んでバイナリサイズが大きくなる、ということが今では .NET でもまったく同じように起きるのがとても笑えます。
とても面白いです。
こういう発想の転換的な最適化が好きです。
自分が鈍いのかもしれませんが、タイトルの「14k」が 14kB を意味するのだと気づくまで少し時間がかかりました。
少なくとも歴史的には、k は kB の一般的な略記です。