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

From The Joel on Software Translation Project

Revision as of 10:23, 30 May 2012 by Kirill (Talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Автор: Джоэл Сполски
Переводчик: Михаил Казаков
В оригинале статья называлась Back to Basics и была написана 11 декабря 2001 года

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

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

А копнём ещё глубже. DLL'ки? Объекты? Функции? Нет. Ещё ниже! В какой-то момент мы увидим строки программного кода

Это ещё не достаточно глубоко. Сегодня мне хочется подумать о процессорах. Небольшой кусочек кремния, двигающий байты. Представим, что вы - начинающий программист. Забудем все накопленные знания о программировании, программном обеспечении, управлении проектами и вернёмся на нижний фундаментальный уровень - машины Фон Неймана. Выкиньте из головы J2EE на это время. Подумаем о байтах.

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

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

Вспомним, как работают строки в С: они состоят из кучки байтов, заканчивающейся нулевым символом, значение которого 0. Отсюда следует вот что:

  1. Нет другого способа узнать, когда заканчивается строка (сиречь какова её длина), кроме как пройти по ней, ища нулевой символ.
  2. В таких строках не могут находиться нули. Так что вы не сможете поместить кусок бинарных данных вроде JPEG-картинки в строку на С.

Почему строки на C ведут себя так? Из-за того, что процессор PDP-7, на котором были придуманы Unix и C, имел тип строк ASCIZ. То есть ASCII с нулем (Z - zero) в конце.

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

Давайте начнём писать свою реализацию функции strcat, которая подклеивает одну строку к другой.

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

Посмотрим на код и разберёмся, что тут происходит. Сначала мы проходим первую строку, ища при этом нулевой символ. Когда мы его нашли, проходим вторую строку, копируя по символу в первую строку. Такой способ обработки строк и их склеивания был неплох для Кернигана и Ричи, но он имеет свои недостатки. Представим, что у вас есть несколько имён, которые вы желаете добавить в одну большую строку:

 char bigString[1000];     /* Никогда не знаешь сколько выделить... */
 bigString[0] = '\0';
 strcat(bigString,"Вася, ");
 strcat(bigString,"Петя, ");
 strcat(bigString,"Боря, ");
 strcat(bigString,"Саша ");

Это будет работать? Будет. Выглядит чисто и понятно.

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

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

Шлемель получил работу маляра: проводить пунктирные линии посреди дороги. В первый день он притащил бидон с краской и покрыл 300 метров дороги. "Это просто отлично" - сказал его босс, "ты шустрый малый!" и заплатил ему.
На следующий день Шлемель покрыл только 150 метров дороги. "Ну, это не так хорошо как вчера, но всё равно неплохо", сказал его босс, и заплатил ему.
На следующий день Шлемель покрыл 30 метров дороги. "Только 30!" вскричал его босс, "Это невозможно! В первый день ты сделал в десять раз больше работы! Что происходит?".
"Я ничего не могу с этим" ответил Шлемель. "Каждый день я удаляюсь дальше и дальше от бидона с краской!" (Для особо въедливых: какие же числа на самом деле? (англ.))

Эта туповатая шутка (явно из разряда английского юмора, но к теме это отношения не имеет) демонстрирует, что на самом деле происходит при использовании strcat как в примере выше. Так как первая часть strcat каждый раз просматривает строку каждый раз, ища чёртов нулевой символ, она будет работать медленнее, чем могла бы. Множество кода, которым мы пользуемся ежедневно, имеет эту проблему. Многие файловые системы задуманы таким образом, что не стоит класть слишком большое количество файлов в одну директорию, так как производительность будет ужасно падать, когда у вас будут тысячи файлов в одном месте. Попробуйте открыть захламлённую Корзину в Windows и убедитесь воочию - это может занять часы, причём зависимость времени открытия корзины от количества файлов в ней явно нелинейная. Должно быть, там где-то используется алгоритм Шлемеля. Когда что-то выглядит, как будто это должно иметь линейную сложность, а в итоге получается сложность n2, ищите спрятанного Шлемеля. Они часто прячутся и у вас в библиотеках. Глядя на столбик вызовов strcat или его вызов в цикле - не бросается в глаза "сложность n2", но это на самом деле происходит.

Как мы можем исправить проблему? Некоторые хитрые программисты на С пишут собственные функции 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,"Вася, ");
 p = mystrcat(p,"Петя, ");
 p = mystrcat(p,"Боря, ");
 p = mystrcat(p,"Саша  ");

Естественно этот код имеет линейную сложность, не n2, так что он не впадает в ступор от большого количества вызовов.

Создатели языка Pascal знали об этой проблеме и "починили" её, храня однобайтовый счётчик в первом байте строки. То, что получилось, назвали паскалевскими строками (Pascal Strings). Они могут содержать нули и не обязательно заканчиваются нулевым символом. Так как один байт может хранить числа от 0 до 255, паскалевые строки имеют максимальную длину 255, а так как они не заканчиваются нулевым символом они занимают в памяти ровно столько же места, сколько и ASCIZ строки. Главное в них - вам никогда не придётся пробегать всю строку только чтобы узнать её длину. Нахождение длины паскалевской строки это всего одна инструкция на ассемблере, вместо целого цикла, это намного быстрее.

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

Долгое время, если вам нужно было объявить паскалевскую строку в коде на C, вы бы писали:

 char* str = "\007Привет!";

Ага, тут нужно считать байты ручками, самому, прописывать их жёстко в первый байт вашей строки. Ленивы программисты писали следующее и получали медленные программы:

 char* str = "*Привет!";
 str[0] = strlen(str) - 1;


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

Я не упомянул ещё об одной важной вещи выше. Помните эту строчку кода?

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

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

Не правда ли?

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

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

Но, в действительности, специфика языка C не делает это таким уж простым занятием. Вернёмся к нашим баранам:

 char bigString[1000];     /* Никогда не знаешь сколько выделить... */
 char *p = bigString;
 bigString[0] = '\0';
 p = mystrcat(p,"Вася, ");
 p = mystrcat(p,"Петя, ");
 p = mystrcat(p,"Боря, ");
 p = mystrcat(p,"Саша  ");

Сколько же нам нужно выделить? Давайте-ка сделаем это правильно.

 char* bigString;
 int i = 0;
 i = strlen("Вася, ") 
      + strlen("Петя, ") 
      + strlen("Боря, ") 
      + strlen("Саша  ");
 bigString = (char*) malloc (i + 1); 
 /* помним о месте для нулевого символа! */
 ...

Становится скучно и вы уже, наверное, готовы переключиться куда-нибудь. Я вас не виню, но постойте, скоро будет интересней.

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

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

Умные программисты стараются уменьшить захламление malloc, выделяя блоки размера, кратного степени двойки. Ну там, 4 байта, 8 байт, 16 байт, 18446744073709551616 байт и так далее. Для тех, кто играл в Лего, должно быть интуитивно понятно, что это уменьшает фрагментацию при освобождении блоков . Хотя может показаться, что такой способ - просто пустая трата памяти, легко доказать, что перерасход не превышает 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;

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

А теперь посмотрим на таблицу books в формате 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, расстроит вас до слёз. Любой, писавший компиляторы знает, что разбор и анализ - самая медленная часть компиляции. Достаточно сказать, что потребуется куча строк, которые, как мы уже выяснили, страшно медленны, куча выделений памяти, которые тоже медленны - всё это для того, чтобы разобрать файл, проанализировать и построить абстрактное дерево в памяти. При этом считаем - у вас есть достаточно памяти, чтобы всё это провернуть за раз. С реляционными базами данных скорость передвижения от записи к записи фиксирована, и де-факто, одна инструкция CPU. Фактически - благодаря изначальному дизайну. И благодаря отображению файлов в память, вам нужно загружать лишь те страницы диска, которые именно сейчас нужно использовать. В случае же XML, если вы подготовите дерево заранее, скорость перемещения от записи к записи тоже будет фиксированной, но только ценой огромного времени загрузки. Если же дерева в памяти не будет, перемещение между записями будет зависеть от количества записей перед ними и так же будет требовать тысяч инструкций CPU.

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

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

Все эти вопросы требуют задуматься о байтах и влияют на серьёзные высокоуровневые решения, которые мы принимаем при проектировании и разработке стратегии. Вот почему, с моей точки зрения, обучение программированию на первом курсе должно начинаться с основ, использования C и выстраиваться наверх, начиная с CPU. Я и вправду испытываю физическое отвращение от того, как часто программа обучения строится на посылке, что Java представляет собой хороший язык для того, чтобы начинать программировать, потому что это так "просто" и не нужно отвлекаться на эти скучные детали про строки и выделение памяти, и сразу можно изучить кульные ООП-штучки, которые помогут сделать ваши большие программы так восхитительно модульными. На самом деле - это педагогическая катастрофа, которая вот-вот случится. Поколения выпускников повалятся на нас и будут писать алгоритмы Шлемеля направо и налево даже не понимая этого, просто у них не будет представления, что строки, на очень низком уровне, страшно сложная вещь, даже если этого и не видно из скрипта на Perl. Если хочешь обучить чему-то хорошо - придётся начинать с самого нижнего уровня. Это как карате для детей. Вдох. Выдох. Вдох. Выдох. Так три недели. После этого Снести Башню Другому Пацану несложно.

Personal tools