(и не только строки)

Всем практикующим программистам приходится конкатенировать строки. Именно конкатенировать, у нас не какой-то там JavaScript или PHP, у нас в C++ это называется вот таким заумным словом. Программисты на других языках без излишних мудрствований строки просто "складывают", даже не особо задумываясь об этой операции. Ведь что может быть проще, чем

return "The answer is " + str_answer + ", count is " + count;

Но если для скриптописателей простительно не думать о том, что стоит за такой простой записью, для опытного разработчика не приемлемо так безответственно подходить к такому важному вопросу. Опытный разработчик, представив такой код на C++, сразу видит ужасающую бездну проблем, которые может породить такой подход.

  • Что за тип у str_answer? Хорошо, если это std::string, его можно будет сложить со строковым литералом. А если мы в духе последних веяний оптимизации (всё-таки с 2017го прошло уже 9 лет) используем для него std::string_view? Конвертировать в std::string литерал "The answer is " или переменную str_answer? Ок, учитывая, что складывание конкатенацию std::string c std::string_view даже ещё не во все компиляторы с C++26 завезли, будем в этом случае преобразовывать в std::string переменную str_answer (не понятно тогда, для чего городили "оптимизацию" с std::string_view?).

  • Какой тип у count? Скорее всего это число, но число не прибавить просто так к строке. Использовать std::to_string, созадав ещё один std::string? Ну ок... Повезло, что нам надо получить std::string, а не допустим std::u16string, метода std::to_u16string до сих пор нет.

  • "The answer is " и ", count is " - литералы, складывающиеся с std::string как const char*. Значит, будет вызываться strlen. Интересно, сможет ли компилятор оптимизировать и посчитать их длину во время компиляции? Ну да ладно, там вроде всё-таки в сложении constexpr, будем надеяться.

Это пока первый уровень проблем. И допустим, мы их успешно решили, создав такой код:

std::string make_answer(std::string_view str_answer, int count) {
    return "The answer is " + std::string{str_answer}
        + ", count is " + std::to_string(count);
}

Звучит "Ура!", но как-то негромко что ли...
Потому что опытный разработчик видит, что тут создаётся 5 (пять!) временных промежуточных объектов std::string, в которые последовательно перекладываются символы из одного объекта в другой.

Хорошо, если результирующие строки небольшие, и попадают под SSO (как известно, стандартные строки в x64 при размере в 32 байта могут хранить в себе до 15 символов без аллокации памяти). Хорошо, что стандартные строки написаны с умом, и во всю силу используют мощь rvalue ссылок, при сложении со временными объектами используя append и std::move. Это позволяет хоть сколько-то оптимизировать выполнение. Но при всём желании компилятор не может выкинуть эти пять временных объектов и как минимум обязан вызывать для них пять деструкторов, проверяя, не пустые ли они и не надо ли вызвать delete на буферах символов. Хотя нам-то понятно, что все они будут пустые, так как перемещены в итоге в результирующий объект, и такая проверка - просто пустая трата времени. Не забываем, что компилятору надо ещё предусмотреть исключения, генерируя код для очистки этих временных объектов при раскрутке стека.

Да, если этот код работает не в критическом участке выполнения, то нынешние процессоры всё стерпят, но это не путь опытного стринг-фу мастера. Истинный стринг-фу мастер ищет совершенства. Поэтому начинает перебирать варианты и делать замеры.

Итак, возможно, проблема в том, что слишком много временных объектов и перемещений символов между ними? Попробуем сделать всё за один заход, у нас же есть std::stringstream и std::format:

std::string make_answer_format(std::string_view str_answer, int count) {
    return std::format("The answer is {}, count is {}", str_answer, count);
}

std::string make_answer_stream(std::string_view str_answer, int count) {
    std::stringstream s;
    s << "The answer is " << str_answer << ", count is " << count;
    return s.str();
}

Удивительно, но замеры показывают, что такой подход - полное фиаско. Чуть ниже будет ссылка на все замеры. std::format в этой ситуации проигрывает тупому сложению строк, а std::stringstream - проигрывает и std::format ещё в два раза. И это под Linux, под Windows всё ещё хуже.

Как же быть? Вообще-то, стратегия быстрой конкатенации строк известна давно - нужно сначала посчитать длину результата, выделить нужное количество места, и скопировать символы сразу в этот буфер, избегая создания временных промежуточных строк. Засучив рукава, опытный разработчик берётся за дело:

std::string make_answer_append(std::string_view str_answer, int count) {
    static const auto s1 = "The answer is "sv, s2 = ", count is "sv;
    char buf[40];
    size_t count_len = std::to_chars(buf, std::end(buf), count).ptr - buf;
    std::string res;
    res.reserve(s1.length() + s2.length() + str_answer.length() + count_len);
    res = s1;
    res.append(str_answer);
    res.append(s2);
    res.append(buf, count_len);
    return res;
}

Запустив замеры и посмотрев результаты, опытный разработчик с полным правом кричит "Бинго!!!". Данный способ уверенно обгоняет простое сложение, в среднем в полтора-два раза.

Но имеет ли он право воскликнуть "Эврика"? Нет, и ещё раз нет. Посмотрите, какую простыню кода ему пришлось писать для такой простой операции. Если так расписывать каждое сложение строк в программе, можно её вообще не успеть написать.

А ведь это ещё простой случай. Числа может быть необходимо выводить не только в десятичном виде. Строки могут потребоваться не только char - в стандарте вообще-то 5 типов символов для строк, а std::to_chars есть только для char. А ещё может потребоваться "соединять" строки из контейнера в одну строку, или заменять подстроки на другие подстроки при сложении. Или в зависимости от условий прибавлять к строке что-либо одно или другое.

Есть ли способ все эти конкатенации писать так же просто, как простое сложение строк,
но при этом так же эффективно, как при ручной оптимизации?

Ну что же, опытный программист добавляет в код две строчки

#include <simstr/strexpr.h>
using namespace simstr;

и добавляет ещё один способ к своим замерам:

std::string make_answer_strexpr(ssa str_answer, int count) {
    return "The answer is " + str_answer + ", count is " + count;
}

И вот теперь давайте наконец посмотрим на результаты всех замеров с Compiler Explorer. (Ещё более полные и красивые бенчмарки можно увидеть тут)

Run on (2 X 2303.05 MHz CPU s)
Load Average: 0.28, 0.33, 0.41
------------------------------------------------------------------------------
Benchmark                                    Time             CPU   Iterations
------------------------------------------------------------------------------
do_make_answer<make_answer_str>            130 ns         95.4 ns      7369631
do_make_answer<make_answer_format>         368 ns          165 ns      7422333
do_make_answer<make_answer_stream>         748 ns          422 ns      1546946
do_make_answer<make_answer_append>         111 ns         60.3 ns      9724967
do_make_answer<make_answer_strexpr>       79.5 ns         32.9 ns     21483240

Вот тут то уже можно и крикнуть "Эврика!". Код, который оказался таким же простым, как на каком-нибудь JavaScript - оказался самым быстрым, опережая наш вручную оптимизированный код ещё примерно на 20%. И всё благодаря строковой библиотеке simstr и применяемой в ней технике "строковых выражений".

Как же это работает?

Всё дело в том, что в библиотеке simstr на самом деле нет ни "конкатенации", ни "сложения" строк. Складываются в ней "строковые выражения". Это первое, на чем основана техника быстрого сложения. Второе - то, что в C++ промежуточные временные объекты во время выполнения выражения живут до его конца, до точки с запятой. Рассмотрим подробнее.

Строковое выражение - это не строка, а "инструкция", как собрать строку. Можно назвать его "генератором строки". Это объект любого типа, удовлетворяющий концепту StrExpr:

template<typename A>
concept StrExpr = requires(const A& a) {
    typename std::remove_cvref_t<A>::symb_type;
    { a.length() } -> std::convertible_to<size_t>;
    { a.place(std::declval<typename std::remove_cvref_t<A>::symb_type*>()) }
        -> std::same_as<typename std::remove_cvref_t<A>::symb_type*>;
};

То есть он знает, с каким типом символов он оперирует, у него есть метод length(), который возвращает длину генерируемой им строки, и есть метод place(ptr), в котором он собственно и генерирует строку, помещая символы строки в предоставленный буфер.

Когда мы хотим "материализовать" строку, генерируемую строковым выражением, мы сначала запрашиваем у него длину результата, потом аллоцируем нужное место, а потом просим строковый объект разместить его строку в это место. Пока ничего сложного, и ещё непонятно, почему это называется "выражением". Следите за руками. Мы создаем шаблонный класс, который объединяет два строковых выражения:

template<StrExpr A, StrExprForType<typename A::symb_type> B>
struct strexprjoin {
    using symb_type = typename A::symb_type;
    const A& a;
    const B& b;
    constexpr strexprjoin(const A& a_, const B& b_) : a(a_), b(b_){}

    constexpr size_t length() const noexcept {
        return a.length() + b.length();
    }

    constexpr symb_type* place(symb_type* p) const noexcept {
        return b.place(a.place(p));
    }
};

Он хранит ссылки на два переданных ему строковых выражения. Когда у него запрашивают длину, он возвращает сумму длин двух выражений, а когда просят разместить результат - помещает в буфер сначала первое выражение, а за ним - второе.

И дальше немного шаблонной магии:

template<StrExpr A, StrExprForType<typename A::symb_type> B>
constexpr strexprjoin<A, B> operator+(const A& a, const B& b) {
    return {a, b};
}

Теперь, когда мы складываем два строковых выражения любых типов, создается временный объект типа strexprjoin<A,B>, который сохраняет ссылки на свои слагаемые - строковые выражения, и который живёт до конца выражения, до точки с запятой. Самое главное - этот объект тоже удовлетворяет концепту StrExpr, т.е. он сам является строковым выражением, и к нему можно по цепочке снова применить операцию сложения, создав новый объект strexprjoin, ссылающийся на предыдущую цепочку выражений и новое слагаемое. Таким образом, в итоге создаётся временный объект, хранящий ссылки на все слагаемые выражения.

Все владеющие строковые типы в simstr - умеют инициализироваться из любого строкового выражения. Они запрашивают его длину, выделяют место, и материализуют выражение в это место. Мутабельные типы строк в simstr также умеют использовать строковые выражения при вставке и заменах, аналогично получая необходимую длину, готовя место и размещая символы выражения в это место.

А для совместимости с std::string объекты "строковые выражения" содержат оператор конвертации в стандартную строку, выполняя тот же алгоритм - считая длину, выделяя место, размещая символы. При использовании в C++20 - для этого используется resize() и data(), начиная с C++23 используется resize_and_overwrite().

Также все строковые типы в simstr - удовлетворяют концепту строкового выражения, поэтому могут напрямую служит слагаемыми в операциях сложения с другими строковыми выражениями. При этом они просто копируют себя в указанное место.

Но просто копированием строк выражения не ограничиваются. Ведь это "генераторы". Мы можем например создать тип, который генерирует указанное количество указанных символов. Или преобразующие число в строку. Или в зависимости от условия - выдающие результат одного или другого строкового выражения. Также в библиотеке перегружены операции сложения строкового выражения и строкового литерала, или числа, а также сложение с std::basic_string и std::basic_string_view.

Рассмотри подробнее код из примера выше:

std::string make_answer_strexpr(ssa str_answer, int count) {
    return "The answer is " + str_answer + ", count is " + count;
}

Тип ssa - это simstr::simple_str<char> - аналог std::string_view, то есть просто указатель на текст и его длина. Он может инициализироваться из любых строковых объектов simstr, из строковых литералов, �� также std::basic_string и std::basic_string_view. Поэтому использование его параметром функции вместо std::string_view - не сломает существующий код, как видите, функция прекрасно вызывается и с std::string_view.
Однако данный тип в это же время является строковым выражением, а поэтому может складываться со строковым литералом. Таким образом, "The answer is " + str_answer - создает новый временный объект - строковое выражение. Прибавление к нему ", count is " - создает следующий строковый объект, хранящий ссылку на предыдущий и на строковый литерал. И в завершении к нему прибавляется число, при этом формируется строковый
подобъект, который преобразует число в строку. И в завершение у этого итогового объекта вызывается метод конвертации в std::string, который и материализует строковое выражение в строку-результат.

Кто-то возможно возразит, что в этом методе мы не избавляемся от временных промежуточных объектов. Да, это так. Но все эти объекты простые и примитивные - зачастую они состоят просто из ссылок на другие объекты. Все они создаются на стеке, имеют тривиальные конструкторы и деструкторы, не используют динамическую память, вся их жизнь хорошо видна компилятору, и у него получается отлично оптимизировать их использование.
Посмотрите например, как красиво GCC смог оптимизировать небольшую конкатенацию - от этих промежуточных объектов не осталось и следа, и он просто вставил копирование символов в буфер строки. Там же можете сравнить с генерацией кода при классическом способе конкатенации - кода больше, явно видны все деструкторы промежуточных std::string. Clang пока справляется с оптимизацией чуть хуже, но не критично.

Библиотека simstr не ограничивается только реализацией эффективной конкатенации строк.
В ней помимо этого содержатся и многие другие полезные алгоритмы.

Бенчмарки различных вариантов её использования можно посмотреть здесь.

Думаю, в вопросе, как же наиболее эффективно конкатенировать строки в C++ поставлена жирная точка.