Оптимизируя неоптимизируемое: ускорение компиляции C++

Kate

Administrator
Команда форума
В этой статье речь пойдёт о повышении скорости компиляции библиотеки {fmt} до уровня библиотеки ввода-вывода Cи stdio.

Дня начала немного теории. {fmt} – это популярная открытая библиотека С++, представляющая более эффективную альтернативу С++ библиотеке iostreams и библиотеке Си stdio. Последнюю она обошла по целому ряду аспектов:

  • Безопасность типов с проверками форматирующих строк во время компиляции. Эти проверки включены по умолчанию начиная с С++ 20, и присутствуют в качестве дополнения для С++ 14/17. Форматирующие строки среды выполнения в {fmt} также оказываются безопасными, чего невозможно достичь в printf.
  • Расширяемость. Определяемый пользователем тип можно сделать форматируемым. При этом большинство типов стандартных библиотек, например, контейнеры и пакеты для обработки даты и времени, предлагают возможность форматирования изначально.
  • Производительность. {fmt} намного быстрее любой распространённой реализации printf, порой на несколько порядков (например, в форматировании чисел с плавающей запятой).
  • Возможность переноса поддержки Unicode.

Тем не менее одной из областей, в которой stdio по-прежнему опережала {fmt}, являлось время компиляции.

Мы вложили немало усилий в оптимизацию времени компиляции {fmt}, применив стирание типов на уровне аргументов и вывода, ограничив шаблоны небольшим слоем API верхнего уровня и добавив fmt/core.h с минимальным числом зависимостей.

В итоге {fmt} стала компилироваться быстрее таких альтернатив С++, как iostreams, Boost Format и Folly Format, но до скорости stdio всё равно не дотягивала. Мы понимали, что узким местом является зависимость <string>, но она была необходима для основного API, fmt::format.

Со временем стало понятно, что в некоторых случаях использование std::string не является необходимым. Процитирую комментарий Sean Middleditch с GitHub:

Если я не использую std::string (а так оно и есть), то не хочу привлекать тяжёлые зависимости для этого заголовка и для каждой единицы трансляции, которая может выполнять какое-либо форматирование (а значит, требует доступа к специализациям formatter<>).

{fmt} стала всё чаще использоваться для ввода-вывода и библиотек логирования, где объекты std::string могут появляться только в виде аргументов в некоторых точках вызова.

И самым важным случаем использования их всех, естественно, является проект Godbolt, в котором {fmt} часто применяют для вывода, особенно не поддерживаемого printf, и здесь несколько сотен накладных миллисекунд оказываются заметны.

С другой стороны, в С++ трудно избежать <string>. При использовании любой части библиотеки она наверняка будет подтягиваться транзитивно. К тому же, время компиляции оказывалось вполне терпимым, и поскольку у меня были другие задачи, то этим вопросом я долгое время не занимался.

Однако с выходом С++20 ситуация сильно изменилась. Взгляните на следующую программу Hello World с простым форматируемым выводом (hello.cc):

#include <fmt/core.h>

int main() {
fmt::print("Hello, {}!\n", "world");
}

В случае C++11 её компиляция через Clang на моём M1 MacBook Pro заняла ~225 мс (здесь и ниже я привожу лучший результат из трёх выполнений):

% time c++ -c hello.cc -I include -std=c++11
c++ -c hello.cc -I include -std=c++11 0.17s user 0.04s system 90% cpu 0.225 total


Теперь же при работе в C++20 тот же процесс занимает ~319 мс, то есть оказывается на 40% дольше:

% time c++ -c hello.cc -I include -std=c++20
c++ -c hello.cc -I include -std=c++20 0.26s user 0.05s system 95% cpu 0.319 total

К сравнению, вот равноценная программа на Си (hello-stdio.c):

#include <stdio.h>

int main() {
printf("Hello, %s!\n", "world");
}

И она компилируется всего за ~33 мс:

% time cc -c hello-stdio.c
cc -c hello-stdio.c 0.01s user 0.01s system 68% cpu 0.033 total

Получается, ввиду неконтролируемого раздувания стандартной библиотеки между версиями С++11 и С++20 компиляция стала примерно в 10 раз медленнее в сравнении с printf – и всё из-за включения <string>. Можно ли с этим что-то сделать?

Как оказалось, стирание типов минимизировало присутствующую в fmt/core.h зависимость от std::string, поэтому я решил попробовать её удалить. Но сначала рассмотрим процесс компиляции подробнее путём трассировки:

c++ -ftime-trace -c hello.cc -I include -std=c++20

Также откроем hello.json в Chrome с помощью chrome://tracing/:

36-e8kmodf8klp4jgb3kgqaexq8.png


Время, проведённое в самом fmt/core.h, составляет всего 7,5 мс и в основном состоит из:

  • <iterator>: ~71 мс;
  • <memory>: ~37 мс;
  • <string>: ~122 мс (выделены в трейсе выше).

Хорошо, <string> действительно выполняется дольше всех, но что насчёт остальных? К сожалению, удаление других компонентов ситуацию не изменит, поскольку объём транзитивно подтягиваемого материала останется примерно таким же. Эти заголовочные файлы отражаются в трейсе, только потому, что включены до <string>.

Хорошенько погуглив вопрос, я выяснил, что, благодаря _LIBCPP_REMOVE_TRANSITIVE_INCLUDES, можно кое-что проделать в libc++. Попробуем:

% time c++ -D_LIBCPP_REMOVE_TRANSITIVE_INCLUDES -c hello.cc -I include -std=c++20
c++ -D_LIBCPP_REMOVE_TRANSITIVE_INCLUDES -c hello.cc -I include -std=c++20 0.18s user 0.03s system 91% cpu 0.231 total

Итак, это сократило время компиляции до ~231 мс, почти до уровня С++11. Неплохо, хотя до stdio ещё далеко.

Но в отсутствии транзитивных зависимостей теперь есть смысл избавиться от <iterator> и <memory>.

<memory> используется всего в одном месте для std::addressof в качестве обхода сломанной реализации std::vector<bool>::reference в libc++, которая обеспечивает инновационный способ перегрузки унарного оператора &. Вот это место:

custom.value = const_cast<value_type*>(std::addressof(val));

Мы можем заменить её несколькими операциями приведения, поплатившись за это утратой возможности непосредственного форматирования std::vector<bool>::reference во время компиляции, с чем я вполне могу смириться:

if constexpr (std::is_same<decltype(&val), T*>::value)
custom.value = const_cast<value_type*>(&val);
if (!is_constant_evaluated())
custom.value = const_cast<char*>(&reinterpret_cast<const char&>(val));

Теперь, когда у нас больше нет <memory> (я бы предпочёл забыть об этом обходном решении (здесь игра слов, don't have memory of, — прим. пер.)), время компиляции сократилось до ~195 мс, уже лучше, чем изначальный показатель в С++11.

Удаление окажется более хитрой задачей, поскольку мы используем back_insert_iterator для обнаружения и оптимизации форматирования в неразрывных контейнерах. К сожалению, обнаружить это нельзя даже с помощью SFINAE, потому что back_insert_iterator имеет ту же форму API, что и front_insert_iterator. У этой проблемы есть разные решения, например, перемещение оптимизации в fmt/format.h. Я же пока добавил простую локальную замену, fmt::back_insert_iterator. Без <iterator> время компиляции сократилось до ~178 мс.

Здесь наступает подходящий момент для того, чтобы взяться за <string>, но, как оказывается, мы также ненамеренно включили <string_view>, или <experimental/string_view> (вздох). Это не добавляет непосредственных издержек, потому что всё равно подтягивается из <string>, но нам нужно удалить одно, чтобы избавиться от другого. У нас в диапазонах уже есть класс свойств (trait) для обнаружения API, похожего на std::string_view, и мы можем применить его с некоторым упрощением:

template <typename T, typename Enable = void>
struct is_string_like : std::false_type {};

// Эвристика для обнаружения std::string и std::string_view.
template <typename T>
struct is_string_like<T, void_t<decltype(std::declval<T>().find_first_of(
typename T::value_type(), 0))>> : std::true_type {
};

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

Вот мы и подошли к финальному боссу, <string >. В fmt/core.h было очень мало ссылок на std::string. Тем не менее у нас также был std::char_traits, который мы использовали в резервной реализации string_view, необходимой для совместимости с C++11. char_traits не имел особой ценности, поэтому его было легко заменить функциями Си, такими как strlen и её резервными вариантами для constexpr.

Единственным API, использовавшим std::string, был fmt::format. Один из вариантов заключался в его перемещении в fmt/format.h. Но это бы стало критическим изменением, поэтому я решил пойти на ужасный, но ничего не нарушающий, шаг и предварительно объявить std::basic_string. Подобные действия не одобряются, но это не худшее, что нам пришлось проделать в {fmt}, чтобы обойти ограничения стандартных библиотек Си и С++. Вот немного упрощённая версия:

#ifdef FMT_BEGIN_NAMESPACE_STD
FMT_BEGIN_NAMESPACE_STD
template <typename Char>
struct char_traits;
template <typename T>
class allocator;
template <typename Char, typename Traits, typename Allocator>
class basic_string;
FMT_END_NAMESPACE_STD
#else
# include <string>
#endif

FMT_BEGIN_NAMESPACE_STD и FMT_END_NAMESPACE_STD определяются в зависимости от реализации. Сейчас поддерживаются обе ведущие стандартные библиотеки, libstdc++ и libc++.

Естественно, с нашим определением fmt::format это не сработало:

template <typename... T>
FMT_NODISCARD FMT_INLINE auto format(format_string<T...> fmt, T&&... args)
-> basic_string<char> {
return vformat(fmt, fmt::make_format_args(args...));
}

И мы получили следующую ошибку:

In file included from hello.cc:1:
include/fmt/core.h:2843:31: error: implicit instantiation of undefined template 'std::basic_string<char, std::char_traits<char>, std::allocator<char>>'
FMT_NODISCARD FMT_INLINE auto format(format_string<T...> fmt, T&&... args)
^

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

template <typename... T, typename Char = char>
FMT_NODISCARD FMT_INLINE auto format(format_string<T...> fmt, T&&... args)
-> basic_string<Char> {
return vformat(fmt, fmt::make_format_args(args...));
}

Теперь проверим, стоило ли оно того:

% time c++ -c hello.cc -I include -std=c++20
c++ -c hello.cc -I include -std=c++20 0.04s user 0.02s system 81% cpu 0.069 total

Мы сократили время компиляции с ~319 мс до ~69 мс и при этом больше не нуждаемся в _LIBCPP_REMOVE_TRANSITIVE_INCLUDES. В результате всех оптимизаций fmt/core.h стал сопоставим с stdio.h по времени компиляции – тестирование показало лишь 2х кратное отличие в скорости. Думаю, это разумная плата за повышенную безопасность, быстродействие и расширяемость.

▍ P.S.​


После оптимизации stdio.h стал вторым по тяжести включением, увеличивающим компиляцию на целые 5 мс.


 
Сверху