Совершенный код. Совершенный код. Мастер-класс. Стив Макконнелл. Руководство по стилю программирования и конструированию по
 Скачать 5.88 Mb.
|
|
ГЛАВА 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 ГЛАВА 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 при инициализации программы или читать его из файла. Вы также могли бы инициализировать массив нулями, вычислять каждый элемент при его первом запросе, сохранять его, а впоследствии просто извлекать из массива. Это было бы одной из форм кэширования, которое обсуждалось выше. > |