Comments 23
uint32_t lenхранит длину строки: эта переменная ограничена до 2³², но кому вообще понадобится создавать одну строку в 4 ГБ? Размер: 4 байта.
Ну мне понадобиться. Прочитать > 4 GiB файл полностью.
Уж не знаю, зачем Вам тратить 4+ ГБ ОЗУ на 1 строку (и не закончится ли запись на первом же '\0' — а она закончится, если использовать версию с strlen()), но я все равно подумывал над разными версиями string (например, string64, которая бы потенциально включала в себя 2^64 символов — таков лимит как раз у SDS и std::string на 64-битной ОС.
Памяти много, 4+ GiB не жалко. Распарсить какой-нибудь большой датасет там: раз памяти много, то чтобы быстрее обработать можно загрузить сразу все. Стандартный std::string может содержать '\0' в середине строки. ReadFile из WinAPI или std::fread из <cstdio> спокойно прочитают контент с символом '\0'. WriteFile из WinAPI или std::fwrite из <cstdio> спокойно запишут контент с символом '\0' в середине. Правда, следует проявлять осторожность при подаче результата от .data() в функцию, которая ожидает нуль-терминированную строку типа char*.
Повсеместно используем std::string в очень большом, с элементами легаси кросс-платформенном десктопном софте. Периодически делаем профилирование. Да, иногда строки становятся узким местом, но настолько редко что хватает точечных оптимизаций через string_view. В 99% случаев проблемы с перформансом из-за других вещей.
Я никогда не говорил, что std::string тормозят код. Я сказал, что для такого языка, как C++, std::string сделан плохо. А на string_view у меня свои планы, его я тоже когда-нибудь реализую.
шок, есть разные реализации std::string, идите изучайте другие варианты :)
И кстати, заявлено, что собирается любым C99/C11 компилятором. Но это не так, например: gcc 16.1.0 на Windows падает с ошибкой, ибо strcat_s это нестандартная функция из состава стандартной C библиотеки под Windows, а перегрузки функций в C нет. Проект, однако, собирается на g++ под Windows, но это компилятор языка C++, а не C.
Буду чинить, благодарю за репорт. Я предполагал, что использование исключительно libc гарантирует кроссплатформенность. Но нет, Windows опять надо было встрять¯\_(ツ)_/¯
А вот на самом деле, тут Windows права. Ибо стандарт ISO C11 (Annex K) резервирует функции типа strcat_s, strcpy_s и strcmp_s . Строго следуя стандарту языка языка С, программы не имеют права определять собственные функции с этими именами. В libc для Linux по умолчанию эти функции скрыты. Чтобы gcc с libc их увидел, надо писать #define __STDC_WANT_LIB_EXT1__ 1. В Windows эти функции были давно, до С11, как нестандартные расширения.
3. Вычисляется хэш за счет XOR указателей на данные, длину строки и самой длины.
Одинаковые строки разве не должны иметь одинаковый хэш?
Уровень реализации не соответствует уровню пафоса. Хеш одинаковых строк должен быть одинаковым - в вашей реализации это не так. Пока, к сожалению, не тянет даже на учебную поделку.
А как вы различаете SSO строки от длинных в вашей структуре?
Хеш от указателя считать такое себе. Т.е. две одинаковые строки будут иметь разный хеш? Поведение, мягко говоря, нестандартное.
Цифры бенча на гихабе конечно интересные, в операции сложения вы проиграли std::string на три порядка, а это, мне кажется, наиболее частая операция над строками.
SSO:
static inline bool is_sso(const string* s) {
return s != NULL && (s->sso_len & STR_SSO_FLAG) != 0;
}Про хеши от указателей уже писали
Бенч конкатенации подразумевал добавление 1 символа 100000 раз в цикле. C++ и SDS тащат за счет геометрического роста capacity, а у меня malloc() на каждое расширение. Даже в документации напрямую указано, что так делать нельзя, надо делать одну точечную и большую.
Хотелось бы комментария, чем обосновано ваше решение.
Потому, что я вижу тут следующее:
- предположим мы на 64 битной системе, форма хранения числе - LE
- sso_len ложится на capacity, причём это последний байт всей структуры
- последний байт всей структуры - самый младший байт capacity
- флаг 0x80 = 128, т.е. если мы выделим 128 байт под буфер для длинной строки (или любое другое число байт где нужный бит будет установлен в 1), мы спутаем её с короткой?
Бенч конкатенации подразумевал добавление 1 символа 100000 раз в цикле. C++ и SDS тащат за счет геометрического роста capacity, а у меня malloc() на каждое расширение. Даже в документации напрямую указано, что так делать нельзя, надо делать одну точечную и большую.
std::string тоже позволяет сделать reserve(size), а вас альтернативы как бы нет.
union вы конечно сделали, но кажется забыли о том, а как теперь понять, какой из вариантов активный. Ладно, допустим, пока capacity не используется, флаги из sso_len оказываются там, в них и можно хранить признак, но как только вы туда что-то засуните (вот хеш хотя бы), то все.
Тот факт, что вы ставите под сомнение устои - хорошо, когда мы прекращаем это делать, общество скатывается до поклонения авторитетам. У вас просматривается огромное желание что-то привнести в мир программирования, но вам не хватает а - знаний, б - желания сперва изучить то, что было создано до вас. Без первого ваши заявления будут вызывать в лучшем случае - улыбку и непонимание, как это случилось в хешированием. Без второго вы обречены изобретать колесо.
По первому пункту я рекомендую, как минимум, ознакомиться с методиками тестирования реализаций строк. Ваше тестирование исключительно синтетическое, никто в реальных программах не вызывает конструктор миллион раз в одном месте. В реальности программы оперируют какими-то кусками строк, конкатенируют их, обрезают, накапливают и так далее, и измерять производительности нужно на тестах, близких к реальному сценарию использования: лексически разбор, поиск вхождений регулярных выражений, сжатие.
По второму пункту я рекомендую всё таки внимательнее изучить реализацю, как минимум, трёх проектов: LLVV, Facebook/Meta и Qt. А ещё посмотреть прекрасное выступление https://www.youtube.com/watch?v=kPR8h4-qZdk
P.S. Что касается "философия моих строк заключается в том, что они занимают как раз столько места, сколько им дали" - накладные расходы в десяток байт для современного мира это ничто по сравнению с проигрышем, который будет вызван промахом кэша или неправильным/отсутствием предсказания ветвления. Непонимание этого ведёт к тому, что создаются проекты, которые умещаются на дискету, но совершенно никому не интересны. Оптимизации в стиле демосцены это сегодня удел исключительно встроенных систем, да и те постепенно приближаются по производительности к настольным.
Make STL Cringe Again: Как я динамические строки на C создавал