Руководство по стилю программирования и конструированию по
 Скачать 7.6 Mb.
|
|
ГЛАВА 26 Методики оптимизации кода 611 26.3. Изменения типов данных Изменение типов данных может быть эффективным способом сокращения кода и повышения его быстродействия. Проектирование структур данных в этой кни- ге не рассматривается, но умеренные изменения реализации отдельных типов данных также могут повышать производительность. Ниже описано несколько способов оптимизации типов данных. Использование целых чисел вместо чисел с плавающей запятой Сложение и умножение целых чисел, как правило, выпол- няются быстрее, чем аналогичные операции над числами с плавающей запятой. Например, циклы выполняются быст- рее, если индекс имеет целочисленный тип. Пример неэффективного цикла с индексом с плавающей запятой (Visual Basic) Dim x As Single For x = 0 to 99 a( x ) = 0 Next Сравните этот код с аналогичным циклом, в котором явно используется целочис- ленный индекс: Пример эффективного цикла с целочисленным индексом (Visual Basic) Dim i As Integer For i = 0 to 99 a( i ) = 0 Next Насколько выгоден этот вид оптимизации? Вот результаты выполнения указанных фрагментов кода Visual Basic и аналогичных циклов, написанных на C++ и PHP: Соотношение Время выполнения Время выполнения Экономия быстродействия Язык кода до оптимизации оптимизированного времени кода C++ 2,80 0,801 71% 3,5:1 PHP 5,01 4,65 7% 1:1 Visual Basic 6,84 0,280 96% 25:1 Использование массивов с минимальным числом измерений Использовать массивы, имеющие несколько измерений, накладно. Если вы сможете структурировать данные так, чтобы их можно было хранить в одномерном, а не двумер- Перекрестная ссылка Об ис- пользовании целых чисел и чи- сел с плавающей запятой см. главу 12. Перекрестная ссылка О масси- вах см. раздел 12.8. 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 |