Совершенный код. Совершенный код. Мастер-класс. Стив Макконнелл. Руководство по стилю программирования и конструированию по
 Скачать 5.88 Mb.
|
|
ГЛАВА 25 Стратегии оптимизации кода 587 Табл. 25-2. (продолжение) Относительное время выполнения Операция Пример C++ Java Операции над целочислен ными переменными Целочисленное присваивание i = j 1 1 (локальная операция) Целочисленное присваивание i = j 1 1 (унаследованная операция) Сложение i = j + k 1 1 Вычитание i = j % k 1 1 Умножение i = j * k 1 1 Деление i = j \ k 5 1,5 Операции над переменными с плавающей запятой Присваивание x = y 1 1 Сложение x = y + z 1 1 Вычитание x = y % z 1 1 Умножение x = y * z 1 1 Деление x = y / z 4 1 Трансцендентные функции Извлечение квадратного корня x = sqrt( y ) 15 4 из числа с плавающей запятой Вычисление синуса числа x = sin( y ) 25 20 с плавающей запятой Вычисление логарифма числа x = log( y ) 25 20 с плавающей запятой Вычисление экспоненты числа x = exp( y ) 50 20 с плавающей запятой Операции над массивами Обращение к массиву целых чи# i = a[ 5 ] 1 1 сел с использованием константы Обращение к массиву целых чисел i = a[ j ] 1 1 с использованием переменной Обращение к двумерному i = a[ 3, 5 ] 1 1 массиву целых чисел с исполь# зованием констант Обращение к двумерному i = a[ j, k ] 1 1 массиву целых чисел с исполь# зованием переменных Обращение к массиву чисел x = z[ 5 ] 1 1 с плавающей запятой с исполь# зованием константы Обращение к массиву чисел x = z[ j ] 1 1 с плавающей запятой с исполь# зованием целочисленной переменной ( см. след. стр.) 588 ЧАСТЬ V Усовершенствование кода Табл. 25-2. (окончание) Относительное время выполнения Операция Пример C++ Java Обращение к двумерному x = z[ 3, 5 ] 1 1 массиву чисел с плавающей запятой с использованием констант Обращение к двумерному x = z[ j, k ] 1 1 массиву чисел с плавающей запятой с использованием целочисленных переменных Примечание: показатели, приведенные здесь, сильно зависят от локальной среды, компилятора и выполняемых компилятором видов оптимизации. Результаты, указанные для языков C++ и Java, нельзя сравнивать непосредственно. С момента выхода первого издания этой книги относительное быстродействие отмеченных операций значительно изменилось, так что, если вы все еще подхо# дите к оптимизации кода, опираясь на идеи 10#летней давности, пересмотрите свои взгляды. Большинство частых операций — в том числе вызовы методов, присваивание, ариф# метические операции над целыми числами и числами с плавающей запятой — имеет примерно одинаковую цену. Трансцендентные математические функции очень дороги. Вызовы полиморфных методов чуть дороже вызовов других методов. Табл. 25#2 или похожая таблица, которую вы можете создать сами, — ключ, от# крывающий все двери в мир быстрого кода, описанные в главе 26. В каждом слу# чае повышение быстродействия исходит из замены дорогой операции на более дешевую (см. главу 26). 25.4. Оценка производительности На небольшие фрагменты программы обычно приходится непропорционально большая доля времени ее выполнения, поэтому перед оптимизацией кода вам следует оценить его и найти в нем горячие точки. Обнаружив горячие точки и оптимизировав их, снова оцените код, чтобы узнать, насколько вы его улучшили. Многие аспекты производительности противоречат интуиции. Выше я уже при# вел один пример этого, когда 10 строк кода оказались в итоге значительно быст# рее и компактнее, чем одна строка. Опыт также не особо полезен при оптимизации. Опыт может быть ос# нован на использовании старого компьютера, языка или компилятора, но когда что#либо из этого изменяется, все начинается сначала. Невоз# можно точно сказать, каковы результаты оптимизации, не оценив их. Много лет назад я написал программу, суммирующую элементы матрицы. Перво# начальный код выглядел примерно так: ГЛАВА 25 Стратегии оптимизации кода 589 Пример простого кода, суммирующего элементы матрицы (C++) sum = 0; for ( row = 0; row < rowCount; row++ ) { for ( column = 0; column < columnCount; column++ ) { sum = sum + matrix[ row ][ column ]; } } Как видите, код был прост, но суммирование элементов матрицы должно было выполняться как можно быстрее, а я знал, что все обращения к массиву и проверки условий цикла довольно дороги. Я знал, что при каждом обращении к двумерному масси# ву выполняются дорогие операции умножения и сложения. Так, обработка мат# рицы размером 100 на 100 требовала 10 000 умножений и сложений, что допол# нялось еще и затратами, связанными с управлением циклами. Использовав указа# тели, рассудил я, я смогу просто увеличивать указатель, заменив 10 000 дорогих умножений на 10 000 относительно дешевых операций инкремента. Я тщательно преобразовал код и получил: Пример попытки оптимизации кода, суммирующего элементы матрицы (C++) sum = 0; elementPointer = matrix; lastElementPointer = matrix[ rowCount 1 ][ columnCount 1 ] + 1; while ( elementPointer < lastElementPointer ) { sum = sum + *elementPointer++; } Хотя код стал менее удобочитаемым, особенно для программистов, не являющихся экспертами в C++, я был очень доволен собой. Оно и понятно: все#таки я изба# вился от 10 000 умножений и многих операций, связанных с управлением цикла# ми! Я был так доволен, что решил подкрепить свои чувства конкретными цифра# ми и оценить повышение скорости, хотя в то время я выполнял это не всегда. Знаете, что я обнаружил? Никакого улучшения. Ни для мат# риц размером 100 на 100. Ни для матриц размером 10 на 10. Ни для каких#либо других матриц. Я был так разочаро# ван, что погрузился в ассемблерный код, сгенерированный компилятором, чтобы понять, почему моя оптимизация не сработала. К моему удивлению, оказалось, что я был не пер# вым, кому понадобилось перебирать элементы массива: ком# пилятор сам преобразовывал обращения к массиву в опе# рации над указателями. Я понял, что единственным резуль# татом оптимизации, в котором можно быть полностью уверенным без измерения производительности, является затруднение чтения кода. Если оценка эффектив# ности не оправдывает себя, не стоит приносить понятность кода в жертву сомни# тельному повышению производительности. Дополнительные сведения Джон Бентли описывает похожий слу- чай, когда переписывание кода с использованием указателей снизило производительность примерно на 10%. В другой си- туации этот же подход повысил производительность более чем на 50%. См. «Software Explora- torium: Writing Efficient C Prog- rams» (Bentley, 1991). Ни один программист никогда не мог предсказать или обнару- жить узкие места, не обладая данными. Что бы вы ни дума- ли, реальность окажется совер- шенно другой. Джозеф М. Ньюкамер (Joseph M. Newcomer) 590 ЧАСТЬ V Усовершенствование кода Оценка должна быть точной Оценка производительности должна быть точной. Измере# ние времени выполнения программы с помощью секундо# мера или путем подсчета «один слон, два слона, три слона» точным не является. Используйте инструменты профилиро# вания или системный таймер и методы, регистрирующие истекшее время выполнения операций. Используете ли вы инструмент, написанный другим программистом, или пишете для оценки производительности программы собственный код, убедитесь, что из# меряете время выполнения только того оптимизируемого кода. Опирайтесь на число тактов процессора, выделенных вашей программе, а не на время суток. Иначе при переключении системы с вашей программы на другую программу один из ваших методов будет оштрафован на время, выделенное другой программе. Кро# ме того, попытайтесь исключить влияние процесса оценки кода и запуска про# граммы на первоначальный и оптимизированный код. 25.5. Итерация Обнаружив в коде узкое место и попробовав его устранить, вы удивитесь, насколько можно повысить производительность кода путем его оптимизации. Единственная методика редко приводит к десятикратному улучшению, но методики можно эф# фективно комбинировать, поэтому даже после обнаружения одного удачного вида оптимизации продолжайте пробовать другие виды. Однажды я написал программную реализацию алгоритма Data Encryption Standard (DES). Ну, на самом деле я писал ее не один раз, а около тридцати. При шифрова# нии по алгоритму DES цифровые данные кодируются так, что их нельзя расшиф# ровать без правильного пароля. Этот алгоритм шифрования так хитер, что иног# да кажется, что он сам зашифрован. Моя цель состояла в том, чтобы файл объе# мом 18 кб шифровался на IBM PC за 37 секунд. Первая реализация алгоритма вы# полнялась 21 минуту 40 секунд, так что мне предстояла долгая работа. Хотя большинство отдельных видов оптимизации было незначительно, в сумме они привели к впечатляющим результатам. Никакие три или даже четыре вида оптимизации не позволили бы мне достичь цели, однако итоговая их комбина# ция оказалась эффективной. Мораль: если копать достаточно глубоко, можно до# биться подчас неожиданных результатов. Оптимизация алгоритма DES — самая агрессивная оптими# зация, которую я когда#либо проделывал. В то же время я никогда не создавал более непонятного и трудного в сопро# вождении кода. Первоначальный алгоритм был сложен. Код, получившийся в результате трансформаций высокоуровневого кода, оказался практически нечитаемым. После преобразования кода на ассемблер я получил один метод из 500 строк, на который боюсь даже смотреть. Это отношение между оп# тимизацией кода и его качеством справедливо почти всегда. Вот таблица, отра# жающая историю оптимизации: Перекрестная ссылка Методи- ки, указанные в этой таблице, обсуждаются в главе 26. Перекрестная ссылка Об инст- рументах профилирования см. подраздел «Оптимизация кода» раздела 30.3. ГЛАВА 25 Стратегии оптимизации кода 591 Вид оптимизации Время выполнения Улучшение Первоначальная реализация 21:40 Преобразование битовых полей в массивы 7:30 65% Развертывание самого внутреннего цикла for 6:00 20% Удаление перестановок 5:24 10% Объединение двух переменных 5:06 5% Использование логического тождества 4:30 12% для объединения первых двух этапов алгоритма DES Объединение областей памяти, используемых 3:36 20% двумя переменными, для сокращения числа операций над данными во внутреннем цикле Объединение областей памяти, используемых 3:09 13% двумя переменными, для сокращения числа операций над данными во внешнем цикле Развертывание всех циклов и использование 1:36 49% литералов для индексации массива Удаление вызовов методов и встраивание 0:45 53% всего кода Переписывание всего метода на ассемблере 0:22 51% Итог 0:22 98% Примечание: постепенный процесс оптимизации, описанный в этой таблице, не под# разумевает, что все виды оптимизации эффективны. Я мог бы указать массу других ви# дов, приводивших к удвоению времени выполнения. Минимум две трети видов оптими# зации, которые я попробовал, оказались неэффективными. 25.6. Подход к оптимизации кода: резюме Рассматривая целесообразность оптимизации кода, придерживайтесь следующе# го алгоритма: 1. Напишите хороший и понятный код, поддающийся легкому изменению. 2. Если производительность вас не устраивает: a. сохраните работоспособную версию кода, чтобы позднее вы могли вернуться к «последнему нормальному состоянию»; b. оцените производительность системы с целью нахождения горячих точек; c. узнайте, обусловлено ли плохое быстродействие неадекватным проектом, не# верными типами данных или неудачными алгоритмами и определите, умест# на ли оптимизация кода; если оптимизация кода неуместна, вернитесь к п. 1; d. оптимизируйте узкое место, определенное на этапе (c); e. оцените каждое улучшение по одному за раз; f. если оптимизация не привела к улучшению кода, вернитесь к коду, сохра# ненному на этапе (a) (как правило, более чем в половине случаев попытки оптимизации будут приводить лишь к незначительному повышению про# изводительности или к ее снижению). 3. Повторите процесс, начиная с п. 2. 592 ЧАСТЬ V Усовершенствование кода Дополнительные ресурсы В этом разделе я указал работы, посвященные повышению производительности в общем. Книги, в которых обсуждаются специфические методики оптимизации кода, указаны в раз# деле «Дополнительные ресурсы» в конце главы 26. Производительность Smith, Connie U. and Lloyd G. Williams. Performance Solutions: A Practical Guide to Creating Responsive, Scalable Software. Boston, MA: Addison#Wesley, 2002. В этой книге обсуждается создание высокопроизводительного ПО, предусматривающее обеспечение нужной произво# дительности на всех этапах разработки. В ней вы найдете много примеров и кон# кретных случаев, относящихся к программам нескольких типов, а также конкрет# ные рекомендации по повышению производительности Web#приложений. Особое внимание в книге уделяется масштабируемости программ. Newcomer, Joseph M. Optimization: Your Worst Enemy. May 2000, www.flounder.com/optimization.htm. В этой статье, принадле# жащей перу опытного системного программиста, описыва# ются разные ловушки, в которые вы можете попасть, используя неэффективные стратегии оптимизации. Алгоритмы и типы данных Knuth, Donald. The Art of Computer Programming, vol. 1, Fundamental Algorithms, 3d ed. Reading, MA: Addison#Wesley, 1997. Knuth, Donald. The Art of Computer Programming, vol. 2, Seminumerical Algorithms, 3d ed. Reading, MA: Addison#Wesley, 1997. Knuth, Donald. The Art of Computer Programming, vol. 3, Sorting and Searching, 2d ed. Reading, MA: Addison#Wesley, 1998. Это три первых тома серии, которая по первоначальному замыслу автора должна включить семь томов. В этих несколько пугающих книгах алгоритмы описываются не только на обычном языке, но и с использованием математической нотации, или MIX — языка ассемблера для воображаемого компьютера MIX. Кнут подроб# нейшим образом описывает огромное число вопросов, и, если вы испытываете сильный интерес к конкретному алгоритму, лучшего ресурса вам не найти. Sedgewick, Robert. Algorithms in Java, Parts 1%4, 3d ed. Boston, MA: Addison#Wesley, 2002. В четырех частях этой книги исследуются лучшие методы решения широ# кого диапазона проблем. В число тем книги входят фундаментальные сведения, сортировка, поиск, реализация абстрактных типов данных и более сложные во# просы. В книге Седжвика Algorithms in Java, Part 5, 3d ed. (Sedgewick, 2003) обсуж# даются алгоритмы, основанные на графах. Книги Algorithms in C++, Parts 1%4, 3d ed. (Sedgewick, 1998), Algorithms in C++, Part 5, 3d ed. (Sedgewick, 2002), Algorithms in C, Parts 1%4, 3d ed. (Sedgewick, 1997) и Algorithms in C, Part 5, 3d ed. (Sedgewick, 2001) организованы похожим образом. Седжвик имеет степень доктора филосо# фии и в свое время был учеником Кнута. http://cc2e.com/2592 http://cc2e.com/2599 http://cc2e.com/2585 ГЛАВА 25 Стратегии оптимизации кода 593 Контрольный список: стратегии оптимизации кода Производительность программы в общем Рассмотрели ли вы возможность повышения производи- тельности посредством изменения требований к программе? Рассмотрели ли вы возможность повышения производительности путем изменения проекта программы? Рассмотрели ли вы возможность повышения производительности путем изменения проектов классов? Рассмотрели ли вы возможность повышения производительности путем сокращения объема взаимодействия с ОС? Рассмотрели ли вы возможность повышения производительности путем устранения операций ввода/вывода? Рассмотрели ли вы возможность повышения производительности путем использования компилируемого языка вместо интерпретируемого? Рассмотрели ли вы возможность повышения производительности путем видов оптимизации, поддерживаемых компилятором? Рассмотрели ли вы возможность повышения производительности путем перехода на другое оборудование? Рассматриваете ли вы оптимизацию кода только как последнее средство? Подход к оптимизации кода Убедились ли вы в полной корректности программы перед началом оптими- зации кода? Нашли ли вы узкие места в коде перед началом его оптимизации? Оцениваете ли вы результаты выполнения каждого вида оптимизации кода? Отменяете ли вы изменения, которые не привели к ожидаемому улучшению? Пробуете ли вы несколько способов оптимизации каждого узкого места, т. е. используете ли вы итерацию? Ключевые моменты Производительность — всего лишь один из аспектов общего качества ПО, и, как правило, не самый важный. Оптимизация кода — лишь один из способов повышения производительности ПО, и тоже обычно не самый важный. Быст# родействие программы и ее объем обычно в большей степени зависят не от эффективности кода, а от архитектуры программы, детального проектирова# ния выбора структур данных и алгоритмов. Важнейшее условие максимизации быстродействия кода — его количествен# ная оценка. Она необходима для обнаружения областей, производительность которых действительно нуждается в повышении, а также для проверки того, что в результате оптимизации производительность повысилась, а не пони# зилась. http://cc2e.com/2506 594 ЧАСТЬ V Усовершенствование кода Как правило, основная часть времени выполнения программы приходится на небольшую часть кода. Не выполнив оценку, вы не найдете этот код. Достижение желаемого повышения производительности кода при помощи его оптимизации обычно требует нескольких итераций. Во время первоначального кодирования нет лучше способа подготовки к по# вышению производительности программы, чем написание ясного и понятно# го кода, поддающегося легкому изменению. |