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

612
ЧАСТЬ V Усовершенствование кода ном или трехмерном массиве, вы скорее всего ускорите выполнение программы.
Допустим, у вас есть подобный код инициализации массива:
Пример стандартной инициализации двумерного массива (Java)
for ( row = 0; row < numRows; row++ ) {
for ( column = 0; column < numColumns; column++ ) {
matrix[ row ][ column ] = 0;
}
}
При инициализации массива из 50 строк и 20 столбцов этот код выполняется вдвое дольше, чем код инициализации аналогичного одномерного массива, сгенериро- ванный тем же компилятором Java. Вот как выглядел бы исправленный код:
Пример одномерного представления массива (Java)
for ( entry = 0; entry < numRows * numColumns; entry++ ) {
matrix[ entry ] = 0;
}
А вот результаты тестирования этого кода и похожего кода, написанного на не- скольких других языках:
Время выполнения
Время выполнения
оптимизированного Экономия Соотношение
Язык
кода до оптимизации кода
времени
быстродействия
C++
8,75 7,82 11%
1:1
C#
3,28 2,99 9%
1:1
Java
7,78 4,14 47%
2:1
PHP
6,24 4,10 34%
1,5:1
Python
3,31 2,23 32%
1,5:1
Visual Basic 9,43 3,22 66%
3:1
Примечание: временные показатели, указанные для Python и PHP, получены в резуль- тате более чем в 100 раз меньшего числа итераций, чем показатели, приведенные для других языков, поэтому их непосредственное сравнение недопустимо.
Результаты этого вида оптимизации прекрасны для Visual Basic и Java, хороши для
PHP и Python, но довольно заурядны для C++ и C#. Правда, время выполнения не- оптимизированного кода C# было лучшим, так что на это едва ли можно жаловаться.
Широкий разброс результатов лишь подтверждает недальновидность слепого сле- дования любым советам по оптимизации. Не испытав методику в конкретных об- стоятельствах, ни в чем нельзя быть уверенным.
Минимизация числа обращений к массивам
Кроме минимизации числа обращений к двумерным или трехмерным массивам часто выгодно минимизировать число обращений к массивам вообще. Подходя- щий кандидат для применения этой методики — цикл, в котором повторно ис-

ГЛАВА 26 Методики оптимизации кода
613
пользуется один и тот же элемент массива. Вот пример необязательного обраще- ния к массиву:
Пример необязательного обращения к массиву внутри цикла (C++)
for ( discountType = 0; discountType < typeCount; discountType++ ) {
for ( discountLevel = 0; discountLevel < levelCount; discountLevel++ ) {
rate[ discountLevel ] = rate[ discountLevel ] * discount[ discountType ];
}
}
При изменении индекса
discountLevel по мере выполнения внутреннего цикла обращение к массиву
discount[ discountType ] остается все тем же. Вы можете вы- нести его за пределы внутреннего цикла, и тогда у вас будет одно обращение к массиву на одну итерацию внешнего, а не внутреннего цикла. Вот оптимизиро- ванный код:
Пример вынесения обращения к массиву за пределы цикла (C++)
for ( discountType = 0; discountType < typeCount; discountType++ ) {
thisDiscount = discount[ discountType ];
for ( discountLevel = 0; discountLevel < levelCount; discountLevel++ ) {
rate[ discountLevel ] = rate[ discountLevel ] * thisDiscount;
}
}
Результаты:
Время выполнения
Время выполнения
Экономия
Язык
кода до оптимизации
оптимизированного кода
времени
C++
32,1 34,5
-7%
C#
18,3 17,0 7%
Visual Basic
23,2 18,4 20%
Примечание: тестирование выполнено для typeCount = 10 и levelCount = 100.
Как обычно, результаты зависят от конкретного компилятора.
Использование дополнительных индексов
Использование дополнительного индекса предполагает добавление данных, свя- занных с основным типом данных и повышающих эффективность обращений к нему. Связанные данные можно добавить к основному типу или хранить в парал- лельной структуре.
Индекс длины строки
Примером использования дополнительного индекса может служить одна из форм представления строк. В языке C строки заканчиваются нулевым байтом. Что каса- ется строк Visual Basic, то их длина хранится в начальном байте. Чтобы опреде- лить длину строки C, нужно начать с начала строки и продвигаться по ней, под- считывая байты, до достижения нулевого байта. Для определения длины строки
Visual Basic, нужно просто прочитать байт длины. Байт длины строки Visual Basic

614
ЧАСТЬ V Усовершенствование кода
— наглядный пример дополнения типа данных индексом, ускоряющим выполне- ние определенных операций, таких как вычисление длины строки.
Идею индексации длины можно приспособить к любому типу данных перемен- ной длины. Слежение за длиной структуры часто — более эффективный подход,
чем вычисление длины каждый раз, когда она требуется.
Независимая параллельная структура индексации
Иногда выгоднее работать с индексом типа данных, а не с самим типом данных.
Если элементы типа данных велики или их накладно перемещать (скажем, на диск),
сортировка и поиск по индексам будут выполняться быстрее, чем непосредственные операции над данными. Если каждый элемент данных велик, вы можете создать вспомогательную структуру, состоящую из ключевых значений и указателей на подробную информацию. Если различие размеров элемента структуры данных и элемента вспомогательной структуры достаточно велико, элемент-ключ можно хранить в памяти, а сами данные — на внешнем носителе. Все операции поиска и сортировки будут выполняться в памяти, а к диску можно будет обращаться толь- ко после определения точного расположения нужного вам элемента.
Кэширование
Кэширование — это такой способ хранения нескольких значений, при котором значения, используемые чаще всего, получить легче, чем значения, используемые реже. Так, если программа случайным образом читает записи с диска, метод мо- жет хранить в кэше записи, считываемые наиболее часто. Получив запрос запи- си, метод проверяет, имеется ли запись в кэше. Если да, запись возвращается не- посредственно из памяти, а не считывается с диска.
Кэширование можно применять и в других областях. В программе обработки шрифтов Microsoft Windows узким местом было получение ширины символа при его отображении на экране. Кэширование ширины символа, использованного последним, позволило примерно вдвое ускорить отображение.
Вы можете кэшировать и результаты ресурсоемких вычислений, особенно если их параметры просты. Пусть, например, вам нужно найти длину гипотенузы пря- моугольного треугольника по длинам двух катетов. Простая реализация этого метода была бы примерно такой:
Пример метода, напрашивающегося на кэширование (Java)
double Hypotenuse(
double sideA,
double sideB
) {
return Math.sqrt( ( sideA * sideA ) + ( sideB * sideB ) );
}
Если вы знаете, что те же значения скорее всего будут переданы в метод повтор- но, их можно кэшировать:

ГЛАВА 26 Методики оптимизации кода
615
Пример кэширования для предотвращения дорогих вычислений (Java)
private double cachedHypotenuse = 0;
private double cachedSideA = 0;
private double cachedSideB = 0;
public double Hypotenuse(
double sideA,
double sideB
) {
// Присутствуют ли параметры треугольника в кэше?
if ( ( sideA == cachedSideA ) && ( sideB == cachedSideB ) ) {
return cachedHypotenuse;
}
// Вычисление новой гипотенузы и ее кэширование.
cachedHypotenuse = Math.sqrt( ( sideA * sideA ) + ( sideB * sideB ) );
cachedSideA = sideA;
cachedSideB = sideB;
return cachedHypotenuse;
}
Вторая версия метода сложнее и объемнее первой, поэтому она должна обосно- вать свое право на жизнь быстродействием. Многие схемы кэширования предпо- лагают кэширование более одного элемента, и с ними связаны еще большие за- траты. Вот быстродействие двух версий метода:
Время выполнения
Время выполнения
оптимизированного Экономия Соотношение
Язык
кода до оптимизации кода
времени
быстродействия
C++
4,06 1,05 74%
4:1
Java
2,54 1,40 45%
2:1
Python
8,16 4,17 49%
2:1
Visual Basic 24,0 12,9 47%
2:1
Примечание: эти результаты предполагают, что на каждый промах кэша приходятся два попадания.
Польза кэширования зависит от относительной стоимости обращения к кэширо- ванному элементу, создания некэшированного элемента и сохранения нового элемента в кэше. Она также зависит от числа запросов кэшированной информа- ции. Иногда она может зависеть и от аппаратного кэширования. В целом чем до- роже генерирование нового элемента и чем чаще запрашивается та же самая ин- формация, тем выгоднее кэширование. Чем дешевле обращение к кэшированно- му элементу и сохранение новых элементов в кэше, тем выгоднее кэширование.
Как и другие методики оптимизации, кэширование усложняет код и часто оказы- вается источником ошибок.

616
ЧАСТЬ V Усовершенствование кода
26.4. Выражения
Многие задачи программирования требуют применения математических и логических выражений. Сложные выра- жения обычно дороги, и в этом разделе мы рассмотрим способы их удешевления.
Алгебраические тождества
Алгебраические тождества иногда позволяют заменить дорогие операции на бо- лее дешевые. Так, следующие выражения логически эквивалентны:
not a and not b not (a or b)
Выбрав второе выражение вместо первого, вы сэкономите одну операцию
not.
Устранение одной операции
not, вероятно, не приведет к заметным результатам,
однако в целом этот принцип очень полезен. Так, Джон Бентли пишет, что в од- ной программе проверялось условие
sqrt(x) < sqrt(y) (Bentley, 1982). Так как sqrt(x)
меньше
sqrt(y), только когда x меньше, чем y, исходную проверку можно заменить на
x < y. Если учесть дороговизну метода sqrt(), можно ожидать, что это приведет к огромной экономии. Так и есть:
Время выполнения
Время выполнения
оптимизированного Экономия Соотношение
Язык
кода до оптимизации кода
времени
быстродействия
C++
7,43 0,010 99,9%
750:1
Visual Basic 4,59 0,220 95%
20:1
Python
4,21 0,401 90%
10:1
Снижение стоимости операций
Как уже было сказано, снижение стоимости операций подразумевает замену до- рогой операции более дешевой. Вот некоторые возможные варианты:
쐽
замена умножения сложением;
쐽
замена возведения в степень умножением;
쐽
замена тригонометрических функций их эквивалентами;
쐽
замена типа
longlong на long или int (следите при этом за аспектами произво- дительности, связанными с применением целых чисел естественной и неес- тественной длины);
쐽
замена чисел с плавающей запятой числами с фиксированной точкой или целые числа;
쐽
замена чисел с плавающей запятой с удвоенной точностью числами с одинар- ной точностью;
쐽
замена умножения и деления целых чисел на два операциями сдвига.
Допустим, вам нужно вычислить многочлен. Если вы забыли, что такое многочле- ны, напомню, что это выражения вида
Ax2 + Bx + C. Буквы A, B и C — это коэффи-
Перекрестная ссылка О выраже- ниях см. раздел 19.1.

ГЛАВА 26 Методики оптимизации кода
617
циенты, а
x — переменная. Обычный код вычисления значения многочлена n-ной степени выглядит так:
Пример вычисления многочлена (Visual Basic)
value = coefficient( 0 )
For power = 1 To order value = value + coefficient( power ) * xˆpower
Next
Если вы подумаете о снижении стоимости операций, то поймете, что оператор возведения в степень — не самое эффективное решение в этом случае. Возведе- ние в степень можно заменить на умножение, выполняемое при каждой итера- ции цикла, что во многом похоже на снижение стоимости, выполненное нами ранее, когда умножение было заменено на сложение. Вот как выглядел бы код,
снижающий стоимость вычисления многочлена:
Пример снижения стоимости вычисления многочлена (Visual Basic)
value = coefficient( 0 )
powerOfX = x
For power = 1 to order value = value + coefficient( power ) * powerOfX
powerOfX = powerOfX * x
Next
Если вы имеете дело с многочленами второй или более высокой степени, выгода может быть очень приличной:
Время выполнения
Время выполнения
оптимизированного Экономия Соотношение
Язык
кода до оптимизации кода
времени
быстродействия
Python
3,24 2,60 20%
1:1
Visual Basic 6,26 0,160 97%
40:1
Если вы действительно серьезно отнесетесь к снижению стоимости операций, то позаботитесь и о двух умножениях чисел с плавающей запятой. Стоимость опе- раций, выполняемых в цикле, можно сделать еще меньшей, если постепенно воз- водить в нужную степень сразу несколько компонентов выражения, а не находить нужную степень при каждой итерации путем умножения:
Пример дальнейшего снижения стоимости вычисления многочлена (Visual Basic)
value = 0
For power = order to 1 Step -1
value = ( value + coefficient( power ) ) * x
Next value = value + coefficient( 0 )
В этой версии метода отсутствует переменная
powerOfX, а вместо двух умноже- ний при каждой итерации выполняется одно. Результаты таковы:

618
ЧАСТЬ V Усовершенствование кода
Экономия
Время
Время выполнения Время выполнения времени за
кода выполнения после первой
после второй
счет второй
Язык
до оптимизации
оптимизации
оптимизации
оптимизации
Python
3,24 2,60 2,53 3%
Visual Basic 6,26 0,16 0,31
-94%
Это хороший пример расхождения теории и практики. Код, имеющий снижен- ную стоимость, казалось бы, должен работать быстрее, но на деле это не так. Воз- можно, в Visual Basic снижение производительности объясняется декрементом счетчика цикла на
1 вместо инкремента, но чтобы говорить об этом с уверенно- стью, эту гипотезу нужно оценить.
Инициализация во время компиляции
Если вы вызываете метод, передавая ему в качестве единственного аргумента именованную константу или магическое число, попробуйте предварительно вы- числить нужное значение, присвоить его константе и избежать вызова метода. Это же справедливо для умножения, деления, сложения и других операций.
Однажды мне понадобилось вычислять значение двоичного логарифма целого числа, округленное до ближайшего целого числа. Система не предоставляла ме- тод вычисления двоичного логарифма, поэтому я написал собственный. Быстрый и легкий подход был основан на формуле:
log(x)base = log(x) / log(base)
Опираясь на это тождество, я написал такой метод:
Пример метода, вычисляющего двоичный логарифм
с использованием системных методов (C++)
unsigned int Log2( unsigned int x ) {
return (unsigned int) ( log( x ) / log( 2 ) );
}
Этот метод был очень медленным, а так как значение
log(2) измениться не может,
я заменил вызов метода
log(2) на действительное значение, равное 0.69314718:
Пример метода, вычисляющего двоичный логарифм
с использованием системного метода и константы (C++)
const double LOG2 = 0.69314718;
unsigned int Log2( unsigned int x ) {
return (unsigned int) ( log( x ) / LOG2 );
}
Вызов метода
log() довольно дорог — гораздо дороже преобразования типа или деления, и поэтому резонно предположить, что уменьшение числа вызовов мето- да
log() вдвое должно примерно в два раза ускорить выполнение метода. Вот ре- зультаты измерений:
Перекрестная ссылка О связы- вании переменных со значени- ями см. раздел 10.6.

ГЛАВА 26 Методики оптимизации кода
619
Время выполнения
Время выполнения
Экономия
Язык
кода до оптимизации
оптимизированного кода
времени
C++
9,66 5,97 38%
Java
17,0 12,3 28%
PHP
2,45 1,50 39%
Обоснованное предположение оказалось довольно близким к действительности.
Если учесть невысокую предсказуемость результатов, приводимых в этой главе,
точность моего прогноза в этом случае доказывает только то, что даже слепые белки иногда наталкиваются на орехи.
Недостатки системных методов
Системные методы дороги и часто обеспечивают избыточную точность. Напри- мер, большинство системных математических методов написаны с тем расчетом,
чтобы космонавт, отправившийся на Луну, прилунился с точностью ±2 фута. Если вам не нужна такая точность, нет смысла тратить на нее время.
В предыдущем примере метод
Log2() возвращал целое число, но использовал для его вычисления метод
log(), возвращающий число с плавающей запятой. Я не нуждался в такой точности, так что после своей первой попытки я написал ряд целочисленных проверок, которые прекрасно вычисляли целое значение двоичного логарифма:
Пример метода, возвращающего примерное значение двоичного логарифма (C++)
unsigned int Log2( unsigned int x ) {
if ( x < 2 ) return 0 ;
if ( x < 4 ) return 1 ;
if ( x < 8 ) return 2 ;
if ( x < 16 ) return 3 ;
if ( x < 32 ) return 4 ;
if ( x < 64 ) return 5 ;
if ( x < 128 ) return 6 ;
if ( x < 256 ) return 7 ;
if ( x < 512 ) return 8 ;
if ( x < 1024 ) return 9 ;
if ( x < 2147483648 ) return 30;
return 31 ;
}
Этот метод использует целочисленные операции, никогда не преобразовывает целые числа в числа с плавающей запятой и значительно превосходит по быст- родействию оба метода, работающих с числами с плавающей запятой:
Время выполнения
Время выполнения
оптимизированного Экономия Соотношение
Язык
кода до оптимизации кода
времени
быстродействия
C++
9,66 0,662 93%
15:1
Java
17,0 0,882 95%
20:1
PHP
2,45 3,45
-41%
2:3

620
ЧАСТЬ V Усовершенствование кода
Большинство так называемых «трансцендентных» функций разработано для наи- худшего случая, т. е. внутри себя они даже целочисленный аргумент преобразуют в число с плавающей запятой с удвоенной точностью. Обнаружив вызов такой функции в проблемном фрагменте кода, уделите ей самое пристальное внимание,
если, конечно, вам не нужна подобная точность.
Но вернемся к нашему методу. Еще один вариант его оптимизации основан на том факте, что деление на 2 аналогично операции сдвига вправо. Двоичный логарифм числа равен количеству операций деления на 2, которое можно выполнить над этим числом до получения нулевого значения. Вот как выглядит соответствующий код:
Пример альтернативного метода, определяющего примерное значение
двоичного логарифма с использованием оператора сдвига вправо (C++)
unsigned int Log2( unsigned int x ) {
unsigned int i = 0;
while ( ( x = ( x >> 1 ) ) != 0 ) {
i++;
}
return i ;
}
Читать этот код трудно, особенно программистам, не работавшим с C++. Слож- ное выражение в условии цикла
while — прекрасный пример того, что следует использовать только в крайних случаях.
Этот метод выполняется примерно на 350% дольше, чем более длинная предыду- щая версия (2,4 и 0,66 секунды соответственно), но он быстрее, чем первый опти- мизированный метод, и легко адаптируется к 32-, 64-разрядным и другим средам.
Этот пример ясно показывает, насколько полезно продолжать поиск после нахождения первого успешного вида оптимизации. Первый вид оптими- зации привел к приличному повышению быстродействия на 30–40%, но это не идет ни в какое сравнение с результатами второго и третьего видов опти- мизации.
Использование констант корректного типа
Используйте именованные константы и литералы, имеющие тот же тип, что и переменные, которым они присваиваются. Если константа и соответствующая ей переменная имеют разные типы, перед присвоением константы переменной ком- пилятор должен будет выполнить преобразование типа. Хорошие компиляторы преобразуют типы во время компиляции, чтобы не снижалась производительность в период выполнения программы.
Однако менее эффективные компиляторы или интерпретаторы генерируют код,
преобразующий типы в период выполнения. Чуть ниже указаны различия во вре- мени инициализации переменной с плавающей точкой
x и целочисленной пере- менной
i в двух случаях. В первом случае инициализация выглядит так:
x = 5
i = 3.14