Совершенный код. Совершенный код. Мастер-класс. Стив Макконнелл. Руководство по стилю программирования и конструированию по
 Скачать 5.88 Mb.
|
|
ГЛАВА 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. ГЛАВА 26 Методики оптимизации кода 601 category = 0; } Вместо этого теста вы можете использовать более модифицируемый и быстро# действующий подход, основанный на просмотре табличных данных: Пример использования таблицы вместо сложной логики (C++) // Определение таблицы categoryTable. Определение таблицы понять нелегко, поэтому используйте любые комментарии, способные помочь. static int categoryTable[ 2 ][ 2 ][ 2 ] = { // !b!c !bc b!c bc 0, 3, 2, 2, // !a 1, 2, 1, 1 // a }; category = categoryTable[ a ][ b ][ c ]; Определение этой таблицы кажется запутанным, но, если она хорошо докумен# тирована, читать ее будет не труднее, чем код сложной логической цепи. Кроме того, изменить таблицу будет гораздо легче, чем более раннюю логику. Вот ре# зультаты сравнения быстродействия обоих подходов: Время выполнения Время выполнения оптимизированного Экономия Соотношение Язык кода до оптимизации кода времени быстродействия C++ 5,04 3,39 33% 1,5:1 Visual Basic 5,21 2,60 50% 2:1 Отложенные вычисления Один из моих бывших соседей любил все откладывать на потом. В оправдание своей лени он говорил, что многое из того, что люди порываются сделать, делать просто не нужно. Если подождать достаточно долго, утверждал он, неважные дела канут в Лету, и он не будет тратить на них свое время. Методика отложенных вычислений основана на принципе моего соседа: программа делает что#то, только когда это действительно нужно. Отложенное вычисление похоже на стратегию решения задач «по требованию», при которой работа вы# полняется максимально близко к тому месту, где нужны ее результаты. Допустим, ваша программа работает с таблицей из 5000 значений, полностью генерируя ее при запуске и затем обращайтесь к ней по мере выполнения. Если программа использует только небольшую часть элементов таблицы, возможно, есть смысл вычислять их по мере надобности, а не все сразу. После вычисления эле# мента его можно сохранить на будущее (это называется «кэшированием»). > 602 ЧАСТЬ V Усовершенствование кода 26.2. Циклы Так как циклы выполняются многократно, горячие точки часто следует искать именно внутри циклов. Методики, описываемые в этом разделе, помогают ускорить выполне# ние циклов. Размыкание цикла Замыканием (switching) цикла называют принятие решения внутри цикла при каждой его итерации. Если во время выполнения цикла решение не изменяется, вы можете разомкнуть (unswitch) цикл, приняв решение вне цикла. Обычно для этого нужно вывернуть цикл наизнанку, т. е. поместить циклы в условный опера# тор, а не условный оператор внутрь цикла. Вот пример цикла до размыкания: Пример замкнутого цикла (C++) for ( i = 0; i < count; i++ ) { if ( sumType == SUMTYPE_NET ) { netSum = netSum + amount[ i ]; } else { grossSum = grossSum + amount[ i ]; } } В этом фрагменте проверка if ( sumType == SUMTYPE_NET ) выполняется при каж# дой итерации, хотя ее результат остается постоянным. Вы можете ускорить вы# полнение этого кода, переписав его так: Пример разомкнутого цикла (C++) if ( sumType == SUMTYPE_NET ) { for ( i = 0; i < count; i++ ) { netSum = netSum + amount[ i ]; } } else { for ( i = 0; i < count; i++ ) { grossSum = grossSum + amount[ i ]; } } Примечание: Этот фрагмент нарушает несколько правил хорошего программирования. Удобочитаемость и удобство сопровождения кода обычно важнее его быстродействия или размера, но темой этой главы является производительность, а для ее повышения час# то нужно поступиться другими целями. Как и в предыдущей главе, здесь вы найдете при# меры методик кодирования, которые в других частях этой книги не рекомендуются. Перекрестная ссылка О циклах см. также главу 16. ГЛАВА 26 Методики оптимизации кода 603 Размыкание этого цикла позволяет ускорить его выполнение примерно на 20%: Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C++ 2,81 2,27 19% Java 3,97 3,12 21% Visual Basic 2,78 2,77 <1% Python 8,14 5,87 28% К сожалению, после размыкания цикла вам придется сопровождать оба цикла параллельно. Так, если переменную count потребуется заменить на clientCount, нужно будет изменить два фрагмента, что будет раздражать и вас, и всех других програм# мистов, которым придется работать с вашим кодом. Этот пример также иллюстрирует главную проблему оптимизации кода: результат любого отдельного вида оптимизации непредсказуем. Размыкание цикла оказалось выгодным для трех языков из четырех, но не для Visual Basic. В случае этой конк# ретной версии Visual Basic размыкание цикла только затруднило сопровождение кода, ничего не дав взамен. Урок очевиден: чтобы с уверенностью говорить о ре# зультатах любого вида оптимизации, вы должны их оценить. Никаких исключений. Объединение циклов Если два цикла работают с одним набором элементов, можно выполнить их объе# динение (jamming). Выгода здесь объясняется устранением затрат, связанных с выполнением дополнительного цикла. Например, на объединение претендуют следующие циклы: Пример отдельных циклов, которые можно объединить (Visual Basic) For i = 0 to employeeCount 1 employeeName( i ) = “” Next For i = 0 to employeeCount 1 employeeEarnings( i ) = 0 Next Объединение циклов обычно требует, чтобы условия циклов были одинаковы. В нашем примере оба цикла выполняются от 0 до employeeCount % 1, поэтому мы можем их объединить: Пример объединенного цикла (Visual Basic) For i = 0 to employeeCount 1 employeeName( i ) = “” employeeEarnings( i ) = 0 Next Результаты объединения циклов таковы: 604 ЧАСТЬ V Усовершенствование кода Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C++ 3,68 2,65 28% PHP 3,97 2,42 32% Visual Basic 3,75 3,56 4% Примечание: тестирование выполнено для случая employeeCount = 100. Как и прежде, все зависит от конкретного языка. С объединением циклов связаны два главных фактора риска. Во#первых, индек# сы двух объединенных циклов могут позднее измениться, утратив совместимость. Во#вторых, объединить циклы иногда трудно. Прежде чем объединять циклы, убедитесь, что это не нарушит работу остальных частей кода. Развертывание цикла Целью развертывания (unrolling) цикла является сокращение затрат, связанных с его выполнением. Если помните, после полного развертывания цикла из трех строк в главе 25 оказалось, что 10 отдельных обращений к массиву выполняются быстрее. Полное развертывание цикла — быстрое решение, эффективное при малом числе элементов, но оно непрактично, если элементов много или вы не знаете заранее, с каким числом элементов вы будете иметь дело. Вот пример обычного цикла: Пример цикла, допускающего развертывание (Java) Для решения подобной задачи вы, вероятно, использовали бы цикл for, но перед оптимизацией вы должны были бы преобразовать его в цикл while. Ради ясности здесь показан цикл while. i = 0; while ( i < count ) { a[ i ] = i; i = i + 1; } После частичного развертывания цикла при каждой его итерации обрабатывает# ся не один случай, а два или более. Это ухудшает удобочитаемость, но не наруша# ет общность цикла. Вот цикл, развернутый один раз: Пример однократного развертывания цикла (Java) i = 0; while ( i < count 1 ) { a[ i ] = i; a[ i + 1 ] = i + 1; i = i + 2; } > |