Руководство по стилю программирования и конструированию по
 Скачать 7.6 Mb.
|
|
ГЛАВА 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 Усовершенствование кода 쐽 Как правило, основная часть времени выполнения программы приходится на небольшую часть кода. Не выполнив оценку, вы не найдете этот код. 쐽 Достижение желаемого повышения производительности кода при помощи его оптимизации обычно требует нескольких итераций. 쐽 Во время первоначального кодирования нет лучше способа подготовки к по- вышению производительности программы, чем написание ясного и понятно- го кода, поддающегося легкому изменению. ГЛАВА 25 Стратегии оптимизации кода 595 Г Л А В А 2 6 Методики оптимизации кода Содержание 쐽 26.1. Логика 쐽 26.2. Циклы 쐽 26.3. Изменения типов данных 쐽 26.4. Выражения 쐽 26.5. Методы 쐽 26.6. Переписывание кода на низкоуровневом языке 쐽 26.7. Если что-то одно изменяется, что-то другое всегда остается постоянным Связанные темы 쐽 Стратегии оптимизации кода: глава 25 쐽 Рефакторинг: глава 24 Оптимизация кода уже давно привлекает пристальное внимание программистов. Если вы решили повысить производительность и хотите сделать это на уровне кода (с учетом предупреждений, описанных в главе 25), то можете использовать це- лый ряд методик. Эта глава посвящена в первую очередь повышению быстродействия, но включает и несколько советов по сокращению объема кода. Производительность обычно охватывает и быстродействие, и объем кода, но при необходимости сокращения объема кода обычно лучше прибегнуть к перепроектированию классов и данных, а не к оптимизации кода. Последняя подразумевает небольшие изменения, а не изменения более крупномасштабных аспектов проектирования. В этой главе вы почти не найдете методик, настолько общих, чтобы код приме- ров можно было копировать прямо в другие программы. Я просто хочу проил- люстрировать ряд видов оптимизации кода, которые вы сможете приспособить к своей ситуации. Виды оптимизации, описываемые в этой главе, могут показаться похожими на виды рефакторинга из главы 24, однако помните, что рефакторинг направлен на улуч- http://cc2e.com/2665 596 ЧАСТЬ V Усовершенствование кода шение внутренней структуры программы (Fowler, 1999). То, о чем мы будем гово- рить в этой главе, возможно, лучше называть «антирефакторингом». Эти измене- ния ухудшают внутреннуюю структуру программы ради повышения ее произво- дительности. Это верно по определению. Если бы изменения не ухудшали внут- реннюю структуру, мы не считали бы их видами оптимизации — мы использова- ли бы их по умолчанию и считали стандартными методиками кодирования. Некоторые авторы характеризуют методики оптимизации кода как «практические правила» или приводят данные, го- ворящие о том, что определенный вид оптимизации непре- менно обеспечит желательный результат. Однако, как вы ско- ро увидите, концепция «практических правил» плохо описывает оптимизацию кода. Единственным надежным практическим правилом является оценка результатов каждого вида оптимизации в конкретной среде. Так что в этой главе представлен каталог «вещей, которые стоит попробовать»: многие из них в вашей среде пользы не принесут, но некоторые на самом деле окажутся очень эффективными. 26.1. Логика Многие задачи программирования связаны с манипулиро- ванием логикой программы. В этом разделе мы рассмотрим эффективное использование логических выражений. Прекращение проверки сразу же после получения ответа Допустим, у вас есть выражение: if ( 5 < x ) and ( x < 10 ) then ... Как только вы определили, что x больше 5, вторую часть проверки выполнять не нужно. Некоторые языки поддерживают так называемую «сокращен- ную оценку выражений», при которой компилятор генери- рует код, автоматически прекращающий проверку после получения ответа. Сокращенная оценка выполняется, напри- мер, для стандартных операторов C++ и «условных» опера- торов Java. Если ваш язык не поддерживает сокращенную оценку, избегайте операторов and и or, используя вместо них дополнительную логику. Для сокращенной оценки наш код следовало бы изменить так: if ( 5 < x ) then if ( x < 10 ) then ... Принцип прекращения проверки сразу по получении ответа уместен и в других случаях. В качестве примера можно привести цикл поиска. Если вы сканируете массив введенных чисел и вам нужно только узнать, присутствует ли в массиве отрицательное значение, вы могли бы проверять значения по очереди, устанав- Перекрестная ссылка Оптими- зация кода основана на эврис- тике (см. раздел 5.3). Перекрестная ссылка О сокра- щенной оценке логических выра- жений см. также подраздел «По- нимание правил вычисления логи- ческих выражений» раздела 19.1. Перекрестная ссылка О других аспектах использования опера- торов, определяющих логику программы, см. главы 14–19. ГЛАВА 26 Методики оптимизации кода 597 ливая при обнаружении отрицательного числа флаг negativeFound. Вот как вы- глядел бы такой цикл поиска: Пример, в котором цикл продолжает выполняться даже после получения ответа (C++) negativeInputFound = false; for ( i = 0; i < count; i++ ) { if ( input[ i ] < 0 ) { negativeInputFound = true; } } Лучше было бы прекращать просмотр массива сразу по обнаружении отрицатель- ного значения. Любой из следующих советов привел бы к решению проблемы. 쐽 Включите в код оператор break после строки negativeInputFound = true. 쐽 Если язык не поддерживает оператор break, имитируйте его при помощи опе- ратора goto, передающего управление первой команде, расположенной после цикла. 쐽 Измените цикл for на цикл while и проверяйте значение negativeInputFound вместе с проверкой того, не превысил ли счетчик цикла значение count. 쐽 Измените цикл for на цикл while, поместите сигнальное значение в первый элемент массива, расположенный после последнего исходного значения, а в условии цикла while просто проверяйте, не отрицательно ли значение. По за- вершении цикла узнайте, относится ли индекс обнаруженного отрицательно- го значения к исходному массиву или превышает на 1 индекс верхней грани- цы массива. Подробнее о сигнальных значениях см. ниже. Вот результаты использования ключевого слова break в коде C++ и Java: Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C++ 4,27 3,68 14% Java 4,85 3,46 29% Примечания: (1) Временные показатели в этой и следующих таблицах данной главы ука- зываются в секундах, а их сравнение имеет смысл только в пределах конкретных строк каждой из таблиц. Действительные показатели будут зависеть от компилятора, параметров компи- лятора и среды, в которой выполняется тестирование. (2) Большинство результатов срав- нительного тестирования основано на выполнении фрагментов кода от нескольких тысяч до многих миллионов раз, что призвано устранить колебания результатов. (3) Конкретные марки и версии компиляторов не указываются. Показатели производительности во многом зависят от марки и версии компилятора. (4) Сравнение результатов тестирования фрагментов, написанных на разных языках, имеет смысл не всегда, поскольку компиляторы разных языков не всегда позволяют задать одинаковые параметры генерирования кода. (5) Фрагменты, написанные на интерпретируемых языках (PHP и Python), в большинстве случаев тестиро- вались с использованием более чем в 100 раз меньшего числа тестов, чем фрагменты, на- писанные на других языках. (6) Некоторые из показателей «экономии времени» не совсем точны из-за округления «времени выполнения кода до оптимизации» и «времени выполне- ния оптимизированного кода». 598 ЧАСТЬ V Усовершенствование кода Результаты этого вида оптимизации во многом зависят от числа проверяемых значений и вероятности обнаружения отрицательного значения. В данном тесте число значений в среднем было равным 100, а отрицательные значения состав- ляли половину всех значений. Упорядочение тестов по частоте Упорядочивайте тесты так, чтобы самый быстрый и чаще всего оказывающийся истинным тест выполнялся первым. Нормальные случаи следует обрабатывать первыми, а вероятность выполнения неэффективного кода должна быть низкой. Этот принцип относится к блокам case и цепочкам операторов if-then-else. Рассмотрим, например, оператор Select-Case, обрабатывающий символы, вводимые с клавиатуры: Пример плохо упорядоченного логического теста (Visual Basic) Select inputCharacter Case “+”, “=” ProcessMathSymbol( inputCharacter ) Case “0” To “9” ProcessDigit( inputCharacter ) Case “,”, “.”, “:”, “;”, “!”, “?” ProcessPunctuation( inputCharacter ) Case “ “ ProcessSpace( inputCharacter ) Case “A” To “Z”, “a” To “z” ProcessAlpha( inputCharacter ) Case Else ProcessError( inputCharacter ) End Select Порядок обработки символов в этом фрагменте близок к порядку сортировки ASCII. Однако блоки case во многом похожи на большой набор операторов if-then-else, так что если первым введенным символом будет « a», данный фрагмент проверит, является ли символ математическим символом, числом, знаком пунктуации или пробелом, и только потом определит, что это алфавитно-цифровой символ. Зная примерную вероятность ввода тех или иных символов, вы можете разместить самые вероятные случаи первыми. Вот переупорядоченные блоки case: Пример хорошо упорядоченного логического теста (Visual Basic) Select inputCharacter Case “A” To “Z”, “a” To “z” ProcessAlpha( inputCharacter ) Case “ “ ProcessSpace( inputCharacter ) Case “,”, “.”, “:”, “;”, “!”, “?” ProcessPunctuation( inputCharacter ) Case “0” To “9” ProcessDigit( inputCharacter ) Case “+”, “=” ГЛАВА 26 Методики оптимизации кода 599 ProcessMathSymbol( inputCharacter ) Case Else ProcessError( inputCharacter ) End Select Теперь наиболее вероятные символы обрабатываются первыми, что снижает об- щее число выполняемых тестов. При типичной смеси вводимых символов резуль- таты этого вида оптимизации таковы: Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C# 0,220 0,260 -18% Java 2,56 2,56 0% Visual Basic 0,280 0,260 7% Примечание: тестирование выполнено для ввода, включавшего 78% алфавитых симво- лов, 17% пробелов и 5% знаков пунктуации. С Visual Basic все ясно, а вот результаты тестирования кода Java и C# довольно неожиданны. Очевидно, это объясняется способом структурирования операторов switch-case в языках C# и Java: из-за необходимости перечисления всех значений по отдельности, а не в форме диапазонов, код C# и Java не выигрывает от этого вида оптимизации в отличие от кода Visual Basic. Это доказывает, что никакой из видов оптимизации не следует применять слепо: результаты будут во многом за- висеть от реализации конкретных компиляторов. Вы могли бы предположить, что для аналогичного набора операторов if-then-else компилятор Visual Basic сгенерирует похожий код. Взгляните на результаты: Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C# 0,630 0,330 48% Java 0,922 0,460 50% Visual Basic 1,36 1,00 26% Совершенно иная картина. Те же тесты на Visual Basic теперь выполняются мед- леннее в пять раз без оптимизации и в четыре — в случае оптимизированного кода. Это говорит о том, что для блоков case и операторов if-then-else компилятор ге- нерирует разный код. Результаты оптимизации операторов if-then-else более согласованны, но общая ситуация от этого не проясняется. Обе версии кода C# и Visual Basic, основанно- го на блоках case, выполняются быстрее, чем обе версии кода, написанного на основе if-then-else, тогда как в случае Java все наоборот. Это различие результатов наводит на мысль о третьем виде оптимизации, описанном чуть ниже. Сравнение быстродействия похожих структур логики Описанное выше тестирование можно выполнить и для блоков case, и для опера- торов if-then-else. В зависимости от среды любой из подходов может оказаться более 600 ЧАСТЬ V Усовершенствование кода выгодным. Ниже данные из двух предыдущих таблиц представлены в форме, об- легчающей сравнение быстродействия оптимизированного кода, написанного с применением обоих подходов: Соотношение Язык case if-then-else Экономия времени быстродействия C# 0,260 0,330 –27% 1:1 Java 2,56 0,460 82% 6:1 Visual Basic 0,260 1,00 258% 1:4 Эти результаты не имеют логического объяснения. В одном из языков case гораз- до лучше, чем if-then-else, а в другом наоборот. В третьем языке различие относи- тельно невелико. Можно было бы предположить, что из-за похожего синтаксиса case в C# и Java результаты тестирования этих языков также будут похожими, но на самом деле имеет место обратное. Этот пример ясно показывает, что оптимизация кода не подчиняется ни «прак- тическим правилам», ни «логике». Так что без оценки результатов вам не обойтись. Замена сложных выражений на обращение к таблице Иногда просмотр таблицы может оказаться более быстрым, чем выполнение сложной логической цепи. Суть сложной цепи обычно сводится к категоризации чего-то и выполне- нии того или иного действия, основанного на конкретной категории. Допустим, вы хотите присвоить чему-то номер категории на основе принадлежности этого чего-то к группам A, B и C: Вот как эта задача решается при помощи сложной логической цепи: Пример сложной логической цепи (C++) if ( ( a && !c ) || ( a && b && c ) ) { category = 1; } else if ( ( b && !a ) || ( a && c && !b ) ) { category = 2; } else if ( c && !a && !b ) { category = 3; } else { Перекрестная ссылка Об ис- пользовании таблиц вместо сложной логики см. главу 18. |