"Автор должен брать пример с Ноя и научиться, как он это делал
на своем ковчеге, помещать так много всего в таком малом объеме."
(Сидней Смит "Эдинбургское обозрение")
Размер программы как стоимость
Какова стоимость программы? Если не рассматривать время выполнения программы, то именно ее объем является основным показателем ее стоимости в глазах пользователя. Это справедливо даже для арендуемых программ, где пользователь платит автору сумму, составляющую, по сути, часть стоимости разработки. Рассмотрим диалоговую систему математического обеспечения APL, разработанную фирмой IBM. Она сдается в аренду за 400 долларов в месяц и требует для своего использования по крайней мере 160 тыс. байтов памяти. В модели ЩМ 370/165 стоимость аренды памяти составляет 12 долларов за тысячу байтов в месяц.
Если программа работает круглосуточно, то стоимость ее использования составит 400 долларов за математическое обеспечение и 1920 долларов за память. Если система APL используется только 4 часа в день, то стоимость составит 400 долларов арендной платы ва математическое обеспечение и 320 долларов за память в месяц. Нередко приходится слышать, с каким ужасом воспринимается тот факт, что в машине с памятью 2 млн. байтов операционная система может занимать 400 тыс. байтов. Ужасаться так же глупо, как критиковать Боинг 747 за то, что он стоит 27 миллионов долларов. Необходимо только задать себе вопрос: а что операционная система делает? Что можно получить за свои деньги в смысле удобства и производительности (при эффективном использовании системы)? Может быть, 4800 долларов в месяц, затрачиваемые на аренду памяти, более целесообразно истратить на другое оборудование, на программистов, на прикладные программы?
Разработчик системы превращает часть отведенных ему ресурсов оборудования в память с резидентными программами, когда он уверен, что для пользователя это лучше, чем иметь дело с сумматорами, дисками и т. д. Поступать иначе было бы в высшей степени безответственно, и результат должен оцениваться как одно целое. Нельзя критиковать систему программирования за размер как таковой, и в то же время постоянно выступать за все более тесное объединение проектов создания аппаратуры и математического обеспечения.
Поскольку львиная доля затрат пользователя отводится на программу, разработчик комплексного программного продукта должен установить контрольные цифры, следить за их соблюдением и придумывать методы уменьшения размеров программ точно так же, как разработчик аппаратуры устанавливает контрольные значения числа компонент, следит за их соблюдением и изобретает методы их сокращения.
Контроль за размерами программ
Управление размерами программ представляет для руководителя проекта частично техническую, а частично - административную задачу. Для установления размеров предлагаемых систем необходимо изучить потребности пользователей и те прикладные области, в которых они работают. Далее эти системы следует разбить на части и определить контрольные цифры размеров каждой компоненты. Поскольку с изменением размеров программы быстродействие меняется очень резко, установление контрольных цифр требует от руководителя профессиональной ловкости и знания допустимых соотношений в каждой части системы. Кроме того, мудрый руководитель всегда оставляет для себя лазейку, которой он сможет воспользоваться впоследствии. Хотя в OS/360 все это было проделано очень тщательно, не обошлось без болезненных уроков. Во-первых, недостаточно просто установить контрольные цифры размеров оперативной памяти, необходимо учесть все аспекты, связанные с размером программы. Большая часть предыдущих операционных систем размещалась на лентах и поскольку поиск на лентах занимал много времени, это препятствовало их интенсивному вызову из сегментов программы. Система OS/360, как и ее непосредственные предшественники - операционные системы Stretch и DOS IBM 1410/7010, располагалась на дисках. Ее создатели наслаждались свободой дешевого обращения к дискам. Первоначальный результат был катастрофичным для производительности.
При установлении размеров оперативной памяти для каждой компоненты бюджет расхода памяти не устанавливался заранее. Как и предсказывали сверхпроницательные люди, программист, обнаруживая, что его программа выходит за отведенный ему участок оперативной памяти, разбивал ее на сегменты. Тем самым увеличивались общие размеры системы и уменьшалась скорость выполнения. Наша служба административного контроля не выявляла таких случаев. Каждый сообщал, какой объем оперативной памяти он использует, и если программист оставался в пределах контрольных цифр, то никто не беспокоился. К счастью, пришел день, когда начала работать программа, моделирующая производительность OS/360. Первые же результаты показали, что не все благополучно. Фортран Н на машине IBM 360/65 с барабанами транслировался со скоростью пять операторов в минуту. Расследование показало, что модули управляющей программы осуществляли слишком много обращений к дискам. Даже очень часто используемые модули супервизора "ходили к колодцу с наперстками" п результат весьма напоминал непрерывную "лихорадку" памяти.
Первая мораль ясна: устанавливайте не только размеры резидентных частей, но и общие размеры памяти, а также вводите ограничения на число обращений к внешней памяти.
Второй урок был очень похожим. Бюджеты памяти были установлены прежде, чем было сделано точное распределение функций в каждом модуле. В результате, как только программист начинал испытывать нехватку памяти, он смотрел, нельзя ли "перелезть через забор" в память соседа. Таким образом, буферы, отведенные управляющей программе, становились частью памяти пользователя. И что еще серьезнее, такая же ситуация сложилась со всеми видами управляющих блоков, и в результате ставились под угрозу защита памяти и надежность всей системы.
Вторая мораль тоже ясна: точно определяйте функции модуля при установлении его размеров.
И третий, гораздо более глубокий, урок можно извлечь из этого опыта. Проект был достаточно велик, а административная связь достаточно плоха, так что многие члены коллектива вели себя как соперники, ломающие копья, а не как строители, совместно создающие программный продукт. Каждый старался оптимизировать свой кусок программы с тем, чтобы уложиться в контрольные цифры; однако мало кто заботился о том, во что все это выльется для заказчика. Такое нарушение ориентации и связи представляет главную опасность для больших проектов.
В течение всей реализации системные архитекторы не должны терять бдительности, чтобы сохранить концептуальное единство проекта. Кроме этих механизмов принуждения существенную роль должно сыграть и отношение самих разработчиков. Может быть, самая важная функция руководителя программистского проекта заключается в воспитании у программистов внимания к нуждам пользователя и к интересам всей системы.
Методы экономии памяти
Никакие меры по установлению бюджета расхода памяти и по контролю за его соблюдением не помогут уменьшить размера программы. Здесь нужны изобретательность и мастерство.
Очевидно, что чем больше функций, тем больший объем памяти требуется при постоянном быстродействии. Прежде всего мастерство необходимо при установлении возможных компромиссов между функциями и размерами программы. Но это вопрос очень тонкой политики. В какой мере право выбора может быть предоставлено пользователю? Можно написать программу со многими факультативными свойствами, каждое из которых требует совсем немного памяти. Можно придумать генератор, который будет располагать списком вариантов и приспосабливать программу к каждому из них. Но для каждого конкретного набора вариантов более монолитная программа требует меньшего объема памяти. Здесь как в автомобиле: лампа, зажигалка и часы, встроенные в один блок, будут стоить дешевле, чем их отдельное исполнение. Поэтому сам разработчик должен определять степень дробления вариантов, выбираемых пользователем.
При разработке системы с широким диапазоном размеров памяти возникает другой важнейший вопрос. Существуют эффекты, ограничивающие область допустимых размеров памяти даже при очень мелком дроблении функции. Действительно, в самых малых системах большинство модулей будет в памяти перекрываться. Значительная часть резидентной памяти в таких системах должна быть выделена как буфер-пая или страничная область, в которую попадают другие части системы. Ее величина определяет размеры всех модулей. Кроме того, распределение функций системы по мелким модулям приводит к потере и производительности, и памяти. В, большой системе, где буферная область может быть в двадцать раз больше, сокращается лишь число обращений к памяти, однако остаются затруднения с быстродействием и памятью из-за малых размеров модулей. Этот эффект ограничивает максимальную эффективность системы с малыми модулями.
Другая область, требующая мастерства,- это достижение компромисса между быстродействием системы и объемом памяти. Для данной функции чем больше объем памяти, тем быстрее система. Это справедливо для поразительно широкого круга случаев. Именно этот факт делает разумным установление бюджета расхода памяти.
Руководитель, если он хочет помочь своей группе добиться хорошего соотношения между быстродействием и памятью, должен поступить следующим образом. Во-первых, убедиться в том, что разработчики хорошо знакомы с методами программирования, а не полагаться на их природную смекалку и прежний опыт. Это особенно важно при разработке нового языка или новой машины. Следует быстро и широко распространять новые идеи или методы, всячески поощряя их появление специальными премиями или другими знаками отличия. Во-вторых, необходимо осознать, что программирование - это техника, и компоненты нужно собирать из готовых элементов. Поэтому при работе над каждым проектом нужно иметь набор хороших подпрограмм или макрокоманд для установления очередей, поиска, расстановки и сортировки. Для каждой такой функции нужно иметь, по меньшей мере, две программы, быструю и медленную. Разработка такой техники - это важнейшая задача, которую следует осуществлять параллельно с планированием системы.
Представление данных - сущность программирования
Следом за мастерством идет изобретательность, и именно благодаря ей рождаются экономичные и быстрые программы. Почти всегда они являются результатом стратегического прорыва, а не тактической мудрости. Иногда это может быть новый алгоритм, такой как быстрое преобразование Фурье, предложенное Кули - Тюки, или замена алгоритма сортировки с п 2 сравнениями па алгоритм с п log re сравнениями.
Но гораздо чаще стратегические находки приходят в результате изменения способа представления данных или таблиц. Именно здесь лежит сердце программы. Покажите мне ваши блок-схемы, но спрячьте таблицы, и я останусь в неведении. Покажите мне ваши таблицы, и мне уже не надо смотреть блок-схемы, они и так очевидны.
Легко продолжить примеры могущества представлений. Я вспоминаю молодого человека, занимавшегося созданием сложного пультового интерпретатора для IBM 650. Он смог поместить его в неправдоподобно малый объем памяти, сделав интерпретатор для интерпретатора, поскольку контакты с человеком медленны и редки, а память была дорогой. Элегантный маленький транслятор с фортрана, созданный фирмой Digitek, использует очень сжатое специальное представление Для самой программы транслятора, так что внешняя память оказывается ненужной. Время, потерянное на интерпретацию этого представления, окупается в десятикратном размере благодаря исключению ввода/вывода.
(Целый ряд таких примеров можно найти в упражнениях к шестой главе книги Брукса и Айверсона "Автоматическая обработка данных')", а также в упражнениях, предлагаемых Кнутом 2).)
Лучшее, что может зачастую сделать программист, оказавшийся в затруднительном положении из-за нехватки памяти,- это отвлечься от своей программы, а потом вернуться назад и пересмотреть свои данные. Представление данных - это сущность программирования