Джоэл Сполски. Назад, к основам.
Назад, к основам Автор: Джоэл СполскиПереводчик: Дмитрий Майоров Редактор: Александр Ширшов 11 декабря 2001 г.Мы проводим немало времени, обсуждая на этом сайте разные восхитительные и грандиозные вещи, такие как противостояние .NET и Java, стратегия XML, привязывание клиентов, стратегия конкурентной борьбы, архитектура программного обеспечения, и т.п. Всё это напоминает слоёный пирог. Сверху лежит стратегия программного обеспечения. Под ней архитектуры вроде .NET, и ещё ниже - отдельные продукты: языковые средства разработки, как Java, или платформы вроде Windows.Забуримся поглубже в пирог. Динамические библиотеки? Объекты? Функции? Нет! Глубже! В какой-то момент мы увидим строки программного кода.Ещё глубже. Сегодня я хочу поговорить о процессорах. Маленький кусочек кремния, который байты двигает. Представим себе, что мы учимся программировать. Отложим знания об управлении проектами и языках высокого уровня и вернёмся к основам, заложенным ещё фон Нейманом. Забудем на минуту о J2EE. Подумаем о Байтах.А зачем? Потому что я думаю, что некоторые из самых серьёзных ошибок, которые люди совершают на верхних уровнях архитектуры, обусловлены неполным или неправильным пониманием некоторых простых вещей самого низкого уровня. Вы построили восхитительный замок, но слегка облажались где-то в районе фундамента. Вместо бетонных блоков там оказался какой-то мусор. Дворец выглядит замечательно, только ванна иногда отъезжает в сторону, и непонятно, почему.Так что сегодня наберитесь терпения, и давайте выполним небольшое упражнение на языке C.Помните, как в C устроены строки: они представляют собой последовательность байтов, и последний байт всегда содержит особое значение 0. Это порождает два очевидных следствия:Единственый способ определить, где строка кончается (то есть узнать её длину) - это пройти по ней в поисках нулевого байта в самом конце. Строка не может содержать нулевые байты. Так что хранить произвольные двоичные данные вроде картинки в формате JPEG в строке нельзя. Почему строки в языке 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!" заорал прораб. "Это никуда не годится! В первый день было в десять раз больше! В чём дело?""Ничего не могу поделать," -- говорит Шлемиэль. "Каждый день я ухожу всё дальше и дальше от банки!"(Для особо въедливых, каковы правильные цифры?) Эта несмешная шутка точно иллюстрирует что происходит, когда strcat используется так, как я только что описал. Поскольку strcat сначала должен пробежать по всей длине строки в поисках нулевого байта, функция работает намного медленнее, чем могла бы, и совсем плохо масштабируется. Масса кода, который вы используете каждый день, содержит эту проблему. Файловые системы часто сделаны так, что класть много файлов в один каталог не стоит, потому что производительность начинает быстро падать при нескольких тысячах файлов. Попробуйте открыть переполненную корзину Windows - это займёт часы, причём зависимость времени открытия корзины от количества файлов в ней явно нелинейная. Там точно где-то есть алгоритм Шлемиэля. Каждый раз, когда что-то, что должно быть линейным по производительности, вдруг оказывается степеннЫм, ищите спрятавшихся Шлемиэлей. Они часто встречаются в библиотеках. Столбик вызовов strcat или strcat в цикле не кричит "n в квадрате", но происходит именно это.Как с этим бороться? Многие хитрые программисты на 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, которая изменяет по необходимости размер буфера для хранения результата. Сколько именно памяти ей имеет смысл выделять? Ровно столько, сколько сейчас надо? Мой учитель и наставник Стэн Эйзенстет (Stan Eisenstat) рекомендует при вызове 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.UI Design for Programmers Joel Spolsky The Chop Suey Club Bruce Weber