Руководство по стилю программирования и конструированию по
 Скачать 7.6 Mb.
|
|
ГЛАВА 26 Методики оптимизации кода 621 и требует преобразований типов. Во втором случае преобразования типов не нужны: x = 3.14 i = 5 Результаты в очередной раз указывают на большие различия между компиляторами: Время выполнения Время выполнения оптимизированного Экономия Соотношение Язык кода до оптимизации кода времени быстродействия C++ 1,11 0,000 100% Не поддается измерению C# 1,49 1,48 <1% 1:1 Java 1,66 1,11 33% 1,5:1 Visual Basic 0,721 0,000 100% Не поддается измерению PHP 0,872 0,847 3% 1:1 Предварительное вычисление результатов При низкоуровневом проектировании часто приходится решать, вычислять ли результаты по ходу дела или лучше вычислить их один раз, сохранить и извле- кать по мере надобности. Если результаты используются много раз, второй вари- ант часто предпочтительнее. Этот выбор проявляется несколькими способами. На самом простом уровне вы можете вычислить часть выражения вне цикла вместо того, чтобы вычислять его внутри. Пример этого я приводил выше. На более сложном уровне вы можете вычислить табличные данные один раз при запуске программы и использовать их позднее; вы также можете сохранить результаты в файле данных или встроить их в программу. Например, работая над игрой «звездные войны», програм- мисты сначала вычисляли коэффициенты гравитации для разных расстояний от Солнца. Эти вычисления были ресур- соемкими и снижали производительность программы. Од- нако число разных расстояний, используемых в игре, было небольшим, поэтому разработчики в итоге вычислили коэффициенты гравитации предварительно и сохранили их в массиве из 10 элементов. Получение коэффициентов из массива оказалось гораздо более быстрым, чем их вычисление. Допустим, у вас есть метод, вычисляющий сумму, которую нужно уплатить при погашении ссуды на покупку автомобиля. Код подобного метода мог бы выгля- деть так: Пример сложного выражения, которое можно вычислить предварительно (Java) double ComputePayment( long loanAmount, int months, Перекрестная ссылка Об исполь- зовании табличных данных вме- сто сложной логики см. главу 18. 622 ЧАСТЬ V Усовершенствование кода double interestRate ) { return loanAmount / ( ( 1.0 - Math.pow( ( 1.0 + ( interestRate / 12.0 ) ), -months ) ) / ( interestRate / 12.0 ) ); } Формула вычисления платежей по ссуде сложна и довольно дорога. Помещение информации в таблицу, наверное, сделало бы вычисление более дешевым. Насколько крупной была бы эта таблица? Переменной с наибольшим диапазоном является переменная loanAmount. Переменная interestRate может принимать зна- чения от 5% до 20% с шагом 0,25%, что дает нам 61 значение. Переменная months может иметь значение от 12 до 72, или 61 значение. Значение переменной loan- Amount, вероятно, может находиться в пределах от 1000 до 100 000 долларов, и вам едва ли удастся сохранить все эти значения в таблице. Однако большая часть выражения не зависит от loanAmount, поэтому параметры действительно отвратительной части (знаменатель более крупного выражения) можно сохранить в таблице, индексируемой значениями interestRate и months. Значение loanAmount нужно будет вычислять: Пример предварительного вычисления сложного выражения (Java) double ComputePayment( long loanAmount, int months, double interestRate ) { Новая переменная interestIndex используется как индекс массива loanDivisor. int interestIndex = Math.round( ( interestRate - LOWEST_RATE ) * GRANULARITY * 100.00 ); return loanAmount / loanDivisor[ interestIndex ][ months ]; } Итак, сложное вычисление мы заменили вычислением индекса массива и одним обращением к массиву. К чему же это привело? Время выполнения Время выполнения оптимизированного Экономия Соотношение Язык кода до оптимизации кода времени быстродействия Java 2,97 0,251 92% 10:1 Python 3,86 4,63 –20% 1:1 В зависимости от обстоятельств вы должны были бы предварительно вычислять массив loanDivisor при инициализации программы или читать его из файла. Вы также могли бы инициализировать массив нулями, вычислять каждый элемент при его первом запросе, сохранять его, а впоследствии просто извлекать из массива. Это было бы одной из форм кэширования, которое обсуждалось выше. > ГЛАВА 26 Методики оптимизации кода 623 Предварительное вычисление выражения не обязывает вас создавать таблицу — возможен и иной вариант. Допустим, у вас есть код, вычисляющий взносы, кото- рые нужно уплатить при погашении ссуд на разную сумму: Пример второго сложного выражения, которое можно вычислить предварительно (Java) double ComputePayments( int months, double interestRate ) { for ( long loanAmount = MIN_LOAN_AMOUNT; loanAmount < MAX_LOAN_AMOUNT; loanAmount++ ) { payment = loanAmount / ( ( 1.0 – Math.pow( 1.0+(interestRate/12.0), - months ) ) / ( interestRate/12.0 ) ); Следующий код делал бы что-то с переменной payment; что именно — в данном примере не важно. } } Даже без таблицы, вы можете предварительно вычислить сложную часть выраже- ния вне цикла и использовать найденное значение внутри цикла: Пример предварительного вычисления второго сложного выражения (Java) double ComputePayments( int months, double interestRate ) { long loanAmount; Предварительное вычисление части выражения. double divisor = ( 1.0 – Math.pow( 1.0+(interestRate/12.0). - months ) ) / ( interestRate/12.0 ); for ( long loanAmount = MIN_LOAN_AMOUNT; loanAmount <= MAX_LOAN_AMOUNT; loanAmount++ ) { payment = loanAmount / divisor; } } Этот вид оптимизации похож на уже рассмотренные нами методики, предпола- гающие вынесение обращений к массиву и разыменований указателей за преде- лы цикла. Результаты оптимизации кода Java в данном случае сравнимы с резуль- татами предыдущего вида оптимизации, основанного на предварительном вычис- лении табличных данных: > > 624 ЧАСТЬ V Усовершенствование кода Время выполнения Время выполнения оптимизированного Экономия Соотношение Язык кода до оптимизации кода времени быстродействия Java 7,43 0,24 97% 30:1 Python 5,00 1,69 66% 3:1 В отличие от первой попытки оптимизации быстродействие кода Python сейчас также выросло. Это происходит довольно часто: если один вид оптимизации не приводит к желаемым результатам, другой, казалось бы, аналогичный вид оказы- вается очень эффективным. Оптимизация программы путем предварительного вычисления выражений име- ет несколько вариантов: 쐽 вычисление результатов до выполнения программы и связывание их с констан- тами во время компиляции; 쐽 вычисление результатов до выполнения программы и присвоение их перемен- ным, используемым в период выполнения; 쐽 вычисление результатов до выполнения программы и сохранение их в файле, загружаемом в период выполнения; 쐽 однократное вычисление результатов при запуске программы и их использо- вание во всех последующих случаях; 쐽 вычисление как можно большего числа значений до начала цикла, позволяю- щее свести к минимуму объем работы, выполняемой внутри цикла; 쐽 вычисление результатов при возникновении первой потребности в них и их сохранение, позволяющее получить результаты, когда они понадобятся снова. Устранение часто используемых подвыражений Если какое-то выражение повторяется в коде несколько раз, присвойте его зна- чение переменной и используйте переменную вместо вычисления выражения в нескольких местах. Подвыражение, которое можно устранить, уже встречалось нам в предыдущем подразделе: Пример часто используемого подвыражения (Java) payment = loanAmount / ( ( 1.0 – Math.pow( 1.0 + ( interestRate / 12.0 ), - months ) ) / ( interestRate / 12.0 ) ); Вместо двукратного вычисления выражения interestRate/12.0 вы можете присво- ить его переменной и обратиться к ней два раза. Если вы присвоите переменной удачное имя, этот вид оптимизации не только повысит производительность кода, но и улучшит его удобочитаемость. Вот оптимизированный код: Пример устранения часто используемого подвыражения (Java) monthlyInterest = interestRate / 12.0; payment = loanAmount / ( ГЛАВА 26 Методики оптимизации кода 625 ( 1.0 – Math.pow( 1.0 + monthlyInterest, - months ) ) / monthlyInterest ); Результаты не впечатляют: Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени Java 2,94 2,83 4% Python 3,91 3,94 –1% По-видимому, метод Math.pow() настолько дорог, что он перекрывает выгоду уст- ранения подвыражения. Возможно также, что подвыражение уже было устранено компилятором. Если бы подвыражение составляло не такую малую часть стоимо- сти всего выражения или если бы оптимизатор компилятора был менее эффек- тивен, этот вид оптимизации, наверное, оказал бы большее влияние на произво- дительность. 26.5. Методы Одним из самых эффективных способов оптимизации кода является грамотная декомпозиция программы на методы. Небольшие, хорошо определенные методы делают програм- му компактнее, устраняя повторяющиеся фрагменты кода. Они упрощают опти- мизацию, потому что рефакторинг одного метода улучшает все методы, которые его вызывают. Небольшие методы относительно легко переписать на низкоуров- невом языке. Объемные хитроумные методы понять сложно, а после переписы- вания их на низкоуровневом языке вроде ассемблера это вообще невыполнимо. Встраивание методов На заре программирования вызывать методы на некоторых компьютерах было крайне дорого. Вызов метода означал, что ОС должна выгрузить программу, за- грузить каталог методов, загрузить конкретный метод, выполнить метод, выгру- зить метод и снова загрузить вызвавший метод. Все это потребляло много ресур- сов и замедляло программу. Современные компьютеры облагают вызовы методов гораздо меньшей пошлиной. Например, встраивание метода копирования строк приводит к таким результатам: Время выполнения Время выполнения Экономия Язык метода встроенного кода времени C++ 0,471 0,431 8% Java 13,1 14,4 –10% В некоторых случаях вы можете сэкономить несколько наносекунд, встроив код метода в программу, используя ключевое слово inline языка C++ или аналогичную возможность. Если ваш язык не поддерживает inline непосредственно, но имеет препроцессор макросов, вы можете встраивать код при помощи макроса, вклю- чая и выключая встраивание по требованию. Однако современные компьютеры Перекрестная ссылка Об исполь- зовании методов см. главу 7. 626 ЧАСТЬ V Усовершенствование кода (под «современными» я понимаю любые машины, с которыми вы можете столк- нуться в своей работе), при вызове метода почти не тратят дополнительных ре- сурсов. Как показывает пример, встроив код, вы можете как улучшить производи- тельность, так и ухудшить ее. 26.6. Переписывание кода на низкоуровневом языке Давняя мудрость, которую не стоит оставлять без внимания, гласит, что при низ- ком быстродействии код следует переписать на языке низкого уровня. Если вы пишете на C++, языком низкого уровня может быть ассемблер, если на Python — C. Переписывание кода на низкоуровневом языке обычно положительно влияет и на быстродействие кода, и на его объем. Типичный подход к оптимизации при помощи низкоуровневого языка таков. 1. Напишите все приложение на высокоуровневом языке. 2. Выполните полное тестирование приложения и проверьте его корректность. 3. Если производительность недостаточна, выполните про- филирование приложения с целью выявления горячих то- чек. Так как около 50% времени выполнения программы обычно приходится примерно на 5% кода, горячими точ- ками обычно будут небольшие фрагменты программы. 4. Перепишите несколько небольших фрагментов на низ- коуровневом языке для повышения общей производительности программы. Последуете ли вы по этому проторенному пути, зависит от того, насколько хоро- шо вы программируете на низкоуровневых языках, насколько хорошо проблема подходит для решения на низкоуровневом языке, а также от степени вашего от- чаяния. Сам я впервые применил эту методику при реализации алгоритма Data Encryption Standard, о чем я упоминал в главе 25. Я перепробовал все виды опти- мизации, о которых когда-либо слышал, но программа все равно работала вдвое медленнее, чем нужно. Мне ничего не оставалось делать, кроме как переписать часть программы на ассемблере. Не имея особого опыта программирования на ассемблере, я по сути ограничился простым переводом кода с высокоуровневого языка на ассемблер, но даже этот примитивный подход ускорил выполнение про- граммы на 50%. Рассмотрим переписывание на ассемблере метода, преобразующего двоичные данные в символы ASCII верхнего регистра. В следующем примере показан соот- ветствующий код Delphi: Пример кода на Delphi, который лучше переписать на ассемблере procedure HexExpand( var source: ByteArray; var target: WordArray; byteCount: word ); Перекрестная ссылка Подроб- нее о том, что основная часть времени выполнения програм- мы приходится на малый про- цент кода, см. подраздел «Прин- цип Парето» раздела 25.2. ГЛАВА 26 Методики оптимизации кода 627 var index: integer; lowerByte: byte; upperByte: byte; targetIndex: integer; begin targetIndex := 1; for index := 1 to byteCount do begin target[ targetIndex ] := ( (source[ index ] and $F0) shr 4 ) + $41; target[ targetIndex+1 ] := (source[ index ] and $0f) + $41; targetIndex := targetIndex + 2; end; end; Трудно увидеть жир в этом коде, однако он содержит много манипуляций с бита- ми, что не является сильной стороной Delphi. А вот ассемблер подходит для это- го как нельзя лучше, так что этот код является хорошим кандидатом на перепи- сывание. Вот что получается в итоге: Пример метода, переписанного на ассемблере procedure HexExpand( var source; var target; byteCount : Integer ); label EXPAND; asm MOV ECX,byteCount // Загрузка числа расширяемых байт. MOV ESI,source // Смещение источника. MOV EDI,target // Смещение приемника. XOR EAX,EAX // Обнуление индекса смещения в массиве. EXPAND: MOV EBX,EAX // Смещение в массиве. MOV DL,[ESI+EBX] // Получение байта источника. MOV DH,DL // Копирование байта источника. AND DH,$F // Получение старших разрядов. ADD DH,$41 // Преобразование символа в верхний регистр. SHR DL,4 // Сдвиг разрядов на нужную позицию. AND DL,$F // Получение младших разрядов. ADD DL,$41 // Преобразование символа в верхний регистр. SHL BX,1 // Удвоение смещения в массиве-приемнике. MOV [EDI+EBX],DX // Копирование слова в приемник. 628 ЧАСТЬ V Усовершенствование кода INC EAX // Увеличение индекса смещения в массиве. LOOP EXPAND // Повторение цикла. end; Переписывание этого кода на ассемблере привело к уменьшению времени выпол- нения на 41%. Логично предположить, что код, написанный на языке, более под- ходящем для операций над битами, (скажем, на C++), менее восприимчив к этому виду оптимизации, чем код Delphi. Проверим: Время выполнения Время выполнения Экономия Язык высокоуровневого кода ассемблерного кода времени C++ 4,25 3,02 29% Delphi 5,18 3,04 41% Второй столбец этой таблицы отражает эффективность двух языков в отношении операций над битами. После оптимизации время выполнения стало почти оди- наковым — перевод кода на ассемблер свел к минимуму первоначальные разли- чия между Delphi и C++. Полученный нами метод показывает, что результатом переписывания кода на ас- семблере не всегда является огромный и уродливый метод. Итоговый код часто оказывается довольно компактным. Иногда ассемблерный код почти так же ком- пактен, как его высокоуровневый эквивалент. Существует одна относительно легкая и эффективная стратегия переписывания кода на ассемблере. В самом начале воспользуйтесь компилятором, генерирую- щем ассемблерные листинги во время компиляции. Извлеките ассемблерный код метода, который вам нужно оптимизировать, и сохраните его в отдельном исходном файле. Используя этот код как основу, выполните оптимизацию вручную, прове- ряя корректность кода и оценивая улучшения на каждом этапе. Некоторые ком- пиляторы вставляют в ассемблерный код высокоуровневые операторы в форме комментариев. Если ваш компилятор на это способен, можете сохранить перво- начальные операторы в ассемблерном коде в качестве документации. Контрольный список: методики оптимизации кода Улучшение и быстродействия, и объема Замените сложную логику на обращения к таблице. Объедините циклы. Используйте целочисленные переменные вместо переменных с плавающей запятой. Инициализируйте данные во время компиляции. Используйте константы корректного типа. Вычислите результаты предварительно. Устраните часто используемые подвыражения. Перепишите ключевые методы на низкоуровневом языке. Улучшение только быстродействия Прекращайте проверку сразу же после получения ответа. Упорядочивайте тесты в блоках case и цепочках операторов if-then-else по частоте. http://cc2e.com/2672 ГЛАВА 26 Методики оптимизации кода 629 Сравните быстродействие похожих структур логики. Используйте методику отложенных вычислений. Разомкните цикл, содержащий оператор if. Выполните развертывание цикла. Минимизируйте объем работы, выполняемой внутри цикла. Используйте сигнальные значения в циклах поиска. Вложите более ресурсоемкий цикл в менее ресурсоемкий. Снизьте стоимость операций, выполняемых внутри цикла. Замените многомерные массивы на одномерные. Минимизируйте число обращений к массивам. Дополните типы данных индексами. Кэшируйте часто используемые значения. Проанализируйте алгебраические тождества. Снизьте стоимость логических и математических выражений. Остерегайтесь системных методов. Встройте методы. 26.7. Если что-то одно изменяется, что-то другое всегда остается постоянным Трудно не согласиться с тем, что за 10 лет, прошедших со времени первого изда- ния этой книги, некоторые параметры производительности систем изменились. Компьютеры стали гораздо быстрее, а объем памяти вырос во много раз. Работая над первым изданием, для получения выразительных измеримых результатов я выполнял большинство тестов этой главы от 10 000 до 50 000 раз. При подготов- ке этого издания мне пришлось выполнять большинство тестов от 1 до 100 млн раз. Если для получения измеримых результатов тест нужно выполнить 100 млн раз, стоит задуматься над тем, заметит ли хоть кто-нибудь последствия выполненной оптимизации в реальной программе. Компьютеры стали столь мощными, что для многих распространенных типов программ виды оптимизации, описанные в этой главе, стали нерелевантными. В то же время другие аспекты производительности совсем не изменились. Воз- можно, программистов, создающих приложения для настольных ПК, вопросы оптимизации уже почти не тревожат, но разработчики программ для встроенных систем, систем, работающих в реальном времени, и других систем, обладающих ограниченными ресурсами, все еще должны владеть методиками оптимизации кода. Необходимость оценки результатов каждой попытки оптимизации кода не теряет актуальности с 1971 г., когда Дональд Кнут опубликовал свое исследование программ Fortran. Судя по данным, приведенным в этой главе, результаты отдельных видов оптимизации на самом деле сейчас менее предсказуемы, чем 10 лет назад. Они за- висят от языка, компилятора, и его версии, используемых библиотек, их версий, параметров компилятора и многого другого. Оптимизация кода неизбежно подразумевает нахождение компромисса между сложностью, удобочитаемостью, простотой и удобством сопровождения програм- мы, с одной стороны, и желанием повысить производительность — с другой. Не- 630 ЧАСТЬ V Усовершенствование кода обходимое при оптимизации перепрофилирование кода приводит к значитель- ному росту затрат на сопровождение программы. Есть один хороший способ сопротивления соблазну преждевременной оптимиза- ции и содействия созданию ясного и простого кода: требуйте, чтобы оптимизация приводила к измеримому улучшению. Если оптимизация оправдывает профилиро- вание кода и оценку результатов, наверное, ее следует выполнить, если будет пока- зано, что она работает. Но если оптимизация не оправдывает проведения профи- лирования, она не может оправдать ухудшения удобочитаемости, удобства сопро- вождения и других характеристик кода. Влияние неоцененной оптимизации кода на производительность в лучшем случае может быть только теоретическим, тогда как ее влияние на удобочитаемость столь же определенно, сколь пагубно. Дополнительные ресурсы По-моему, лучшая работа по оптимизации кода — Writing Efficient Programs (Bentley, Englewood Cliffs, NJ: Prentice Hall, 1982). Это довольно старая книга, и все же постарайтесь ее найти. В ней вы найдете экспертное обсуждение общих вопросов оптимизации кода. Бентли описывает методики обмена времени на пространство и простран- ства на время, а также приводит несколько примеров перепроектирования типов данных, позволяющего и ускорить код, и сделать его компактнее. Подход Бентли чуть более описателен, чем тот, что принял я, но приведенные им случаи весьма интересны. Бентли проводит несколько методов через несколько этапов оптими- зации, позволяя увидеть результаты первой, второй и третьей попыток. Описание главной идеи занимает 135 страниц. Эта книга отличается необычайно высоким отношением «сигнал/шум», что делает ее одним из редких бриллиантов, которые следует иметь каждому практикующему программисту. В приложении 4 книги Бентли Programming Pearls, 2d ed. (Bentley, Boston, MA: Addison-Wesley, 2000) вы можете найти резюме правил оптимизации кода, опи- санных в его более ранней книге. Кроме того, есть целый ряд книг, в которых вопросы опти- мизации рассматриваются в контексте конкретных техно- логий. Некоторые из них перечислены ниже, а самый све- жий список вы найдете на Web-странице, адрес которой указан слева. Booth, Rick. Inner Loops: A Sourcebook for Fast 32-bit Software Development. Boston, MA: Addison-Wesley, 1997. Gerber, Richard. Software Optimization Cookbook: High-Performance Recipes for the Intel Architecture. Intel Press, 2002. Hasan, Jeffrey and Kenneth Tu. Performance Tuning and Optimizing ASP.NET Applica- tions. Berkeley, CA: Apress, 2003. Killelea, Patrick. Web Performance Tuning, 2d ed. Sebastopol, CA: O’Reilly & Associates, 2002. Larman, Craig and Rhett Guthrie. Java 2 Performance and Idiom Guide. Englewood Cliffs, NJ: Prentice Hall, 2000. http://cc2e.com/2679 http://cc2e.com/2686 |