Small String Optimization: где заканчивается стек и начинается куча

При написании одного парсинга, в цикле которого создается std::string заметил одну странность, что при определенных ключах цикл работает заметно дольше. Оказалось, дело в инициализации std::string. Написал на это дело бенчмарк.

void BM_Ferrari(benchmark::State& state) {
     for (auto _ : state) {
         std::string s("=>white Ferrari");
         benchmark::DoNotOptimize(s);
     }
 }
 BENCHMARK(BM_Ferrari); 

 void BM_Lada(benchmark::State& state) {
     for (auto _ : state) {
         std::string s("=>raspberry Lada");
         benchmark::DoNotOptimize(s);
     }
 }
 BENCHMARK(BM_Lada);

Тут просто идет только инициализация std::string. Ничего более. Строки отличаются ровно на один символ. Интересно то, что показал он.

// GCC + libstdc++
-----------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------
BM_Ferrari 3.90 ns 3.90 ns 178347068
BM_Lada 13.2 ns 13.2 ns 53488287

Всего один дополнительный символ - и разница почти в 3.5 раза.

А если собрать этот же код clang, то мы увидим

// clang (-stdlib=libc++)
-----------------------------------------------------
Benchmark Time CPU Iterations
-----------------------------------------------------
BM_Ferrari 0.643 ns 0.636 ns 1095821788
BM_Lada 0.639 ns 0.633 ns 1105950011

Баг gcc?

На самом деле, виноват в этом Small String Optimization.

Small String Optimization (SSO) - это оптимизация, которую часто применяют в реализациях стандартной библиотеки C++ для ускорения работы со строками. Её суть в том, чтобы для коротких строк не выделять динамическую память в куче, а хранить их прямо внутри самого объекта строки.

У каждой реализации стандартной библиотеки свой порог. В моих версиях у libstdc++(GCC) - до 15 символов, для libc++(Clang) - 22. При этом clang с libstdc++ даст те же 15. SSO не гарантирован стандартом, так что порога может и вовсе не быть.

Зная, что в случае sso, указатель структуры хранит адрес на внутренний буфер, расположенный внутри объекта (по крайней мере в реализациях libstdc++ и libc++), то можно вот таким кодом увидеть когда происходит переход в кучу.

 int main() {
     std::print("\nsizeof(std::string) = {}\n", sizeof(std::string));
     for (int len = 0; len <= sizeof(std::string); ++len) {
         std::string s(len, 'x');
         const char* data = s.data();
         const char* obj = reinterpret_cast<const char*>(&s);
         bool is_sso = (data >= obj && data < obj + sizeof(std::string));
         std::print("  len={} -> {}\n", len, is_sso ? "SSO" : "HEAP");
         if (!is_sso) break;
    }
     std::print("\n");
 }

// gcc
sizeof(std::string) = 32
len=0 -> SSO
len=1 -> SSO
len=2 -> SSO
len=3 -> SSO
len=4 -> SSO
len=5 -> SSO
len=6 -> SSO
len=7 -> SSO
len=8 -> SSO
len=9 -> SSO
len=10 -> SSO
len=11 -> SSO
len=12 -> SSO
len=13 -> SSO
len=14 -> SSO
len=15 -> SSO
len=16 -> HEAP

// clang++ (-stdlib=libc++)
sizeof(std::string) = 24
len=0 -> SSO
len=1 -> SSO
len=2 -> SSO
len=3 -> SSO
len=4 -> SSO
len=5 -> SSO
len=6 -> SSO
len=7 -> SSO
len=8 -> SSO
len=9 -> SSO
len=10 -> SSO
len=11 -> SSO
len=12 -> SSO
len=13 -> SSO
len=14 -> SSO
len=15 -> SSO
len=16 -> SSO
len=17 -> SSO
len=18 -> SSO
len=19 -> SSO
len=20 -> SSO
len=21 -> SSO
len=22 -> SSO
len=23 -> HEAP

15 и 22 из-за разницы структур std::string у разных стандартных библиотек. В случае libstdc++ буфер хранится отдельно, а в libc++ упаковывается через union.

Это объясняет, почему тест BM_Ferrari отрабатывал быстрее, чем BM_Lada.

"=>white Ferrari" - 15 символов. Конструктор не аллоцирует память, а копирует всё внутрь объекта.

"=>raspberry Lada" - 16 символов. Конструктор уже аллоцирует память, потом копирует данные туда, потом пишет длину и емкость. При выходе ещё и free. Всё это дополнительные такты.

Ещё есть один важный момент. После выделения внешнего буфера обычное уменьшение размера строки не возвращает её автоматически в SSO. В частности, присваивание короткой строки не обязано освобождать ранее выделенную память.

int main() {
    std::print("\nsizeof(std::string) = {}\n", sizeof(std::string));
    std::string s;
    s.reserve(32);
    s = "x";
    const char* data = s.data();
    const char* obj = reinterpret_cast<const char*>(&s);
    bool is_sso = (data >= obj && data < obj + sizeof(std::string));
    std::print("{}\n", is_sso ? "SSO" : "HEAP");
    std::print("\n");
}

Получим: HEAP, хотя мы и записали туда один символ.

Тот парсер замедлялся на ключах длиннее 15 символов. Не на сложных алгоритмах - на одном невидимом пороге внутри std::string. Решение было не в оптимизации, а в понимании, где проходит эта граница.