Один из моих старых постов о strlcpy недавно вызвал обсуждения на различных форумах. Вероятно, с этим как-то связан выпуск новой версии POSIX. Многие авторы приводили один контраргумент, который я слышал и раньше:
В общем случае, когда исходная строка умещается в конечный буфер,
strlcpyбудет обходить строку только один раз, аstrlen + memcpyбудут обходить её дважды.
Под этим аргументом скрывается допущение о том, что однократный обход строки выполняется быстрее. И, честно говоря, это вполне разумное допущение. Но справедливо ли оно? Об этом мы и поговорим в статье.
CPU и здравый смысл
У компьютеров нет здравого смысла. Компьютеры удивляют.
- Энтони Хоар
Приведённый ниже код взят из openbsd, где и появилась strlcpy (код немного сокращён).
size_t strlcpy(char *dst, const char *src, size_t dsize)
{
const char *osrc = src;
size_t nleft = dsize;
if (nleft != 0) while (--nleft != 0) { /* Копируе as many bytes as will fit. */
if ((*dst++ = *src++) == '\0')
break;
}
if (nleft == 0) { /* Not enough room in dst, add NUL and traverse rest of src. */
if (dsize != 0) *dst = '\0'; /* NUL-terminate dst */
while (*src++) ;
}
return(src - osrc - 1); /* count does not include NUL */
}Сначала в нём выполняется максимально возможное копирование из src в dst, и если данные приходится урезать из-за недостаточного размера dst, то выполняется обход оставшейся части src, чтобы получить значение strlen(src) для его возврата. То есть если исходная строка умещается, то обход будет выполняться только один раз.
Если же взглянуть на реализацию strlcpy из glibc, то можно сразу заметить. что первая строка выглядит так:
size_t src_length = strlen (src);... а далее следует остальной код, в котором для копирования используется memcpy. Это уже разрушает иллюзию о том, что strlcpy выполняет обход строки единожды, такого требования нет, и как вы видите на практике, одна из значимых libc всегда обходит строку дважды, по одному разу в strlen и в memcpy.
Но прежде чем вы откроете баг-репорт glibc из-за её неэффективности, взгляните на бенчмарк многократного копирования 512-байтовой строки в цикле:
512 byte
openbsd: 242us
glibc: 12usВозможно, строка настолько мала, что этот двойной обход не так важен? Тогда как насчёт строки на 1 МиБ?
1MiB
openbsd: 501646us
glibc: 31793usЗдесь ситуация для версии openbsd становится только хуже, а не лучше. Откровенно говоря, это огромное ускорение возникает благодаря тому, что glibc передаёт всю работу strlen и memcpy, которые в glibc SIMD-оптимизированы. Тем не менее, мы уже видим, что делать что-то дважды, но быстро — это быстрее, чем делать один раз, но медленно.
Сравниваем сравнимое
Чтобы выполнить правильное сравнение, я написал следующую реализацию strlcpy, которая очень близка к реализации glibc, если не считать того, что вызовы strlen и memcpy записаны в циклы for.
size_t bespoke_strlcpy(char *dst, const char *src, size_t size)
{
size_t len = 0;
for (; src[len] != '\0'; ++len) {} // strlen() loop
if (size > 0) {
size_t to_copy = len < size ? len : size - 1;
for (size_t i = 0; i < to_copy; ++i) // memcpy() loop
dst[i] = src[i];
dst[to_copy] = '\0';
}
return len;
}Важно отметить. что для настоящего сравнения нужно добавить при компиляции -fno-builtin. В противном случае gcc поймёт, что «цикл strlen» можно оптимизировать до вызова strlen, и сгенерирует его. -fno-builtin позволяет избежать этого и делает сравнение честным.
Как же проявит себя эта версия, выполняющая обход src дважды, по сравнению с вариантом openbsd, обходящим src только один раз?
512 byte
openbsd: 237us
bespoke: 139usПочти в два раза быстрее. А как насчёт строк подлиннее?
1MiB
openbsd: 488469us
bespoke: 277183usВсё равно примерно вдвое быстрее. Как же так получилось?
Зависимости
Постоянно подчёркивается важность промахов кэша (и с полным на то основанием), но о зависимостях говорят не так часто. У CPU есть несколько ядер, и у каждого ядра есть несколько портов (или логических блоков), способных исполнять команды. Это означает. что если у нас есть подобные команды (на псевдоассемблере, где заглавные буквы обозначают регистр):
A <- add B, C
X <- add Y, Z
E <- add A, Xто вычисления A и X не зависят друг от друга, а значит, могут выполняться параллельно. Однако вычисление E требует результата A и X, а потому не может быть распараллелено. Такой процесс, позволяющий исполнять независимые команды одновременно, называется параллелизмом уровня команд (instruction-level-parallelism, ILP). И его криптонитом становятся зависимости.
Если мы попытаемся профилировать нашу самодельную версию strlcpy, то заметим, что почти 100% времени CPU тратится на «цикл strlen», в то время как цикл copy практически свободен. И в самом деле, если заменить «вызов strlen» настоящим вызовом strlen (напоминание: в glibc она SIMD-оптимизирована), то самодельная версия достаточно неплохо начинает конкурировать с версией glibc, хотя мы не используем оптимизированную memcpy. Чтобы понять, почему это происходит, давайте рассмотрим «цикл strlen», написанный в многословном стиле:
len = 0;
while (true) {
if (src[len] == '\0')
break; // <- это влияет на следующую итерацию
else
++len;
}В показанном выше цикле то, будет ли выполняться следующая итерация цикла, зависит от результата предыдущей итерации (имело ли src[len] значение nul или нет). Мы расплачиваемся за это в нашем цикле strlen. Но наш цикл memcpy не имеет таких привносимых циклом зависимостей, текущая итерация происходит вне зависимости от того, что происходило в предыдущей.
for (size_t i = 0; i < to_copy; ++i) // memcpy() loop
dst[i] = src[i]; // <- НЕ зависит от предыдущей итерацииТак как в версии openbsd длина и цикл копирования объединены, решение о копировании следующего байта принимается в зависимости от значения байта предыдущей итерации.
while (--nleft != 0) { // цикл копирования openbsd
if ((*dst++ = *src++) == '\0') // <- выбранное здесь ветвление влияет на следующую итерацию
break;
}По сути, затраты на эту зависимость теперь накладываются не только на вычисление длины, но и на операцию копирования. Хуже того, зависимости не только сложны для CPU, они сложны и для компилятора в оптимизации/автовекторизации, что приводит к снижению качества генерируемого кода, создавая кумулятивный эффект.
Дополнение: не избавляйтесь от длины
Секрет создания быстрых программ заключается в том, чтобы они практически ничего не делали.
- Майк Хэртел, why GNU grep is fast
Два года назад, когда я писал статью о strlcpy, я всё ещё был уверен, что строки с завершающим нулём в конце — это «нормально», и что проблему вызывает низкое качество стандартной библиотеки. Но я заметил, что даже при наличии более качественных процедур обработки таких строк при работе с ними на написание кода тратится несоразмерно большой объём мыслительных усилий и возникает слишком много багов. С тех пор я сделал два важных вывода:
Длина строки — это бесценная информация.
Без знания длины строка становится больше похожей на связанный список, заставляя нас использовать паттерн последовательного доступа, а не на массив с возможностью произвольного доступа. Многие популярные функции работы со строками можно удобнее выразить (а значит, и совершить меньше ошибок), когда длину можно узнать малозатратным образом. С другой стороны, строки с завершающим нулём в конце мотивируют постоянно отказываться от этой ценной информации, что приводит к необходимости беспричинно вычислять её снова, и снова, и снова (при этом всегда вспоминается инцидент с экраном загрузки GTA [перевод на Хабре]).
Возможность иметь подстроки без копирования — это огромное преимущество.
Это позволяет избавиться от множества беспричинных копий (то есть повышает эффективность), а также от распределения памяти (то есть избавляет от ненужного управления памятью). И в результате большая доля логики и кода, необходимых для обработки строк с завершающим нулём в конце, просто исчезает.
Помня об этих двух пунктах, сегодня я просто использую sized string (что-то в стиле std::string_view языка C++) и преобразую их в nul-string только тогда, когда этого требует внешний API. Эта тема заслуживает отдельной статьи, поэтому здесь я упоминаю её только по касательной.
Но здорово то, что вне группы пользователей C, сильно подверженной логическому искажению «умолчания» (если что-то используется по умолчанию, то использовать это правильно и нужно), подавляющее число разработчиков более-менее осознало, что строки с завершающим нулём были ошибкой. Это очевидно, если взглянуть на большинство других языков программирования, в том числе и многие новые, предназначенные для системного программирования: в них nul-string не используются по умолчанию (если вообще используются). Даже языки, наследующие от C, отходят от применения nul-string — вспомним, например, string_view из C++.
Заключение
При обсуждении производительности важно чётко определиться, говорим ли мы о ней в научном смысле, или в практическом, потому что CPU не заботят здравый смысл и «большое O». Современные CPU невероятно сложны и полны сюрпризов. Поэтому скорость алгоритма зависит не только от высокоуровневых алгоритмических факторов: необходимо также принимать во внимание и низкоуровневые факторы, например, промахи кэша, ILP, ошибочное прогнозирование ветвления и так далее. Многие вещи, которые с точки зрения здравого смысла могут казаться быстрыми, на практике оказываются медленнее, и наоборот.
Комментарии (54)
datacompboy
24.08.2024 10:29Простите... А где противоречие? strlen+memcpy = O(n); комбинированный цикл = O(n)...
UranusExplorer
24.08.2024 10:29+4А причем здесь вообще О-большое? O-большое говорит о том, насколько меняется время выполнения при увеличении n, но ничего не говорит о разнице в производительности реализаций при одинаковом n. А разница там может быть очень существенная, и именно этот вопрос автор в статье и исследовал.
datacompboy
24.08.2024 10:29+1При том, что умозрительная оценка сложности заканчивается на O-большом. Дальше начинаются эксперименты, результат которых валиден прямо тогда, когда ты их снял... :)
Оценка константы внутри умозрительная -- это гадание на кофейной гуще.
Просто фраза "потому что CPU не заботят здравый смысл и «большое O»" несколько далека от истины. Большое О очень даже заботит, и квадратичный алгоритм будет квадратичным, и с ростом входных данных превратится в нечто очень медленное -- см.упомянуют статью про GTA.
А "здравый смысл" должен говорить -- "если важно -- надо не только прикинуть, но и замерить, так как любое предположение следует попытаться опровергнуть, прежде чем считать его истинным". Вместо этого люди склонны делать эксперименты, поддерживающие их точку зрения...
aamonster
24.08.2024 10:29+2Ну сравниваем два алгоритма с одинаковым O, различаются константой при n. И значение этой константы оказывается контринтуитивным.
vkni
24.08.2024 10:29Как только мы вспоминаем про то, что memcpy оптимизируется руками, мы понимаем, что можем облажаться в оценках раза в 4 как с куста.
aamonster
24.08.2024 10:29+1Да!
Но странно, что BSD-шный stricpy не оптимизирован по полной.
vkni
24.08.2024 10:29Ну это же под машину оптимизируется. А там вроде кроссплатформенность. На RISC-V эти самые SIMD (кстати, не упомянуто, чьи именно эти SIMD - ARM/x86?) не помогут, там свои, которые не факт, что вообще есть.
aamonster
24.08.2024 10:29Так либа с stricpy берётся ведь для конкретной платформы, и удивительно видеть для такой базовой функции отсутствие оптимизации под платформу.
SIISII
24.08.2024 10:29Если б это зависело от меня, я бы предлагал две реализации: чисто Си/Си++, полностью соответствующую стандартам языка и переносимую между любыми более-менее разумными платформами, ну а для определённых платформ -- тщательно оптимизированную ассемблерную под конкретную платформу, а то и под конкретное семейство процессоров (или вообще зашитую на уровне компилятора: скажем, мэйнфреймы z/Architecture имеют команды для шифрования данных по всяким там AES, команды для преобразования между разными кодировками Юникода и прочая, про "тупые" пересылки строк уж и не говорю -- очевидно, что для эффективности соответствующие функции конкретно на этой платформе нужно реализовать с помощью таких команд, а не компилировать универсальный сишный исходник, который, конечно, работать будет, но наверняка сильно медленнее).
apro
24.08.2024 10:29+5Так автор же допустил ошибку в опциях gcc. Читал об этом на reddit. Автор конечно отключил автозамену циклов на memcpy и strlen, использующих SIMD, с помощью
-fno-builtin, но не отключал автовекторизацию (-fno-tree-vectorize). Поэтому его дальнейшие рассуждения после bespoke_strlcpy следуют воспринимать весьма скептически.
tzlom
24.08.2024 10:29а зачем её отключать?
apro
24.08.2024 10:29а зачем её отключать?
Так в этом по сути вся идея статьи.
Берем код который проходит одну и ту же строку два раза, показываем что он быстрее кода,
который делает один проход.Далее сообщаем крамольную мысль, что это не потому что использовался SIMD,
который может быть и в 10 раз быстрее чем обычный код, поэтому 0.1 * N + 0.1 N всяко быстрее N,
а потому что процессор умеет быстро работать с несколькими одновременными чтениями и записями в память, если поймет что это независимые чтения и записи.И сравнение скорости как бы это подтверждают. Но на самом деле это сравнение скорости абсолютно неверно, так как версия без SIMD на самом деле использует SIMD.
И поэтому вся статья собственно сомнительна, так как главный "поворот сюжета" в ней ложен.
Sadler
24.08.2024 10:29+1Помня об этих двух пунктах, сегодня я просто использую 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 -- тоже вариант, но мне было бы ещё ленивее его менеджить.
aamonster
24.08.2024 10:29+3Ага, вначале строки без \0, потом string_view и иммутабельные строки, и вот ты уже пишешь на Хаскеле и используешь ropes :-)
RedEyedAnonymous
24.08.2024 10:29+1...и тут мне вспомнился Delphi и его "длинные" строки (те, у которых хранилась собственно длина строки, счётчик ссылок на строку, а заодно и завершающий нуль, чтоб не создавать копию строки, если понадобится PChar). Впрочем, заодно вспомнилось, что после появления [censored] юникода для каких-то операций сложнее "скопировать всю строку целиком" оную строку один чорт нужно последовательно разгребать и длина строки в машинных словах почти с гарантией не соответствует длине строки в символах. Убил бы...
redsh0927
24.08.2024 10:29Стандартная библиотека, как и строки с завершающим нулём - не "умолчание", а просто набор заготовок, полезных в некоторых типовых случаях. Си сделан так что на нём просто пишешь то что нужно так как нужно. В отличие от кучи новомодных языков где шагу нельзя отступить от авторского (вечно заточенного на какие-то синтетические примеры) видения с кучей неуниверсальных шаблонов и связывающих руки ограничений.
Впервые сегодня услышал про какую-то strlcpy. Есть классические strncpy и прочие strn*, использующиеся в типовом сценарии, когда длина строки ограничена либо нулём либо размером буфера (например, по сети или ком-порту прилетает/улетает структура в которой есть char buf[N] содержащий текст до N символов). Нахрена нужна какая-то strlcpy, я так и не понял.
SIISII
Ну, лично я изначально считал порочной идею не хранить длину строки в явном виде, а заканчивать строку нулевым символом. Да, длина строки будет ограничена максимальным значением счётчика, но если выделить под него 4 байта, то вряд ли найдётся разумный случай, где этой длины для строки будет мало (4 Гбайта или 4 Гсимвола в зависимости от того, как трактовать значение длины, что в данном случае вторично). Ну а выделение лишних трёх байтов даже на машинах с адресным пространством в 64 Кбайта (в т.ч. PDP-11, где, по сути, и появился Уних вместе с Це) -- отнюдь не гигантский перерасход памяти, не говоря о том, что на таких архитектурах можно было бы выделять под длину два байта, а не четыре -- всё равно строка в памяти не может быть длинней, чем этой памяти можно адресовать. (Ну а где каждый байт на счету в буквальном смысле -- пишите на ассемблере, и будет вам счастье.)
А вот с заключением автора не очень-то согласен. Противоречия возникают не между реальным поведением программ на реальных процах и "здравым смыслом", а между реальным поведением и ожиданием программиста, плохо понимающего (или вообще не понимающего), как в реальности работает железо. Когда такое понимание есть, сюрпризов будет намного меньше.
ptr128
Идеология C закладывалась на PDP-7, где в базовом варианте было всего 4К слов. Но речь даже не об этом. Популярность C приобрел потому, что подходил не только для весьма мощных для того времени PDP-11, но так же и для микропроцессоров и микроконтроллеров.
Для понимания, первый ZX Spectrum имел всего 16К RAM, из которых почти половина была занята под видеобуфер. Atari 800 имела только 8К. МК 8048 имел всего 128 байт RAM, а до сих пор встречающийся 8051 - 256 байт.
Даже сейчас на маломощных МК можно встретить эти же 128 или 256 байт оперативной памяти. Наапример, в МК Padauk.
Так что будьте снисходительны к Ричи. Тогда действительно каждый байт считали. И сейчас на некоторых МК тоже приходится это делать.
GBR-613
В те старые добрые времена (и ещё долго после них) не было ни ILP, ни оптимизирующих компиляторов. Поэтому то, что казалось логичным, было логичным действительно. А хранение длины строки отдельно от неё означало и усложнение компилятора, и уменьшение скорости его работы: на тот момент немаловажные факторы.
SIISII
Вообще-то, оптимизирующие компиляторы в 1970-е уже точно были.
Ну а усложнять компилятор для работы со строками не требуется, если с ними он работать не умеет (а сишный НЕ умеет, по большому счёту, единственная "поддержка строк" -- это формирование массива символов с завершающим нулём, что ничуть не сложней, чем формирование массива символов с предваряющей его длиной).
ptr128
Почти за 10 лет до C, в PL/I длина строки хранилась в отдельном 16-битном поле.
gudvinr
А почему не varint тогда?
Хотите короткую строку - длина 1 байт, хотите длинную - 2 байта и т.д.
Когда в строке уже н-цать тысяч байт, один байт погоды не сделает
ptr128
Variant требует места для хранения типа. Чаще используют метод более сложного кодирования, как, например, base 128 encoding в Protobuf. 64-битное беззнаковое целое тогда может занимать от 1 до 9 байт. Но следует понимать, что кодирование и декодирование такого представления требует дополнительных ресурсов CPU. Поэтому и используется оно только тогда, когда размер важнее, чем производительность. Из-за этого, например, в PostgreSQL в памяти длина строки кодируется всегда 4 байтами, тогда как в странице БД - уже от 1 до 4 байт.
Похожим образом работает row compression в MS SQL, но уже не для длин строк, а для всех чисел.
gudvinr
Не variant, а varint. Т.е. VLQ или base 128 encoding, о котором вы и сказали (:
gudvinr
Да, но:
чем короче строка, тем меньше затраты на работу со значением длины. для коротких строк (до 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 - это просто бессмысленные байты, которые компилятор сам должен преобразовать в числа. И основная проблема, на мой взгляд, именно в этом, а не в производительности работы со строками.
ptr128
А вы посмотрите на ассемблерный код декодирования base 128 encoding и сравните его с одной командой чтения выравненного в памяти uint32. При этом, с учетом размера страницы кэша CPU, обычно, 64 байта, разницу на чтение одного и четырех байт не заметите.
Что касается C, то там нет проблем в хранении и обработке строк в любом формате. Альтернатив стандартной библиотеке множество. Например, мне нравится универсальность sds
gudvinr
А зачем? (Мне) очевидно, что работа с varint будет дороже в плане ресурсов CPU чем работа с нативными integer типами.
Но какая разница насколько дорога работа с varint, если речь идёт о работе со строками, длина которых (теоретически) представлена в виде varint?
В контексте работы со строками эта операция будет проводиться один раз для того чтобы преобразовать int в varint и наоборот, чтобы определить границы строки или создать строку. Это побочная операция т.к., в подавляющем большинстве случаев работа со строками на этом не заканчивается. То, что будут сэкономлены пару тактов, большой погоды не сделает, т.к. копирование, парсинг, поиск, сортировка и пр. будут занимать намного больше времени.
SIISII
Так экономия пары байт на длине строки тоже ни на что, по большому счёту, не повлияет...
gudvinr
Это зависит от масштабов.
Когда строки в приложении большие (допустим, от 64кб), 8 байт size_t действительно теряются на фоне строки. В этом случае varint будет кодироваться 3+ байтами.
8 байт size_t для строк длиной 128 байт и меньше - это уже достаточно много. В этом случае только длина - это ~6% размера самой строки. В таком ключе работа с мелкими строками становится дорогой по памяти, если таких строк много.
В 1ГиБ может быть ~8.4млн таких строк, для которых 8 байт размера будут занимать 64МиБ. Или, другими словами, ещё ~500к мелких строк.
А от того, сможет приложение загрузить в память целиком огромный массив данных или нет, может зависеть и производительность приложения в целом, т.к. "лишиние" сотни тысяч-миллионы строк может быть нужно читать уже с диска.
ptr128
Вы не осознаете проблему. Попробуйте написать сортировку строк с префиксом длины в base 128 encoding и с префиксом фиксированной длины 4 байта. При каждом(!) сравнении строк в первом случае потребуется вычислять смещение начала строки, чего не потребуется во втором.
gudvinr
Смелое утверждение. Это вам так кажется :)
А проблемы-то это какие вызывает? Само вычисление смещения - это не сортировка
В случае с короткими строками разницы нет никакой т.к. varint до значения 128 занимает 1 байт
Смещение вычисляется простым подсчётом байта, у которого первый бит 0
В случае, если длины строк различаются, конвертировать в обычный int их для сравнения может быть даже и не нужно
Когда длины строк равны - вычисление смещения в общем море операций сравнения будет в пределах погрешности
Чтобы сортировать строки, вам их надо будет перемещать. Перемещение строк дороже, чем сравнение заголовка.
ptr128
А Вы напишите. Вероятность того, что у двух строк одинаковые первые символы - меньше 1%. А значит в 99% случаев, кроме сравнения двух символов одной машинной командой, будете вычислять смещение каждого их этих символов.
Вы так прикалываетесь? По-моему, в технической дискуссии - это бескультурно.
gudvinr
А вы образчик культуры, как я погляжу:
Раз уж вы опускаетесь до хамства и перехода на личности, то не вижу смысла дальше продолжать.
ptr128
Простите, но я не мог даже предположить, что программист не в курсе того, что при сортировке строк сортируются указатели на них, без перемещения самих строк.
SIISII
Справедливости ради -- иногда и сами строки. Скажем, если надо отсортировать строки в файле. Но разумный программист, конечно, прочитает исходный файл, отсортирует, переставляя указатели, и запишет результат -- всё с минимумом телодвижений и без пересылок собственно строк.
andreykorol
Думаю имелось в виду variant length, т.е. что-то типа: длина строки от 0 до 127 - поле длины занимает 1 байт. Если длиннее - ставим старший бит в поле длины и используем ещё один байт для поля длины строки. И так далее
ptr128
Это и есть base 128 encoding. И почему такие приемы распространены для передачи данных или их хранения на диске, но редки в оперативной памяти - я тоже указал.
Термин variant length слышу впервые. Есть variable length [quantity], есть variant type. Дайте хоть ссылку на описание этого термина.
andreykorol
Мой комментарий был не про термин - я пытался понять суть того, что сказал @gudvinr. Я как он выше уже обратил наше внимание, что он имел в виду varint - https://habr.com/ru/articles/350796
Т.е. все "представили" себе один и тот же метод, но не сошлись в терминологии :)
aamonster
Вы просто выросли в те времена, когда под длину строки выделяли целый int, а не byte :-) (Turbo Pascal и более ранние паскали на 8-битных машинках).
SIISII
Вообще-то, мне за 50, и на Турбо Паскале я много что писал, причём ещё на Роботроне-1715 и лишь позже на IBM-совместимых ПК -- и всегда не понимал, что им мешало выделить хотя б 2 байта.
aamonster
Надо, кстати, глянуть, как представляли строки в PL-M.
pda0
Только не 4 байта, а машинное слово. Тогда точно нехватки не будет.
ptr128
Машинное слово тут не при чем. У Z80 машинное слово 8 бит, а адресует он напрямую 64К (были ZX Spectrum и со 128К). PDP-11/70 имела машинное слово 16 бит и 4 МБ оперативной памяти. У 8086 (IBM PC/AT) машинное слово тоже 16 бит, но адресное пространство до 1 МБ (640К хватит всем ...). А 80286, имея машинное слово 16 бит, напрямую мог адресовать до 16 МБ памяти.
SIISII
Поправочка: напрямую PDP-11 могла адресовать только 64 Кбайта (если с разделением на код и данные, что есть у PDP-11/70, но отсутствует у многих других моделей -- то по 64 Кбайт кода и данных), 80286 -- в совокупности до 256 Кбайт в 4 сегментах. Выход за эти пределы -- только манипуляциями с регистрами MMU (на PDP-11) или с сегментными регистрами (на 80286), что является нетривиальной задачей и усложняет адресацию и не всегда возможно без вмешательства ОС на том или ином уровне.
ptr128
Это тут при чем? Я с примерами показал, что машинное слово и адресуемая память - разные вещи. На каких то CPU адресная шина уже, чем машинное слово (например, 48 бит против 64). На каких то наоборот (22 бита против 16, как на PDP-11/70). Вот и доказывайте, что Z80 с машинным словом 8 бит не мог работать со строками длинней 256 байт.
SIISII
Ну, наиболее разумным выглядит выделение под счётчик стольких разрядов, сколько имеется в виртуальном адресе. Правда, 8 байт для 64-разрядных архитектур выглядит избыточным с практической точки зрения, но на них-то каждый байт уж точно считать не приходится, а при таком подходе (ширина поля длины = ширине виртуального адреса) можно было бы формат строки стандартизировать на уровне библиотеки для любых платформ.
Sadler
Чертовски избыточным. Вы никогда бы не смогли использовать nul-строки, сравнимые со строками со счётчиком длины даже в 32 бита, strlen на размерах в гигабайты будет максимально некомфортным. malloc тоже имеет свои ограничения на длину выделяемого куска памяти, так что, если речь не идёт о перелопачивании языка, придётся быть чуть скромнее.
fshp
А потом вспоминаем java, где имея хип в пару террабайт нельзя выделить массив байт размером больше 2 гигабайт.
SIISII
Как я написал, избыточность 8-байтового поля длины можно оправдать идентичным подходом к библиотеке на любых платформах: поле длины везде имеет ширину виртуального адреса. Просто, чем меньше исключений из правил, тем проще и лучше.
strlen -- да, будет очень долгим, но он-то как раз станет ненужным, если длина хранится в явном виде. Что до malloc и прочих подобных вещей, то они завязаны не на язык, а на конкретную реализацию, которая может накладывать свои не очень-то обоснованные ограничения. В частности, нет принципиальных причин для того, почему нельзя выделить за одну операцию, скажем, 2**40 байтов -- ограничения имеются чисто технические (объём доступного файла подкачки, например: если выделяемая область не может быть целиком размещена в физическом ОЗУ, придётся её держать, хотя б частично, именно в файле подкачки, а он тоже резиновый не до бесконечности). Соответственно, как по мне, malloc должен выделять любой объём, какой способна выделить приложению ОС.
Sadler
Ваши бы слова, да разработчикам языка в уши :)
vkni
Проблема ещё в том, что вот вы пересылаете строки от машины с 16 бит (клиент на Win3.11) на машину с 32 битовой адресацией (сервер). Ну и что брать в качестве длины строки? Придётся делать "сетевую длину строки", писать аналоги
ntoh*функций. А если вы не угадаете в момент экспоненциального развития цифровой техники с размером, то либо вам будут тыкать избыточностью, либо наоборот, рассказывать, что "эти идиоты решили, что строк на 64к хватит всем, а туда даже типичная повесть не помещается".А это очень вероятное развитие событий, если учесть, когда был разработан tcp и старые сетевые протоколы.
Конечно, кто-то гениальный мог бы предусмотреть что-то вроде аналога кодирования UTF-8 для длины строки (если выставлен старший бит, то читать ещё байт). Но это сильно усложняет обработку в условиях, когда каждый программист пишет свои обработчики для строк. И вряд ли в 1970х кто-то написал бы правильный API для таких строк.
SIISII
Протокол обмена между клиентом и сервером -- это отдельная песня, которая должна быть хорошо документирована, реализовать же его особых проблем не составит. Если протокол сам по себе налагает ограничения на длину строки -- что ж, придётся передавать её частями, при этом ПО должно уметь делить, а потом соединять строку -- это усложняет реализацию, но не сказать чтоб слишком сильно, и уж точно критической проблемой не является.
В OS/360, кстати (а это вторая половина 1960-х), поддерживались записи данных и фиксированной, и переменной длины (с длиной, задаваемой двумя байтами), причём они могли образовывать отдельные физические блоки или же паковаться по несколько записей в блок (и даже переходить с одной дорожки диска на другую, но только в пределах одного цилиндра, т.е. пока не нужно механически перемещать блок головок). ОС умела всё сама упаковывать-распаковывать за программиста, поэтому он мог работать либо на уровне логических записей, либо физических блоков -- последнее потенциально эффективнее, но ощутимо геморройнее. Сама длина в 64 Кбайта, конечно, сейчас представляется недостаточной, но API в виде соответствующих функций ОС благополучно разработали и реализовали, и он работает (для совместимости с древним софтом) до сих пор в современной z/OS. В общем, в 1970-х написать "правильный API" вполне могли -- собственно, нередко и писали, хотя временами и ошибались, конечно.
jakobz
Плохо в null-terminated strings даже не лишние байты и плохие алгоритмы. А то, что одно из 256 значений байта «заныкали». И дальше вот эти все ascii, http, json, регекспы, бесконечный парсинг и сериализация. Только потому что в си последовательность байт где ноль нельзя - отличается от последовательности байт, где ноль - можно.
vkni
То, что надо "выделить лишние три байта" - это послезнание. Если у вас 8 битная машина, то совершенно непонятно, почему надо остановиться не на 8 байтах, не на 16, и не на 2х. Завершающий '\0' полезен тем, что действительно масштабируется, в отличие от тех же Паскалевских строк в 1 байт.
Это вы сейчас, через 20 лет после перехода на 64 бита осознаёте, что "4Гб хватит всем" - это не такая уж и шутка, а 64 Гб точно нужны единицам.