LINUX.ORG.RU
ФорумTalks

История появления null-терминированных строк

 , ,


0

4

Стало любопытно, как такое странное решение появилось и закрепилось. Каков исторический констекст и чем это было обусловлено? Дело было только в экономии памяти на дополнительный указатель на конец строки, или?

★★★★★

Последнее исправление: thunar (всего исправлений: 2)

в экономии памяти на дополнительный указатель на конец строки

Только в экономии на хранение информации о длине строки.

vvn_black ★★★★★
()

Во всём виноваты любители ставить точку в конце заголовка :)

quickquest ★★★★★
()

Где-то читал, что дело было в удобстве переписывания файлов с одной ленты на другую.

praseodim ★★★★★
()

Си не разрабатывался комитетом, который все обсуждал и обдумывал, поэтому нуль-терминированые строки были выбраны из личных предпочтений. Си их популяризовал.

Они не такие уж и странные, часто длинна не нужна, нужно просто пройтись по всей строке до конца, маркер конца это довольно простое решение.

Строки с маркером конца были и до С, и будут после него.

MOPKOBKA ★★★★
()
Последнее исправление: MOPKOBKA (всего исправлений: 2)

Ничего не странное. В DOS и наверно CP/M есть ещё $-терминированные строки в одном месте.

Дело было только в экономии памяти на дополнительный указатель на конец строки, или?

Не столько экономия чуть-чуть памяти, сколько большая экономия в сложности многих алгоритмов. Кроме твоего варианта есть ещё другие, итого:

1) строка, терминированная спецсимволом (null или не null, не особо важно)

2) строка, для передачи которой надо слать два указателя (твой вариант)

3) строка, для передачи которой надо слать указатель и длину

4) строка, у которой длина записана в начале выделенной ей области памяти

5) строка, у которой указатель на конец записан в начале выделенной ей области памяти

6) строка, состоящая из двух выделенный блоков памяти, один с двумя указателями либо указателем+длиной, второй собственно с данными

Все варианты кроме первого требуют так или иначе задействовать две сущности вместо одной, а они и занимают память (что не особо важно), и регистры проца (важнее), и замусоривают исходный код работы со строками (важнее).

Во вариантах 2 и 3 замусоривается не только код собственно обработки строк, но и все места, где строки вообще упоминаются.

Вариант 4 получается либо зависящим от платформы (т.е. его нельзя сдампить в файл как есть), либо ограничивающим длину строки непонятными ограничениями (если длина фиксрованной битности). Вариант 5 зависящий от платформы и, хуже того, от расположения строки в памяти (нельзя не только сдампить, но и побайтово скопировать). Оба варианта 4 и 5 не дадут скользить вдоль строки, переставляя её начало на новое место.

Вариант 6 устраивает разные проблемы с аллокатором памяти, когда ты не знаешь что там выделено статически а что динамически.

У варианта 1 конечно тоже есть недостаток: невозможность быстро узнать длину строки. Но он видимо не таокй существенный как остальное перечисленное.

Впрочем, варианты 3 и 6 в Си тоже используют. А вот твой с двумя указателями я где-то видел но очень мало. Причём 6 можно дальше развивать, но это уже не просто строка а буфер с дополнительным функционалом.

firkax ★★★★★
()
Последнее исправление: firkax (всего исправлений: 1)

Были до этого нуль терминированные списки, Кнут об этом писал. Да и нуль терминированные строки выглядят естественно, так как под ASCII 7 бит, так ещё и символов меньше 128, посему бы не выделить ноль под конец?

realbarmaley ★★
()

Как и всё остальное говно в C, это говно появилось под влиянием системы команд PDP-11 (на самом деле, ещё PDP-7). Там была фактически бесплатная проверка на 0, поэтому его и взяли флагом окончания строки.

hateyoufeel ★★★★★
()
Ответ на: комментарий от firkax

Не столько экономия чуть-чуть памяти, сколько большая экономия в сложности многих алгоритмов.

Хороший пример экономии в малом ценой увеличения сложности в крупном. На практике, поскольку для реальной работы приходится обычно выделять динамическую память, то длину строки все-равно необходимо где-то хранить и вручную следить за соответствием. Плюс выходы за пределы буфера и уязвимости из-за этого. Или придумывать другие типы строк.

praseodim ★★★★★
()
Ответ на: комментарий от praseodim

Или придумывать другие типы строк.

Сишники никогда на такое не пойдут! Будут страдать до конца!

https://lwn.net/Articles/948408/

Хотя даже до ядерщиков уже дошло, что это полное днище и так нельзя, а они те ещё тугодумы:

We need to stop pretending that direct manipulation of nul-terminated strings is a good idea

hateyoufeel ★★★★★
()
Ответ на: комментарий от hateyoufeel

И как это записывалось? В x86 примерно одинаково выходит.

puts_z:
  test rsi, rsi
  jz .end
.begin:
  lodsb
  test al, al
  jz .end
  call putchar
  jmp .begin
.end:
  ret
puts_n:
  mov rcx, [rsi]
  test rcx, rcx
  jz .end
  add rsi, 8
.begin:
  lodsb
  call putchar
  loop .begin
.end:
  ret
MOPKOBKA ★★★★
()
Ответ на: комментарий от MOPKOBKA

Как записывалось, вообще насрать:

; TOUPPER2:
; Scan a null-terminated ASCII string, converting
; all alphabetic characters to upper case.
;
; Entry stack parameters,
;      [SP+2] = Address of target string
;      [SP+0] = Return address
;
TOUPPER2:
       TSTB	  @2(SP)           ; Test char at address on stack
	   BEQ	  DONE             ; If zero, then done
	   CMPB	  @2(SP), #’z      ; Is it between a and z?
	   BGT	  LCASE            ; If not, point to next char
	   CMPB	  @2(SP), #’a
	   BLT	  LCASE
	   BICB	  #40,@2(SP)       ; If a-z, the make it A-Z
LCASE: INC	  2(SP)            ; Inc address of next char on stack
	   BR	  TOUPPER2

DONE:  RTS	  PC

Тут суть в том, что TSTB и BEQ были практически бесплатными, в отличие от, например, декремента счётчика. На говножелезе из 60х это было важно!

hateyoufeel ★★★★★
()
Ответ на: комментарий от praseodim

Нет, всё не так. Длина динамического блока это длина динамического блока, к строке она отношения не имеет. И выход за пределы тут тоже ни при чём.

firkax ★★★★★
()
Ответ на: комментарий от hateyoufeel

Сишники никогда на такое не пойдут! Будут страдать до конца!

Ну что за враньё? Прекрасно используются в Си строки с указанной длиной. Но, как и всё, эта указанная длина явно прописана в виде например { char *buffer; size_t len; }, и это хорошо. Ты можешь сделать len другого типа, или захотеть кроме len указать ещё например alloc_size и pos, и тебе не надо будет для этого заниматься хакерством и костылями, ты просто пропишешь всё это в своей структуре.

Не надо тут впаривать это передёргивание вида, что раз у компилятора есть синтаксис для null-term строк то эти строки - единственно возможные.

firkax ★★★★★
()
Последнее исправление: firkax (всего исправлений: 1)
Ответ на: комментарий от hateyoufeel

Как и всё остальное говно в C, это говно появилось под влиянием системы команд PDP-11 (на самом деле, ещё PDP-7). Там была фактически бесплатная проверка на 0, поэтому его и взяли флагом окончания строки.

Еще имеет значение, что программирование тогда было еще очень молодой отраслью и о многих вещах, их последствиях просто не думали в принципе.

Ну представь себе: начало семидесятых. Первые языки программирования вообще появились лет так 13-15 назад. Как бы вот если мы сидим тут на ЛОР, а первые языки возникли в 2009-2010-м и вообще первые компьютеры (не считая всяких Цузе и Коллосов) где-то в 2000-м.

praseodim ★★★★★
()
Ответ на: комментарий от firkax

Ну что за враньё? Прекрасно используются в Си строки с указанной длиной. Но, как и всё, эта указанная длина явно прописана в виде например{ char *buffer; size_t len; }, и это хорошо.

В стандартной библиотеке этого нет. Я про этих сишников, которые её пилят.

hateyoufeel ★★★★★
()
Ответ на: комментарий от praseodim

Еще имеет значение, что программирование тогда было еще очень молодой отраслью и о многих вещах, их последствиях просто не думали в принципе.

Ну, что многие не думали, я заметил уже. Тем не менее, в поцкале и прочих алголах строки были с длиной. Сишка – это именно продукт убогости PDP-11.

hateyoufeel ★★★★★
()
Ответ на: комментарий от firkax

Не надо тут впаривать это передёргивание вида, что раз у компилятора есть синтаксис для null-term строк то эти строки - единственно возможные.

Ну естественно запрограммировать можно что угодно. Но в 99% случаях вот это { char *buffer; size_t len; } с ручным управлением, просто лишняя сложность и источник ошибок по этой причине.

praseodim ★★★★★
()
Последнее исправление: praseodim (всего исправлений: 1)
Ответ на: комментарий от praseodim

Но в 99% случаях вот это { char *buffer; size_t len; } с ручным управлением, просто лишняя сложность и источник ошибок по этой причине.

Да нет, seq_buf в ядре вполне норм работает. Собственно, строки там потихоньку в seq_buf и превращают.

hateyoufeel ★★★★★
()
Ответ на: комментарий от hateyoufeel

Тем не менее, в поцкале и прочих алголах строки были с длиной. Сишка – это именно продукт убогости PDP-11.

Да, с длиной и само по себе это проблем не создавало. Проблемой была длительное время ограниченность строк 255 символами - на практике это было неудобно, пока не появились длинные строки.

praseodim ★★★★★
()
Ответ на: комментарий от praseodim

Проблемой была длительное время ограниченность строк 255 символами - на практике это было неудобно, пока не появились длинные строки.

ТЫ НЕ ПОВЕРИШЬ! Там было всегда больше одного типа строки!

hateyoufeel ★★★★★
()
Ответ на: комментарий от hateyoufeel

Что ты прицепился к ней? Си стандартной библиотекой не ограничивается. В ней только самые базовые вещи, которые у всех одинаковые. А строку с указанной длиной можно сделать 50 разными способами - выбирай какой нужен и делай (ну либо найди библиотеку где сделано). Ничего сложного там нет. Выбирать за тебя самый правильный они не будут, потому что самого правильного нет, нужный зависит от контекста.

firkax ★★★★★
()
Ответ на: комментарий от praseodim

Уже был ALGOL с нормальными типами, функциями, процедурами, переменными, были компьютеры Burroughs Large Systems с тегированой и дескрипторной памятью, AMP, сегментированная память, где невозможен был выход за пределы массива, и вообще вся машина проектировалась под высокоуровневые языки. Был multics написанный на PL/1, с контролем доступа, квотами, кешированной фс, динамическими библиотеками, виртуальной памятью с подкачкой, итд...

С и UNIX уже тогда выглядели отставшими, особенно если вспомнить первые версии, в С поля структур глобальные, нормальной системы типов нету, в OS файлы максимум 64 кб, многопоточность отсутствует...

MOPKOBKA ★★★★
()
Последнее исправление: MOPKOBKA (всего исправлений: 1)
Ответ на: комментарий от firkax

Что ты прицепился к ней? Си стандартной библиотекой не ограничивается.

А другими библиотеками сишники не пользуются. Ты мне тут сам расписывал, что против сторонних библиотек.

В итоге, каждый сишный проект реализует строки с нуля. Так и живём.

hateyoufeel ★★★★★
()
Ответ на: комментарий от praseodim

Ну естественно запрограммировать можно что угодно

В этом и есть суть Си. Нужно - запрограммируй. Не нравится - ищи другой язык где алгоритмы спрятаны под базовым синтаксисом. Дело не в строках.

с ручным управлением

Не «ручным» а «explicit». Опять же, не нравится - есть другие языки, а в Си неявное поведение сведено к минимуму, а по-хорошему вообще должно отсутствовать.

firkax ★★★★★
()
Ответ на: комментарий от firkax

В этом и есть суть Си. Нужно - запрограммируй.

Да-да, и конечно же все сишники пишут без ошибок, поэтому CVE считается доской почёта среди сишников. Чем больше ты породил CVE, тем круче ты сишник.

Не «ручным» а «explicit». Опять же, не нравится - есть другие языки, а в Си неявное поведение сведено к минимуму, а по-хорошему вообще должно отсутствовать.

А почему цикл без побочных эффектов удаляется компилятором?

hateyoufeel ★★★★★
()
Ответ на: комментарий от hateyoufeel

Давай не будем опять в обсуждение оптимизатора уходить. Это отдельная тема и сводится в целом к «некоторые подходы к кодингу могут нарушить алгоритм после применения оптимизатора». Это не неявное поведение как когда за знаком + скрывается аллокация памяти для конкатенированной строки и подобное.

firkax ★★★★★
()
Последнее исправление: firkax (всего исправлений: 1)
Ответ на: комментарий от hateyoufeel

Сишка – это именно продукт убогости PDP-11.

Си таким создавался специально, никаких проверок, никаких гарантий, никакой метаинфы в рантайм, потому что это продукт своего времени. Даже в 90-х оставался пласт кодеров которые утверждали что любые производительное приложение нужно писать на ассемблере(макроассемблере) и ни как иначе. Си был дефолтным языком почти для всего, но он считался непригодным для микрокомпьютеров. На Pascal смотрели как на Python сейчас, а на С++ как на Java/C#.

Aber ★★★★★
()
Последнее исправление: Aber (всего исправлений: 1)
Ответ на: комментарий от firkax

Ещё один неочевидный плюс терменирования спецсимволом в том, что такую строку можно заменить на любую той же длины или более короткую прямо в бинарнике, ничего не поломав. Это позволяет, например, локализацию при помощи маленьких патчей.

CrX ★★★★★
()
Ответ на: комментарий от Aber

Си таким создавался специально

Ну как сказать, он создавался таким, потому что нормально сделать это сложно. И еще нормальные оптимизирующие компиляторы только относительно недавно появились.

MOPKOBKA ★★★★
()
Последнее исправление: MOPKOBKA (всего исправлений: 1)

Сейчас сюда придут сишники и объяснят за «системное программирование» ™®©, которое бывает только такое как придумал Ритчи со товарищи и в 2024м году может быть тоже только так, ибо это скрижаль, а раст говно

FishHook
()
Ответ на: комментарий от Werenter

теперь пройди по всем топикам где ты корчил из себя дофига специалиста и поставь себе клоуна

FishHook
()
Ответ на: комментарий от firkax

Давай не будем опять в обсуждение оптимизатора уходить.

Почему нет? Ты тут пишешь про «очевидность», «предсказуемость» и отсутствие «неявности», но по факту сишные компиляторы насилуют код так, что сишники сами охреневают и отказываются в это верить.

Это не неявное поведение как когда за знаком + скрывается аллокация памяти для конкатенированной строки и подобное.

А если за знаком + скрывается UB, после которого компилятор выкидывает половину твоего кода и всё сегфолтится?

hateyoufeel ★★★★★
()
Ответ на: комментарий от MOPKOBKA

Си таким создавался специально

Ну как сказать, он создавался таким, потому что нормально сделать это сложно. И еще нормальные оптимизирующие компиляторы только относительно недавно появились.

Относительно недавно – это в 1980х? 40 лет уже прошло, дядя!

hateyoufeel ★★★★★
()
Последнее исправление: hateyoufeel (всего исправлений: 1)

странное решение

Почему странное? Это называется в общем случае «барьер» и очень удобно для многих алгоритмов. Особенно учитывая что адресные регистры не редко были длиннее регистров данных и произвольно работать с адресами было геморройно. А тут нужен только инкремент. Такое обычно было доступно аппаратно для специальных индексных регистров.

no-such-file ★★★★★
()
Последнее исправление: no-such-file (всего исправлений: 1)
Ответ на: комментарий от hateyoufeel

Во многих случаях и TSTB не нужно, флаг Z устанавливается при многих операциях, в том числе и пересылке MOVB.

То есть, скажем, пересылка строки реализуется двумя командами:

10$:   MOVB (R1)+, (R2)+
       BNE 10$
alegz ★★★★
()
Последнее исправление: alegz (всего исправлений: 2)
Ответ на: комментарий от alegz

флаг Z

Вот именно, за счёт этого и знаменитое if(*p=*q).
Но кто-то из дедов говорил, что это было лишь побочным эффектом, потому как Си делался ещё до PDP-11.

GAMer ★★★★★
()
Ответ на: комментарий от hateyoufeel

Тем не менее, в поцкале и прочих алголах строки были с длиной.

За алгол не скажу, но в классическом паскале эта длинна весьма ограничена, хранится в первом байте т.е. не более 254 символов. Поэтому потом стали изобретать велосипеды, как пример AnsiString.

Сишка – это именно продукт убогости PDP-11.

Простите, но если вы что-то не осилили, то это не значит что оно убогое.

anc ★★★★★
()
Ответ на: комментарий от hateyoufeel

ТЫ НЕ ПОВЕРИШЬ! Там было всегда больше одного типа строки!

Та ладно... Пруфы в студию или наглое 4.2.

anc ★★★★★
()
Ответ на: комментарий от anc

За алгол не скажу, но в классическом паскале эта длинна весьма ограничена, хранится в первом байте

В классическом паскале строки задавались фиксированным массивом, неиспользуемое место заполнялось пустотой. В алголе строк не было. В общем то и паскаль и алгол это проекты для получения вайба, а не четкие стандарты. Предполагалось что каждый сделает из этого что то свое, под задачу.

MOPKOBKA ★★★★
()
Последнее исправление: MOPKOBKA (всего исправлений: 2)
  1. Линейность обращения(при малом числе регистров ты не должен тратить время на вычисления длины, сравнения, загрузки-выгрузки регистров и пр. - ты просто выполняешь сравнение, что на уровне ассемблера ох как экономит место на инструкциях)
  2. Ранее существовала инструкции для работы со строками и по сути поиск нулевого символа можно было оптимизировать по скорости.

Соответственно при увеличении скорости, числа регистров, появлении кэшей, 0-строки стали лишь элементом унаследованным от сишки.

AKonia ★★
()
Ответ на: комментарий от MOPKOBKA

можно начинать с произвольного смещения

Для этих целей есть срезы

grem ★★★★★
()
Ответ на: комментарий от anc

Простите, но если вы что-то не осилили, то это не значит что оно убогое.

а если осилил? Где тут выдают диплом заслуженного сишника, чтобы я его получил и мог обсирать сишку в срачах без претензий к моим навыкам?

hateyoufeel ★★★★★
()
Ответ на: комментарий от MOPKOBKA

В общем то и паскаль и алгол это проекты для получения вайба, а не четкие стандарты.

Алголы были стандартом когда сишки в проекте не было ещё: Алгол 60 и 68. А вот сишка стандарт обрела только в 1990 (ANSI C, он же C89).

hateyoufeel ★★★★★
()
Последнее исправление: hateyoufeel (всего исправлений: 1)
Закрыто добавление комментариев для недавно зарегистрированных пользователей (со score < 50)