Комментарии 55
Ну, лично я изначально считал порочной идею не хранить длину строки в явном виде, а заканчивать строку нулевым символом. Да, длина строки будет ограничена максимальным значением счётчика, но если выделить под него 4 байта, то вряд ли найдётся разумный случай, где этой длины для строки будет мало (4 Гбайта или 4 Гсимвола в зависимости от того, как трактовать значение длины, что в данном случае вторично). Ну а выделение лишних трёх байтов даже на машинах с адресным пространством в 64 Кбайта (в т.ч. PDP-11, где, по сути, и появился Уних вместе с Це) -- отнюдь не гигантский перерасход памяти, не говоря о том, что на таких архитектурах можно было бы выделять под длину два байта, а не четыре -- всё равно строка в памяти не может быть длинней, чем этой памяти можно адресовать. (Ну а где каждый байт на счету в буквальном смысле -- пишите на ассемблере, и будет вам счастье.)
А вот с заключением автора не очень-то согласен. Противоречия возникают не между реальным поведением программ на реальных процах и "здравым смыслом", а между реальным поведением и ожиданием программиста, плохо понимающего (или вообще не понимающего), как в реальности работает железо. Когда такое понимание есть, сюрпризов будет намного меньше.
выделение лишних трёх байтов даже на машинах с адресным пространством в 64 Кбайта (в т.ч. PDP-11, где, по сути, и появился Уних вместе с Це) -- отнюдь не гигантский перерасход памяти
Идеология C закладывалась на PDP-7, где в базовом варианте было всего 4К слов. Но речь даже не об этом. Популярность C приобрел потому, что подходил не только для весьма мощных для того времени PDP-11, но так же и для микропроцессоров и микроконтроллеров.
Для понимания, первый ZX Spectrum имел всего 16К RAM, из которых почти половина была занята под видеобуфер. Atari 800 имела только 8К. МК 8048 имел всего 128 байт RAM, а до сих пор встречающийся 8051 - 256 байт.
Даже сейчас на маломощных МК можно встретить эти же 128 или 256 байт оперативной памяти. Наапример, в МК Padauk.
Так что будьте снисходительны к Ричи. Тогда действительно каждый байт считали. И сейчас на некоторых МК тоже приходится это делать.
В те старые добрые времена (и ещё долго после них) не было ни ILP, ни оптимизирующих компиляторов. Поэтому то, что казалось логичным, было логичным действительно. А хранение длины строки отдельно от неё означало и усложнение компилятора, и уменьшение скорости его работы: на тот момент немаловажные факторы.
Вообще-то, оптимизирующие компиляторы в 1970-е уже точно были.
Ну а усложнять компилятор для работы со строками не требуется, если с ними он работать не умеет (а сишный НЕ умеет, по большому счёту, единственная "поддержка строк" -- это формирование массива символов с завершающим нулём, что ничуть не сложней, чем формирование массива символов с предваряющей его длиной).
Почти за 10 лет до C, в PL/I длина строки хранилась в отдельном 16-битном поле.
А почему не varint тогда?
Хотите короткую строку - длина 1 байт, хотите длинную - 2 байта и т.д.
Когда в строке уже н-цать тысяч байт, один байт погоды не сделает
Variant требует места для хранения типа. Чаще используют метод более сложного кодирования, как, например, base 128 encoding в Protobuf. 64-битное беззнаковое целое тогда может занимать от 1 до 9 байт. Но следует понимать, что кодирование и декодирование такого представления требует дополнительных ресурсов CPU. Поэтому и используется оно только тогда, когда размер важнее, чем производительность. Из-за этого, например, в PostgreSQL в памяти длина строки кодируется всегда 4 байтами, тогда как в странице БД - уже от 1 до 4 байт.
Похожим образом работает row compression в MS SQL, но уже не для длин строк, а для всех чисел.
Не variant, а varint. Т.е. VLQ или base 128 encoding, о котором вы и сказали (:
Но следует понимать, что кодирование и декодирование такого представления требует дополнительных ресурсов CPU
Да, но:
чем короче строка, тем меньше затраты на работу со значением длины. для коротких строк (до 127) разницы с 1-байтовой длиной не будет
чем длиннее строка, тем для работы с ней в принципе нужно больше ресурсов, и с увеличением длины длины (простите) линейно, "рабочая" длина строки увеличивается нелинейно и уже может не влезать в кеш CPU более низкого уровня. В этом случае преобразование variable-width integer в fixed-width integer может не играть значительной роли
всё это справедливо исключительно для runtime представления строк, компилятору в общем-то итак известны длины констант
компиляторы (LLVM) используют variable-width integer во внутреннем представлении
на современных процессорах кодирование/декодирование такого рода может быть ускорено SIMD операциями
В общем и целом, если ресурсы на "кодирование и декодирование" такого представления оказываются незначительны по сравнению с ресурсами на работу с null-terminated строками, то это не то что бы плохой вариант.
Но это в любом случае невозможно в C, т.к. C - это по большому счету синтаксический сахар для опкодов процессора. И если fixed-width integer - это число с точки зрения процессора, то variable-width integer - это просто бессмысленные байты, которые компилятор сам должен преобразовать в числа. И основная проблема, на мой взгляд, именно в этом, а не в производительности работы со строками.
А вы посмотрите на ассемблерный код декодирования base 128 encoding и сравните его с одной командой чтения выравненного в памяти uint32. При этом, с учетом размера страницы кэша CPU, обычно, 64 байта, разницу на чтение одного и четырех байт не заметите.
Что касается C, то там нет проблем в хранении и обработке строк в любом формате. Альтернатив стандартной библиотеке множество. Например, мне нравится универсальность sds
А вы посмотрите на ассемблерный код декодирования base 128 encoding и сравните его с одной командой чтения выравненного в памяти uint32
А зачем? (Мне) очевидно, что работа с varint будет дороже в плане ресурсов CPU чем работа с нативными integer типами.
Но какая разница насколько дорога работа с varint, если речь идёт о работе со строками, длина которых (теоретически) представлена в виде varint?
В контексте работы со строками эта операция будет проводиться один раз для того чтобы преобразовать int в varint и наоборот, чтобы определить границы строки или создать строку. Это побочная операция т.к., в подавляющем большинстве случаев работа со строками на этом не заканчивается. То, что будут сэкономлены пару тактов, большой погоды не сделает, т.к. копирование, парсинг, поиск, сортировка и пр. будут занимать намного больше времени.
Так экономия пары байт на длине строки тоже ни на что, по большому счёту, не повлияет...
Это зависит от масштабов.
Когда строки в приложении большие (допустим, от 64кб), 8 байт size_t действительно теряются на фоне строки. В этом случае varint будет кодироваться 3+ байтами.
8 байт size_t для строк длиной 128 байт и меньше - это уже достаточно много. В этом случае только длина - это ~6% размера самой строки. В таком ключе работа с мелкими строками становится дорогой по памяти, если таких строк много.
В 1ГиБ может быть ~8.4млн таких строк, для которых 8 байт размера будут занимать 64МиБ. Или, другими словами, ещё ~500к мелких строк.
А от того, сможет приложение загрузить в память целиком огромный массив данных или нет, может зависеть и производительность приложения в целом, т.к. "лишиние" сотни тысяч-миллионы строк может быть нужно читать уже с диска.
Вы не осознаете проблему. Попробуйте написать сортировку строк с префиксом длины в base 128 encoding и с префиксом фиксированной длины 4 байта. При каждом(!) сравнении строк в первом случае потребуется вычислять смещение начала строки, чего не потребуется во втором.
Вы не осознаете проблему
Смелое утверждение. Это вам так кажется :)
При каждом(!) сравнении строк в первом случае потребуется вычислять смещение начала строки, чего не потребуется во втором.
А проблемы-то это какие вызывает? Само вычисление смещения - это не сортировка
В случае с короткими строками разницы нет никакой т.к. varint до значения 128 занимает 1 байт
Смещение вычисляется простым подсчётом байта, у которого первый бит 0
В случае, если длины строк различаются, конвертировать в обычный int их для сравнения может быть даже и не нужно
Когда длины строк равны - вычисление смещения в общем море операций сравнения будет в пределах погрешности
Чтобы сортировать строки, вам их надо будет перемещать. Перемещение строк дороже, чем сравнение заголовка.
А Вы напишите. Вероятность того, что у двух строк одинаковые первые символы - меньше 1%. А значит в 99% случаев, кроме сравнения двух символов одной машинной командой, будете вычислять смещение каждого их этих символов.
Чтобы сортировать строки, вам их надо будет перемещать.
Вы так прикалываетесь? По-моему, в технической дискуссии - это бескультурно.
По-моему, в технической дискуссии - это бескультурно.
А вы образчик культуры, как я погляжу:
Вы так прикалываетесь?
Вы не осознаете проблему.
Раз уж вы опускаетесь до хамства и перехода на личности, то не вижу смысла дальше продолжать.
Думаю имелось в виду variant length, т.е. что-то типа: длина строки от 0 до 127 - поле длины занимает 1 байт. Если длиннее - ставим старший бит в поле длины и используем ещё один байт для поля длины строки. И так далее
Это и есть base 128 encoding. И почему такие приемы распространены для передачи данных или их хранения на диске, но редки в оперативной памяти - я тоже указал.
Термин variant length слышу впервые. Есть variable length [quantity], есть variant type. Дайте хоть ссылку на описание этого термина.
Мой комментарий был не про термин - я пытался понять суть того, что сказал @gudvinr. Я как он выше уже обратил наше внимание, что он имел в виду varint - https://habr.com/ru/articles/350796
Т.е. все "представили" себе один и тот же метод, но не сошлись в терминологии :)
Вы просто выросли в те времена, когда под длину строки выделяли целый int, а не byte :-) (Turbo Pascal и более ранние паскали на 8-битных машинках).
Только не 4 байта, а машинное слово. Тогда точно нехватки не будет.
Машинное слово тут не при чем. У Z80 машинное слово 8 бит, а адресует он напрямую 64К (были ZX Spectrum и со 128К). PDP-11/70 имела машинное слово 16 бит и 4 МБ оперативной памяти. У 8086 (IBM PC/AT) машинное слово тоже 16 бит, но адресное пространство до 1 МБ (640К хватит всем ...). А 80286, имея машинное слово 16 бит, напрямую мог адресовать до 16 МБ памяти.
Поправочка: напрямую PDP-11 могла адресовать только 64 Кбайта (если с разделением на код и данные, что есть у PDP-11/70, но отсутствует у многих других моделей -- то по 64 Кбайт кода и данных), 80286 -- в совокупности до 256 Кбайт в 4 сегментах. Выход за эти пределы -- только манипуляциями с регистрами MMU (на PDP-11) или с сегментными регистрами (на 80286), что является нетривиальной задачей и усложняет адресацию и не всегда возможно без вмешательства ОС на том или ином уровне.
могла адресовать
Это тут при чем? Я с примерами показал, что машинное слово и адресуемая память - разные вещи. На каких то CPU адресная шина уже, чем машинное слово (например, 48 бит против 64). На каких то наоборот (22 бита против 16, как на PDP-11/70). Вот и доказывайте, что Z80 с машинным словом 8 бит не мог работать со строками длинней 256 байт.
Ну, наиболее разумным выглядит выделение под счётчик стольких разрядов, сколько имеется в виртуальном адресе. Правда, 8 байт для 64-разрядных архитектур выглядит избыточным с практической точки зрения, но на них-то каждый байт уж точно считать не приходится, а при таком подходе (ширина поля длины = ширине виртуального адреса) можно было бы формат строки стандартизировать на уровне библиотеки для любых платформ.
Правда, 8 байт для 64-разрядных архитектур выглядит избыточным
Чертовски избыточным. Вы никогда бы не смогли использовать nul-строки, сравнимые со строками со счётчиком длины даже в 32 бита, strlen на размерах в гигабайты будет максимально некомфортным. malloc тоже имеет свои ограничения на длину выделяемого куска памяти, так что, если речь не идёт о перелопачивании языка, придётся быть чуть скромнее.
А потом вспоминаем java, где имея хип в пару террабайт нельзя выделить массив байт размером больше 2 гигабайт.
Как я написал, избыточность 8-байтового поля длины можно оправдать идентичным подходом к библиотеке на любых платформах: поле длины везде имеет ширину виртуального адреса. Просто, чем меньше исключений из правил, тем проще и лучше.
strlen -- да, будет очень долгим, но он-то как раз станет ненужным, если длина хранится в явном виде. Что до malloc и прочих подобных вещей, то они завязаны не на язык, а на конкретную реализацию, которая может накладывать свои не очень-то обоснованные ограничения. В частности, нет принципиальных причин для того, почему нельзя выделить за одну операцию, скажем, 2**40 байтов -- ограничения имеются чисто технические (объём доступного файла подкачки, например: если выделяемая область не может быть целиком размещена в физическом ОЗУ, придётся её держать, хотя б частично, именно в файле подкачки, а он тоже резиновый не до бесконечности). Соответственно, как по мне, malloc должен выделять любой объём, какой способна выделить приложению ОС.
Ну а выделение лишних трёх байтов даже на машинах с адресным пространством в 64 Кбайта
Проблема ещё в том, что вот вы пересылаете строки от машины с 16 бит (клиент на Win3.11) на машину с 32 битовой адресацией (сервер). Ну и что брать в качестве длины строки? Придётся делать "сетевую длину строки", писать аналоги ntoh* функций. А если вы не угадаете в момент экспоненциального развития цифровой техники с размером, то либо вам будут тыкать избыточностью, либо наоборот, рассказывать, что "эти идиоты решили, что строк на 64к хватит всем, а туда даже типичная повесть не помещается".
А это очень вероятное развитие событий, если учесть, когда был разработан tcp и старые сетевые протоколы.
Конечно, кто-то гениальный мог бы предусмотреть что-то вроде аналога кодирования UTF-8 для длины строки (если выставлен старший бит, то читать ещё байт). Но это сильно усложняет обработку в условиях, когда каждый программист пишет свои обработчики для строк. И вряд ли в 1970х кто-то написал бы правильный API для таких строк.
Протокол обмена между клиентом и сервером -- это отдельная песня, которая должна быть хорошо документирована, реализовать же его особых проблем не составит. Если протокол сам по себе налагает ограничения на длину строки -- что ж, придётся передавать её частями, при этом ПО должно уметь делить, а потом соединять строку -- это усложняет реализацию, но не сказать чтоб слишком сильно, и уж точно критической проблемой не является.
В OS/360, кстати (а это вторая половина 1960-х), поддерживались записи данных и фиксированной, и переменной длины (с длиной, задаваемой двумя байтами), причём они могли образовывать отдельные физические блоки или же паковаться по несколько записей в блок (и даже переходить с одной дорожки диска на другую, но только в пределах одного цилиндра, т.е. пока не нужно механически перемещать блок головок). ОС умела всё сама упаковывать-распаковывать за программиста, поэтому он мог работать либо на уровне логических записей, либо физических блоков -- последнее потенциально эффективнее, но ощутимо геморройнее. Сама длина в 64 Кбайта, конечно, сейчас представляется недостаточной, но API в виде соответствующих функций ОС благополучно разработали и реализовали, и он работает (для совместимости с древним софтом) до сих пор в современной z/OS. В общем, в 1970-х написать "правильный API" вполне могли -- собственно, нередко и писали, хотя временами и ошибались, конечно.
Плохо в null-terminated strings даже не лишние байты и плохие алгоритмы. А то, что одно из 256 значений байта «заныкали». И дальше вот эти все ascii, http, json, регекспы, бесконечный парсинг и сериализация. Только потому что в си последовательность байт где ноль нельзя - отличается от последовательности байт, где ноль - можно.
Ну а выделение лишних трёх байтов даже на машинах с адресным пространством в 64 Кбайта
То, что надо "выделить лишние три байта" - это послезнание. Если у вас 8 битная машина, то совершенно непонятно, почему надо остановиться не на 8 байтах, не на 16, и не на 2х. Завершающий '\0' полезен тем, что действительно масштабируется, в отличие от тех же Паскалевских строк в 1 байт.
Это вы сейчас, через 20 лет после перехода на 64 бита осознаёте, что "4Гб хватит всем" - это не такая уж и шутка, а 64 Гб точно нужны единицам.
Простите... А где противоречие? strlen+memcpy = O(n); комбинированный цикл = O(n)...
При том, что умозрительная оценка сложности заканчивается на O-большом. Дальше начинаются эксперименты, результат которых валиден прямо тогда, когда ты их снял... :)
Оценка константы внутри умозрительная -- это гадание на кофейной гуще.
Просто фраза "потому что CPU не заботят здравый смысл и «большое O»" несколько далека от истины. Большое О очень даже заботит, и квадратичный алгоритм будет квадратичным, и с ростом входных данных превратится в нечто очень медленное -- см.упомянуют статью про GTA.
А "здравый смысл" должен говорить -- "если важно -- надо не только прикинуть, но и замерить, так как любое предположение следует попытаться опровергнуть, прежде чем считать его истинным". Вместо этого люди склонны делать эксперименты, поддерживающие их точку зрения...
Ну сравниваем два алгоритма с одинаковым O, различаются константой при n. И значение этой константы оказывается контринтуитивным.
Как только мы вспоминаем про то, что memcpy оптимизируется руками, мы понимаем, что можем облажаться в оценках раза в 4 как с куста.
Да!
Но странно, что BSD-шный stricpy не оптимизирован по полной.
Ну это же под машину оптимизируется. А там вроде кроссплатформенность. На RISC-V эти самые SIMD (кстати, не упомянуто, чьи именно эти SIMD - ARM/x86?) не помогут, там свои, которые не факт, что вообще есть.
Так либа с stricpy берётся ведь для конкретной платформы, и удивительно видеть для такой базовой функции отсутствие оптимизации под платформу.
Если б это зависело от меня, я бы предлагал две реализации: чисто Си/Си++, полностью соответствующую стандартам языка и переносимую между любыми более-менее разумными платформами, ну а для определённых платформ -- тщательно оптимизированную ассемблерную под конкретную платформу, а то и под конкретное семейство процессоров (или вообще зашитую на уровне компилятора: скажем, мэйнфреймы z/Architecture имеют команды для шифрования данных по всяким там AES, команды для преобразования между разными кодировками Юникода и прочая, про "тупые" пересылки строк уж и не говорю -- очевидно, что для эффективности соответствующие функции конкретно на этой платформе нужно реализовать с помощью таких команд, а не компилировать универсальный сишный исходник, который, конечно, работать будет, но наверняка сильно медленнее).
Так автор же допустил ошибку в опциях gcc. Читал об этом на reddit. Автор конечно отключил автозамену циклов на memcpy и strlen, использующих SIMD, с помощью -fno-builtin, но не отключал автовекторизацию (-fno-tree-vectorize). Поэтому его дальнейшие рассуждения после bespoke_strlcpy следуют воспринимать весьма скептически.
а зачем её отключать?
а зачем её отключать?
Так в этом по сути вся идея статьи.
Берем код который проходит одну и ту же строку два раза, показываем что он быстрее кода,
который делает один проход.
Далее сообщаем крамольную мысль, что это не потому что использовался SIMD,
который может быть и в 10 раз быстрее чем обычный код, поэтому 0.1 * N + 0.1 N всяко быстрее N,
а потому что процессор умеет быстро работать с несколькими одновременными чтениями и записями в память, если поймет что это независимые чтения и записи.
И сравнение скорости как бы это подтверждают. Но на самом деле это сравнение скорости абсолютно неверно, так как версия без SIMD на самом деле использует SIMD.
И поэтому вся статья собственно сомнительна, так как главный "поворот сюжета" в ней ложен.
Помня об этих двух пунктах, сегодня я просто использую sized string (что-то в стиле
std::string_viewязыка C++) и преобразую их в nul-string только тогда, когда этого требует внешний API.
Тоже прельщает, но очень неохота отказываться практически полностью от стандартной библиотеки, либо конвертировать туда-сюда. Можно, конечно, реализовать комбинированный подход: и записывать длину, и ставить \0 в конце, но это будет работать не слишком хорошо для бинарных строк, где нули могут быть в середине, и этим создаст больше путаницы. Так что пока просто нарулил себе библиотеку более безопасных с т.з. использования функций для работы с nul-строками, и на этом успокоился.
В своей библиотеке работы со строками я использую строки в динамической памяти, стараюсь избавиться от деструктивных функций и прочей математики указателей. При этом немного раздражает необходимость проработки каждого случая выделения памяти. Можно было, конечно, использовать сугубо статичные буферы, но это лишний расход памяти и ограниченность миллионом констант размеров буферов. И всё равно остаётся необходимость отслеживания overflow (truncate) буферов.
Я пробовал в своей библиотеке использовать выходной аргумент error, в котором ошибка "проваливается", и можно не проводить проверку после каждой операции
Пример
int str_to_int(const char* str, int default_value, string_error_t* error) {
char endptr;
errno = 0;
long result = strtol(str, &endptr, 10);
if (endptr == str || *endptr != '\0' || errno || result > INT_MAX || result < INT_MIN) {
if (error) {
*error |= STRING_ERROR_UNSPECIFIED;
}
return default_value;
}
return (int)result;
}Плюсы у такого подхода есть, но на подкорке постоянно сидит "если я забуду заинициализировать error, то цепочка действий над строками может разваливаться как попало. longjmp -- тоже вариант, но мне было бы ещё ленивее его менеджить.
...и тут мне вспомнился Delphi и его "длинные" строки (те, у которых хранилась собственно длина строки, счётчик ссылок на строку, а заодно и завершающий нуль, чтоб не создавать копию строки, если понадобится PChar). Впрочем, заодно вспомнилось, что после появления [censored] юникода для каких-то операций сложнее "скопировать всю строку целиком" оную строку один чорт нужно последовательно разгребать и длина строки в машинных словах почти с гарантией не соответствует длине строки в символах. Убил бы...
Стандартная библиотека, как и строки с завершающим нулём - не "умолчание", а просто набор заготовок, полезных в некоторых типовых случаях. Си сделан так что на нём просто пишешь то что нужно так как нужно. В отличие от кучи новомодных языков где шагу нельзя отступить от авторского (вечно заточенного на какие-то синтетические примеры) видения с кучей неуниверсальных шаблонов и связывающих руки ограничений.
Впервые сегодня услышал про какую-то strlcpy. Есть классические strncpy и прочие strn*, использующиеся в типовом сценарии, когда длина строки ограничена либо нулём либо размером буфера (например, по сети или ком-порту прилетает/улетает структура в которой есть char buf[N] содержащий текст до N символов). Нахрена нужна какая-то strlcpy, я так и не понял.
strlcpy, или как CPU противоречат здравому смыслу