Reducing {fmt} library size 4x using Bloaty McBloatface

When it comes to comparing different software solutions, speed is often the main if not the only factor considered. This is not the case in the {fmt} library which tries to find a good balance between speed, binary size and compile times by default and give you an option to get maximum performance in cases that matter.

A lot of effort has been put into making binary code at the usage site very compact, comparable to that of printf. For example (godbolt):

#include <fmt/core.h>

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

compiles to just

main:                                   # @main
        sub     rsp, 24
        mov     qword ptr [rsp], 42
        mov     rcx, rsp
        mov     edi, offset .L.str
        mov     esi, 18
        mov     edx, 1
        call    fmt::v6::vprint(fmt::v6::basic_string_view<char>, fmt::v6::format_args)
        xor     eax, eax
        add     rsp, 24
        ret
.L.str:
        .asciz  "The answer is {}.\n"

Compare this to iostreams (godbolt):

#include <iostream>

int main() {
  std::cout << "The answer is " << 42 << ".\n";
}
main:                                   # @main
        push    rax
        mov     edi, offset std::cout
        mov     esi, offset .L.str
        mov     edx, 14
        call    std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
        mov     edi, offset std::cout
        mov     esi, 42
        call    std::basic_ostream<char, std::char_traits<char> >::operator<<(int)
        mov     esi, offset .L.str.1
        mov     edx, 2
        mov     rdi, rax
        call    std::basic_ostream<char, std::char_traits<char> >& std::__ostream_insert<char, std::char_traits<char> >(std::basic_ostream<char, std::char_traits<char> >&, char const*, long)
        xor     eax, eax
        pop     rcx
        ret
_GLOBAL__sub_I_example.cpp:             # @_GLOBAL__sub_I_example.cpp
        push    rax
        mov     edi, offset std::__ioinit
        call    std::ios_base::Init::Init() [complete object constructor]
        mov     edi, offset std::ios_base::Init::~Init() [complete object destructor]
        mov     esi, offset std::__ioinit
        mov     edx, offset __dso_handle
        pop     rax
        jmp     __cxa_atexit            # TAILCALL
.L.str:
        .asciz  "The answer is "

.L.str.1:
        .asciz  ".\n"

(You can ignore the _GLOBAL__sub_I_example.cpp part.)

Not only {fmt}’s binary code is smaller, it has fewer function calls and is faster. And this is one of the best cases for iostreams specifically chosen to avoid blog post bloat. With ostringstream the compiler can generate half of a kilobyte of binary code even for trivial formatting (see e.g. Binary code comparison). Code bloat is a common problem with concatenation-based formatting methods compared to replacement-based ones like printf.

While per-use binary size in {fmt} is highly optimized, little effort has been put so far into making the library itself smaller. We try not to do anything obviously silly that would result in an explosion of template instantiations but little more than that.

At the same time, reducing library size has been a frequently requested feature from folks working on mobile and embedded systems. So I finally decided to look into this problem more systematically. In this post I use the wonderfully named and overall super nice tool called Bloaty McBloatface, a size profiler for binaries, to try making the {fmt} library smaller.

Let’s use the earlier example and compile it with {fmt} revision 5b02881.

test.cc:

#include <fmt/core.h>

int main() {
  fmt::print("The answer is {}.\n", 42);
}
% clang++ -std=c++17  -I include -O2 -DNDEBUG test.cc src/format.cc
% strip a.out
% ls -l a.out
...  367708 May 21 08:24 a.out

So we start with ~368k which seems excessive even considering that {fmt} implements a replacement for (s)printf, iostreams and double-conversion including full implementation of Grisu3 and Dragon4 floating point formatting algorithms. Can we do better?

Recompiling the test binary to restore symbols and running bloaty gives the following result:

% bloaty a.out -d symbols
     VM SIZE                                                                    FILE SIZE
 --------------                                                              --------------
  59.5%   242Ki fmt::v6::internal::basic_writer<>::write_padded<>()            242Ki  59.5%
  13.3%  54.1Ki [152 Others]                                                  54.1Ki  13.3%
   3.4%  13.7Ki fmt::v6::internal::format_decimal<>()                         13.7Ki   3.4%
   3.0%  12.3Ki fmt::v6::internal::basic_writer<>::int_writer<>::on_num()     12.3Ki   3.0%
   ...

As you can see write_padded is responsible for 59% of the binary code. So much for not doing anything silly 🤦😂. This function adds padding before and after the formatted argument so that it appears aligned to the left, center, or right per format specifications. For example, in

fmt::print("{:>10}", 42);

it will write 8 spaces and then call a function that writes “42”.

template <typename F> void write_padded(const format_specs& specs, F&& f) {
  unsigned width = to_unsigned(specs.width);
  size_t size = f.size();
  size_t num_code_points = width != 0 ? f.width() : size;
  if (width <= num_code_points) return f(reserve(size));
  size_t padding = width - num_code_points;
  size_t fill_size = specs.fill.size();
  auto&& it = reserve(size + padding * fill_size);
  if (specs.align == align::right) {
    it = fill(it, padding, specs.fill);
    f(it);
  } else if (specs.align == align::center) {
    std::size_t left_padding = padding / 2;
    it = fill(it, left_padding, specs.fill);
    f(it);
    it = fill(it, padding - left_padding, specs.fill);
  } else {
    f(it);
    it = fill(it, padding, specs.fill);
  }
}

Here f.size() returns the data size in code units, f.width() returns width in user-perceived characters and f(it) writes the data.

write_padded itself is relatively small but because it’s used in many places and thanks to overly eager inliner we get this code bloat. Fortunately it has turned out to be a recent issue which hasn’t affected most of the earlier library versions and also very easy to fix - just mark the fill function called from write_padded as noinline:

__attribute__((noinline)) OutputIt fill(
    OutputIt it, size_t n, const fill_t<Char>& fill) {
  ...
}

This trivial change reduced the binary size from ~368k to ~245k which is better but still not perfect. Let’s look at full symbols to see why we have so many instantiations:

% bloaty a.out -d fullsymbols
     VM SIZE                                                                  FILE SIZE
 --------------                                                            --------------
  71.8%   206Ki [358 Others]                                                206Ki  71.9%
   3.8%  10.8Ki [__LINKEDIT]                                               10.8Ki   3.7%
   1.8%  5.11Ki void fmt::...fallback_format<double>(double, fmt::v6::int  5.11Ki   1.8%
   1.5%  4.21Ki void fmt::...<fmt::v6::buffer_range<wchar_t> >::write_pad  4.21Ki   1.5%
   1.4%  4.09Ki void fmt::...<fmt::v6::buffer_range<wchar_t> >::write_pad  4.09Ki   1.4%
   1.4%  4.03Ki void fmt::...<fmt::v6::buffer_range<wchar_t> >::write_pad  4.03Ki   1.4%
   ...

Many of the instantiations are for wchar_t which we don’t even need. A simple way to get rid of those is by using link-time optimization (LTO):

clang++ test.cc -O2 -I include -std=c++17 src/format.cc -DNDEBUG -flto

This reduces the binary size to ~164k. To get the same reduction without LTO let’s remove the wchar_t vformat instantiation:

template FMT_API std::wstring internal::vformat<wchar_t>(
    wstring_view, basic_format_args<wformat_context>);

This way users don’t pay for what they don’t use.

While at it I also noticed and nuked a few deprecated functions such as

     VM SIZE                                                                    FILE SIZE
 --------------                                                              --------------
   ...
   0.4%  1.28Ki fmt::v6::internal::arg_map<>::init()                         1.28Ki   0.4%

and another interesting thing - we get type_info for std::allocator which is not even a polymorphic type:

   0.0%      65 typeinfo name for std::__1::allocator<char>                      65   0.0%
   0.0%      65 typeinfo name for std::__1::allocator<unsigned int>              65   0.0%
   0.0%      65 typeinfo name for std::__1::allocator<wchar_t>                   65   0.0%

The type info is generated because we use the empty base class optimization in memory_buffer, which is a polymorphic class, inheriting from std::allocator:

template <typename T, std::size_t SIZE = inline_buffer_size,
          typename Allocator = std::allocator<T>>
class basic_memory_buffer : private Allocator ...

The type info is tiny but let’s nuke it too replacing inheritance with composition to reduce symbol noise:

template <typename T, std::size_t SIZE = inline_buffer_size,
          typename Allocator = std::allocator<T>>
class basic_memory_buffer : ... {
  Allocator alloc_;
  ...
};

In C++20 we’ll be able to use [[no_unique_address]] to get the same optimization without the unwanted side-effects.

This brings library size to ~132k (mostly thanks to removing wchar_t instantiations), even better than with LTO. However, write_padded still takes way too much space:

     VM SIZE                                                                 FILE SIZE
 --------------                                                           --------------
  30.7%  48.0Ki fmt::v6::internal::basic_writer<>::write_padded<>()        48.0Ki  30.9%
  26.0%  40.5Ki [128 Others]                                               40.4Ki  26.0%
   6.5%  10.2Ki [__LINKEDIT]                                               9.34Ki   6.0%
   ...

Let’s improve it by doing all the padding computation first and reducing the number of calls to fill:

template <typename F> void write_padded(const format_specs& specs, F&& f) {
  unsigned width = to_unsigned(specs.width);
  size_t size = f.size();
  size_t num_code_points = width != 0 ? f.width() : size;
  size_t padding = width > num_code_points ? width - num_code_points : 0;
  size_t left_padding = 0;
  if (specs.align == align::right)
    left_padding = padding;
  else if (specs.align == align::center)
    left_padding = padding / 2;
  auto&& it = reserve(size + padding * specs.fill.size());
  it = fill(it, left_padding, specs.fill);
  f(it);
  it = fill(it, padding - left_padding, specs.fill);
}

This brings the size to 108k. Now let’s reduce branching by using a bit shift to compute left_padding. Also while at it let’s pass the size and width explicitly:

const char padding_shifts[] = {
// shift     align    meaning
// -----     -------  -------
      31, // default  same as left
      31, // left     shift left padding out of existence
       0, // right    left padding takes it all
       1, // center   left padding gets half
       0  // numeric  I don't even but let's say it's similar to right
};

template <typename F>
void write_padded(const format_specs& specs, size_t size, size_t width,
                  const F& f) {
  unsigned spec_width = to_unsigned(specs.width);
  size_t padding = spec_width > width ? spec_width - width : 0;
  size_t left_padding = padding >> data::padding_shifts[specs.align];
  auto&& it = reserve(size + padding * specs.fill.size());
  it = fill(it, left_padding, specs.fill);
  it = f(it);
  it = fill(it, padding - left_padding, specs.fill);
}

Now we are at ~104k and optimized write_padded so much (30x) that it is no longer the main contributor to the binary size (yay!):

     VM SIZE                                                                 FILE SIZE
 --------------                                                           --------------
  30.6%  37.9Ki [125 Others]                                               37.8Ki  30.6%
   8.0%  9.95Ki [__LINKEDIT]                                               9.39Ki   7.6%
   7.5%  9.24Ki fmt::v6::internal::basic_writer<>::write_int<>()           9.24Ki   7.5%
   6.4%  7.97Ki fmt::v6::internal::write_padded<>()                        7.97Ki   6.5%
   ...

Let’s look into write_int which is an internal function used for fancy integer formatting. It writes an integer in the format <left-padding><prefix><numeric-padding><digits><right-padding> per format specs:

template <typename F>
void write_int(int num_digits, string_view prefix, format_specs specs, F f) {
  std::size_t size = prefix.size() + to_unsigned(num_digits);
  char_type fill = specs.fill[0];
  std::size_t padding = 0;
  if (specs.align == align::numeric) {
    auto unsiged_width = to_unsigned(specs.width);
    if (unsiged_width > size) {
      padding = unsiged_width - size;
      size = unsiged_width;
    }
  } else if (specs.precision > num_digits) {
    size = prefix.size() + to_unsigned(specs.precision);
    padding = to_unsigned(specs.precision - num_digits);
    fill = static_cast<char_type>('0');
  }
  if (specs.align == align::none) specs.align = align::right;
  out_ = write_padded(out_, specs, size, [=](reserve_iterator it) {
    ...
  });
}

Here prefix is a base prefix such as “0x” and f is a callable that writes digits through the output iterator. We can optimize this by moving the part that doesn’t depend on F to a separate function only parameterized by the character type:

template <typename Char> struct write_int_params {
  std::size_t size;
  std::size_t padding;
  Char fill;
};

template <typename Char>
write_int_params<Char> make_write_int_params(int num_digits, string_view prefix,
                                             basic_format_specs<Char>& specs) {
  std::size_t size = prefix.size() + to_unsigned(num_digits);
  Char fill = specs.fill[0];
  std::size_t padding = 0;
  if (specs.align == align::numeric) {
    auto width = to_unsigned(specs.width);
    if (width > size) {
      padding = width - size;
      size = width;
    }
  } else if (specs.precision > num_digits) {
    size = prefix.size() + to_unsigned(specs.precision);
    padding = to_unsigned(specs.precision - num_digits);
    fill = static_cast<Char>('0');
  }
  if (specs.align == align::none) specs.align = align::right;
  return {size, padding, fill};
}

template <typename F>
void write_int(int num_digits, string_view prefix, format_specs specs, F f) {
  auto params = make_write_int_params(num_digits, prefix, specs);
  out_ = write_padded(out_, specs, params.size, [=](reserve_iterator it) {
    ...
  });
}

Bloaty also shows some suspicious instantiations of int_writer for signed integral types:

     VM SIZE                                                          FILE SIZE
 --------------                                                    --------------
   ...
   0.7%     863 fmt::...basic_writer<...>::int_writer<int...       863   0.7%
   0.7%     863 fmt::...basic_writer<...>::int_writer<long...      863   0.7%

Why are these suspicious? {fmt} tries to reduce the number of instantiations of internal templates by mapping integral types into a smaller subset which still covers all possible bit sizes. On most platforms it’s just 3 unsigned types: 32-bit, 64-bit and 128-bit. However, int_writer slipped through the cracks and was accidentally instantiated for signed types. This also explains much of the code bloat we’ve seen so far because those functions are used from int_writer.

template <typename Int> struct int_writer {
  using unsigned_type = uint32_or_64_or_128_t<Int>;

  int_writer(basic_writer<Range>& w, Int value,
             const basic_format_specs<char_type>& s)
      : abs_value(static_cast<unsigned_type>(value)), ...

The fix is to move type mapping (uint32_or_64_or_128_t<Int>) from the int_writer class to its constructor and add a static assert so that it doesn’t happen again:

 template <typename UInt> struct int_writer {
  template <typename Int>
  int_writer(basic_writer<Range>& w, Int value,
             const basic_format_specs<char_type>& s)
      : abs_value(static_cast<UInt>(value)), ... {
    static_assert(std::is_same<uint32_or_64_or_128_t<Int>, UInt>::value, "");
  }

This reduces the binary size to ~92k. We can go even further by compiling with -Os instead of -O2 which gives ~75k or with -Os -flto which gives ~57k.

Summary

With the help of Bloaty McBloatface and a few simple transformations we managed to reduce library size 4x, from 368k to just 92k without affecting performance. These improvements have been achieved by

  • reducing the number of template instantiations,
  • reducing inlining,
  • moving code that doesn’t have to be parameterized outside of templates,
  • reducing branching.

Numbers reported here are obtained on x86-64 macOS with clang++ and -O2. On embedded/mobile targets they will likely be smaller. It is possible to reduce library size even more by disabling floating-point support which could be useful on some embedded platforms.

All of these size optimizations and more are already available in {fmt}’s master and will ship in the next major release since they affect ABI.

comments powered by Disqus