Самая дорогая однобайтовая ошибка

Original author: Poul-Henning Kamp
  • Translation
Предлагаю вашему вниманию перевод недавнего поста в электронном журнале Queue авторства Poul-Henning Kamp.

Ошиблись ли Кен, Деннис и Брайан при выборе использовать NUL-завершенные текстовые строки?

ИТ стимулирует и реализует современную западную экономику. Соответственно мы часто видим заголовки про ошеломляюще огромные суммы денег, связанные с ошибками в ИТ. Какое же решение, связанное с ИТ или КН [компьютерными науками], является наиболее дорогим?

Недавно достаточное количество экспертов разводили руками при упоминании финансовых последствий для Sony от проблем, связанных с их PlayStation Network, но такое событие незначительно в данном контексте. Когда я учился в школе, мне довелось пообщаться с инспектором из Книги рекордов Гиннеса, который объяснил, что что-то не может просто случайно стать настоящим рекордом, должна быть причинная связь, начинающаяся с человеческого намерения (например, мы загнали 26 учеников старшей школы в Volkswagen Beetle нашего учителя музыки и закрыли двери).

Sony (вероятно) не хотели выяснять, какой же беспорядок случится, если уделять безопасности мало внимания, поэтому этот и другие примеры ложной экономии не проходят отбор. Другим бы кандидатом мог быть выбор IBM Билла Гейтса, а не Гари Килдалла [Gary Kildall], в качестве поставщика операционной системы для их персонального компьютера. Ущерб от этого решения по-прежнему накапливается с головокружительной скоростью: Stuxnet [прим. пер. сетевой червь] и искажение процесса ISO стандартизации OOXML наглядно демонстрируют, как далеко и широко может распространиться ущерб. Но это не было решением, связанным с ИТ или КН. Как на данный момент известно, это было бизнес решение, основанное на отказе Килдала принимать требования IBM о неразглашении.

Более подходящим примером было бы решение изобрести собственный разделитель имени каталога/файла для MS-DOS: была выбрана обратная косая черта (\), а не прямая косая черта (/), которая использовалась в Unix или точка, которая использовала DEC в своих операционных системах. Хоть фактический ущерб сравнительно умеренный, это решение тоже не подходит как хороший пример, поскольку это не было настоящим решением, это было истинным предпочтением. В IBM выбрали использовать косую черту для флагов команд, игнорируя Unix, а точка была использована как разделитель имени файла и расширения, что сделало невозможным следовать примеру DEC.

История исследования космоса предлагает целый набор раскрученных и дорогих ошибок, но, что интересно, я не смог найти ни одного подходящего кандидата. Ошибки синтаксиса Fortran и ошибки синхронизации бортового компьютера шаттла не подходят по причине отсутствия намерения. Ведение части проекта в имперских единицах измерения, а другой части в метрических является «случайным актом управления» и никак не относится к КН или ИТ.

Наилучшим примером, который я смог найти, является использование NUL-завершенных текстовых строк в C/Unix/Posix. Стоял очень простой выбор: должен ли язык C представлять строки как кортеж адрес + длина или просто как адрес и некий магический символ (NUL), отмечающий конец строки? Именно это решение приняло динамическое трио Кен Томпсон, Деннис Ритчи и Брайан Керниган в начале 70-х, и они были вольны выбрать любой способ. Я не смог найти ни одной записи о решении, которое я признаю слабым кандидатом: у меня нет никаких доказательств, что это решение было осознанным.

Тем не менее, насколько я могу определить из моего исследования, формат адрес + длина был предпочтительным для большинства языков программирования того времени, тогда как адрес + магический маркер использовался в основном в программах, написанных на ассемблере. Поскольку язык C вырос из ассемблера, как более переносимый и высокоуровневый язык, мне сложно поверить, что Кен, Деннис и Брайан об этом даже не думали.

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

Затраты на разработку аппаратного обеспечения



Изначально Unix слабо влиял на разработку аппаратного обеспечения и набора команд [прим. пер. процессора]. Процессоры, предоставлявшие инструкции для манипуляции строками, например, Z-80 и DEC VAX, осуществляли это, используя гораздо более распространенную модель адрес + смещение. Как только Unix и C получили поддержку, NUL-завершенные строки стали целью для оптимизаций. Разработчики ЦПУ начали добавлять инструкции для работы с ними. Примером служит инструкции Logical String Assist добавленные IBM в 1992 году в процессоры, основанные на ES/9000 520.

Добавление инструкций в ЦПУ не является дешевым и происходит только тогда, когда существуют ощутимые и исчислимые денежные причины.

Затраты на производительность



IBM добавила инструкции для работы с NUL-завершенными строками потому, что ее покупатели тратили дорогие циклы ЦПУ на обработку таких строк. Однако, это нам не говорит о том, что циклов ЦПУ потребовалось бы меньше, если бы формат адрес + длина был использован.

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

Одним примером служит библиотека libc во FreeBSD, где реализация bcopy(3)/memcpy(3) перемещает как можно больше информации фрагментами по «беззнаковое целое»: обычно 32 или 64 бита, а затем «очищает любые замыкающие байты» используя побайтовое копирование, как описано в комментариях.

При использовании NUL-завершенной строки, попытка работы с ней частями, превышающими один байт, может привести к обращению к символам за символом NUL. Если NUL символ является последним байтом страницы виртуальной памяти и следующая страница не определена, это может привести к крушению процесса с ошибкой «страница не найдена» [«page not present»].

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

Если мы заранее знаем длину строки — все по-другому.

Затраты на разработку компилятора



Часто компилятор знает одну вещь о строках — их длину, особенно, когда строки константны. Это позволяет компилятору выполнять вызов к более быстрой memcpy(3) даже, если программист использовал strcpy(3) в исходном коде.

Более глубокая инспекция кода позволяет компилятору осуществлять более продвинутые оптимизации, некоторые из них очень умелые, но только в том случае, если кто-то реализовал это в компиляторе. Разработка оптимизирующих компиляторов никогда не была простой или дешевой, однако очевидно, что Apple надеется, что это изменится с использованием LLVM (Low-level Virtual Machine), где оптимизаторов навалом.

Обратной стороной глубоких оптимизаций, проводимых компилятором, являются оптимизации, которые проводят целостный обзор исходного кода и переупорядочивают его в больших объемах. Они требуют, чтобы программист тщательно следил за тем, что исходный код точно описывает то, что необходимо. Программист, работавший с компилятором для суперкомпьютеров серии Convex C3800, обозначил это как «необходимо программировать так, как будто компилятор твоя бывшая жена».

Затраты на безопасность



Даже если ваш компилятор не имеет вражеских намерений, исходный код должен писаться таким образом, чтобы он мог противостоять атакам и NUL-завершенная строка имеет мрачное досье в этом отношении. Полным бедствием, с точки зрения безопасности, является gets(3), которая «полагает, что буфер будет достаточно большим», и эта проблема «относительно под нашим контролем».

Взятие под контроль, однако, означает, что компилятор будет дополнительно жаловаться, если gets(3) где-либо вызывается. Несмотря на 15 лет внимания, переполнение и недогрузка [under-running] строковых буферов являются предпочтительным вектором атаки для злоумышленников и слишком часто это окупается.

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

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

Предотвращая Slashdot-сенсации



Мы учимся на своих ошибках и не стоит придумывать «желтые» заголовки для этой статьи. Кен, Деннис и Брайан никак не могли предвидеть все последствия своего выбора, сделанного 30 лет назад, и тогда они ничего не гарантировали. На сколько мне известно, понадобилось 15 лет, чтобы понять, что это тонкое решение является плохой идеей. Наверное, ни одно из моих решений не продержалось столь же долго.

Другими словами, Кен, Деннис и Брайан сделали все правильно.

Но это не решает проблему



Для множества людей C умер, и ${lang} является языком будущего, для постоянно меняющегося кратковременного значения ${lang}. В реальности же, все другие языки напрямую или опосредствованно сидят на вершине Posix API и NUL-завершенных строк языка C.

Когда ваша Java, Python, Ruby или Haskell программа открывает файл, среда выполнения передает имя файла как NUL-завершенную строку в open(3); или когда она преобразует queue.acm.org в IP адрес, она передает имя хоста как NUL-завершенную строку в getaddrinfo(3). До тех пор, как вы будете продолжать так делать, вы сохраните все преимущества при работе вашей программы на PDP/11, и все недостатки при запуске на чем-либо другом.

Вы можете здесь написать свое предложение об API в борьбе с воображаемым противником, предложить способ задания функций, операций и стратегии обработки ошибок, но я уверен, это будет полной растратой прекрасного вечера. Опыт показывает, что такие предложения идут в никуда, поскольку обратная совместимость с PDP/11 и конечное количество написанных программ куда важнее, чем потенциальная возможность написать бесконечное количество программ в будущем более эффективным и безопасным способом.

Таким образом, затраты на решение Кена, Денниса и Брайана будут продолжать накапливаться, как пыль почти похоронившая Древний Рим на протяжении столетий.

Ссылки


1. Computer Business Review. 1992. Partitioning and Escon enhancements for top-end ES/9000s; http://www.cbronline.com/news/ibm_announcements_71.
2. ViewVC. 2007. Contents of /head/lib/libc/string/bcopy.c; http://svnweb.freebsd.org/base/head/lib/libc/string/bcopy.c?view=markup.
3. Wikipedia. 2011. Lifeboat sketch; http://en.wikipedia.org/wiki/Lifeboat_sketch.
Share post

Similar posts

Comments 169

    +24
    тема интересная, спасибо за перевод.
    Но я бы посоветовал в дальнейшем читать предложение целиком, а затем по памяти записывать на русском. А то в этом переводе стиль не русский какой-то, что ли. Порядок слов и частей в сложных предложениях более характерен для английского, чем для русского.
      +42
      Это очень мягко сказано. Статья интересная, спасибо, но вот перевод вырвиглазный, прошу прощения. Английский текст надо адаптировать, а не просто переводить, тогда не будет появляться предложений вроде: «Sony (вероятно) не хотели выяснять, какой же беспорядок случится, если уделять безопасности мало внимания, поэтому этот и другие примеры ложной экономии не проходят отбор.».
        +9
        И, если можно заметить, Computer Science (CS) не принято переводить как Компьютерные Науки (КН).
          0
          Другим бы кандидатом мог быть выбор IBM Билла Гейтса, а не Гари Килдалла [Gary Kildall], в качестве поставщика операционной системы для их персонального компьютера. Ущерб от этого решения по-прежнему накапливается с головокружительной скоростью

          Одним из элементов этого ущерба сейчас является компьютер в каждом доме :) Зато «идеальный» unix world породил такие брёвна в глазу как NUL-strings, UTF8 и XML.
            +2
            Вам рассказать про такие чудесные вещи как IE, ActiveX, WinAPI, и т.п. или вы сами догадаетесь?
              +1
              WinAPI, кстати, очень грамотная штука :) намного грамотнее и современней, чем POSIX. Особенно когда дело касается потоков и синхронизации. Про IE и ActiveX не знаю — ни разу не пришлось ими пользоваться. Наверно потому что хорошо владею API ;)
                +3
                Интересно, что же тогда в wine/reactos так долго делают реализацию WinAPI, и до сих пор нормально не сделали, если это такая грамотная штука? Тогда как различных слабо связанных с собой клонов Юникса около десятка, плюс несчётное множество библиотек, реализующих какое-то подмножество POSIX.
                  +1
                  Интересно, что же тогда в wine/reactos так долго делают реализацию WinAPI, и до сих пор нормально не сделали, если это такая грамотная штука?

                  По-моему они упёрлись в реализацию недокументированных возможностей WinAPI для полной совместисмости, включая поддержку быдлокода. Либо в DDK закопались. Либо пока делали не смогли сделать быстрее чем MS :) а релизить то же самое, но медленное смысла нет.

                  Тогда как различных слабо связанных с собой клонов Юникса около десятка, плюс несчётное множество библиотек, реализующих какое-то подмножество POSIX.

                  Слабо связанных клонов юникса не бывает. Начиная от bash'ей с /usr/bin'ам и заканчивая устройством ядра с одним и тем же набором файловых систем. Весь зоопарк юниксов — это разновидность обвеса +-трёх различных ядер. И даже при всём при этом без тысячи #ifdef'ов со стокилобайтными ./configre тру кроссплатформенности не добьёшься.
                • UFO just landed and posted this here
                    –1
                    Если грамотность измерять количеством передаваемых функциям параметров.
                    То получится POSIX, где нет ни CreateWindow, ни BitBlt.

                    Если же грамотность измерять фундаментальной функциональностью, то получится WinAPI, где можно в один WaitForMultipleObjects засунуть логический event с сокетным.
                    • UFO just landed and posted this here
                        +1
                        Я в курсе про графический интерфейс. Поэтому и упомянул с иронией о кол-ве аргументов в CreateWindow/BitBlt, т.к. среди базовых файловых/потоковых функций такого кол-ва параметров не наблюдается.

                        И меня в первую очередь инетерсует не количество функций и аргументов, а что API в принципе может делать.

                        Серьёзнейшие минусы POSIX'а касаемо потоков:

                        1. нельзя одновременно ждать condition_variable и события на сокете (приём/отправка), приходится применять polling.

                        2. нельзя проверить, завершился ли поток или ождать это событие лишь какое-то время. pthread_join работает как Wait(INFINITE). Опять же приходится изворачиваться на condvar'ах, выставляемых в конце функции потока.

                        3. самое главное — condvar'ы провоцируют проверку условия в user mode, что вызывает кучу spurious wakeups — проснулись, проверили что еще не время бежать дальше, заснули дальше. Особенно этот overhead доставляет с broadcast'ом.

                        4. нет толковой межпроцессной синхронизации, только flock()
                        • UFO just landed and posted this here
                            –1
                            Explicit vs. implicit не в пользу POSIX. По остальным критериям они примерно одинаковы.
                  –2
                  В MS есть разные отделения. Те, кто делают интернеты с офисам и DCOM'ами — согласен, стрёмные ребята. В отличие от тех, кто делают ядро операционки, компилятор и WinAPI.
                    +1
                    А «„идеальный“ unix world», значит, состоит из одной команды, да?
                      +1
                      А я и не сравниваю весь MS со всем unix. Речь про WinAPI vs. POSIX, про UTF8 vs. UCS2 и про length+chars vs. NUL-terminated. Хотя можно и MS Office с OpenOffice/LibreOffice сравить на больших документах :) единственное где юниксы оторвались — это opensource браузеры. И опять же благодаря тому, что начали их под винду делать.
                      –1
                      офис тоже ниче так. свои задачи решает
                        0
                        Я про внутреннее устройство, когда в нём надо что-то автоматизировать — activex'овое api скачет от версии к версии. С точки зрения user UI нареканий нет :)
                      +2
                      COM, DCOM, COM+ — очень неплохие решения, кстати, учитывая требования к ним. Большего удалось достичь, только создав .NET.
                        +3
                        Решения хорошие, но слишком перемудренные. Как будто их проектировал человек, не выросший из возраста «шаблон для каждой гайки».
                      0
                      Microsoft purchased all rights to 86-DOS in July 1981, and «IBM Personal Computer DOS 1.0» was ready for the introduction of the IBM PC in October 1981.
                      IBM subjected the operating system to an extensive quality-assurance program, reportedly found well over 300 bugs, and decided to rewrite the programs.
                      This is why PC-DOS is copyrighted by both IBM and Microsoft.
                        +8
                        Бля, опять холивары! Гейтс — бог, минусуйте, черти! )
                          +7
                          art008
                          Нравится: Apple

                          палишься.
                        • UFO just landed and posted this here
                            +2
                            Переменной длиной символа в байтах. А предпочли его UCS2/UCS4 по причине всё тех же NUL-strings.
                            • UFO just landed and posted this here
                                +3
                                Стандартом UTF8 оказался, т.к. это было решение меньшей крови чтобы древний софт с PDP терминалов смог и дальше показывать английский язык без изменений и не ломать зубы о NUL chars. В мире unix'ов совместимость с ламповыми коамьютерами — священный грааль. В частности, именно поэтому мы до сих пор гоняем email в base64 дабы в 7 бит уложиться.

                                XML слишком избыточен, как минимум из-за закрывающих тегов. Это уже в сравнении с JSON видно. И не даёт возможности O(log(N)) поиска, т.к. неизвестно заранее где заканчивается ветка. XML надо парзить. В отличие от аналогичных бинарных структур.
                                  +1
                                  Любой человекочитаемый язык разметки надо парсить. Но мне лично ближе YAML, чем XML.
                                    +5
                                    Непонятно, зачем человекочитаемый язык гонять там, где читают машины.

                                    Собственно, в этом весь сетевой unix world — внутреннее устройство протоколов заточено под человека, а внешний интерфейс с пользователем заточен под железо.
                                      0
                                      Человекочитаемость XML — миф
                                      +1
                                      Про существование xsd вы видимо не в курсе. Как и про binary xml.

                                      А еще мне интересно как бы вы поправили руками бинарник.
                                        0
                                        Дык с binary xml и надо было начинать, не выпуская просто xml за рамки текстовых редакторов. (Де)компиляция это называется.

                                        > А еще мне интересно как бы вы поправили руками бинарник.
                                        А зачем его руками править? JPEG'и вроде не руками правят.
                                          +2
                                          Потому что xml`ем удобно описывать конфиги и вообще всякие данные и их схемы. Отсюда — необходимость читать глазами и править руками.

                                          И, да, отвечу в этом же комменте — xml значительно активней используется в винде и в разработке под нее. Под юниксами его почти нет, там ворох разных форматов.
                                            –3
                                            Для конфигов XML приемлем, хоть и не очень удобен. Я говорил про межпроцессное и сетевое взаимодействие, куда человек если и лезет, то только в целях отладки.

                                            xml пришёл из html. по крайней мере его неприятная текстовая сторона.
                                              0
                                              А xml изначально и не предназначался для межпроцессного и сетевого взаимодействия. Он в первую очередь язык разметки.

                                              На майкрософтовской платформе сейчас гоняется mtom, binary xml и так далее.
                                                0
                                                Да вы что? XML это совместимость и ничего более. Для разметки бизнес-данных и csv отлично подходит и работает.
                                                  0
                                                  Заставить бы тех, кто данные придумывает слать в csv или хуже того в файле с колонками фиксированной (предопределённой) длины самих искать проблемы в массивах данных больше 100к записей. :(

                                                  Самокомментированность XML данных реально помогает.
                                                  –2
                                                  Ок, кто первым предложил организовывать межпроцессное взаимодействие через XML и кто разрабатывал SOAP монстра?
                                                  • UFO just landed and posted this here
                                                      –1
                                                      Неожиданно :) хотя… вполне в духе Don Box'овского COM.
                                                  –1
                                                  Наоборот, HTML «пришёл» из XML, так как является его диалектом.
                                                    +2
                                                    XML — обобщение HTML, появившееся значительно позже. Почему HTML не стали гонять в бинарном виде — отдельная песня. Как минимум, решили бы проблему невалидных html'ок — они бы тупо не компилировались.
                                                      0
                                                      Речь, разумеется, про server-side/designer-side компиляцию, а не про отказ браузера показывать битый html.
                                                        +1
                                                        Действительно, первая спецификация XML на несколько лет позже, чем Бернерс-Ли предложил HTML.

                                                        Приношу извинения за непросвещенность =(
                                                    –4
                                                    За конфиги в XML-е надо выгонять из профессии.
                                                    «А давайте приделаем программе тормозов просто так».
                                                    • UFO just landed and posted this here
                                                        –1
                                                        XML нужен для обмена данными между разными платформами, его главное преимущество — совместимость, за которую иногда можно и заплатить тормозами и огромным размером файла. Конфиги читает только «своя» программа. Точка.
                                                        • UFO just landed and posted this here
                                                            +1
                                                            «Конфиги читает только «своя» программа.»
                                                            А еще люди, которые их пишут. А еще все системы управления конфигурациями.
                                                          0
                                                          Вы сейчас радостно опустили весь энтерпрайз и огромное количество профессиональных энтерпрайзных решений ;)
                                                            –1
                                                            Они сами себя опустили. Благодаря тормозам их примитивного по своей сути софта намного облегчается миграция на SaaS-системы. См. мой ответ RankoR-у выше.
                                                            • UFO just landed and posted this here
                                                            –1
                                                            «За конфиги в XML-е надо выгонять из профессии.»
                                                            Угу. MS, Oracle, hibernate и далее по тексту.
                                                  +1
                                                  А чем вам это мешает?
                                                    0
                                                    Невозможностью найти 1005й или средний символ (по длине в символах, а не по длине в байтах) за O(1). И потребностью вешать логику с битовыми масками для перехода к следующему символу, который может занимать от 1 до 4 байт в зависимости от значения первого байта символа.
                                                      –1
                                                      Про UTF16 и UTF32 вы тоже не в курсе?
                                                        0
                                                        В курсе, но я говорил про UTF8, а не про весь utf8. К тому же, UTF32 = UCS4 — я за них. UTF16 страдает той же разнобайтовостью, что и UTF8 (только там это суррогатными парами называется). А UCS2 — это UTF16, но без суррогатных пар, т.е. с неполной кодовой таблицей, всего 65536 позиций. Хотя если бы проектировщики unicode подошли к иероглифам с правильной стороны, считая иероглиф не символов, а словом, состоящим из чёрточек-символов, то 65536 позиций вполне бы хватило.
                                                          0
                                                          edit: а не про весь utf.
                                                        0
                                                        Операция нахождения 1005-ого символа или среднего именно для строк не характерна. Может давайте тогда по килобайту сразу закладывать на каждый символ — вдруг захочется long число туда засунуть. Или как в лиспе — держать указатель на каждый символ: там как раз от этого во внутреннем представлении стали отходить — а вы тут их р-р-раз, и перегоните.
                                                          0
                                                          Для строк не характерна, зато характерна для текстовых документов. Особенно взятие среднего или 90%-го при прокрутке. Но тут кроме nul-проблемы придётся решать еще и \n-проблему.
                                                            0
                                                            Для прокрутки строка может быть дополнительно представлена в двумерном-пространстве, что не делает одномерную строку плохим решением.
                                                    • UFO just landed and posted this here
                                                        0
                                                        Скорее в UCS2, а не в UTF32(UCS4). Проблема в том, что utf8 так же часто назвязывается как средство обработки.
                                                        • UFO just landed and posted this here
                                                            0
                                                            От ситуации зависит. Если будет нужен весь набор символов, хранение будет в utf8(.gz), обработка в utf32. Если достаточно UCS2, то и хранение, и обработка будет в нём. По поводу востребованности UCS4 и почему не хватило UCS2 я свои доводы приводил здесь: habrahabr.ru/blogs/programming/126566/?reply_to=4177062#comment_4171396
                                                            • UFO just landed and posted this here
                                                                0
                                                                Зачем в 2 раза увеличивать объем файла и ломать обратную совместимость, если этого можно не делать без какого-либо ущерба — непонятно.

                                                                Ущерб есть в необходимости обработки процессором каждого байта. Когда файловое содержимое соответствует рабочему представлению в памяти, работают DMA каналы и file mapping'и. Когда требуется битовая логика c if/else — они не работают. Согласен, что для строк не особо критично, но примыленный к скорости глаз это корёжит :)

                                                                Зачем доказывать, что в интернете кто-то неправ :)?

                                                                А забавно бывает позырить на реакцию :) особенно на контр-доводы, которые обычно взывают не к практическому удобству бывалого системного программиста, а к теоретической идейности и обобщённым сферическим понятиям, к которым человек еще и не сам пришёл, а где-то прочитал/услышал.
                                                +3
                                                А мне понравилось "… основанное на отказе Килдала не принимать требования IBM о неразглашении". Вот и думай, что это значит %)
                                                +1
                                                ЦПУ…
                                                  0
                                                  Топорно получилось :(. Спасибо всем в этой ветке! Будем совершенствоваться :).
                                                  +40
                                                  NUL-terminated string имеет ещё одну очень важную особенность: это универсальный формат, совместимый с сетью. Если бы у нас строки передавались как (int)(array), то вы представляете себе, сколько бы было пролито слёз по поводу того, СКОЛЬКО БИТ в int'е, знаковый он или беззнаковый (а есть ещё окамловский знаковый, угу), и какой у него порядок байт.

                                                  Более того, мы бы не имели возможности работать со строками неизвестной длинны: сейчас их можно парсить конечным автоматом «пока не NULL продолжаем работать», а в случае с кортежной записью, мы бы всегда должны были бы говорить размер строки ДО того, как её передавать. Даже если мы сами не знаем, какой оно там длины.

                                                  Правильно говорить о дурацкой идее делать sprintf/gets — это да. Но однозначно осуждать null-строки как ошибку — я бы не стал.
                                                    +1
                                                    Наверное можно сказать что оба решения имеют свои горы плюсов и минусов в равном степени.
                                                    Разные ситуации — разные плюсы/минусы.
                                                    Возможно наилучший вариант, было бы использовать оба варианта, а может и наихудший.

                                                    Не редко адрес + длина используется и довольно успешно в WinAPI, за что лично я делаю большой поклон Microsoft.
                                                      +6
                                                      >WinAPI

                                                      вот уже нашли образец для подражания, честное слово.
                                                        +7
                                                        Microsoft кстати очень хорошо решила проблему со строками, например в mfc строки представлены как «размер + строка + null».

                                                        Лет 10 назад Крис Касперски в журнале «Программист» написал хорошую статью по этому поводу с различными замерами паскаль, си и mfc строк. Оптимизированная конкатенация с заранее известным размером вполне очевидно может быть выполнена до двух раз быстрее.
                                                          –1
                                                          Это pascal-строки. Ничего нового microsoft не изобрел.
                                                          +10
                                                          Многим не нравится WinAPI, но мне почему-то кажется, что навряд ли кто-то из них смог бы спроектировать API хотя бы не хуже того, как это сделали ребята из MS.
                                                            0
                                                            API сильно количеством ПО, а не архитектурными изысками.
                                                        +4
                                                        В каком сетевом протоколе, интересно, используются нулевые строки? HTTP/FTP/SMTP/IMAP — например используют 0x0a/0x0d. DNS пакеты вроде содержат длину строки адреса.

                                                        Тем более, что в итоге любой уважающий себя разработчик берет или пишет свою библиотеку для работы со строками, которая хранит длину строки в ней — ну а те, кто использует допотопные char* и strdup, за который жечь надо железом — те обычно висят в топах уязвимостей с buffer overflow.

                                                        Даже в PHP из-за двойного представления строк был долгонеисправляемый баг не так давно: PHP-ные функцие работали с бинарными строками, а вот fopen() — понимала NUL как конец строки.
                                                          0
                                                          а вот fopen() — понимала NUL как конец строки.
                                                          это общая проблема для POSIX интерфейса (fopen является портом с этого API).
                                                          +7
                                                          В передаче по сетям уже столкнулись с этими проблемами и их решением стал ASN.1
                                                            +6
                                                            Вообще-то, есть такое понятие «сетевой порядок байтов», потому с порядком байтов в int'е всё понятно. Про битность и знаковость — согласен, равно как и про строки неизвестной длины.
                                                            Что касаемо «null-строки — ошибка» — есть занимательное чтиво.

                                                            От себя добавлю что разработчики Windows, похоже, не сошлись во мнениях по поводу формата строк в своей операционке. В результате на уровне ядра/native api царят строки с указанием длины (UNICODE_STRING) позволяющие писать высокопроизводительный код без алгоритма маляра Шлемиля. Однако на уровне API/CRT сплошь и рядом используются null-terminated строки, потому в прикладных программах волей-неволей куча пробежек «в поисках заветного нуля», которые явно не улучшают производительность, да и безопасность страдает.
                                                              0
                                                              а ведь вы правы! а то, было, я засомневался из-за статьи СИ предоставляла работу со строками на низком уровне, почти таком же как ассембелер, они к этому стремились и говорили прямо и открыто — следите за своими структурами не меньше, чем в асме. зато «низкоуровневая» работа со строками и переменными оставляла незауженное поле для деятельности и трюков. правда, вот такой вот ценой. но что мешало людям, которые неуверенно оперировали с типами данных написать себе обвязку, тем более есть целые библиотеки работы со строками и variable safe handling — всевозможные проверки на диапазон и переполнение.
                                                                +3
                                                                А если длина строки была бы более одного байта, то каком формате они должны идти в big endian или в little endian? А если бы ребята тридцать (кстати, почему тридцать, если статья написана в 2011, а речь идет о начале 70-х?) приняли решение об использовании длины, то длина была бы точно 1 байт и мы бы поимели какую-нибудь странную оптимизацию, типа, если последний байт строки равен 0x7F, то в предыдущих 4-х байтах идет адрес продолжения этой строки или еще что-нибудь подобное.

                                                                В общем, null-terminated строки наломали дров, конечно, но я очень сомневаюсь, что в то время можно было прийти к решению, последствия от которых были бы меньше, чем сейчас.
                                                                  +1
                                                                  4 байта и баста. Я очень сомневаюсь, что вы захотите передавать 8-гигабайтную текстовую строку как nul-terminated. Хотя бы потому что вряд ли она дойдёт за один коннект ;)

                                                                  В крайнем случае есть и универсальный формат:
                                                                  первый байт (n) — размерность длины
                                                                  0 — пустая строка
                                                                  1 — длина занимает 1 байт
                                                                  2 — длина 2 байта
                                                                  3 — длина занимает 4 байта
                                                                  4 — длина занимает 8 байт

                                                                  следующие 2^(n-1) байт — собственно длина в big-endian, а дальше указанное количество символов. Я думаю, строк длиной вплоть до 256^(2^254)-1 вам хватит надолго :)
                                                                    +3
                                                                    Согласен, но вот в семидесятых никто не принял бы вариант «4 байта и баста». Это ж сейчас 4 байта туда, 4 — сюда — это мелочи, а тогда у тебя 512 байт (!) рама и баста:)

                                                                    Но, мне кажется, что влияние этой ошибки автором в любом случае преувеличено.

                                                                    Возьмите, в качестве примера BSTR. Ее формат следующий: вначале 4 байта длины, затем сама строка, а в конце идет 2 нулевых байта. В этом случае, мы получаем выгоду «от двух миров»: мы за О(1) получаем длину строки и, в принципе, получаем обратную совместимость с С-строками (при учете, что нули не содержатся внутри строки, поскольку в BSTR это не запрещено).

                                                                    Так что, по поводу null-terminated string и самой большой ошибки во вселенной, я не согласен.
                                                                      0
                                                                      4 байта — тю на вас. Маскимум для backslash0-завершенных строк это в пределах до 1024 байт (имена файлов, путь до файла, и так далее и тому подобное). Для файлов кстати еще один символ имеет свойство коварности '/'. По сути ведь «путь» — это не строка вовсе, а кортеж имен.
                                                                        0
                                                                        По сути ведь «путь» — это не строка вовсе, а кортеж имен.
                                                                        Согласен. Даже тут мы видим проблему распространённости подхода «хранить как можно больше информации в текстовом представлении».
                                                                    +2
                                                                    Не совсем понял Ваше высказвание про сеть и байты. Сериализация структур данных — отдельная задача, не связанная с их представлением в памяти машины. Формат и протокол передачи между терминалами на данном уровне OSI четко согласуется и иногда стандартизируется в RFC.

                                                                    Кроме того, десериализация строк в формате (int)(array) реализовывать в разы проще и надежнее, чем NULL-ending, т.к. буфер нужной длины резервируем сразу.

                                                                    Про парсинг строк неизвестной длины: здесь Вы путаете концепт строки и символьного потока. Строка — это объект в памяти фиксированной и заранее известной длины, допускающий доступ к любому символу по смещению. Поток — объект неизвестной длины, допускающий в общем случае только последовательный посимвольный доступ. Конечные автоматы работают именно с символьными потоками.

                                                                    Видимо Керниган и Ричи в свое время тоже мыслили о строках исключительно как о символьных потоках.
                                                                      0
                                                                      Строка — это объект в памяти фиксированной и заранее известной длины, допускающий доступ к любому символу по смещению.
                                                                      Поэтому я не люблю utf8 :)
                                                                        0
                                                                        Сжатые данные еще хуже в этом смысле — и ничего, живут же с этим как-то.
                                                                          0
                                                                          Сжатые данные не используют в контекстах, где нужна DMA скорость и random access.
                                                                            0
                                                                            Печаль какая, а строку в utf-8 «разжать» до utf-32 и наслаждаться О(1) религия не позволяет?
                                                                            Конечно, пускай лучше делают стандарт где строки не сжаты, и невдомёк что данное сжатие сэкономило сотни нефти, в другом случае потраченные бы на хранение и передачу кучи ненужной информации.
                                                                              0
                                                                              нефть как раз на такты процессора усходит по этому сжатию/разжатию :) а про кучу ненужной информации в проводах — для начала бы избавились от 7-битовых mime/base64 и текстовых http/html.
                                                                      0
                                                                      сколько бы было пролито слёз по поводу того, СКОЛЬКО БИТ в int'е, знаковый он или беззнаковый (а есть ещё окамловский знаковый, угу), и какой у него порядок байт.

                                                                      С порядком байт вроде удалось договориться — big-endian (хоть он и менее логичен для железок, ну да бог с ним). Зато сколько бит пролито в XML никто не парится :) А против nul-terminated строк в сетевом трафике есть очень веский довод — необходимость принимать символы по одному байту, чтобы не перечитать лишнего. Либо опять буфера, буфера, буфера…

                                                                      Вообще, всё что ломает DMA каналы и затрудняет данных пачками с заранее известной длиной должно быть со временем искоренено. Это и nul-strings, и utf-8, и XML, и HTTP со своими текстовыми заголовками. Незачем внутреннему устройству компьтеров human-readability, она мешает.
                                                                        +1
                                                                        Что может быть альтернативой utf8? UNICODE16 уже не справляется со всеми символами unicode. Если мы сделаем UNICODE32, то это будет во-первых жирновато (4 байта на символ), а во-вторых что мы будем делать, когда окажется, что символов не хватает? Устраивать всемирную панику класса ipv4->ipv6?
                                                                          +1
                                                                          Учитывая что подавляющая часть WinAPI (включая GDI) работает как раз с Unicode16 и что на винде сидит поболее пользователей, чем на posix системах, у меня сильные сомнения, что эти символы over 64k так уж сильно нужны в универсальном доступе в любой строке мира — возможно их следует отнести к графике, а не к тексту. К тому же уже отписывался в другом комменте, почему вдруг 64k стало не хватить — иероглифы надо рассматривать не как буквы, а как слова, состоящие из одинаковых элементов (символов), для поддержки каких-то тайских иероглифов так и начали делать. После того как уже испанахали половину свободного пространства китайским и японским по одному иероглифу на кодовую позицию. К тому же, кто будет рисовать фонты для миллиона символов, не говоря уже о 4 миллиардах?
                                                                            +2
                                                                            А не слишком ли дороговато получится при необходимости работы с редкими символами (например, для написания курсовика по вэньяню) — менять платформу, потомучто в виндах «64k символов хватит для любых задач»?

                                                                              –1
                                                                              А её и так придётся менять, потому что Windows GDI со всеми его вордами и экселями работает с 64k символов. Плюс я думаю очень вряд ли эти символы будут набираться с клавиатуры, а не браться в виде растровых сканов из вэньяньских летописей. Так же я не думаю, что вы найдёте вменяемые шрифты с вэньянем.

                                                                              А не слишком ли дороговато получится
                                                                              Не слишком. В вэньяне нет денег, и поэтому он не нужен.
                                                                                0
                                                                                Софт с поддержкой utf-8 менять не придётся.
                                                                                То, что в винде используется 64k это критерий только ограниченности винды, а не нужд людей.
                                                                                  0
                                                                                  Софт с поддержкой utf-8 менять не придётся.
                                                                                  Ок, софт будет. А шрифты откуда возьмутся? :)

                                                                                  То, что в винде используется 64k это критерий только ограниченности винды, а не нужд людей.
                                                                                  Метрика искренности желания — готовность заплатить деньги. Эта же метрика определяет и развитие/ограниченность винды — что в ней есть, а чего в ней нет. Раз MS до сих пор не сунулась в over-64k набор символов, значит там нет рынка, т.е. людям это не надо.
                                                                                    0
                                                                                    Шрифты есть в репозитории убунты, например.
                                                                                    Наверно, кому-то нужны.
                                                                              +1
                                                                              Тайское письмо — алфавитное.
                                                                              Японское письмо — слоговое, с использованием китайских иероглифов.
                                                                              Иероглифы на запчасти раскладываются только в корейском хангуле, но алгоритм комбинирования элементов на порядок сложнее парсинга utf8.

                                                                              Зайдите на unicode.org/charts/unihanrsindex.html
                                                                              и посмотрите как комбинируются «одинаковые» элементы в иероглифах.
                                                                                +1
                                                                                Китайские иероглифы тоже бьются на части, китайские клавиатуры на этом принципе устроены (недавно была статья на хабре). По сути это можно свести к навороченному XY кернингу в шрифтах.

                                                                                Не стоит проводить аналогию между «глиф» = «знакоместо». Все проблемы уникдов с иероглифами именно от этого «европейского» подхода к буквам.
                                                                                  0
                                                                                  Сложность такого навороченного кернинга значительно превышает сложность кодирования символов.
                                                                                    0
                                                                                    Алгоритм кернинга, как и файловая система, пишется один раз и навека.
                                                                                      0
                                                                                      А мужики-то не знают.
                                                                                        0
                                                                                        Тогда вам должно быть понятно, что каким бы сложным не вышел алгоритм кернинга — это приемлемая разовая плата за возможность хранить любой текст через 2-байтовые символы.
                                                                                    0
                                                                                    И зачем, по-вашему, китайцы и корейцы изобретали кучу «посимвольных» (в том числе переменнобайтовых) кодировок иероглифов задолго до юникода?
                                                                                    Может, они чего-то не знают о конструировании иероглифов, чего знаете вы?
                                                                                      0
                                                                                      Чтобы сохранить совместимость с европейскими растеризаторами шрифтов.
                                                                                        0
                                                                                        Не угадали.
                                                                                        Кодировки придумывались для телеграфа.
                                                                                        А на момент создания компьютерных кодировок (середина 80ых) европейские растеризаторы никак не умели рисовать иероглифы.
                                                                                          0
                                                                                          А на момент создания компьютерных кодировок (середина 80ых) европейские растеризаторы никак не умели рисовать иероглифы.

                                                                                          Зашитые в видеопамять битмапы символов — тоже своеобразный «растеризатор». Чтобы натянуть на эту битмаповую модель иероглифы, пришлось делать по иероглифу на знакоместо, по-моему был даже период, когда их из кусочков собирали по 2-4 экранных символа в текстовом режиме на один иероглиф. Те же технические особенности продиктовали и кодировку в телеграфе.

                                                                                          А когда на смену битмапам и ромашковым печатным машинкам пришли векторные растеризаторы, никто этот подход рефакторить не стал — кодировки так и остались еще с довекторных времён.
                                                                                +1
                                                                                Если под UNICODE16 подразумевалась UTF16, то в ней может быть представлен любой Unicode character, но она, как и UTF8, является variable-width. Кроме того, UTF16 может быть BE, а может быть LE, что тоже не является преимуществом перед UTF8, которая таких проблем лишена.

                                                                                Возможно имелась в виду UCS2, которую часто неверно отождествляют с UTF16, она действительно не покрывает весь Unicode.
                                                                            +11
                                                                            Энтони Хоар считает миллиардно-долларовой ошибкой свое изобретение, Null reference:

                                                                            I call it my billion-dollar mistake. It was the invention of the null reference in 1965. At that time, I was designing the first comprehensive type system for references in an object oriented language (ALGOL W). My goal was to ensure that all use of references should be absolutely safe, with checking performed automatically by the compiler. But I couldn't resist the temptation to put in a null reference, simply because it was so easy to implement. This has led to innumerable errors, vulnerabilities, and system crashes, which have probably caused a billion dollars of pain and damage in the last forty years.

                                                                            Я с ним согласен =)
                                                                              +4
                                                                              Конечно использование завершающихся NULL строк, не очень хорошая затея. Но дело в том что это единственный формат, который позволяет не заморачиваться на ее длину. И при достаточно малой длине это хорошее решение. В случае же добавления длины строки, надо думать какого размера будет этот самый счетчик. Если один байт, то максимальная длина строки 255 байтов, если два байта то ладно уже лучше 64 килобайта, но и накладные расходы уже на использование строк больше. Приемлемым было бы решение в 4 байта, но это дает уже существенные накладные расходы.

                                                                              Кстати почему в статье нет упоминания про BigEndian и LittleEndian. Эта штука жизни мешает довольно сильно.
                                                                                +7
                                                                                Давно придумали VLQ и его вариации. Первый бит обозначает наличие следующего байта, остальные биты — знаковые.
                                                                                Получается для строк длиной до 127 (27) байт нужен 1 байт, для строк длиной до 16383 (214) — 2 байта и т.д.

                                                                                Есть еще другой вариант — BER (и ASN.1), который используется, например, в SNMP: если установлен первый бит, то следующие 7 бит означают количество следующих байт содержащих значение, если же первый бит не установлен, то в следующих 7 битах само значение.

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

                                                                                Кстати, в Delphi (камнями не кидаться), например, у типа String есть размер, но для совместимости в конце есть и null. PChar(string) вернет вполне валидную null-terminated строку (а PInteger(PChar(string)-4) будет указателем на её длину), но при этом программа на Delphi не будет испытывать неудобств в работе с нулями в самой строке.

                                                                                А вот вам исходник strlen() из FreeBSD:
                                                                                size_t strlen(const char *str) {
                                                                                    const char *s;
                                                                                    for (s = str; *s; ++s);
                                                                                    return(s - str);
                                                                                }
                                                                                

                                                                                А по ссылке из glibc.

                                                                                Не очень то дешевая операция для такой простой, казалось бы, задачи.
                                                                                Всё ещё хотите работать со строками неизвестной длины?
                                                                                  0
                                                                                  Давно придумали VLQ и его вариации. Первый бит обозначает наличие следующего байта, остальные биты — знаковые.
                                                                                  Получается для строк длиной до 127 (27) байт нужен 1 байт, для строк длиной до 16383 (214) — 2 байта и т.д.

                                                                                  Есть еще другой вариант — BER (и ASN.1), который используется, например, в SNMP: если установлен первый бит, то следующие 7 бит означают количество следующих байт содержащих значение, если же первый бит не установлен, то в следующих 7 битах само значение.

                                                                                  У меня вопрос! А что делать с unicode при этом раскладе, а так же что делать с однобайтовыми кодировками использующими все биты?

                                                                                  Кстати, в Delphi (камнями не кидаться), например, у типа String есть размер, но для совместимости в конце есть и null.

                                                                                  Это кстати пошло из pascal.

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

                                                                                    Кстати говоря, по поводу unicode: почитайте, как устроен utf-8 и вы заметите удивительное сходство с идеей vlq :)
                                                                                      0
                                                                                      Да там вопрос просто касается больше начала строки. Если оно сдвинется и внутри будет однобитная национальная кодировка можно скажем так получить тот же фофект как и в случае с нетерминированной NULL строкой.
                                                                                      0
                                                                                      А чем ваш юникод отличается от другого набора байтов?
                                                                                      Ну да, длина строки и количество занимаемых ей байтов не равны, но даже std::string в своей реализации имеет отдельные length и capacity.
                                                                                      Для «общения» с недоверенным источником очевидно лучше передавать байтовый размер, так как в конце может оказаться 0x80, а вы будете пытаться считать еще байт, что по сути примерно то же самое что и отсутствующий ноль при ожидании null-terminated строки.
                                                                                        0
                                                                                        К примеру в utf-16 еще есть указатель bigendian и littleendian.
                                                                                        –1
                                                                                        Вот, кстати, не совсем. Нуль-терминированная строка с известным размером будет побыстрее, чем не-нуль-терминированная. Потому как при операциях по всей длинне не обязательно постоянно делать сравнение указателя с концом, можно просто брать флаг после операции с самими данными.
                                                                                        0
                                                                                        Извиняюсь, в первом предложении не «знаковые», а «значимые».
                                                                                        –2
                                                                                        А невозможность использования одного из 256-и значений внутри самой строки не дает существенных накладных расходов?
                                                                                          –1
                                                                                          почему внутри строки? это только в первых байтах кодирующих длину первый бит означает что возьмите еще один байт. А как длина получена — дальше в строке все можно юзать :)
                                                                                            –1
                                                                                            > почему внутри строки?
                                                                                            Потому что нуль нельзя использовать внутри строки. Про первый бит в прокомментированном мной сообщении ничего нет.
                                                                                            0
                                                                                            Можно, но надо не 1 байт, а два (PDP имела 16 разрядную шину адреса), об этом лишнем байте автор и говорит.
                                                                                              0
                                                                                              Вы о чем?
                                                                                                0
                                                                                                О том, что где бы не записывалась длинна, хоть в самой строке, хоть где-то рядом, хоть в специальной области, на тот момент она бы потребовала двух байт, а не одного, как нулевой байт.
                                                                                                Два байта необходимо, поскольку процессор имел 16 разрядную шину адреса, не уверен по поводу использования сегментации, но все равно это означает, что можно адресовать 64кб, соответственно максимальна длина строки — 65536 — 2 байта на длинну.

                                                                                                По тем временам это и был накладной расход в дополнительный байт на каждую строку, о котором Вы говорите.
                                                                                                  0
                                                                                                  Выше уже все написали про хранение длины строки. Как это связано с 16-и разрядными процессорами я не въезжаю.

                                                                                                  Нулевой байт дает намного больше накладных расходов. При хранении, при операциях, везде.
                                                                                          0
                                                                                          Можно ведь придумать какой-то производный от паскалевских и сишных строк вариант.
                                                                                          Например:
                                                                                          VLQ, строка, [NULL]
                                                                                          Если VQL отлично от 0, то это строка фиксированной длины, собственно в VQL эта длина и записана, NULL в конце не добавляется. Если VQL равно 0, то это NULL-завершаемая строка. Второй вариант на случай если нужно принять строку неизвестной длины. Хотя строки неизвестной длины наверное лучше не принимать.
                                                                                            +3
                                                                                            'Наилучшим примером, который я смог найти, является использование NUL-завершенных текстовых строк в C/Unix/Posix. Стоял очень простой выбор: должен ли язык C представлять строки как кортеж адрес + длина или просто как адрес и некий магический символ (NUL), отмечающий конец строки? Именно это решение приняло динамическое трио Кен Томпсон, Деннис Ритчи и Брайан Керниган в начале 70-х, и они были вольны выбрать любой способ. Я не смог найти ни одной записи о решении, которое я признаю слабым кандидатом: у меня нет никаких доказательств, что это решение было осознанным.'

                                                                                            Странно видеть такое замечание от разработчика (http://en.wikipedia.org/wiki/Poul-Henning_Kamp). Недостаток такого представления в основном сказывается только при вычислении длины строки. Не надо забывать, что одно из достоинств, благодаря которому С стал одним из основных языков, это его адресная арифметика. А для нее такое представление строк идеально подходит, особенно при однопроходной обработке. Например:

                                                                                            int strcmp (const char *s1, const char *s2) {
                                                                                                while (*s1 == *s2++)
                                                                                                    if (*s1++ == '\0')
                                                                                                        return 0;
                                                                                                return *s1 — s2[- 1];
                                                                                            }

                                                                                            В результате задействовано только две переменные. Запишите это все через массивы, нужно будет иметь 2 переменных для массива символов, две на размер этих массивов, одна на текущее положение в массивах. А также раздутый примерно в 2-3 раза код.

                                                                                            Конечно адресная арифметика не так проста, но за эффективность надо платить.

                                                                                            Я поэтому считаю, что 'трио Кен Томпсон, Деннис Ритчи и Брайан Керниган', все сделали правильно, в едином ключе, а Poul-Henning Kamp написал не по делу. Лучше бы, он тогда свою статью назвал так «Нужно отказаться от адресной арифметики в C и перейти на массивы», но тогда не получился бы C.
                                                                                              0
                                                                                              Думаю, что можно считать, что создатели 0-терминированных строк, равно как и создатели нулевой ссылки ровно также ошиблись, как многие другие изобретатели и конструкторы, чьи детища по невежеству или по злой воле были использованы против людей.
                                                                                              0
                                                                                              Не понятно, а что мешает программистам для своих приложений написать модуль строк хранящих длину? Это совсем не сложно.
                                                                                              Тема статьи надумана, гораздо больше проблем, на мой взгляд, вызывает адресная арифметика.
                                                                                                +1
                                                                                                Ничего не мешает. developer.gnome.org/glib/2.28/glib-Strings.html
                                                                                                  0
                                                                                                  Это был риторический вопрос )
                                                                                                  0
                                                                                                  1) для многих (интерпретируемых прежде всего) языков этот модуль наверняка будет не столь эффективен, как стандартные библиотеки
                                                                                                  2) рано или поздно придётся вызывать функции стандартных библиотек и API ОС, а значит ещё конвертацией туда-сюда придётся озаботиться
                                                                                                    0
                                                                                                    1) На многих задачах хранение длины строки наоборот увеличит эффективность. Уже не говоря о том, что можно хранить данные строки со счетчиком ссылок и копировать строку только при необходимости.

                                                                                                    2) Можно хранить null-байт вконце и преобразовывать ничего не нужно.
                                                                                                  +1
                                                                                                  Самая дорогая однобайтовая ошибка, это в договоре на миллиард долларов вместо $ поставить р )
                                                                                                  +1
                                                                                                  имею сильнейший гемморой с софтом управления своими железяками — на стороне железяк сидят управляющие регистры, которые начинаются с 0x00 и часто имеют значения 0x00. В Qt мне по случаю полного программистского невежества очень удобно работать с классом QString, но очень неудобно с классом QByteArray и с методами readRawData() и writeRawData. Сижу бывало весь вечер напролет и матерю эти чертовы строки.

                                                                                                  Ну а если отвлечься от однобайтовости, то хочется передать отдельный привет товарищам Кириллу и Мефодию.
                                                                                                    +2
                                                                                                    Это если у вас нет fine grained grant tables. В гипервизорах такое бывает, думаю, и в ос тоже. (сегфолт при границах по размерам в байтах, а не в страницах).
                                                                                                      –1
                                                                                                      еще б я понял, что вы мне написали :-) неужели из моего комментария не понятно, что я на этом языке не разговариваю? :-)))
                                                                                                      0
                                                                                                      чем вам не угодили Кирилл и Мефодий?
                                                                                                        0
                                                                                                        тем, что смс-ка не может быть длинее 70-ти символов.
                                                                                                          0
                                                                                                          придётся вам разочароваться,
                                                                                                          но ни Кирилл с Мефодием, ни Константин не придумывали ни кодировок, ни протокола передачи smsок.
                                                                                                          еслибы кириллицу не придумали, мы бы писали в лучшем случае греческим, в худшем — глаголицей, и ограничение былобы такимже.
                                                                                                      –2
                                                                                                      При использовании NUL-завершенной строки, попытка работы с ней частями, превышающими один байт, может привести к обращению к символам за символом NUL. Если NUL символ является последним байтом страницы виртуальной памяти и следующая страница не определена, это может привести к крушению процесса с ошибкой «страница не найдена» [«page not present»].>

                                                                                                      На деле этого никогда не произойдёт. Библиотека осуществляет доступ к строке как к многобайтовым целым не начиная с начала строки, а начиная с первого её байта, кратному размеру удобного для процесса целого (часто совпадающему по размеру с указателем). Это называется выравнивание, а при доступе к памяти без выравнивания на одних процессорах происходят тормоза, а на других — ошибки выполнения.
                                                                                                      Границы и размер страниц тоже выровнены по этому размеру, из-за чего выход за пределы страницы в поисках NULL-байта не произойдёт, так как часть многобайтного целого числа никогда не будет проходить по границе страницы.
                                                                                                        +2
                                                                                                        Начало строки может быть не выровняно в памяти, а динамически созданные буферы вообще находятся в куче и положение буфера зависит от свободных слотов в куче. Даже если ее обходить фрагментами по 2, 4 и т.д. байт, есть риск вылезти за границу страницы.
                                                                                                          0
                                                                                                          Копирование строки не будет обращаться к строке как к числам с первых байтов, а начнет делать это по выравниванию. Это и гарантирует непересечение границы страницы. Грубо говоря, код вместо
                                                                                                          void strcpy(char* _dest, const char* _src) {
                                                                                                              int *dest = _dest, src = _src;
                                                                                                              while (!contains_null_byte(*src)) {
                                                                                                                  *dest++ = *src++;
                                                                                                              }
                                                                                                              *dest = 0;
                                                                                                              /* обработка граничных случаев */
                                                                                                          }

                                                                                                          для платформы с выравниванием по 4 байтам имеет вид примерно
                                                                                                          void strcpy(char* _dest, const char* _src) {
                                                                                                              if (_dest & 3 != _src & 3) {
                                                                                                                  while (*_src) *_dest++ = *_src++;
                                                                                                                  *_dest = 0;
                                                                                                                  return;
                                                                                                              }
                                                                                                              while (_dest & 3 && *_dest) {
                                                                                                                  *_dest++ = *_src++;
                                                                                                              }
                                                                                                              int *dest = _dest, src = _src;
                                                                                                              while (!contains_null_byte(*src)) {
                                                                                                                  *dest++ = *src++;
                                                                                                              }
                                                                                                              _dest = dest; _src = src;
                                                                                                              while (*src) *_dest++ = *_src++;
                                                                                                              *_dest = 0;
                                                                                                          }
                                                                                                          То есть, доступ к памяти всегда будет проходить по границе страницы, и будет определено, что строка либо заканчивается на текущей странице, либо продолжается на следующей.
                                                                                                            0
                                                                                                            А кто гарантирует выравнивание?
                                                                                                              0
                                                                                                              Спасибо за пояснения, так понятней. Вы правы, предложенный Вами алгоритм устраняет проблему. Но он только работает, если обе строки начинаются по одному смещению от границы выравнивания, в остальных слуачях все равно побайтно. Вот об этом и говорит автор, что для оптимизации необходимо усложнять алгоритмы.
                                                                                                                0
                                                                                                                С этим согласен.
                                                                                                                Однако, скорее всего, производительность в случае разных смещений от границы выравнивания при «поинтовом» копировании будет даже ниже, чем при побайтовом копировании.
                                                                                                            0
                                                                                                            Вы о чем сейчас?
                                                                                                            Ни о каких выравниваниях речи не идет. Null-байт может без проблем быть последним на странице (как и сказано в статье), следующая страница вполне может быть не определена для процесса (как и сказано в статье) и в таком случае, если я напрямую буду работать со строкой кусками больше чем 1 байт (и тут меня никто не ограничивает в выборе кусков и выборе начала отсчета) — приложение вылетит (как и сказано в статье).
                                                                                                              –2
                                                                                                              А почему Вы будете обращаться к следующей странице, если Вы знаете, что на текущей странице строка уже закончилась?
                                                                                                              В выборе начала отсчёта и кусков Вас как раз ограничивает выравнивание.
                                                                                                                0
                                                                                                                Ну во первых никакое выравнивание меня не ограничивает в выборе размера куска, которым я хочу манипулировать, меня ограничивает адресация, заставляя выбирать кусок, кратный одному байту, а вот написать процедуру, которая берет блоки по 1000 байт мне ничто не мешает, и в случае строки без длины я такой процедурой пользоваться просто не смогу, т.к. она может свалиться.
                                                                                                                Ну и вообще — далеко не все платформы дают ошибку при обращении по невыровненному адресу, так что ни о каком выравнивании речи нет.
                                                                                                                  0
                                                                                                                  >Ну во первых никакое выравнивание меня не ограничивает
                                                                                                                  На ряде платформ оно ограничит Вас SIGBUSом, на других — снизившейся в 4 раза производительностью. *((int*)0) = 0 Вы тоже можете написать и язык Вас в этом не ограничивает, но так делать не нужно.
                                                                                                                  >вот написать процедуру, которая берет блоки по 1000 байт мне ничто не мешает
                                                                                                                  Я же написал — «на деле этого никогда не произойдёт», а не «не существует никаких возможностей написать код, который столкнётся с этой проблемой». Потому что работа с кусками по 1000 байт в данном контектсе не имеет смысла, а имеет смысл копирование кусками по 4/8 байт, чем все активно и пользуются.
                                                                                                                    0
                                                                                                                    Ну во первых то что есть некоторые платформы с невозможностью так сделать — ни о чем не говорит.
                                                                                                                    Второе — читаем статью и там ничего о копировании или прочем, так что какой контекст? В контексте как раз этого совершенно небыло. Там сказано что нельзя работать со строкой кусками — а это на деле очень даже может произойти.

                                                                                                                    А то получается что вы взяли несколько своих конфигураций и юз-кейсов и делаете вид, что автор статьи именно ваш случай имеет ввиду, и поэтому он не прав, потому что частно в вашем случае проблем не будет. Только вот автор говорит на самом деле о гораздо более общей проблеме.
                                                                                                                      0
                                                                                                                      >Ну во первых то что есть некоторые платформы с невозможностью так сделать — ни о чем не говорит.
                                                                                                                      Когда таких платформ — 99%, это о чём-то говорит.

                                                                                                                      >и поэтому он не прав, потому что частно в вашем случае проблем не будет. Только вот автор говорит на самом деле о гораздо более общей проблеме.
                                                                                                                      Где я говорил, что автор не прав? Я пытался показать, что это замечание может привести к указанным последствиям намного реже, чем может показаться.
                                                                                                                        0
                                                                                                                        Ничего не знаю про 99%, давайте цифры по распространенности и с пруфами.
                                                                                                                        По второму пункту — тоже самое, «намного реже» нужно аргументировать, а не просто показать что в одном из случаев копирования ошибок нет.
                                                                                                                          0
                                                                                                                          >Ничего не знаю про 99%, давайте цифры по распространенности и с пруфами.
                                                                                                                          en.wikipedia.org/wiki/Data_structure_alignment#Architectures
                                                                                                                          Распространенность архитектур сами нагуглите?

                                                                                                                          >По второму пункту — тоже самое, «намного реже» нужно аргументировать, а не просто показать что в одном из случаев копирования ошибок нет.
                                                                                                                          Код для копирования/прочих манипуляций со строками есть в stdlib. Можете поставить профайлер и посмотреть на Вашей системе, сколько времени он выполняется. Ещё можете найти мне хотя бы 5 примеров в распространенных проектах, где используется доступ к строкам блоками по 1000 байт.
                                                                                                                            0
                                                                                                                            Я как раз к тому, что самая распространенная архитектура для десктопов как раз может работать без выравнивания — а это не малый кусок, чтобы его игнорировать.
                                                                                                                            Что такое stdlib? Кто сказал про C++? Вроде и статья не о C++, и блог не о C++, да и разговор не о C++ — так причем тут C++?
                                                                                                                              0
                                                                                                                              >Я как раз к тому, что самая распространенная архитектура для десктопов как раз может работать без выравнивания — а это не малый кусок, чтобы его игнорировать.
                                                                                                                              Эта архитектура рекомендует выравнивание и не гарантирует доступ с выравниванием и без выравнивания с одинаковой скоростью.

                                                                                                                              >Что такое stdlib? Кто сказал про C++? Вроде и статья не о C++, и блог не о C++, да и разговор не о C++ — так причем тут C++?
                                                                                                                              О C++ никто не и говорил — там строки с длинной и к ним не применяются эти функции. В C#/Java/Python/вставьте_сюда_Ваш_любимый_язык — скорее всего, тоже.
                                                                                                                              Я говорил о C, на котором работают почти все эти языки и куча юзерспейсных программ.
                                                                                                                              Пожалуйста, перестаньте себе противоречить — сначала Вы требуете показать конкретный случай, который я считаю частоиспользуемым, а потом не принимаете его, так как он привязан к языку.
                                                                                                                                0
                                                                                                                                Не гарантирует с одинаковой скоростью != не работает.
                                                                                                                                Я просил аргументировать, а не представить один случай. Аргументировать то, что приведенные случаи покрывают настолько большой процент — что проблема не является актуальной, как представлено в статье.
                                                                                                                                Еще раз — не который вы считаете частоиспользуемым, а который подтвержденно является настолько частоиспользуемым, что проблему можно считать не актуальной.
                                                                                                                              0
                                                                                                                              Кстати говоря, для использования тех же SSE регистров — разве кто-то гарантирует мне на 32 разрядной платформе выравнивание по 128 битам?
                                                                                                                                0
                                                                                                                                Нет, тут вышла ошибочка, с SSE как раз все будет нормально, там командой за границу страницы не вылезешь.
                                                                                                                                Но с AVX требования к выравниванию — 32 бита, при этом регистр — 256 бит, поэтому вроде они могут попадать на стык страниц.
                                                                                                              +2
                                                                                                              0. мне нравиться постановка — основатели самого используемого системного языка сделали ошибку! Они сделали язык, который фактически стандартизовал системный код, вытеснил ассемблер из системного программирования и заложил основы популярности unix. Насколько на это повлияла совместимость с асмом — еще тот вопрос. В качестве примера — куча языков и реализаций несовместимые по вызовам угасали.
                                                                                                              В общем называть ошибкой это не то что нельзя, а как-то по детски что ли…

                                                                                                              1. рассуждения о цифрах в миллиард без хотя бы базовых прикидок — фуфло. Мне кажется что они правы в том что nul-terminated было дороже, но на сколько — это вопрос. Но есть вероятность что проблем было бы не меньше и затраты на обработку строк с известной длинной соизмеримы. В общем говоря об ошибке надо бы представить доказательства а не мусолить аргументы.

                                                                                                              2. Очевидно что за 40 лет ситуация изменилась кардинально и можно говорить что было бы лучше. Следует учесть что когда-то памяти было мало и она была дорогая и сколько было сэкономлено памяти — еще тот вопрос. Это сейчас железо дешёвое.
                                                                                                              Очень даже возможно что если посчитать байт на строчку в долларах будет миллиардная экономия.
                                                                                                                +9
                                                                                                                Статья конечно интересная, но она хороша как хороший иллюстративный пример. Пример, как одно решение, принятое когда-то в рабочем порядке, может оказать влияние на глобальное развитие технологий на десятки лет. Да и вообще задуматся, какую роль в нашей жизни играют рудименты, то есть наследие когда-то принятых решений.

                                                                                                                Поэтому если все-таки не вырывать «null terminated» из исторического контекста, то нет особого повода метать направо и налево осуждающие возгласы. Вы же, надеюсь, не осуждаете отсталость, несовершенство и экологическу вредность технологий работы с металлом бытовавших в бронзовом веке.

                                                                                                                Поэтому попробую вкратце вернуть «полемику» назад в исторический контекст из которого она успешно общими стараниями выпала.

                                                                                                                Так вот, (пожалуйста, фанфары) сейчас Капитан Очевидность, откроет Вам «большой-большой секрет»: Когда Отцы-основатели придумывали язык C они совсем-совсем не заморачивались над тем, чтобы все использованные ими архитектурные конструкции эффективно работали на компьютерах 21века. Они вообще, наверное даже не делали предположений насчет того, какими будут компьютеры 21 века.

                                                                                                                У них стояла достаточно четкая и понятная задача создание высокоуровнего языка, с помощью которого можно решать большинство задач не менее эффективно, чем с использованием ассемблера. Да, еще о «зоопарке» они тогда не думали, у них под рукой была PDP-архитектура, и именно для нее они разрабатывали «высокоуровневый ассемблер». Как вы понимаете, единственно возможный способ эффективно решить эту задачу — сделать конструкции высокоуровневого языка максимально легко отображаемыми на аппаратную архитектуру.

                                                                                                                А вот после такого «введения», pадумайтесь, почему в языке C нет например оператора циклического сдвига? Почему в язык C «забыли положить» операцию возвратить первый/последний включенный бит в машинном слове? Или почему нет оператора подсчета битов в байте? Ведь было бы так удобно?
                                                                                                                Ответ простой: их «не положили», потому что таких ассемблерных инструкций просто не было в системе комманд PDP-11!
                                                                                                                Поэтому, личности, утверждающие что операции автоинкремента якобы «синтаксический сахар языка C», по меньшей мере показывают свою некомпетентность по историческому вопросу. В языке C не задумывался синтаксический сахар совсем, как понятие. Операции ++,-- это все лишь способ эффективно использовать имевшийся в тогдашней системе комманд режим автоинкрементной адресации (справедливая логика: почему бы не получить профит на пустом месте, просто заюзав в языке то, что «одной ассемблерной коммандой» нахаляву дается в процессоре).

                                                                                                                А теперь, (еще, пожалуйста, фанфары) про «null-byte» решение! Опять-таки, если мы заглянем в описание архитектуры PDP-11, то мы обнаружим что в отличии от большинства современных архитектур, комманды пересылки данных модифицировали флаговый регистр.
                                                                                                                Как в самом языке C и соответственно в стандартной библиотеке языка C этот «профит на пустом месте» следующий из этой «фичи» использован направо и налево — везде и повсеместно! Именно за счет этой особенности архитектуры большинство операций манипулирующих с null-terminated строками за счет подобного «знания архитектуры PDP» легко могли быть превращены в простой и компактный код зачастую всего в несколько ассемблерных комманд!!!

                                                                                                                И это был наверное едиственнный способ создать возможность написания операционной системы на высокоуровневом языке!!! Просто потому что в те годы, память мерялась байтами а не гигабайтами! ;)

                                                                                                                Прошли годы, и оказалось, что язык C и Unix вдруг (неожиданно для самих авторов) оказались «суперпортируемымы». И они взяли с собой все, в том числе и те особенности, которые им достались «в наследство» от древниго Unix на PDP-архитектуре.

                                                                                                                Кстати, я бы отдал должное Кернигану, Ричи и Томпсону, ведь большинство из тех решений которые ими были приняты более чем 40 лет назад (вдумайтесь в эту цифру! более сорока лет!), успешно работают на современных архитектурах!

                                                                                                                Да, некоторые правда решения вроде null-terminated strings оказались действительно не очень заточенными на архитектуру современных процессоров с их векторизацией, out of order execution-ом, cache prefetch-ингом, branch prediction-ом, и прочими «прелестями» которых не было в конце 60х годов прошлого тысячелетия.

                                                                                                                Так вот, наверное очень легко «задним умом» считать, сколько бы кто-то там заработал если бы сорок лет назад Керниган с Ричи придумали другую систему кодирования строк. (Вы знаете, если бы я в 1993 не маялся бы всякой ерундой а купил бы акций АО МММ, а потом бы через два годика продал… ну вы поняли, задним умом все сильны).

                                                                                                                Легко, сидя в 2011 году осуждать «рудименты PDP-11». Однако если приглядется, вся компьютерная технология соткана из таких рудиментов (в одной только x86-архитектуре я могу сходу назвать десятки «8-битных рудиментов», про программные же «рудименты» даже Капитану Очевидность говорить стыдно).

                                                                                                                Да и не только компьютерная технология. Попробуйте, уважаемые хабрачитатели, задуматься, а сколько в вашей ДНК за миллиарды лет эволюции накопилось «рудиментарного кода»? У вас два глаза, две руки и две ноги, потому что это случайно оказалось оптимальным решением для какого-то предка жившего сотни миллионов лет назад. Может, ради прикола, посчитаем сколько стоило «в условных единицах» эволюционное решение нашего далекого предка (принятое сотни миллионов лет назад) иметь две руки а не четыре? :) Только, когда будете считать, имейте ввиду, что кто знает, возможно если бы наш далекий предок тогда не «принял бы решение» иметь две руки и две ноги, нас с вами бы на свете не было, так что с «рудиментами» не все так однозначно;)

                                                                                                                Так, что трудно сказать «ошибка ли это» или это «необходимое решение». Я бы это не называл «ошибкой». Это «решение», и весьма осознанное! И как любое важное решение оно имело свою «стоимость», и не малую — но все имеет свою цену!
                                                                                                                Но если бы эта цена не была заплачена, мы бы наверное сейчас не имели ничего из того, что мы сейчас имеем! Просто попробуйте задуматся на этот счет!
                                                                                                                  +4
                                                                                                                  Спасибо Вам за то, что есть еще такие люди на хабре. Не холиварщики, обсуждающие «плохой» UTF-8, хотя прекрасно понямающие его достоинства и недостатки, а специалисты, знающие историю и последовательность становления вещей и пишущие такие здоровенные коменты!
                                                                                                                    +2
                                                                                                                    Спасибо за емкий комментарий.

                                                                                                                  Only users with full accounts can post comments. Log in, please.