The {fmt} formatting library is known for its small binary footprint, often producing code that is several times smaller per function call compared to alternatives like IOStreams, Boost Format, or, somewhat ironically, tinyformat. This is mainly achieved through careful application of type erasure on various levels, which effectively minimizes template bloat.

Formatting arguments are passed via type-erased format_args:

auto vformat(string_view fmt, format_args args) -> std::string;

template <typename... T>
auto format(format_string<T...> fmt, T&&... args) -> std::string {
  return vformat(fmt, fmt::make_format_args(args...));
}

As you can see, format delegates all its work to vformat, which is not a template.

Output iterators and other output types are also type-erased through a specially designed buffer API.

This approach confines template usage to a minimal top-level layer, leading to both a smaller binary size and faster build times.

For example, the following code:

// test.cc
#include <fmt/base.h>

int main() {
  fmt::print("The answer is {}.", 42);
}

compiles to just

.LC0:
        .string "The answer is {}."
main:
        sub     rsp, 24
        mov     eax, 1
        mov     edi, OFFSET FLAT:.LC0
        mov     esi, 17
        mov     rcx, rsp
        mov     rdx, rax
        mov     DWORD PTR [rsp], 42
        call    fmt::v11::vprint(fmt::v11::basic_string_view<char>, fmt::v11::basic_format_args<fmt::v11::context>)
        xor     eax, eax
        add     rsp, 24
        ret

godbolt

It is much smaller than the equivalent IOStreams code and comparable to that of printf:

.LC0:
        .string "The answer is %d."
main:
        sub     rsp, 8
        mov     esi, 42
        mov     edi, OFFSET FLAT:.LC0
        xor     eax, eax
        call    printf
        xor     eax, eax
        add     rsp, 8
        ret

godbolt

Unlike printf, {fmt} offers full runtime type safety. Errors in format strings can be caught at compile time, and even when the format string is determined at runtime, errors are managed through exceptions, preventing undefined behavior, memory corruption, and potential crashes. Additionally, {fmt} calls are generally more efficient, particularly when using positional arguments, which C varargs are not well-suited for.

Back in 2020, I dedicated some time to optimizing the library size, successfully reducing it to under 100kB (just ~57kB with -Os -flto). A lot has changed since then. Most notably, {fmt} now uses the exceptional Dragonbox algorithm for floating-point formatting, kindly contributed by its author, Junekey Jeon. Let’s explore how these changes have impacted the binary size and see if further reductions are possible.

But why, some say, the binary size? Why choose this as our goal?

There has been considerable interest in using {fmt} on memory-constrained devices, see e.g. #758 and #1226 for just two examples from the distant past. A particularly intriguing use case is retro computing, with people using {fmt} on systems like Amiga (#4054).

We’ll apply the same methodology as in previous work, examining the executable size of a program that uses {fmt}, as this is most relevant to end users. All tests will be conducted on an aarch64 Ubuntu 22.04 system with GCC 11.4.0.

First, let’s establish the baseline: what is the binary size for the latest version of {fmt} (11.0.2)?

$ git checkout 11.0.2
$ g++ -Os -flto -DNDEBUG -I include test.cc src/format.cc
$ strip a.out && ls -lh a.out
-rwxrwxr-x 1 vagrant vagrant 75K Aug 30 19:24 a.out

The resulting binary size is 75kB (stripped). The positive takeaway is that despite numerous developments over the past four years, the size has not significantly regressed.

Now, let’s explore potential optimizations. One of the first adjustments you might consider is disabling locale support. All the formatting in {fmt} is locale-independent by default (which breaks with the C++’s tradition of having wrong defaults), but it is still available as an opt in via the L format specifier. It can be disabled in a somewhat obscure way via the FMT_STATIC_THOUSANDS_SEPARATOR macro:

$ g++ -Os -flto -DNDEBUG "-DFMT_STATIC_THOUSANDS_SEPARATOR=','" \
      -I include test.cc src/format.cc
$ strip a.out && ls -lh a.out
-rwxrwxr-x 1 vagrant vagrant 71K Aug 30 19:25 a.out

Disabling locale support reduces the binary size to 71kB.

Next, let’s examine the results using our trusty tool, Bloaty:

$ bloaty -d symbols a.out

    FILE SIZE        VM SIZE
 --------------  --------------
  43.8%  41.1Ki  43.6%  29.0Ki    [121 Others]
   6.4%  6.04Ki   8.1%  5.42Ki    fmt::v11::detail::do_write_float<>()
   5.9%  5.50Ki   7.5%  4.98Ki    fmt::v11::detail::write_int_noinline<>()
   5.7%  5.32Ki   5.8%  3.88Ki    fmt::v11::detail::write<>()
   5.4%  5.02Ki   7.2%  4.81Ki    fmt::v11::detail::parse_replacement_field<>()
   3.9%  3.69Ki   3.7%  2.49Ki    fmt::v11::detail::format_uint<>()
   3.2%  3.00Ki   0.0%       0    [section .symtab]
   2.7%  2.50Ki   0.0%       0    [section .strtab]
   2.3%  2.12Ki   2.9%  1.93Ki    fmt::v11::detail::dragonbox::to_decimal<>()
   2.0%  1.89Ki   2.4%  1.61Ki    fmt::v11::detail::write_int<>()
   2.0%  1.88Ki   0.0%       0    [ELF Section Headers]
   1.9%  1.79Ki   2.5%  1.66Ki    fmt::v11::detail::write_float<>()
   1.9%  1.78Ki   2.7%  1.78Ki    [section .dynstr]
   1.8%  1.72Ki   2.4%  1.62Ki    fmt::v11::detail::format_dragon()
   1.8%  1.68Ki   1.5%    1016    fmt::v11::detail::format_decimal<>()
   1.6%  1.52Ki   2.1%  1.41Ki    fmt::v11::detail::format_float<>()
   1.6%  1.49Ki   0.0%       0    [Unmapped]
   1.5%  1.45Ki   2.2%  1.45Ki    [section .dynsym]
   1.5%  1.45Ki   2.0%  1.31Ki    fmt::v11::detail::write_loc()
   1.5%  1.44Ki   2.2%  1.44Ki    [section .rodata]
   1.5%  1.40Ki   1.1%     764    fmt::v11::detail::do_write_float<>()::{lambda()#2}::operator()()
 100.0%  93.8Ki 100.0%  66.6Ki    TOTAL

Unsurprisingly, a significant portion of the binary size is dedicated to numeric formatting, particularly floating-point numbers. FP formatting also relies on sizable tables, which aren’t shown here. But what if floating-point support isn’t required? {fmt} provides a way to disable it, though the method is somewhat ad hoc and doesn’t extend to other types.

The core issue is that formatting functions need to be aware of all formattable types. Or do they? This is true for printf as defined by the C standard, but not necessarily for {fmt}. {fmt} supports an extension API that allows formatting arbitrary types without knowing the complete set of types in advance. While built-in and string types are handled specially for performance reasons, focusing on binary size might warrant a different approach. By removing this special handling and routing every type through the extension API, you can avoid paying for types you don’t use.

I did an experimental implementation of this idea. With the FMT_BUILTIN_TYPES macro set to 0, only int is handled specially, and all other types go through the general extension API. We still need to know about int for dynamic width and precision, for example

fmt::print("{:{}}\n", "hello", 10); // prints "hello     "

This gives you the “don’t pay for what you don’t use” model, though it comes with a slight increase in per-call binary size. If you do format floating-point numbers or other types, the relevant code will still be included in the build. While it’s possible to make the FP implementation smaller, we won’t delve into that here.

With FMT_BUILTIN_TYPES=0, the binary size in our example reduced to 31kB, representing a substantial improvement:

$ git checkout 377cf20
$ g++ -Os -flto -DNDEBUG \
      "-DFMT_STATIC_THOUSANDS_SEPARATOR=','" -DFMT_BUILTIN_TYPES=0 \
      -I include test.cc src/format.cc
$ strip a.out && ls -lh a.out
-rwxrwxr-x 1 vagrant vagrant 31K Aug 30 19:37 a.out

However, the updated Bloaty results reveal some lingering locale artifacts, such as digit_grouping:

$ bloaty -d fullsymbols a.out

    FILE SIZE        VM SIZE
 --------------  --------------
  41.8%  18.0Ki  39.7%  11.0Ki    [84 Others]
   6.4%  2.77Ki   0.0%       0    [section .symtab]
   5.3%  2.28Ki   0.0%       0    [section .strtab]
   4.6%  1.99Ki   6.9%  1.90Ki    fmt::v11::detail::format_handler<char>::on_format_specs(int, char const*, char const*)
   4.4%  1.88Ki   0.0%       0    [ELF Section Headers]
   4.1%  1.78Ki   5.8%  1.61Ki    fmt::v11::basic_appender<char> fmt::v11::detail::write_int_noinline<char, fmt::v11::basic_appender<char>, unsigned int>(fmt::v11::basic_appender<char>, fmt::v11::detail::write_int_arg<unsigned int>, fmt::v11::format_specs const&, fmt::v11::detail::locale_ref) (.constprop.0)
   3.7%  1.60Ki   5.8%  1.60Ki    [section .dynstr]
   3.5%  1.50Ki   4.8%  1.34Ki    void fmt::v11::detail::vformat_to<char>(fmt::v11::detail::buffer<char>&, fmt::v11::basic_string_view<char>, fmt::v11::detail::vformat_args<char>::type, fmt::v11::detail::locale_ref) (.constprop.0)
   3.5%  1.49Ki   4.9%  1.35Ki    fmt::v11::basic_appender<char> fmt::v11::detail::write_int<fmt::v11::basic_appender<char>, unsigned __int128, char>(fmt::v11::basic_appender<char>, unsigned __int128, unsigned int, fmt::v11::format_specs const&, fmt::v11::detail::digit_grouping<char> const&)
   3.1%  1.31Ki   4.7%  1.31Ki    [section .dynsym]
   3.0%  1.29Ki   4.2%  1.15Ki    fmt::v11::basic_appender<char> fmt::v11::detail::write_int<fmt::v11::basic_appender<char>, unsigned long, char>(fmt::v11::basic_appender<char>, unsigned long, unsigned int, fmt::v11::format_specs const&, fmt::v11::detail::digit_grouping<char> const&)

After disabling these artifacts in commits e582d37 and b3ccc2d, and introducing a more user-friendly option to opt out via the FMT_USE_LOCALE macro, the binary size drops to 27kB:

$ git checkout b3ccc2d
$ g++ -Os -flto -DNDEBUG -DFMT_USE_LOCALE=0 -DFMT_BUILTIN_TYPES=0 \
      -I include test.cc src/format.cc
$ strip a.out && ls -lh a.out
-rwxrwxr-x 1 vagrant vagrant 27K Aug 30 19:38 a.out

The library includes several areas where size is traded off for speed. For example, consider this function used to compute the number of decimal digits:

auto do_count_digits(uint32_t n) -> int {
// An optimization by Kendall Willets from https://bit.ly/3uOIQrB.
// This increments the upper 32 bits (log10(T) - 1) when >= T is added.
#  define FMT_INC(T) (((sizeof(#T) - 1ull) << 32) - T)
  static constexpr uint64_t table[] = {
      FMT_INC(0),          FMT_INC(0),          FMT_INC(0),           // 8
      FMT_INC(10),         FMT_INC(10),         FMT_INC(10),          // 64
      FMT_INC(100),        FMT_INC(100),        FMT_INC(100),         // 512
      FMT_INC(1000),       FMT_INC(1000),       FMT_INC(1000),        // 4096
      FMT_INC(10000),      FMT_INC(10000),      FMT_INC(10000),       // 32k
      FMT_INC(100000),     FMT_INC(100000),     FMT_INC(100000),      // 256k
      FMT_INC(1000000),    FMT_INC(1000000),    FMT_INC(1000000),     // 2048k
      FMT_INC(10000000),   FMT_INC(10000000),   FMT_INC(10000000),    // 16M
      FMT_INC(100000000),  FMT_INC(100000000),  FMT_INC(100000000),   // 128M
      FMT_INC(1000000000), FMT_INC(1000000000), FMT_INC(1000000000),  // 1024M
      FMT_INC(1000000000), FMT_INC(1000000000)                        // 4B
  };
  auto inc = table[__builtin_clz(n | 1) ^ 31];
  return static_cast<int>((n + inc) >> 32);
}

The table used here is 256 bytes. There isn’t a one-size-fits-all solution, and changing it unconditionally might negatively impact other use cases. Fortunately, we have a fallback implementation of this function for scenarios where __builtin_clz is unavailable, such as with constexpr:

template <typename T> constexpr auto count_digits_fallback(T n) -> int {
  int count = 1;
  for (;;) {
    // Integer division is slow so do it for a group of four digits instead
    // of for every digit. The idea comes from the talk by Alexandrescu
    // "Three Optimization Tips for C++". See speed-test for a comparison.
    if (n < 10) return count;
    if (n < 100) return count + 1;
    if (n < 1000) return count + 2;
    if (n < 10000) return count + 3;
    n /= 10000u;
    count += 4;
  }
}

All that remains is to provide users with control over when to use the fallback implementation via (you guessed it) another configuration macro, FMT_OPTIMIZE_SIZE:

auto count_digits(uint32_t n) -> int {
#ifdef FMT_BUILTIN_CLZ
  if (!is_constant_evaluated() && !FMT_OPTIMIZE_SIZE) return do_count_digits(n);
#endif
  return count_digits_fallback(n);
}

With this and a few similar adjustments, we reduced the binary size to 23kB:

$ git checkout 8e3da9d
$ g++ -Os -flto -DNDEBUG -I include \
      -DFMT_USE_LOCALE=0 -DFMT_BUILTIN_TYPES=0 -DFMT_OPTIMIZE_SIZE=1 \
      test.cc src/format.cc
$ strip a.out && ls -lh a.out
-rwxrwxr-x 1 vagrant vagrant 23K Aug 30 19:41 a.out

We could likely reduce the binary size even further with additional tweaks, but let’s address the elephant in the room which is, of course, the C++ standard library. What’s the point of optimizing the size when you end up getting a megabyte or two of the C++ runtime?

While {fmt} relies minimally on the standard library, is it possible to remove it completely as a dependency? One obvious problem is exceptions and those can be disabled via FMT_THROW, e.g. by defining it to abort. In general it is not recommended but it might be OK for some use cases especially considering that most errors are caught at compile time.

Let’s try it out and compile with -nodefaultlibs and exceptions disabled:

$ g++ -Os -flto -DNDEBUG -I include \
      -DFMT_USE_LOCALE=0 -DFMT_BUILTIN_TYPES=0 -DFMT_OPTIMIZE_SIZE=1 \
      '-DFMT_THROW(s)=abort()' -fno-exceptions test.cc src/format.cc \
      -nodefaultlibs -lc

/usr/bin/ld: /tmp/cc04DFeK.ltrans0.ltrans.o: in function `fmt::v11::basic_memory_buffer<char, 500ul, std::allocator<char> >::grow(fmt::v11::detail::buffer<char>&, unsigned long)':
<artificial>:(.text+0xaa8): undefined reference to `std::__throw_bad_alloc()'
/usr/bin/ld: <artificial>:(.text+0xab8): undefined reference to `operator new(unsigned long)'
/usr/bin/ld: <artificial>:(.text+0xaf8): undefined reference to `operator delete(void*, unsigned long)'
/usr/bin/ld: /tmp/cc04DFeK.ltrans0.ltrans.o: in function `fmt::v11::vprint_buffered(_IO_FILE*, fmt::v11::basic_string_view<char>, fmt::v11::basic_format_args<fmt::v11::context>) [clone .constprop.0]':
<artificial>:(.text+0x18c4): undefined reference to `operator delete(void*, unsigned long)'
collect2: error: ld returned 1 exit status

Amazingly, this approach mostly works. The only remaining dependency on the C++ runtime comes from fmt::basic_memory_buffer, which is a small stack-allocated buffer that can grow into dynamic memory if necessary.

fmt::print can write directly into the FILE buffer and generally doesn’t require dynamic allocation. So we could remove the dependency on fmt::basic_memory_buffer from fmt::print. However, since it may be used elsewhere, a better solution is to replace the default allocator with one that uses malloc and free instead of new and delete.

template <typename T> struct allocator {
  using value_type = T;

  T* allocate(size_t n) {
    FMT_ASSERT(n <= max_value<size_t>() / sizeof(T), "");
    T* p = static_cast<T*>(malloc(n * sizeof(T)));
    if (!p) FMT_THROW(std::bad_alloc());
    return p;
  }

  void deallocate(T* p, size_t) { free(p); }
};

This reduces binary size to just 14kB:

$ git checkout c0fab5e
$ g++ -Os -flto -DNDEBUG -I include \
      -DFMT_USE_LOCALE=0 -DFMT_BUILTIN_TYPES=0 -DFMT_OPTIMIZE_SIZE=1 \
      '-DFMT_THROW(s)=abort()' -fno-exceptions test.cc src/format.cc \
      -nodefaultlibs -lc
$ strip a.out && ls -lh a.out
-rwxrwxr-x 1 vagrant vagrant 14K Aug 30 19:06 a.out

Considering that a C program with an empty main function is 6kB on this system, {fmt} now adds less than 10kB to the binary.

We can also easily verify that it no longer depends on the C++ runtime:

$ ldd a.out
        linux-vdso.so.1 (0x0000ffffb0738000)
        libc.so.6 => /lib/aarch64-linux-gnu/libc.so.6 (0x0000ffffb0530000)
        /lib/ld-linux-aarch64.so.1 (0x0000ffffb06ff000)

Hope you found this interesting and happy embedded formatting!

Last modified on 2024-08-30