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++ на деле ни в коем случае не плохой язык, он просто действительно не подходит для низкоуровневых задач), но не всем известно, что в ядре Linux есть свои динамические строки, которые выглядят примерно так:

// Из include/linux/dcache.hstruct 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++ (см. бенчмарк на гитхабе)

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

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

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