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; } }
Зарисовка пусть и неофициальная (дисклеймер: имена переменных в реальности выглядят не так: они были названы так для наглядности!), но довольно наглядная. Разбираем на запчасти:
char* start— указатель на первый символ в куче. Весит log(n) байт, где n = разрядность вашей ОС: допустим, на 32-битной ОС будет 4 байта, на 64-битной — 8 байт, и так далееsize_t len— длина текущей строки. Показывает, сколько сейчас в строке символов, чтобы можно было без проблем выполнять O(1) операции со строками (нахождение символов и т.п). Размер — log(n) байт, как в start.union— умный механизм языка C, позволяющий упаковывать байты вместе, позволяя не тратить места в структуре под опциональные поля.char smolbuf[16]— буфер из 16 символов, созданный для оптимизации работы с короткими строками (этот алгоритм назван SSO — Small String Optimization), позволяющий вместить в себя 15 символов + нуль‑терминатор без необходимости аллоцировать память (короткие строки лежат на стеке)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_thash (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; }
Работает примерно так:
Задается сырой шаблон;
В цикле вычисляется хэш через XOR шаблона с каждым символом строки;
Перемножается на магическое число;
Возвращается хэш без старшего байта (для того, чтобы можно было определять режим строки без проблем)
Хэш на выходе можно использовать для сравнения строк или закинуть в хэш‑таблицу как ключ для 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++ на деле ни в коем случае не плохой язык, он просто действительно не подходит для низкоуровневых задач), но не всем известно, что в ядре 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++ (см. бенчмарк на гитхабе)
Провел исследование технологий крупных компаний
Поделился своими трудами со внешним миром
Буду признателен, если вы оцените мою работу звездой на гитхабе или плюсиком в карму. До свидания.
Комментарии (39)
Sazonov
21.08.2026 18:56Повсеместно используем std::string в очень большом, с элементами легаси кросс-платформенном десктопном софте. Периодически делаем профилирование. Да, иногда строки становятся узким местом, но настолько редко что хватает точечных оптимизаций через string_view. В 99% случаев проблемы с перформансом из-за других вещей.
Garantia_Tsverga Автор
21.08.2026 18:56Я никогда не говорил, что std::string тормозят код. Я сказал, что для такого языка, как C++, std::string сделан плохо. А на string_view у меня свои планы, его я тоже когда-нибудь реализую.
BorisU
21.08.2026 18:56шок, есть разные реализации std::string, идите изучайте другие варианты :)
Garantia_Tsverga Автор
21.08.2026 18:56Еще одна не повредит. И вообще философия моих строк заключается в том, что они занимают как раз столько места, сколько им дали. Можно посмотреть в string.len и узнать точный размер. А еще они гораздо быстрее SDS и std::string почти во всем
Hardened_Steel
21.08.2026 18:56исходя из вашей же табличке сравнения я не могу сделать такого же вывода
- хеш вы считаете неправильно, в отличии от std::string
- в операции конкатенации проигрываете на три порядка
- исходников бенча для std::string не видно
voldemar_d
21.08.2026 18:56Периодически делаем профилирование
Вот это ключевой момент. Прежде чем пытаться что-то оптимизировать, надо сначала понять, что именно является узким местом. Можно взять и решить, что нужно оптимизировать, а потом окажется, что в 10 раз ускорили то, что работает 1% времени.
Janycz
21.08.2026 18:56И кстати, заявлено, что собирается любым C99/C11 компилятором. Но это не так, например: gcc 16.1.0 на Windows падает с ошибкой, ибо strcat_s это нестандартная функция из состава стандартной C библиотеки под Windows, а перегрузки функций в C нет. Проект, однако, собирается на g++ под Windows, но это компилятор языка C++, а не C.
Garantia_Tsverga Автор
21.08.2026 18:56Буду чинить, благодарю за репорт. Я предполагал, что использование исключительно libc гарантирует кроссплатформенность. Но нет, Windows опять надо было встрять¯\_(ツ)_/¯
Janycz
21.08.2026 18:56А вот на самом деле, тут Windows права. Ибо стандарт ISO C11 (Annex K) резервирует функции типа
strcat_s,strcpy_sиstrcmp_s. Строго следуя стандарту языка языка С, программы не имеют права определять собственные функции с этими именами. В libc для Linux по умолчанию эти функции скрыты. Чтобы gcc с libc их увидел, надо писать#define __STDC_WANT_LIB_EXT1__ 1. В Windows эти функции были давно, до С11, как нестандартные расширения.
Kotofay
21.08.2026 18:563. Вычисляется хэш за счет XOR указателей на данные, длину строки и самой длины.
Одинаковые строки разве не должны иметь одинаковый хэш?
Garantia_Tsverga Автор
21.08.2026 18:56Я строил проект не на самую бодрую голову, а потому все может быть. Мне стоит все пересмотреть позже
tenzink
21.08.2026 18:56Уровень реализации не соответствует уровню пафоса. Хеш одинаковых строк должен быть одинаковым - в вашей реализации это не так. Пока, к сожалению, не тянет даже на учебную поделку.
Garantia_Tsverga Автор
21.08.2026 18:56Изо всех претензий, вы единогласно выбрали именно хэш. Впрочем, стоило отметить, что я вообще не тестировал функцию толком, виноват.
tenzink
21.08.2026 18:56Да бог с ним с хешем, тем более, что сейчас вы его поправили. Теперь, правда, документация некорректна. Там уже O(n), и не то, чтобы реализация быстрая.
Теперь возьмём
ds_push. Каждый вызов делает новую строку (с новой аллокацией памяти), что совсем необязательною Иногда хочется расширять строку, добавляя в конец элементы. Но ваша строка такой API не предоставляет в отличии от критикуемой вами стандартной библиотеки. При этом с ds_push очень легко словить утечку, а при использовании в цикле получить O(n^2). Но страдать с несуразностями этого API вы предоставляете пользователю.Беда вашего подхода не в том, что реализация строки УГ - это нормально для экспериментов в период обучения. Нормально и то, что вы пока сами не осознаёте, насколько эта реализация ужасна.
Проблема в том, что вы огульно охаиваете другие решения, не пытаясь разобраться в том, какие осознанные решения были приняты и как они повлияли на реализацию.
Hardened_Steel
21.08.2026 18:56А как вы различаете SSO строки от длинных в вашей структуре?
Хеш от указателя считать такое себе. Т.е. две одинаковые строки будут иметь разный хеш? Поведение, мягко говоря, нестандартное.
Цифры бенча на гихабе конечно интересные, в операции сложения вы проиграли std::string на три порядка, а это, мне кажется, наиболее частая операция над строками.Garantia_Tsverga Автор
21.08.2026 18:56SSO:
static inline bool is_sso(const string* s) { return s != NULL && (s->sso_len & STR_SSO_FLAG) != 0; }Про хеши от указателей уже писали
Бенч конкатенации подразумевал добавление 1 символа 100000 раз в цикле. C++ и SDS тащат за счет геометрического роста capacity, а у меня malloc() на каждое расширение. Даже в документации напрямую указано, что так делать нельзя, надо делать одну точечную и большую.
Hardened_Steel
21.08.2026 18:56Хотелось бы комментария, чем обосновано ваше решение.
Потому, что я вижу тут следующее:
- предположим мы на 64 битной системе, форма хранения числе - LE
- sso_len ложится на capacity, причём это последний байт всей структуры
- последний байт всей структуры - самый младший байт capacity
- флаг 0x80 = 128, т.е. если мы выделим 128 байт под буфер для длинной строки (или любое другое число байт где нужный бит будет установлен в 1), мы спутаем её с короткой?
Hardened_Steel
21.08.2026 18:56Бенч конкатенации подразумевал добавление 1 символа 100000 раз в цикле. C++ и SDS тащат за счет геометрического роста capacity, а у меня malloc() на каждое расширение. Даже в документации напрямую указано, что так делать нельзя, надо делать одну точечную и большую.
std::string тоже позволяет сделать reserve(size), а вас альтернативы как бы нет.
Garantia_Tsverga Автор
21.08.2026 18:56Вы сравниваете проект, которому 37 лет, с проектом, набросанным вчера на коленке, да еще и без глубокого понимания C. Ну не понимаю я Вас.
wander
21.08.2026 18:56Зачем же тогда писать такое "как именно бы выглядел
std::string, если бы его писал кто‑то действительно вдумчивый?". Это вот самовосхваление с одновременной постановкой под сомнение квалификации других инженеров. Выглядит мерзко. Нет, конечно же, критика нужна и важна, но разве проект, которому 37 лет, не имеет права оцениваться без этих вот "да они там вообще не думают"? О ваших заслугах должны говорить ваши поступки, а не такие вот фразы, отдающие юношеским максимализмом.Garantia_Tsverga Автор
21.08.2026 18:56Штош, я не писатель.
Но если серьезно, то я имел ввиду, что std::string оптимизирован плохо для "низкоуровневого" языка. Даже с его фичами, я смог сделать легче (16 байт ОЗУ). Помимо этого, я также сделал хотфикс хэша (теперь правильно вычисляется) — его можно положить в строку и сравнивать за O(1) (в std::string он не хранится, он вычисляется каждый раз за O(n)).
Дело в том, что надо судить по потенциалу, а не по текущему функционалу (если время не поджимает, конечно же)
HiItsYuri
21.08.2026 18:56Но если серьезно, то я имел ввиду, что std::string оптимизирован плохо для “низкоуровневого” языка.
Да с чего вы вообще взяли что СТАНДАРТНАЯ строка должна быть оптимизирована под низкоуровневое программирование?
Откуда пошла вот эта чушь? Почему второй раз раз за неделю я читаю что плюсы ДОЛЖНЫ удовлетворять больным желаниям железячников? Это в вузах всё ещё учат что плюсы - С с классами?
AskePit
21.08.2026 18:56так ведь в первую очередь Вы сравниваете своей статьей. и вот что действительно, так это что без глубокого понимания.
вдумчивость, которую мы заслужили
Mingun
21.08.2026 18:56union вы конечно сделали, но кажется забыли о том, а как теперь понять, какой из вариантов активный. Ладно, допустим, пока
capacityне используется, флаги изsso_lenоказываются там, в них и можно хранить признак, но как только вы туда что-то засуните (вот хеш хотя бы), то все.
mbait
21.08.2026 18:56Тот факт, что вы ставите под сомнение устои - хорошо, когда мы прекращаем это делать, общество скатывается до поклонения авторитетам. У вас просматривается огромное желание что-то привнести в мир программирования, но вам не хватает а - знаний, б - желания сперва изучить то, что было создано до вас. Без первого ваши заявления будут вызывать в лучшем случае - улыбку и непонимание, как это случилось в хешированием. Без второго вы обречены изобретать колесо.
По первому пункту я рекомендую, как минимум, ознакомиться с методиками тестирования реализаций строк. Ваше тестирование исключительно синтетическое, никто в реальных программах не вызывает конструктор миллион раз в одном месте. В реальности программы оперируют какими-то кусками строк, конкатенируют их, обрезают, накапливают и так далее, и измерять производительности нужно на тестах, близких к реальному сценарию использования: лексически разбор, поиск вхождений регулярных выражений, сжатие.
По второму пункту я рекомендую всё таки внимательнее изучить реализацю, как минимум, трёх проектов: LLVV, Facebook/Meta и Qt. А ещё посмотреть прекрасное выступление https://www.youtube.com/watch?v=kPR8h4-qZdk
P.S. Что касается "философия моих строк заключается в том, что они занимают как раз столько места, сколько им дали" - накладные расходы в десяток байт для современного мира это ничто по сравнению с проигрышем, который будет вызван промахом кэша или неправильным/отсутствием предсказания ветвления. Непонимание этого ведёт к тому, что создаются проекты, которые умещаются на дискету, но совершенно никому не интересны. Оптимизации в стиле демосцены это сегодня удел исключительно встроенных систем, да и те постепенно приближаются по производительности к настольным.
Garantia_Tsverga Автор
21.08.2026 18:56Здоровая критика от людей вроде Вас — лучшее, что может со мной случиться. Благодарю. Но это был не столь серьезный продукт, сколь эксперимент, направленный на то, чтобы показать, насколько C++ для языка, позиционирующего себя как (среди прочих назначений) низкоуровневый, раздут. А еще мне просто было интересно его проводить.
sergio_nsk
21.08.2026 18:56smolbuf - Автор, ты откуда?"примерно так" - на самом деле вообще не так.
AskePit
21.08.2026 18:56более того - этот “примерно так” - это про libstdc++, libc++, msvc stl? а если все они “плохи” в реализации строки - это они каждый по отдельности глупость написали или это сговор глупости такой?
jeeper
21.08.2026 18:56Это как всегда история о поддержке: все, что ты написал своими руками считай взял на поддержку. Если проект - лаба для сдачи, то ок, а если нет - не ок. Кажется ерунда, но когда такой ерунды к концу проекта оказывается вагон и маленькая тележка, то все чем ты будешь заниматься - латанием дыр и поддержкой уже написанного. Ну или другая история: компании заказали специализированный модуль обработки строк, тогда почему бы и нет. Ведь основная цель проекта как раз анписание модуля строк. Ну и одно дело модуль строк, но к нему ведь еще ввод выаод и другие обвязки.
Janycz
Ну мне понадобиться. Прочитать > 4 GiB файл полностью.
Garantia_Tsverga Автор
Уж не знаю, зачем Вам тратить 4+ ГБ ОЗУ на 1 строку (и не закончится ли запись на первом же '\0' — а она закончится, если использовать версию с
strlen()), но я все равно подумывал над разными версиями string (например, string64, которая бы потенциально включала в себя 2^64 символов — таков лимит как раз у SDS иstd::stringна 64-битной ОС.Janycz
Памяти много, 4+ GiB не жалко. Распарсить какой-нибудь большой датасет там: раз памяти много, то чтобы быстрее обработать можно загрузить сразу все. Стандартный std::string может содержать '\0' в середине строки. ReadFile из WinAPI или std::fread из <cstdio> спокойно прочитают контент с символом '\0'. WriteFile из WinAPI или std::fwrite из <cstdio> спокойно запишут контент с символом '\0' в середине. Правда, следует проявлять осторожность при подаче результата от .data() в функцию, которая ожидает нуль-терминированную строку типа char*.
voldemar_d
Не правильнее ли во время чтения парсить? Можно, например, параллельно в разных потоках это делать, что может оказаться заметно быстрее, чем сначала прочитать файл целиком, а уже потом парсить.
Например, есть библиотека, которая читает и парсит CSV-файлы, которая умеет это делать многопоточно, в результате даже здоровенные файлы в гигабайты парсит буквально за секунды (ну, быстрее минуты точно).
Janycz
Не правильнее ли во время чтения парсить? -- ну так вначале все равно надо прочитать. Или вот потом сгенерировать большой выхлоп программы: пишем все строку, а потом выводим одним вызовом write. Так будет быстрее. Операции с диском небыстрые относительно операций с данными из ОЗУ. Вообще, по-хорошему, чтобы прочитать, рекомендуется делать mmap/madvice/munmap.