Хабр Курсы для бэкендеров
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Поток Бэкенд доступен 24/7 благодаря поддержке друзей Хабра
Комментарии 40
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*.
Распарсить какой-нибудь большой датасет
чтобы быстрее обработать можно загрузить сразу все
Не правильнее ли во время чтения парсить? Можно, например, параллельно в разных потоках это делать, что может оказаться заметно быстрее, чем сначала прочитать файл целиком, а уже потом парсить.
Например, есть библиотека, которая читает и парсит CSV-файлы, которая умеет это делать многопоточно, в результате даже здоровенные файлы в гигабайты парсит буквально за секунды (ну, быстрее минуты точно).
Не правильнее ли во время чтения парсить? -- ну так вначале все равно надо прочитать. Или вот потом сгенерировать большой выхлоп программы: пишем все строку, а потом выводим одним вызовом write. Так будет быстрее. Операции с диском небыстрые относительно операций с данными из ОЗУ. Вообще, по-хорошему, чтобы прочитать, рекомендуется делать mmap/madvice/munmap.
Повсеместно используем std::string в очень большом, с элементами легаси кросс-платформенном десктопном софте. Периодически делаем профилирование. Да, иногда строки становятся узким местом, но настолько редко что хватает точечных оптимизаций через string_view. В 99% случаев проблемы с перформансом из-за других вещей.
Я никогда не говорил, что std::string тормозят код. Я сказал, что для такого языка, как C++, std::string сделан плохо. А на string_view у меня свои планы, его я тоже когда-нибудь реализую.
шок, есть разные реализации std::string, идите изучайте другие варианты :)
А точно надо изобретать то, что уже было сделано в C++17?
Периодически делаем профилирование
Вот это ключевой момент. Прежде чем пытаться что-то оптимизировать, надо сначала понять, что именно является узким местом. Можно взять и решить, что нужно оптимизировать, а потом окажется, что в 10 раз ускорили то, что работает 1% времени.
И кстати, заявлено, что собирается любым 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 указателей на данные, длину строки и самой длины.
Одинаковые строки разве не должны иметь одинаковый хэш?
Уровень реализации не соответствует уровню пафоса. Хеш одинаковых строк должен быть одинаковым - в вашей реализации это не так. Пока, к сожалению, не тянет даже на учебную поделку.
Изо всех претензий, вы единогласно выбрали именно хэш. Впрочем, стоило отметить, что я вообще не тестировал функцию толком, виноват.
Да бог с ним с хешем, тем более, что сейчас вы его поправили. Теперь, правда, документация некорректна. Там уже O(n), и не то, чтобы реализация быстрая.
Теперь возьмём ds_push. Каждый вызов делает новую строку (с новой аллокацией памяти), что совсем необязательною Иногда хочется расширять строку, добавляя в конец элементы. Но ваша строка такой API не предоставляет в отличии от критикуемой вами стандартной библиотеки. При этом с ds_push очень легко словить утечку, а при использовании в цикле получить O(n^2). Но страдать с несуразностями этого API вы предоставляете пользователю.
Беда вашего подхода не в том, что реализация строки УГ - это нормально для экспериментов в период обучения. Нормально и то, что вы пока сами не осознаёте, насколько эта реализация ужасна.
Проблема в том, что вы огульно охаиваете другие решения, не пытаясь разобраться в том, какие осознанные решения были приняты и как они повлияли на реализацию.
Учту. Благодарю за критику.
Если тема интересна, есть шикарный доклад по теме CppCon 2016: Nicholas Ormrod “The strange details of std::string at Facebook" (https://www.youtube.com/watch?v=kPR8h4-qZdk)
А как вы различаете 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), а вас альтернативы как бы нет.
Вы сравниваете проект, которому 37 лет, с проектом, набросанным вчера на коленке, да еще и без глубокого понимания C. Ну не понимаю я Вас.
Зачем же тогда писать такое "как именно бы выглядел std::string, если бы его писал кто‑то действительно вдумчивый?". Это вот самовосхваление с одновременной постановкой под сомнение квалификации других инженеров. Выглядит мерзко. Нет, конечно же, критика нужна и важна, но разве проект, которому 37 лет, не имеет права оцениваться без этих вот "да они там вообще не думают"? О ваших заслугах должны говорить ваши поступки, а не такие вот фразы, отдающие юношеским максимализмом.
Штош, я не писатель.
Но если серьезно, то я имел ввиду, что std::string оптимизирован плохо для "низкоуровневого" языка. Даже с его фичами, я смог сделать легче (16 байт ОЗУ). Помимо этого, я также сделал хотфикс хэша (теперь правильно вычисляется) — его можно положить в строку и сравнивать за O(1) (в std::string он не хранится, он вычисляется каждый раз за O(n)).
Дело в том, что надо судить по потенциалу, а не по текущему функционалу (если время не поджимает, конечно же)
Но если серьезно, то я имел ввиду, что std::string оптимизирован плохо для “низкоуровневого” языка.
Да с чего вы вообще взяли что СТАНДАРТНАЯ строка должна быть оптимизирована под низкоуровневое программирование?
Откуда пошла вот эта чушь? Почему второй раз раз за неделю я читаю что плюсы ДОЛЖНЫ удовлетворять больным желаниям железячников? Это в вузах всё ещё учат что плюсы - С с классами?
так ведь в первую очередь Вы сравниваете своей статьей. и вот что действительно, так это что без глубокого понимания.
вдумчивость, которую мы заслужили
union вы конечно сделали, но кажется забыли о том, а как теперь понять, какой из вариантов активный. Ладно, допустим, пока capacity не используется, флаги из sso_len оказываются там, в них и можно хранить признак, но как только вы туда что-то засуните (вот хеш хотя бы), то все.
Тот факт, что вы ставите под сомнение устои - хорошо, когда мы прекращаем это делать, общество скатывается до поклонения авторитетам. У вас просматривается огромное желание что-то привнести в мир программирования, но вам не хватает а - знаний, б - желания сперва изучить то, что было создано до вас. Без первого ваши заявления будут вызывать в лучшем случае - улыбку и непонимание, как это случилось в хешированием. Без второго вы обречены изобретать колесо.
По первому пункту я рекомендую, как минимум, ознакомиться с методиками тестирования реализаций строк. Ваше тестирование исключительно синтетическое, никто в реальных программах не вызывает конструктор миллион раз в одном месте. В реальности программы оперируют какими-то кусками строк, конкатенируют их, обрезают, накапливают и так далее, и измерять производительности нужно на тестах, близких к реальному сценарию использования: лексически разбор, поиск вхождений регулярных выражений, сжатие.
По второму пункту я рекомендую всё таки внимательнее изучить реализацю, как минимум, трёх проектов: LLVV, Facebook/Meta и Qt. А ещё посмотреть прекрасное выступление https://www.youtube.com/watch?v=kPR8h4-qZdk
P.S. Что касается "философия моих строк заключается в том, что они занимают как раз столько места, сколько им дали" - накладные расходы в десяток байт для современного мира это ничто по сравнению с проигрышем, который будет вызван промахом кэша или неправильным/отсутствием предсказания ветвления. Непонимание этого ведёт к тому, что создаются проекты, которые умещаются на дискету, но совершенно никому не интересны. Оптимизации в стиле демосцены это сегодня удел исключительно встроенных систем, да и те постепенно приближаются по производительности к настольным.
Здоровая критика от людей вроде Вас — лучшее, что может со мной случиться. Благодарю. Но это был не столь серьезный продукт, сколь эксперимент, направленный на то, чтобы показать, насколько C++ для языка, позиционирующего себя как (среди прочих назначений) низкоуровневый, раздут. А еще мне просто было интересно его проводить.
smolbuf - Автор, ты откуда?
"примерно так" - на самом деле вообще не так.
Это как всегда история о поддержке: все, что ты написал своими руками считай взял на поддержку. Если проект - лаба для сдачи, то ок, а если нет - не ок. Кажется ерунда, но когда такой ерунды к концу проекта оказывается вагон и маленькая тележка, то все чем ты будешь заниматься - латанием дыр и поддержкой уже написанного. Ну или другая история: компании заказали специализированный модуль обработки строк, тогда почему бы и нет. Ведь основная цель проекта как раз анписание модуля строк. Ну и одно дело модуль строк, но к нему ведь еще ввод выаод и другие обвязки.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Make STL Cringe Again: Как я динамические строки на C создавал