Файл: Руководство по стилю программирования и конструированию по.pdf

ГЛАВА 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. Все используемые в вычис- лении переменные были переменными с плавающей запятой.