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

Привет, Хабр! Однажды я подумал, что вот не умеют разработчики жить. В каждом из языков есть свои напасти (от которых, в принципе, спасаются разве что разработчики‑полиглоты). Возьмем хотя бы 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 {
        // Длинные строки (куча)
        struct {
            char* ptr;
            uint32_t len;
            uint32_t capacity;
        };
        // SSO (стек)
        struct {
            char small[15];
            uint8_t sso_len;
        };
    };
} string;  // всего 16 байт на 64 бит

union я переместил в начало: теперь строка или короткая, или длинная. Нет общих переменных.

1. uint32_t len хранит длину строки: эта переменная ограничена до 2³², но кому вообще понадобится создавать одну строку в 4 ГБ? Размер: 4 байта.

2. uint32_t capacity — на деле, эта переменная — огрызок от одного из моих отвергнутых дизайнов. Не делает ничего, ибо я пока не придумал ей назначения. Считайте это просветом в 4 байта, которые можно залепить... да хотя бы хэшем для сравнения строк. Или расширением len до 64 бит, ибо хэш все равно у меня вычисляется за пару тактов процессора... Но об этом позже. Кстати, если уменьшить буфер SSO и убрать capacity, то строка будет весить только 8 байт на 32-бит=D

3. char small[15] — если строка состоит из меньше, чем 15 символов, то все предыдущие переменные опускаются во имя этого буфера. Этот буфер может вместить максимум 14 символов + нуль‑терминатор. Подумывал о том, как бы приписывать его на лету и освободить 15-й слот, но идей не нашлось.

4. uint8_t sso_len — число от 0 до 255, используемое для вычисления размера короткой строки. Так как мне нужны биты 0–3 (дают числа от 0 до 15), биты 4–7 можно использовать для флагов (например, старший бит может хранить флаг об ошибке). Занимает 1 байт.

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

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

Конечно же, не может все закончиться на объявлении типа! Мне удалось не только воссоздать похудевшую версию неугодного 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. Сначала идут проверки ошибок. В случае чего возвращается 0.

2. Потом получаем указатели. Проверяем режим строки.

3. Вычисляется хэш за счет XOR указателей на данные, длину строки и самой длины.

4. Дополнительно примешиваются первые 2 символа. Сделано это, потому что в большинстве случаев SSO лежат на стеке рядом друг с другом, и хэш выходит одинаковым.

5. Хэш дополнительно перемешивается через константу золотого сечения.

6. Хэш готов.

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

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

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

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

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

string foo = initstr("Hello");
  // O(n) — используется strlen()
string bar = initstr_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++ (см. бенчмарк на гитхабе)

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

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

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