Make STL Cringe Again: Как я динамические строки на C создавал

UPD: Обновлено 23.08.2026

Привет, Хабр! Однажды я подумал, что вот не умеют разработчики жить. В каждом из языков есть свои напасти (от которых, в принципе, спасаются разве что разработчики‑полиглоты). Возьмем хотя бы C++ — даже без его шаблонов, исключений, и так далее, там все еще много мраков. Возьмем хотя бы iostream — он, блин, весит 2 МБ в последней версии GCC при компиляции под Windows! Или, вот, std::string — динамическая строка. Звучит интересно на бумаге, учитывая, что язык не из добрейших, но на практике...

std::string — что за зверь и с чем его едят

(Внимание: данное объяснение предполагает, что вы знаете, что такое стек и куча)

std::string спроектирован довольно умно для такого языка, как C++. Выглядит же он примерно так:

class std::string {
    char* start;
    size_t len;
    union {
        char smolbuf[16];
        size_t capacity;
    }
}

Зарисовка пусть и неофициальная (дисклеймер: имена переменных в реальности выглядят не так: они были названы так для наглядности!), но довольно наглядная. Разбираем на запчасти:

1. char* start — указатель на первый символ в куче. Весит log(n) байт, где n = разрядность вашей ОС: допустим, на 32-битной ОС будет 4 байта, на 64-битной — 8 байт, и так далее

2. size_t len — длина текущей строки. Показывает, сколько сейчас в строке символов, чтобы можно было без проблем выполнять O(1) операции со строками (нахождение символов и т.п). Размер — log(n) байт, как в start.

3. union — умный механизм языка C, позволяющий упаковывать байты вместе, позволяя не тратить места в структуре под опциональные поля.

4. char smolbuf[16] — буфер из 16 символов, созданный для оптимизации работы с короткими строками (этот алгоритм назван SSO — Small String Optimization), позволяющий вместить в себя 15 символов + нуль‑терминатор без необходимости аллоцировать память (короткие строки лежат на стеке)

5. size_t capacity — используется, если размер строки превышает 15 символов. В этом случае активируется аллокация памяти с кучи, и буфер уступает место переменной capacity, определяющей, сколько места уступить строке. В случае, если строка закончится (например, при конкатенации строк), C++ отстегивает больше памяти с кучи, увеличивая переменную capacity в полтора/два раза (зависит от компилятора). Именно capacity определяет, сколько байт занимает строка в ОЗУ, а не size (то есть, может так статься, что при строке в 17 символов у вас будет занято 48 байт — 8 на указатель, 8 на размер, и 32 на строку — ибо ваша строка перешла отметку в 16 байт, заданную прошлым capacity, и ЦПУ умножил capacity на 2)

Четко. Понятно. Абсолютно не восхищает. Меня от такой расточительности чуть удар не хватил, пока я это изучал. Я невольно задумался, как именно бы выглядел std::string, если бы его пытались ужать максимально?

Великий план

Я начал прикидывать варианты оптимизации этого неугодного цифрового эквивалента жировой складки. После получаса раздумий я продумал следующую структуру:

typedef struct {
    union {
        // Heap mode (long strings) - 16 bytes on 64-bit
        struct {
            char* ptr;          // 8 bytes
            uint32_t len;       // 4 bytes
            uint32_t hash;      // 4 bytes (cached hash value)
        } heap;
        
        // SSO mode (short strings) - 16 bytes
        struct {
            char small[15];     // 15 bytes: 14 chars + '\0'
            uint8_t meta;       // 1 byte: mode | length
        } sso;
        
        // Raw access for safe type-punning
        uint8_t raw[16];
    };
} dstring;  // всего 16 байт на 64 бит

unionв начале — как и раньше, строка может находиться только в одном из двух состояний: либо короткая (SSO), либо длинная (Heap). Union гарантирует, что эти состояния не пересекаются, и вся структура всегда занимает 16 байт.

union в начале — строка может находиться только в одном из двух состояний: либо короткая (SSO), либо длинная (куча). union гарантирует, что эти состояния не пересекаются, и вся структура всегда занимает 16 байт.

• char* ptr (8 байт) — указатель на данные в куче. Работает как обычно.

• uint32_t len (4 байта) — длина строки. Ограничена до (2³¹ - 1) символов, с потенциалом расширения до (2⁶³ - 1) символов при использовании uint64_t. Это сделано специально, чтобы старший байт хэша всегда был нулевым (об этом ниже).

• uint32_t hash (4 байта) — кэшированный хэш строки, вычисленный по алгоритму FNV-1a. Старший байт этого поля всегда равен нулю, что используется для определения режима строки.

• char small[15] (15 байт) — буфер для коротких строк (до 14 символов + завершающий нуль). Данные хранятся прямо в структуре, без вызова malloc.

• uint8_t meta (1 байт) — универсальный байт состояния. Старший бит (0x80) всегда установлен в SSO-режиме, а младшие 4 бита хранят длину строки (0–14). Если старший бит сброшен — строка находится в heap-режиме, и этот байт является старшим байтом хэша (всегда 0).

• uint8_t raw[16] — массив для безопасного доступа к последнему байту без нарушения правил C. Используется в функции ds_mode() для определения состояния строки без UB.

Если кому‑то вздумается ознакомиться с проектом, ссылка на гитхаб здесь: Ссылка в Сибирь

Различные навороты

Конечно же, не может все закончиться на объявлении типа! Мне удалось не только воссоздать похудевшую версию неугодного std::string, но и создать некоторые фичи. Например, хэширование для быстрого сравнения строк.

static inline uint32_t strhash(const string* s) {
    if (s == NULL || !strok(s)) return 0;

    const char* data = strdata(s);
    uint32_t len = strlen_s(s);

    uintptr_t data_ptr = (uintptr_t)data;
    uintptr_t len_ptr = (uintptr_t)(is_sso(s) ?
        (const void*)&s->sso_len :
        (const void*)&s->len);

    uint32_t hash = (uint32_t)(data_ptr ^ len_ptr ^ (uintptr_t)len);

    if (len >= 2) {
        hash ^= (uint8_t)data[0] | ((uint8_t)data[1] << 8);
    } else if (len == 1) {
        hash ^= (uint8_t)data[0];
    }

    hash ^= hash >> 16;
    hash *= 0x9e3779b9;
    hash ^= hash >> 16;

    return hash;
}

Работает примерно так:

1. Задается сырой шаблон;

2. В цикле вычисляется хэш через XOR шаблона с каждым символом строки;

3. Перемножается на магическое число;

4. Возвращается хэш без старшего байта (для того, чтобы можно было определять режим строки без проблем)

Хэш на выходе можно использовать для сравнения строк или закинуть в хэш‑таблицу как ключ для O(1) поиска. Стоит отметить, что ни std::string, ни даже SDS не владеют подобными функциями (если мы говорим про вычисление хэша на этапе создания строки и ее кэширования — ведь доступ к хэшу достигается за O(1)!

Помимо этого, я также имплементировал конкатенацию... ладно, «реализовал сложение строк», тут же все свои.

Также я создал и другие интересные алгоритмы, по типу вырезания подстроки из уже существующей строки...

string foo = ds_sub("Hello, World", 7, 5);
// foo: "World"
// O(1)

..инициализацию строки без длины и с длиной...

string foo = ds_init("Hello");
  // O(n) — используется strlen()
string bar = ds_init_len("World", 5);
  // O(1) — длина известна

..и так далее. Но это вы сами посмотрите, ссылку на гитхаб я уже дал. Там, к слову, есть и бенчмарк против std::string и библиотеки SDS от Redis. Который вы, кстати, можете сами скомпилировать и запустить — мой Intel Pentium 2010 года все равно не самый лучший для этого (пусть я и писал с намерением запуска везде, где есть С11). Если запустите бенч — поделитесь результатами в комментах.

Единомышленики

Но не един я оказался в своем презрении к STL! Я совершил еще одно исследование, и оказалось, что большинство компаний выбрасывают std::string из своего кода, заменяя его своими велосипедами.

«C++ — кошмарный язык. Его делает ещё более кошмарным тот факт, что множество недостаточно грамотных программистов используют его, доходя до ситуации, когда на нём гораздо, гораздо проще сгенерировать тотальный, абсолютный мусор.» © Линус Торвальдс

Начнем с самого страшного имени в истории программирования: Линус Торвальдс. Всем известна его ненависть к C++ (которую я, кстати, не одобряю — не взирая на мои высказывания, C++ на деле ни в коем случае не плохой язык, он просто действительно не подходит для низкоуровневых задач), но не всем известно, что в ядре Linux есть свои динамические строки, которые выглядят примерно так:

// Из include/linux/dcache.h
struct qstr {
    union {
        struct {
            u32 hash;
            u32 len;
        };
        u64 hash_len;
    };
    const unsigned char *name;
};

Я впал в ступор, когда увидел схожесть. Я даже поклянусь обоими руками на отсечение, что я не лез в исходники Linux за вдохновением.

Сама структура представляет указатель на первый символ строки (8 байт на 64-битной ОС — но Linux сейчас пихают везде, так что и не исключены микроконтроллеры с 16-битными ОС), а также union хэша (4 байта) и длины (4 байта), смешанную в одну 8-байтовую переменную, отвечающую за обе 4-байтовые.

Есть также технология FBString в Facebook. Слишком сложна для понимания с разбега, так что приведу псевдокод:

FBString {
    // 1. Режим: "Короткая" (≤ 23 символа)
    if (длина <= 23) {
        // Всё лежит прямо в объекте: сам массив байт
        // + один байт на длину. БЕЗ malloc().
    }

    // 2. Режим: "Средняя" (24–255 символов)
    if (длина <= 255) {
        // Указывает на КУСОК памяти. При копировании 
        // создаётся НОВАЯ копия (не разделяется).
        // Просто: malloc(memcpy) + указатель.
    }

    // 3. Режим: "Очень длинная" (> 255 символов)
    else {
        // Указывает на СЧЁТЧИК-ссылку.
        // При копировании увеличиваем счётчик, данные не копируем.
        // Счётчик ссылок атомарный, чтобы не упасть в многопоточке.
    }
}

На вид очень развитая надстройка для многомиллионного продакшена.

Roblox и EA используют SIMDString: грубо говоря, это строка, которую можно настроить под себя и отдать на растерзание ЦПУ:

SIMDString = Шаблон <Размер_внутреннего_буфера, Аллокатор> {
    // 1. Режим: "Супер-короткая"
    // Использует внутренний массив размером, который указал ты.
    // Обычно ставят 64 байта, чтобы влезало много мелких строк.
    Если данные лезут во внутренний буфер:
        Копируем туда и ставим флаг.
        malloc() не вызывается.

    // 2. Режим: "Длинная"
    Иначе:
        malloc() + копирование.

    // Секретная соль:
    // Копирование, конкатенация — используют SIMD-инструкции (SSE, AVX).
    // Это значит, что процессор копирует по 16/32 байта за такт.
}

Есть еще и технология Abseil Cord от Google, но тут я уже не буду вдаваться в подробности. Разве что скажу, что это не строка, а скорее структура данных для огромных текстов. Этакое дерево из чанков, которые хранят либо указатель на внешнюю память, либо часть строки. Если надо склеить — просто создается новый узел. Если надо прочитать всю строку ‑алгоритм проходит по дереву и считывает чанки на лету.

Итоги

За один день я:

• Создал динамические строки на C

• Сделал их почти по всем фронтам лучше, чем в C++ (см. бенчмарк на гитхабе)

• Провел исследование технологий крупных компаний

• Поделился своими трудами со внешним миром

Буду признателен, если вы оцените мою работу звездой на гитхабе или плюсиком в карму. До свидания.