Лекция десятая Сцилла, Харибда энд компани

(редакция от 17.02.87)

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

'товарищ П. П. Петров!

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

Очень вам благодарен за прекрасные комментарии к модулю suр#воr. Я читал их запоем и разобрался в программе очень быстро. Но дело в том, что разбирался я в программе не для собственного удовольствия. Мне поручено было произвести в ней некоторые изменения. Должен вам заметить, что изменения дались мне с трудом.

Вот, например, вы посчитали, что для числа 'пи' достаточно двух знаков после точки и вставили во все формулы константу 3.14. Может быть, для ваших задач этого достаточно, а для наших нужна точность до 10 знаков. Константа эта встречается в suр#воr достаточно часто, и мне пришлось перебить полтора десятка длинных карт. Ну что бы вам стоило сделать так:

рi=3.14;

а затем бы использовать не 3.14, а рi? Для вас это было бы совсем не обременительно, а мне достаточно было бы изменить всего одну строку. Вот еще пример того же рода. Пресловутая матрица квазиминирелаксации является одним из центральных объектов вашей системы suреr. Исходя из каких-то, мне неизвестных, соображений, вы посчитали, что ее размер - 10 на 10. Так вы ее и объявляете во всех модулях, в которых она используется.

Однако так получилось, что нам потребовалось увеличить ее размер до 20 на 20. Это вызвало гигантскую работу. Во-первых, понадобилось перебить все объявления этого массива, ведь у вас границы всюду были 10!

Во-вторых, более чем в сотне циклов, в которых индекс бежал от 1 до 10, пришлось перебить 10 на 20. Замечу, что не везде в циклах 10 было именно размером матрицы - в некоторых это было просто число 10 как основание десятичной системы.

В-третьих, в некоторых местах вы использовали знание того, что размер матрицы именно 10, и что этот размер именно четный (например, обрабатывая верхнюю часть матрицы, вы делали цикл до 5). Ну и еще кое -что по мелочи.

Хорошо еще, что программа ваша была откомментирована, и я довольно легко отделял зерна от плевел. Но попыхтеть все же пришлось.

Что я могу сказать вам по этому поводу? А вот что (извините, но об этом написано во всех букварях по рl/1): совсем не обязательно об'являть размерности массива как константы. Если же вы беретесь делать программный продукт, то вы должны знать, что существует, например, такой способ (причем не единственный!):

rаzmеr=10;

bеgin;

dсl mаtr(rаzmеr,rаzmеr);

- - - - -

dо nоm=1 tо rаzmеr

; - - - - - -

еnd;

и т.д.

Тогда достаточно изменить всего одну строку, и автоматически перестраиваете весь модуль.

Если же массив передается в качестве параметра, в вызываемом модуле его можно описать просто так:

dсl mаtr(*,*);

а конкретные размеры узнать так:

rаzmеr=dim(mаtr,1);

а дальше, как было показано:

Заметьте, что в этом случае достаточно изменить всего одну строку в одном модуле, и больше не нужно делать ничего! Согласитесь, что такая организация массива не требует от вас сверхъестественных усилий и каких-нибудь жертв. Вы можете сделать хорошее дело, ничем не пожертвовав. Что же вам мешает сделать его?

Должен вам заметить, что такой подход вполне возможен даже на таком пошлом языке, как фортран. Очевидно, что ничто вам не помешает сделать границы массива переменными. Что же касается объявления массива, то вы в главном модуле объявляете его полностью, например, так:

dimеnsiоn mаtr(10,10)

rаzmеr=10

а в программах - условно:

subrоutinе subr(mаtr,rаzmеr)

diмеnsiоn mаtr(1,1)

intеgеr rаzmеr

с mаtr имеет размеры (rаzmеr,rаzmеr)

и все дела.

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

Какие выводы мы должны сделать из этого письма, из этого вопля, вырвавшегося из исстрадавшейся души И.И. Иванова?

Самый общий вывод такой: не следует относиться к программе как к чему-то сделанному на века. Если вы рассчитываете на широкую популярность и долгую жизнь вашей программы, вы уже при написании должны учесть тот факт, что она будет не раз изменяться и адаптироваться.

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

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

Это общие соображения. Конкретное же сказал нам И.И. Иванов: нужно избегать использования констант, избегать лишнего знания (например, знания четности размера матрицы: в общем случае этот размер любой, но в конкретном - четный). Кроме того, внутри модуля нужно использовать хорошо знакомое нам правило 'разделяй и властвуй': модуль должен состоять из независимых сегментов, максимально прочных и минимально сцепленных; то, что это правило обеспечивает изменяемость на уровне межмодульных связей, я надеюсь, вы еще помните.

Итак, с этим вопросом мы покончили, и сегодня на повестке дня еще один: эффективность.

Во время оно, как я уже неоднократно говорил вам, эффективность программы была едва ли не единственным ее козырем. Машин было мало, и были они весьма маломощны. Хочешь, не хочешь, а приходилось втискивать всю программу вместе с данными в какой-нибудь килобайт памяти, поскольку другого килобайта не было. Быстродействие же тогдашних машин едва ли превышало быстродействие нынешних калькуляторов. Все это приводило к тому, что процветали методы, безусловно порочные с нынешних позиций: модификация программы во время выполнения, хранение нескольких переменных в одной ячейке и использование одной переменной с разным смыслом, общие области и прочая уголовщина. Многие из этих методов переползли в языки программирования - тогдашние программисты были не в силах с ними расстаться. Особенно богат ими фортран; на нем можно делать почти все из того, что ни в коем случае не следует делать.

Со временем, однако, машины стремительно дешевели, мощность их увеличилась, и овчинка перестала стоить выделки. новые программисты ударились в другую крайность - они вообще перестали заботиться об эффективности, в результате чего их машины 70 процентов времени занимаются ненужной работой. это особенно хорошо заметно на конкурсах программистов, когда человек пятьдесят решают одну и ту же задачу, и вот лучшие программы выдают результат через 2 секунды, худшие через несколько часов, а в основном все укладываются минут в пять.

Я думаю, вам интересно будет услышать историю моих собственных отношений с эффективностью. Я считаю ее поучительной. У меня было тяжелое прошлое: начинал я с машины ПРОМИНЬ. Была такая табуретка с лампочками: сто ячеек памяти под данные и сто дырок для штекеров с командами. Для своего времени это была неплохая машина, но я не скоро избавился от привычек, приобретенных при работе с ней. Сразу с 'проминь' я попал на ЕС, по нынешним меркам совершенно куцую - всего 128 килобайт памяти и два дисковода по 7 мегабайт. Так вот, я как Плюшкин, имея сотню килобайтов в полном владении, константы хранил только в полуслове, а вместо s 5,=f'1' писал bсtr 5,0. Ничего, что bсtr на самом деле - команда перехода: при таком использовании она на самом деле команда вычитания, да к тому же на 2 байта короче, да еще и не нуждается в четырехбайтовой константе.

Это еще не все. Проектируя базу данных системы ДЕЛЬТА мы утрамбовали данные по границе полубайта. Полубайта! И это лишь от того, что процентов 20 данных были целочисленными, и значения их не превышали 16. Можете себе представить, сколько труда нужно было приложить, чтобы затолкать в запись символьное поле, сдвинутое на полбайта! Пожалуй, треть команд первой версии ДЕЛЬТЫ занималась только тем, что добывала данные, вытаскивала их по биту или же по биту запихивала их обратно. О модульном программировании мы тогда не слыхали, и каждый работал с базой данных по своему разумению.

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

Современное отношение к эффективности можно выразить тремя принципами:

1. Оптимизировать надо по крупному, еще на этапе алгоритмизации. То, что не сумел сэкономить на алгоритме, не нагонишь никакими ухищрениями кодирования.

2. Оптимизировать нужно в пределах, указанных в проектной документации. Скажем, в АС, если мы вписались для средних размеров дубля и эталона в 1 минуту процессора и 90К памяти, то проблема решена, и дальнейшая оптимизация уже не оправдана.

3. Оптимизировать нужно не в ущерб другим целям. всегда следует помнить об иерархии целей, описанной в техзадании. Если понятность важнее эффективности, нельзя оптимизировать в ущерб понятности - это означало бы противоречие требованиям заказчика.

Сейчас мы разберем с вами некоторые типичные методы повышения эффективности. Обратите внимание, что почти всегда увеличения быстродействия требует увеличения памяти, и наоборот. Это один из золотых законов программирования: выигрывая в скорости, платишь памятью, и наоборот: выигрывая память, платишь скоростью.

Этюд первый: о модулях.

Несомненно, разбиение программы на независимые модули дает возможность резко увеличить эффективность, хотя программисты, 'экономящие на спичках', говорят, что на вызов подпрограмм требуется лишняя память и время. Однако в результате разбиения системы на модули мы можем дифференцировать и оптимизацию. Скажем, в модуле обработки параметров нашего АС мы вряд ли что-то сможем выиграть на эффективность, так как модуль этот вызываем редко и не в цикле. А вот требования к модулю доступа к дублю/эталону весьма жесткие: строки требуются часто, и если мы организуем быстрый доступ к строке, то, поработав всего над одним модулем, мы резко увеличим быстродействие всей системы! И, если мы впишемся в 90к и минуту только за счет модуля доступа, остальные модули можно не оптимизировать вообще! Мораль: хорошее разбиение на модули позволяет выявить и ликвидировать узкие места системы.

Этюд второй: о наложениях.

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

Этюд третий: о блокировании.

На магнитных лентах блоки разделяются промежутком 1,5-2 миллиметра. Запись длиною 80 байт занимает 2,5 миллиметра. Это означает, что, если длина блока у вас 80 байт, на ленте вы будете хранить в основном межблочные промежутки, а не полезную информацию. Если в блоке хранить не одну запись, а 10 и организовать выборку и помещение записи в блок, то мы одним махом увеличиваем емкость магнитных носителей и скорость считывания, зато платим оперативной памятью. Мы можем выбрать размер блока так, чтобы расход памяти был в разумных пределах.

Примечание. На дисках картина та же самая.

Этюд четвертый: о циклах.

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

dо i1=...

нечто1

dо i2=...

нечто2

.......

dо i15=...

нечто15,

то вы мало что выиграете, оптимизируя нечто1, но даже минимальная оптимизация нечто15 может резко повысить эффективность. Прежде всего нужно вынести за пределы этого цикла все, что можно делать не внутри этого цикла.

Этюд последний: о том, как изобрели колесо.

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

Имеется колесо обозрения из n кресел. Мы сажаем м человек на к-е свободное место. В конце мы должны напечатать номера кресел, оставшихся свободными.

Нерадивый программист не найдет ничего лучшего, как завести массив из n элементов и отмечать в нем занятые места. Алгоритм сложный и медленный, так как нужно уметь перейти от конца массива в начало, и по каждому элементу мы вынуждены пробегать с проверкой.

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

По массиву мы идем не с шагом 1, а берем номер следующего элемента из текущего элемента массива. Это, кстати, начисто убирает проблему перехода в начало массива. Когда мы занимаем кресло, мы его исключаем. В следующем цикле мы с 4 кресла попадаем сразу на 6.

Вот и все. Остается сделать два цикла - внешний по м и внутренний, отсчитав к 'прыжков' через кресла. Алгоритм простой и тем не менее стремительный.

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

На оглавление


© Алексей Бабий 1980-1986