Дорогая, я уменьшил {fmt}: уменьшил размер до 14kB и избавился от рантайма C++

в 16:01, , рубрики: оптимизация

Библиотека форматирования {fmt} известна своим небольшим влиянием на размер бинарников. Чаще всего её код в несколько раз меньше по сравнению с такими библиотеками, как IOStreams, Boost Format или, что иронично, tinyformat. Это достигается за счет аккуратного применения стирания типов на разных уровнях, что минимизирует излишнее использование шаблонов.

Аргументы форматирования передаются через 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...));
}

Как можно заметить, format делегирует всю работу, не являющейся шаблоном, vformat.

Для итераторов вывода и других типов вывода типы стираются с помощью специального API буфера.

Подобный подход снижает использование шаблонов до минимального верхнеуровневого слоя, одновременно уменьшая размер бинарника и время компиляции.

Например, следующий код:

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

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

Компилируется до

.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

Он значительно меньше эквивалентного кода IOStreams и сравним с 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

В отличие от printf, {fmt} предоставляет полную типобезопасность в рантайме. Ошибки в строках форматирования могут быть пойманы еще на этапе компиляции, но даже если строки определяются в рантайме, ошибки обрабатываются как исключения, предотвращая неопределенное поведение, повреждение памяти и потенциальные вылеты. Также в целом вызовы {fmt} более эффективны, особенно когда используются позиционные аргументы, для чего C varargs не очень подходят.

В 2020 году я посвятил некоторое количество времени оптимизации размера библиотеки, успешно уменьшив ее размер до менее 100 kB (всего ~57 kB при использовании -Os -flto). Многое изменилось с тех пор. В частности, {fmt} теперь использует выдающийся алгоритм Dragonbox для форматирования чисел с плавающей запятой, любезно предоставленный его автором Junekey Jeon. Давайте посмотрим, как эти изменения повлияли на размер бинарного файла и можно ли уменьшить его еще больше.

Кто‑то может спросить: почему именно размер бинарного файла?

Использование {fmt} на устройствах с ограниченным размером памяти вызвало значительный интерес — в частности, эти примеры из далекого прошлого: #758 и #1226. Особенно интригующий кейс — программирование под ретро‑машины, где люди используют {fmt} для таких систем, как Amiga (#4054).

Мы будем использовать ту же методологию, что и раньше, исследуя размер исполняемого файла программы, использующей {fmt}, поскольку это будет наиболее релевантно для большинства пользователей. Все тесты будут проводиться на платформе с aarch64 Ubuntu 22.04 и GCC 11.4.0.

В первую очередь определим начальную точку: какой размер бинарного файла у последней версии {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

Размер полученного файла — 75 kB. Из положительного можно отметить, что, несмотря на значительное количество изменений за последние 4 года, размер значительно не увеличился.

Пришло время рассмотреть возможные пути оптимизации. Одним из первых кандидатов может быть отключение поддержки локалей. Все форматирование в {fmt} локале‑независимое по умолчанию (что нарушается из‑за традиции C++ иметь некорректные значения по умолчанию), но все еще доступно с помощью спецификатора формата L. Его можно отключить, используя макрос FMT_STATIC_THOUSANDS_SEPARATOR:

$ 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

Отключение поддержки локалей уменьшает размер бинарного файла до 71 kB.

Теперь проверим результат с помощью нашего верного инструмента — 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

Значительную часть бинарного файла занимает код, посвященный форматированию чисел, в особенности — чисел с плавающей запятой. Форматирование последних также полагается на использование больших таблиц, не показанных здесь. Но что, если поддержка чисел с плавающей запятой нам не требуется? {fmt} позволяет отключить ее, хотя метод отключения немного спонтанный и не распространяется на другие типы.

Основная проблема в том, что функции форматирования должны знать о всех форматируемых типах. Но действительно ли это так? Это верно для printf, определяемой стандартом C, но необязательно для {fmt}. {fmt} поддерживает API расширений, позволяющий форматирование произвольных типов, не зная их полного набора заранее. В то время как встроенные и строковые типы обрабатываются целенаправленно для оптимизации скорости работы, при оптимизации размера файла может потребоваться другой подход. Убирая специальную обработку и обрабатывая каждый тип с помощью API расширений, мы можем избежать оверхэда от неиспользуемых типов.

Я создал экспериментальную реализацию этой задумки. Задав значение 0 для макроса FMT_BUILTIN_TYPES, только int обрабатывается целенаправленно, а все остальные типы проходят через API расширений. Нам все еще необходимо знать про int для динамической ширины и точности, например:

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

Это дает нам модель «не платим за то, что не используем», хотя это немного увеличивает размер каждого вызова в бинарном файле. Если вы обрабатываете числа с плавающей запятой или другие типы, соответствующий код все еще будет включен в итоговую сборку. И хотя реализацию обработки чисел с плавающей запятой можно уменьшить, мы не будем касаться этой темы в этой статье.

Используя FMT_BUILTIN_TYPES=0, размер бинарного файла уменьшился до 31 kB, что дает нам значительное улучшение:

$ 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

Однако обновленные результаты Bloaty показывают, что некоторые артефакты локалей все еще сохраняются, например, 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&)

После отключения этих артефактов в коммитах e582d37 и b3ccc2d, а также добавления более удобной опции для отказа через макрос FMT_USE_LOCALE, размер бинарника уменьшился до 27 kB:

$ 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

В библиотеке есть несколько мест, где размером жертвуют в пользу скорости. Например, рассмотрим функцию вычисления количества десятичных цифр:

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);
}

Используемая здесь таблица занимает 256 байт. Универсального решения не существует, и внесение изменений может негативно сказаться на других ситуациях. К счастью, есть другая реализация этой функции для случаев, когда __builtin_clz недоступен, например, 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;
  }
}

Остается лишь предоставить пользователям возможность выбирать, использовать ли альтернативную реализацию. Как вы можете догадаться, это реализовано с помощью еще одного конфигурационного макроса 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);
}

С помощью этого и нескольких подобных изменений мы сократили размер бинарника до 23 kB:

$ 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

Мы скорее всего можем снизить размер бинарного файла еще сильнее, поиграв с настройками, но давайте обратим наш взор на нечто более глобальное — стандартную библиотеку C++. Какой смысл оптимизировать размер, когда в итоге мы получаем 1–2 мегабайта рантайма C++?

Хотя {fmt} и старается полагаться как можно меньше на стандартную библиотеку, можем ли мы совсем убрать эту зависимость? Одна из очевидных проблем — исключения, их мы можем отключить с помощью FMT_THROW, например указав значение abort. В целом это не рекомендуется делать, но может подойти в ряде случаев, учитывая что большая часть ошибок отлавливается на этапе компиляции.

Попробуем скомпилировать с флагом ‑nodefaultlibs и отключенными исключениями:

$ 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

На удивление, подобный подход почти сработал. Единственная зависимость от рантайма C++ идет от fmt::basic_memory_buffer — небольшого буфера на стеке, который может расширяться в динамическую память при необходимости.

fmt::print может писать напрямую в буфер FILE и в целом не требует динамического выделения памяти, так что мы могли бы убрать зависимость от fmt::basic_memory_buffer из fmt::print. Но поскольку он может быть использован где‑то в другом месте, более корректным подходом будет замена стандартного аллокатора на использование malloc и free вместо new и 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); }
};

Это уменьшает размер бинарника до 14 kB:

$ 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

Учитывая, что программа на C с пустой функцией main занимает 6 kB в используемой системе, {fmt} добавляет меньше 10 kB к размеру бинарника.

Мы также можем убедиться, что больше не зависим от рантайма C++:

$ 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)

Надеюсь, вам было интересно, и желаю удачи со встроенным форматированием!

Автор: MrPizzly

Источник

* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js