Руководство по стилю программирования и конструированию по
 Скачать 7.6 Mb.
|
|
ГЛАВА 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; } > ГЛАВА 26 Методики оптимизации кода 605 Эти строки обрабатывают случай, который может быть упущен из-за увеличении счетчика цикла на 2, а не на 1. if ( i == count ) { a[ count - 1 ] = count - 1; } Как видите, мы заменили первоначальную строку a[ i ] = i на две строки и увели- чиваем счетчик цикла на 2, а не на 1. Дополнительный код после цикла while ну- жен на случай нечетных значений переменной count, при которых цикл завер- шается, так и не обработав один элемент массива. Конечно, девять строк хитрого кода труднее читать и сопровождать, чем пять строк простого. Что греха таить: после развертывания цикла качество кода ухудшилось. Однако любой подход к проектированию предполагает поиск компромиссных решений, и, даже если конкретная методика обычно плоха, в определенных об- стоятельствах она может стать оптимальной. Вот результаты развертывания цикла: Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C++ 1,75 1,15 34% Java 1,01 0,581 43% PHP 5,33 4,49 16% Python 2,51 3,21 -27% Примечание: тестирование выполнено для случая count = 100. Возможность ускорения кода на 16–43% заслуживает внимания, хотя, как пока- зывает тест кода, написанного на Python, тут тоже не все однозначно. Главная опасность при развертывании цикла — ошибка завышения или занижения на единицу в коде, обрабатывающем последнюю итерацию. Что, если мы продолжим развертывание цикла? Принесет ли дополнительную выгоду двойное развертывание? Пример двукратного развертывания цикла (Java) i = 0; while ( i < count - 2 ) { a[ i ] = i; a[ i + 1 ] = i+1; a[ i + 2 ] = i+2; i = i + 3; } if ( i <= count - 1 ) { a[ count - 1 ] = count - 1; } if ( i == count - 2 ) { a[ count -2 ] = count - 2; } > 606 ЧАСТЬ V Усовершенствование кода Развертывание цикла во второй раз привело к таким результатам: Время выполнения Время выполнения кода после второго Экономия Язык кода до оптимизации развертывания цикла времени C++ 1,75 1,01 42% Java 1,01 0,581 43% PHP 5,33 3,70 31% Python 2,51 2,79 -12% Примечание: тестирование выполнено для случая count = 100. Итак, дальнейшее развертывание цикла может принести дополнительную пользу, а может и не принести, как показывает случай языка Java. В то же время сложность кода быстро возрастает. Если предыдущий фрагмент не кажется вам таким уж сложным, вспомните, что в самом начале он был циклом из пяти строк, и сами оцените компромисс между производительностью и удобочитаемостью. Минимизация объема работы, выполняемой внутри циклов Одной из методик повышения эффективности циклов является минимизация объема работы, выполняемой внутри цикла. Если вы можете вычислить выраже- ние или его часть вне цикла и использовать внутри цикла результат вычисления, сделайте это. Это хорошая методика программирования, которая иногда улучша- ет удобочитаемость кода. Допустим, у вас есть цикл, включающий сложное выражение с указателями: Пример цикла, включающего сложное выражение с указателями (C++) for ( i = 0; i < rateCount; i++ ) { netRate[ i ] = baseRate[ i ] * rates->discounts->factors->net; } Присвоив результат выражения удачно названной переменной, вы улучшите удо- бочитаемость кода, а может, и ускорите его выполнение: Пример упрощения сложного выражения с указателями (C++) quantityDiscount = rates->discounts->factors->net; for ( i = 0; i < rateCount; i++ ) { netRate[ i ] = baseRate[ i ] * quantityDiscount; } Дополнительная переменная quantityDiscount (оптовая скидка) ясно показывает, что элементы массива baseRate умножаются на показатель скидки. В первом фраг- менте это совсем не было очевидно. Кроме того, вынесение сложного выражения за пределы цикла устраняет три разыменования указателей при каждой итерации, что приводит к таким результатам: ГЛАВА 26 Методики оптимизации кода 607 Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C++ 3,69 2,97 19% C# 2,27 1,97 13% Java 4,13 2,35 43% Примечание: тестирование выполнено для случая rateCount = 100. За исключением компилятора Java экономия времени не так уж и велика, поэто- му при первоначальном кодировании вы можете применить любую методику, улучшающую удобочитаемость кода, и отложить работу над быстродействием на потом. Сигнальные значения Если цикл включает проверку сложного условия, время его выполнения часто можно сократить, упростив проверку. В случае циклов поиска это можно сделать, использовав сигнальное значение (sentinel value) — значение, которое распола- гается сразу после окончания диапазона поиска и непременно завершает поиск. Классический пример сложной проверки, которую можно упростить с помощью сигнального значения, — условие цикла поиска, включающее проверки обнару- жения нужной переменной и выхода за пределы диапазона поиска. Вот код тако- го цикла: Пример проверки сложного условия цикла (C#) found = FALSE; i = 0; Проверка сложного условия. while ( ( !found ) && ( i < count ) ) { if ( item[ i ] == testValue ) { found = TRUE; } else { i++; } } if ( found ) { При каждой итерации этого цикла проверяются два условия: !found и i < count. Проверка !found служит для определения того, найден ли нужный элемент. Про- верка i < count нужна для предотвращения выхода за пределы массива. Кроме того, внутри цикла проверяются отдельные значения массива item[], так что на самом деле при каждой итерации цикла выполняются три проверки. > 608 ЧАСТЬ V Усовершенствование кода Этот вид циклов поиска позволяет объединить три проверки и выполнять при каждой итерации только одну проверку: для этого нужно поместить в конце диа- пазона поиска «сигнальное значение», завершающее цикл. В нашем случае мож- но просто присвоить искомое значение элементу, располагающемуся сразу пос- ле окончания диапазона поиска (объявляя массив, не забудьте выделить место для этого элемента). Далее вы проверяете по очереди каждый элемент: если вы дос- тигаете сигнального значения, значит, нужного вам значения в массиве нет. Вот соответствующий код: Пример использования сигнального значения для ускорения цикла (C#) // Установка сигнального значения с сохранением начальных значений. initialValue = item[ count ]; Не забудьте зарезервировать в конце массива место для сигнального значения. item[ count ] = testValue; i = 0; while ( item[ i ] != testValue ) { i++; } // Обнаружено ли значение? if ( i < count ) { Если item содержит целые числа, выгода может быть весьма существенной: Время выполнения Время выполнения оптимизированного Экономия Соотношение Язык кода до оптимизации кода времени быстродействия C# 0,771 0,590 23% 1,3:1 Java 1,63 0,912 44% 2:1 Visual Basic 1,34 0,470 65% 3:1 Примечание: поиск выполнялся в массиве из 100 целых чисел. Результаты, полученные для Visual Basic, особенно впечатляют, но и остальные тоже очень неплохи. Однако при изменении типа массива результаты также изменя- ются. Если item включает числа с плавающей запятой, результаты таковы: Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C# 1,351 1,021 24% Java 1,923 1,282 33% Visual Basic 1,752 1,011 42% Примечание: поиск выполнялся в массиве из 100 четырехбайтовых чисел с плаваю- щей запятой. > ГЛАВА 26 Методики оптимизации кода 609 Как обычно, многое зависит от языка. Сигнальное значение можно использовать почти в любой ситуации, требующей выполнения линейного поиска, причем не только в массивах, но и в связных спис- ках. Вы только должны тщательно выбирать сигнальные значения и с осторож- ностью включать их в структуры данных. Вложение более ресурсоемкого цикла в менее ресурсоемкий Если вы имеете дело с вложенными циклами, подумайте, какой из них должен быть внешним, а какой внутренним. Вот пример вложенного цикла, который можно улучшить: Пример вложенного цикла, который можно улучшить (Java) for ( column = 0; column < 100; column++ ) { for ( row = 0; row < 5; row++ ) { sum = sum + table[ row ][ column ]; } } Ключ к улучшению цикла в том, что внешний цикл состоит из гораздо большего числа итераций, чем внутренний. С выполнением любого цикла связаны наклад- ные расходы: в начале цикла индекс должен быть инициализирован, а при каж- дой итерации — увеличен и проверен. Общее число итераций равно 100 для внеш- него цикла и 100 * 5 = 500 для внутреннего цикла, что дает в сумме 600 итераций. Просто поменяв местами внешний и внутренний циклы, вы можете снизить чис- ло итераций внешнего цикла до 5, тогда как число итераций внутреннего цикла останется тем же. В итоге вместо 600 итераций будут выполнены только 505. Можно ожидать, что перемена циклов местами приведет примерно к 16%-ому улучшению: (600 – 505) / 600 = 16%. На самом деле результаты таковы: Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C++ 4,75 3,19 33% Java 5,39 3,56 34% PHP 4,16 3,65 12% Python 3,48 3,33 4% Значительные различия в очередной раз доказывают, что по поводу следствий оптимизации нельзя сказать ничего определенного, не оценив их в конкретной среде. Снижение стоимости операций Под снижением стоимости (strength reduction) понимают замену дорогой опера- ции на более дешевую, например, умножения на сложение. Иногда внутри цикла выполняется умножение индекса на какие-то другие значения. Сложение обычно выполняется быстрее, чем умножение, и, если вы можете вычислить то же число, 610 ЧАСТЬ V Усовершенствование кода заменив умножение на прибавление значения при каждой итерации цикла, это скорее всего приведет к ускорению выполнения кода. Вот пример кода, основан- ного на умножении: Пример умножения с использованием индекса цикла (Visual Basic) For i = 0 to saleCount - 1 commission( i ) = (i + 1) * revenue * baseCommission * discount Next Этот код прост, но дорог. В то же время цикл можно переписать так, чтобы при каждой итерации выполнялось более дешевое сложение: Пример замены умножения на сложение (Visual Basic) incrementalCommission = revenue * baseCommission * discount cumulativeCommission = incrementalCommission For i = 0 to saleCount - 1 commission( i ) = cumulativeCommission cumulativeCommission = cumulativeCommission + incrementalCommission Next Этот вид изменения похож на купон, предоставляющий скидку со стоимости цикла. В первоначальном коде при каждой итерации выполнялось умножение выраже- ния revenue * baseCommission * discount на счетчик цикла, увеличенный на едини- цу: сначала на 1, затем на 2, затем на 3 и т. д. В оптимизированном коде значение выражения revenue * baseCommission * discount присваивается переменной incre- mentalCommission. После этого при каждой итерации цикла значение incremental- Commission прибавляется к cumulativeCommission. При первой итерации оно при- бавляется один раз, при второй — два, при третьей — три и т. д. Эффект тот же, что и при умножении incrementalCommission на 1, на 2, на 3 и т. д., но оптими- зированный вариант дешевле. Чтобы этот вид оптимизации оказался возможным, первоначальное умножение должно зависеть от индекса цикла. В данном примере индекс цикла был единствен- ной изменяющейся частью выражения, поэтому мы и смогли сделать выражение более эффективным. Вот к чему это привело: Время выполнения Время выполнения Экономия Язык кода до оптимизации оптимизированного кода времени C++ 4,33 3,80 12% Visual Basic 3,54 1,80 49% Примечание: тестирование выполнено для saleCount = 20. Все используемые в вычис- лении переменные были переменными с плавающей запятой. |