Назад, к основам

Автор: Джоэл Сполски

Переводчик: Дмитрий Майоров

Редактор: Александр Ширшов

11 декабря 2001 г.

Мы проводим немало времени, обсуждая на этом сайте разные восхитительные и грандиозные вещи, такие как противостояние .NET и Java, стратегия XML, привязывание клиентов, стратегия конкурентной борьбы, архитектура программного обеспечения, и т.п. Всё это напоминает слоёный пирог. Сверху лежит стратегия программного обеспечения. Под ней архитектуры вроде .NET, и ещё ниже - отдельные продукты: языковые средства разработки, как Java, или платформы вроде Windows.

Забуримся поглубже в пирог. Динамические библиотеки? Объекты? Функции? Нет! Глубже! В какой-то момент мы увидим строки программного кода.

Ещё глубже. Сегодня я хочу поговорить о процессорах. Маленький кусочек кремния, который байты двигает. Представим себе, что мы учимся программировать. Отложим знания об управлении проектами и языках высокого уровня и вернёмся к основам, заложенным ещё фон Нейманом. Забудем на минуту о J2EE. Подумаем о Байтах.

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

Помните, как в C устроены : они представляют собой последовательность байтов, и последний байт всегда содержит особое значение 0. Это порождает два очевидных следствия:

Почему строки в языке C так работают? А потому что микропроцессор PDP-7, на котором разрабатывались UNIX и C, имел такой строковый тип ASCIZ. ASCIZ означало "ASCII с нулём (zero) на конце."

Неужели это единственный способ хранить строки? Конечно нет, более того, это наихудший способ хранить строки. Для всех нетривиальных программ, API, операционных систем, библиотек классов следует избегать использования ASCIZ строк, как чумы. Почему?

Начнём с того, что напишем код функции strcat, которая прицепляет одну строку к другой.

void strcat( char* dest, char* src )
{
     while (*dest) dest++;
     while (*dest++ = *src++);
}

Посмотрим на код и разберёмся, что тут происходит. Сначала мы идём по первой строке и ищем её хвост (нулевой байт). После этого мы идём по второй строке и копируем её символы один за другим, добавляя их в хвост первой строки.

Такая работа со строками достаточно хороша для , но у неё есть свои проблемы. Вот проблема. Предположим, что у вас есть ворох имён и вы хотите их все сложить в одну длинную строку:

char bigString[1000]; /* Никогда не знаю, сколько выделить... */
bigString[0] = '\0';
strcat(bigString,"John, ");
strcat(bigString,"Paul, ");
strcat(bigString,"George, ");
strcat(bigString,"Joel ");

Это работает? Да. И выглядит чистенько и опрятно.

Как насчёт эффективности? Достаточно ли быстро это будет работать? А масштабируемость? Подходит ли такой код для обработки миллиона строк?

Нет. Этот код базируется на алгоритме маляра Шлемиэля. Кто такой Шлемиэль? Это персонаж из старого анекдота:

Маляр Шлемиэль подрядился красить пунктирные осевые линии на дорогах. В первый день он получил банку краски, поставил её на дорогу, и к концу дня покрасил 300 метров осевой линии. "Отлично!" сказал прораб, "быстро работаешь!" -- и заплатил ему копейку.

На следующий день Шлемиэль покрасил 150 метров. "Мда, это, конечно, не так здорово, как вчера, но приемлемо." -- сказал прораб и заплатил ему копейку.

На следующий день Шлемиэль покрасил 30 метров. "Всего лишь 30!" заорал прораб. "Это никуда не годится! В первый день было в десять раз больше! В чём дело?"

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

Как с этим бороться? Многие хитрые программисты на C написали свою функцию mystrcat примерно так:

char* mystrcat( char* dest, char* src )
{
   while (*dest) dest++;
   while (*dest++ = *src++);
   return --dest;
}

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

char bigString[1000]; /* Никогда не знаю, сколько выделить... */
char *p = bigString;
bigString[0] = '\0';
p = mystrcat(p,"John, ");
p = mystrcat(p,"Paul, ");
p = mystrcat(p,"George, ");
p = mystrcat(p,"Joel ");

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

Разработчики языка программирования Паскаль были в курсе этой проблемы и "исправили" её, решив сохранять длину строки в первом байте. Такие строки называются паскалевскими. В них можно хранить произвольные двоичные данные, и у них нет замыкающего нулевого байта. Байт может принимать значения от 0 до 255, поэтому паскалевские строки не могут быть длиннее 255 байт. Поскольку у них нет нулевого байта на конце, они занимают в памяти ровно столько же места, как и ASCIZ строки. Одно из преимуществ паскалевских строк состоит в том, что не надо каждый раз пробегать по строке в поисках её конца. Длина строки определяется одной ассемблерной инструкцией вместо целого цикла. Это намного быстрее.

Старая операционная система Макинтошей использовала паскалевские строки повсюду. Многие программисты на C на других платформах использовали паскалевские строки для ускорения работы. Excel использует паскалевские строки внутри себя, поэтому строки во многих местах в Excel не могут быть длиннее 255 байт, и это одна из причин, почему Excel так быстро работает.

Традиционно для того, чтобы поместить паскалевскую строку в программу на C code, приходилось писать:

char* str = "\006Hello!";

Да, надо было посчитать байты вручную и забить полученное число в первый байт строки. Ленивые программисты иногда писали так (и получали медленные программы):

char* str = "*Hello!";
str[0] = strlen(str) - 1;

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

Я обошел вниманием важный момент. Помните эту строку?

char bigString[1000]; /* Никогда не знаю, сколько выделить... */

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

Правда?

Потому что иначе, понимаете, хитрый хакер, прочитав мой код, заметит, что я зарезервировал всего 1000 байт и надеюсь, что этого хватит, и он придумает оригинальный способ заставить мою программу strcat-нуть строку длиной 1100 байт в мои 1000 байт памяти, тем самым переписав стек, включая адрес возврата, так что когда функция вернётся, управление получит злобный код, который хакер сам написал. Именно это имеется в виду, когда говорят о том, что в очередной программе обнаружилось переполнение буфера . Одно время сетевые черви распространялись исключительно используя подобные способы, пока повсеместное распространение Microsoft Outlook не сделало написание сетевых вирусов доступным даже для подростков.

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

Но вообще-то C не сильно тут помогает. Вернёмся к моему примеру с Beatles:

char bigString[1000]; /* Никогда не знаю, сколько выделить... */
char *p = bigString;
bigString[0] = '\0';
p = mystrcat(p,"John, ");
p = mystrcat(p,"Paul, ");
p = mystrcat(p,"George, ");
p = mystrcat(p,"Joel ");

Так сколько будем выделять? Попробуем по книжке.

char* bigString;
int i = 0;
i = strlen("John, ")
+ strlen("Paul, ")
+ strlen("George, ")
+ strlen("Joel ");
bigString = (char*) malloc (i + 1);
/* не забыть про замыкающий нулевой байт! */
...

Глаза б мои не видели. Вы, наверное, уже готовы переключить канал. Я понимаю, но подождите ещё чуть-чуть, потому что сейчас будет самое интересное.

Нам нужно пройти по всем строкам раз, чтобы определить, сколько места выделить, и затем ещё раз, чтобы их соединить. В случае с паскалевскими строками по крайней мере strlen выполняется быстро. Может, мы сможем написать версию strcat, которая будет самостоятельно выделять память.

Это отдельная песня: управление памятью. Вы знаете, как работает malloc? malloc поддерживает связный список свободных блоков памяти. Когда вы вызываете malloc, он проходит по списку в поисках блока достаточной длины. Найдя таковой, malloc разбивает его на две части (одна запрошенного размера, другая -- что осталось), кладёт остаток обратно в список свободных блоков, и возвращает указатель на блок запрошенного размера. Когда вы вызываете free, он просто добавляет освобождаемый блок в список свободных. Через какое-то время оказывается, что все свободные блоки маленькие, а нужен кусок побольше. Соответственно malloc объявляет перерыв и начинает перетряхивать список свободных блоков, сливая соседние маленькие блоки воедино, на что уходит три с половиной дня. В результате в среднем производительность malloc оказывается так себе (ему приходится постоянно ходить по цепочке свободных блоков), и иногда, внезапно, становится совсем никакой (когда приходится заниматься дефрагментацией). (Кстати, точно так же ведут себя и системы со сбором мусора, кто б мог подумать, так что заявления, которые часто можно услышать про неэффективность сборки мусора не совсем верны, ибо типичная реализация malloc обладает теми же самыми проблемами, хотя и в меньшей степени.)

Хитрые программисты борются с фрагментацией памяти, выделяя каждый раз память блоками, размер которых равен степени двойки. Ну вы знаете, 4 байта, 8 байт, 16 байт, 18446744073709551616 байт, и т.д. По причинам, которые должны быть очевидны для тех, кто играл с конструктором Lego, это уменьшает фрагментацию списка свободных блоков. Несмотря на то, что такой подход кажется расточительным, также легко показать, что при нём неиспользуемой остаётся не более чем 50% памяти. Так что ваша программа использует не более чем в два раза больше памяти, чем ей надо, что не так уж страшно.

Допустим, вы написали хитрую функцию strcat, которая изменяет по необходимости размер буфера для хранения результата. Сколько именно памяти ей имеет смысл выделять? Ровно столько, сколько сейчас надо? Мой учитель и наставник рекомендует при вызове realloc удваивать количество памяти по сравнением с прошлым разом. Это значит, что вам никогда не придётся вызывать realloc больше чем lg n раз, что неплохо с точки зрения производительности даже для огромных строк, и вы потратите впустую не больше 50% памяти.

Ладно. Жизнь в стране байтов становится всё сложнее. Правда, хорошо, что вам не надо больше ничего писать на C? В нашем распоряжении есть такие великолепные языки, как Perl, Java, VB и XSLT, которые не заставляют думать ни о чём таком низком, они сами со всем как-то справляются. Вот только иногда трубы вылезают в середине гостиной, и нам приходится думать о том, какой класс использовать -- String или StringBuilder, потому что компилятор всё ещё недостаточно умён, чтобы понять, чего же мы собственно хотим достичь, и помочь нам избежать попадания на алгоритм маляра Шлемиэля.

На прошлой неделе я написал, что команда SQL SELECT author FROM books не может быть быстро выполнена, если исходные данные находятся в формате XML. Если кто тогда не понял, о чём шла речь, то теперь, после целого дня ковыряния в байтах, вывод станет более очевидным.

Как реляционная база данных выполняет команду SELECT author FROM books? В реляционной базе данных каждая строка в таблице (например, в таблице books) имеет одинаковую длину в байтах, и каждое поле находится по фиксированному смещению относительно начала строки. Так что, например, если каждая запись в таблице books имеет длину 100 байт, и поле author находится по смещению 23, то имена авторов расположены начиная с байтов 23, 123, 223, 323, и т.д. Как выглядит код перехода на следующую запись? Примерно так:

pointer += 100;

Одна инструкция процессора. Ну очень быстро.

Теперь посмотрим на ту же таблицу в XML.

<?xml blah blah>
<books>
    <book>
        <title>UI Design for Programmers</title>
        <author>Joel Spolsky</author>
    </book>
    <book>
        <title>The Chop Suey Club</title>
        <author>Bruce Weber</author>
    </book>
</books>

Вопрос. Как выглядит код перехода на следующую запись?

Ээээ..

Тут толковый программист может сказать, ну давайте распарсим XML в памяти в дерево, по которому можно ходить туда-сюда относительно быстро. Объём работы, который придётся выполнить процессору, чтобы выполнить SELECT author FROM books расстроит вас до слёз. Как хорошо известно каждому разработчику компиляторов, лексический разбор и парсинг представляют собой наиболее медленные стадии компиляции. Достаточно сказать, что при разборе XML и построении дерева в памяти используется масса строковых операций, которые, как мы выяснили, медленные. И это при условии, что у вас есть достаточно памяти, чтобы запихать туда всё целиком. В случае реляционных баз данных время, необходимое для перехода от записи к записи фиксировано и определяется временем выполнения одной команды процессора . Просто по определению. И благодаря файлам, отражённым в память, вам надо будет загружать в память только те страницы, которые используются. В случае XML, если парсить заранее, то затраты времени на перемещение от одной записи к другой фиксированы, зато при этом время запуска большое, а если заранее не парсить, то время перехода от записи к записи зависит от длины записи и в любом случае это сотни процессорных инструкций.

Для меня это означает, что если надо работать с большими объёмами данных и при этом не терять в производительности, то использовать XML нельзя. Если данных немного, или то, что вы делаете, не обязано работать быстро, тогда XML годится. А если хочется и на ёлку влезть, и не оцарапаться, то придётся придумать способ хранить метаданные к XML, наподобие счётчика байтов в паскалевских строках, которые помогут быстрее находить, что где в файле лежит без необходимости всё разбирать. Но, конечно, редактировать такие файлы обычным текстовым редактором будет нельзя, потому что съедут метаданные, так что это уже будет неправильный XML.

Для тех трёх вежливых читателей, которые всё ещё со мной: надеюсь, вы узнали что-то новое или посмотрели на известные вещи с необычной стороны. Надеюсь также, что знание такого занудного материала первых занятий по информатике, как работа функций strcat и malloc, даёт вам новый угол зрения на высокоуровневые стратегические и архитектурные решения, которые вы принимаете в отношении технологий вроде XML. В качестве домашнего задания подумайте, почему процессоры от Transmeta всегда будут казаться подторможенными. Или почему исходная спецификация HTML-ного тэга TABLE была настолько плохо продумана, что большие таблицы не могут быть быстро отображены на экранах пользователей с модемами. Или почему COM так чертовски быстро работает, но только не в случае пересечения границ процессов. Или почему разработчики NT запихали драйвер дисплея в пространство ядра системы, а не в пользовательское пространство.

Всё это вещи, которые заставляют думать о байтах, и они оказывают влияние на архитектурные и стратегические решения, которые мы принимаем. Я придерживаюсь мнения, что студенты, начинающие изучать программирование, должны начинать с начала, использовать C и подниматься вверх от процессора. Мне противно, как часто программа обучения строится на посылке, что Java представляет собой хороший язык для того, чтобы начинать программировать, потому что это так "просто" и не нужно отвлекаться на эти скучные детали про строки и выделение памяти, и сразу можно изучить кульные ООП-штучки которые помогут сделать ваши большие программы так восхитительно модульными. Это педагогический провал. Поколения выпускников снисходят на нас, раскидывая алгоритмы маляра Шлемиэля налево и направо, даже не понимая этого, поскольку у них нет представления о том, что строки на нижнем уровне сложны, даже если из их перлового скрипта этого не видно. Если хочешь научить кого-то хорошо, надо начинать с основ. Как в Karate Kid. Wax On, Wax Off. Wax On, Wax Off. Повторять три недели. После этого Снести Башню Другому Пацану несложно.

В английском оригинале статья называется