Эффективность выполнения программ

Эффективность программы во время выполнения определяется использованием двух ресурсов. Первый из них - необходимое для работы время, а второй — память, которая требуется программе. Время — более важный фактор для программиста, так как в боль­шинстве случаев программа оценивается количеством машинного времени, необходимого для ее выполнения. Обычно проблема памяти существенна только тогда, когда ее недоста­точно.

Оптимизировать память труднее, чем время выполнения. Нет ничего удивительного в том, что после оптимизации программа бу­дет выполняться на 25% быстрее, но было бы необычно получить уменьшение размера используемой ею памяти на 25%; при этом предполагается, что не было допущено серьезных ошибок в перво­начальном варианте программы.

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

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

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

Хорошие приемы программирования приводят к уменьшению как времени выполнения, так и объема используемой памяти, од­нако зачастую улучшение одного из этих факторов происходит за счет ухудшения другого. Большинство из обсуждающихся здесь методов экономит как время, так и память. Если использование метода приводит к возникновению конфликта между временем и памятью, это будет оговорено.

В большинстве случаев небольшое увеличение эффективности не имеет смысла, если оно связано с тратой значительного количе­ства времени на программирование и вызывает ухудшение удобо­читаемости, надежности, универсальности или удобства. Однако иногда это стоит делать. Типичным примером является компиля­тор, при создании которого затрачиваются большие усилия для получения эффективной программы. Но, поскольку компилятор ис­пользуется неоднократно, даже малое увеличение эффективности приносит большие дивиденды. Эффективность также очень важна в библиотеках программ. Поскольку эти программы используются часто, небольшое увеличение эффективности будет, как правило, сокращать время работы машины. В каждом конкретном случае повышение эффективности зави­сит от ряда факторов, таких, как

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

Хорошей считается программа, которая выполняется при ми­нимальном расходе машинного времени. В этом случае за данный отрезок времени можно выполнить еще и другие задания. С появ­лением мультипроцессорной обработки (т. е. выполнением более одного задания за то же время) стало желательным также и ми­нимальное использование памяти, так как при работе в указанном режиме каждая программа должна находиться в оперативной па­мяти. Чем меньший объем памяти требуется каждой программе, тем больше программ можно разместить в оперативной памяти и обработать за одно и то же время. В режиме мультипроцессорной ^обработки использование оперативной памяти так же важно, как и расход времени. Сокращение занимаемой памяти или расхода времени будет уменьшать стоимость выполнения программы. Так как ресурсы машины очень дороги, то экономия даже небольшого количества времени или памяти в многократно используемой про­грамме может вполне стоить затраченных усилий.

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

Оптимизация использования памяти

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

Оверлейность программы

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

Виртуальная память

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

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

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

Советы:

1. Структурированные программы и использование модулей увеличат локализованность.
2. Удаляйте подпрограммы, обрабатывающие исключения, под­программы обработки ошибок и другие редко используемые разделы программы из ее основной части, чтобы увеличить интенсивность обращений к наиболее часто используемым страницам.
3. Присваивайте начальные значения элементам каждого мас­сива данных непосредственно перед первым его использованием, а не перед началом работы программы.
4. Обращайтесь к данным для считывания (или для записи) в порядке их расположения в памяти. Например, если массивы рас­положены в памяти по столбцам, выполните вначале все обращения к одному столбцу, прежде чем перейти к следующему.
5. Данные, не являющиеся массивом, можно разместить рядом, перегруппировав их описания. Лучше всего располагать рядом наиболее часто используемые массивы.

Эквивалентность

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

Этот тип операторов можно применять для экономии памяти, потому что, как правило, в программе имеются переменные, кото­рые используются только в отдельных сегментах программы. Уста­новив эквивалентность массивов, можно сэкономить память, по­этому в программах, требующих большого объема памяти, этому вопросу следует уделить особое внимание. Традиционным спосо­бом сокращения объема памяти является уменьшение размера массивов. Это следует делать до установления эквивалентности двух массивов в памяти. А так как эквивалентность несвязанных переменных может быть неявно выраженной, ее следует соответ­ствующим образом прокомментировать.

Использование циклов

Использование циклов для повторения последовательности опе­раторов является обычным способом экономии памяти. Разные части программ нередко содержат одинаковые последовательности операторов. Если программист стремится к экономному расходованию памяти, он должен найти одинаковые части программы, ко­торые могут быть преобразованы в циклы. Циклы требуют некоторого дополнительного количества памя­ти на инициирование, проверку, изменение индекса и установку всех констант. Однако уменьшение общего объема памяти за счет удаления повторяющихся команд весьма значительно. Не много­кратно повторяющиеся последовательности операторов, требующие сложной организации циклов, часто можно писать последователь­но, а не итеративно.