Руководство по стилю программирования и конструированию по
 Скачать 7.6 Mb.
|
|
ГЛАВА 25 Стратегии оптимизации кода 583 25.3. Где искать жир и патоку? При оптимизации кода вы находите части программы, медленные, как патока зи- мой, и огромные, как Годзилла, и изменяете их так, чтобы они были быстры, как молния, и могли скрываться в расщелинах между байтами в оперативной памяти. Без профилирования программы вы никогда не сможете с уверенностью сказать, какие фрагменты медленны и огромны, но некоторые операции давно славятся ленью и ожирением, так что вы можете начать исследование именно с них. Частые причины снижения эффективности Операции ввода/вывода Один из самых главных источников неэффективно- сти — ненужные операции ввода/вывода. Если объем используемой памяти не иг- рает особой роли, работайте с данными в памяти, а не обращайтесь к диску, БД или сетевому ресурсу. Вот результаты сравнения эффективности случайного доступа к элементам 100- элементного массива «в памяти» и записям аналогичного файла, хранящегося на диске: Время обработки Время обработки Экономия Соотношение Язык внешнего файла данных «в памяти» времени быстродействия C++ 6,04 0,000 100% — C# 12,8 0,010 100% 1000:1 Судя по этим результатам, доступ к данным «в памяти» выполняется в 1000 раз быстрее, чем доступ к данным, хранящимся во внешнем файле. В случае моего компилятора C++ время доступа к данным «в памяти» не удалось даже измерить. Результаты аналогичного тестирования последовательного доступа к данным по- хожи: Время обработки Время обработки Экономия Соотношение Язык внешнего файла данных «в памяти» времени быстродействия C++ 3,29 0,021 99% 150:1 C# 2,60 0,030 99% 85:1 Примечание: при тестировании последовательного доступа данные были в 13 раз бо- лее объемными, чем при тестировании случайного доступа, поэтому результаты двух видов тестов сравнивать нельзя. Если для доступа к внешним данным используется более медленная среда (напри- мер, сетевое соединение), разница только увеличивается. При тестировании слу- чайного доступа к данным по сети результаты выглядят так: Время обработки Время обработки Экономия Язык локального файла файла по сети времени C++ 6,04 6,64 -10% C# 12,8 14,1 -10% 584 ЧАСТЬ V Усовершенствование кода Конечно, эти результаты сильно зависят от скорости сети, объема трафика, рас- стояния между компьютером и сетевым диском, производительности сетевого и локального дисков, фазы Луны и других факторов. В целом доступ к данным «в памяти» выполняется гораздо быстрее, так что дваж- ды подумайте, прежде чем включать операции ввода/вывода в фрагменты, к быс- тродействию которых предъявляются повышенные требования. Замещение страниц Операция, заставляющая ОС заменять страницы памяти, выполняется гораздо медленнее, чем операция, ограниченная одной страницей памяти. Иногда самое простое изменение может принести огромную пользу. На- пример, один программист обнаружил, что в системе, использующей страницы объемом по 4 кб, следующий цикл инициализации вызывает массу страничных ошибок: Пример цикла инициализации, вызывающего много страничных ошибок (Java) for ( column = 0; column < MAX_COLUMNS; column++ ) { for ( row = 0; row < MAX_ROWS; row++ ) { table[ row ][ column ] = BlankTableElement(); } } Это хорошо отформатированный цикл с удачными именами переменных, так в чем же проблема? Проблема в том, что каждая строка (row) массива table содер- жит около 4000 байт. Если массив включает слишком много строк, то при каж- дом обращении к новой строке ОС должна будет заменить страницы памяти. В предыдущем фрагменте изменение номера строки, а значит, и подкачка новой страницы с диска выполняются при каждой итерации внутреннего цикла. Программист реорганизовал цикл: Пример цикла инициализации, вызывающего немного страничных ошибок (Java) for ( row = 0; row < MAX_ROWS; row++ ) { for ( column = 0; column < MAX_COLUMNS; column++ ) { table[ row ][ column ] = BlankTableElement(); } } Этот код также вызывает страничную ошибку при каждом изменении номера стро- ки, но это происходит только MAX_ROWS раз, а не MAX_ROWS * MAX_COLUMNS раз. Степень снижения быстродействия кода из-за замещения страниц во многом за- висит от объема памяти. На компьютере с небольшим объемом памяти второй фрагмент кода выполнялся примерно в 1000 раз быстрее, чем первый. При нали- чии большего объема памяти различие было всего лишь двукратным и было за- метно лишь при очень больших значениях MAX_ROWS и MAX_COLUMNS. Системные вызовы Вызовы системных методов часто дороги. Они нередко вклю- чают переключение контекста — сохранение состояния программы, восстановле- ние состояния ядра ОС и наоборот. В число системных методов входят методы, служащие для работы с диском, клавиатурой, монитором, принтером и другими ГЛАВА 25 Стратегии оптимизации кода 585 устройствами, методы управления памятью и некоторые вспомогательные методы. Если вас беспокоит производительность, узнайте, насколько дороги системные вызовы в вашей системе. Если они дороги, рассмотрите следующие варианты. 쐽 Напишите собственные методы. Иногда функциональность системных мето- дов оказывается избыточной для решения конкретных задач. Заменив низко- уровневые системные методы собственными, вы получите более быстрый и компактный код, лучше соответствующий вашим потребностям. 쐽 Избегайте вызовов системных методов. 쐽 Обратитесь к производителю системы и укажите ему на низкую эффективность тех или иных методов. Обычно производители хотят улучшить свою продук- цию и охотно принимают все замечания (поначалу они могут показаться не- много недовольными, но они на самом деле в этом заинтересованы). В программе, про оптимизацию которой я рассказал в подразделе «Когда выпол- нять оптимизацию?» раздела 25.2, использовался класс AppTime, производный от коммерческого класса BaseTime (имена изменены). Объекты AppTime использо- вались в программе на каждом шагу и исчислялись десятками тысяч. Через несколь- ко месяцев мы обнаружили, что объекты BaseTime инициализировались в кон- структоре значением системного времени. В нашей программе системное время не играло никакой роли, а это означало, что мы без надобности генерировали ты- сячи системных вызовов. Простое переопределение конструктора класса BaseTime так, чтобы поле time инициализировалось нулем, дало нам такое же повышение производительности, что и все остальные изменения, вместе взятые. Интерпретируемые языки При выполнении интерпретируемого кода каждая команда должна быть обработана и преобразована в машинный код, поэтому интерпретируемые языки обычно гораздо медленней компилируемых. Вот при- мерные результаты сравнения разных языков, полученные мной при работе над этой главой и главой 26 (табл. 25-1): Табл. 25-1. Относительное быстродействие кода, написанного на разных языках Время выполнения кода Язык Тип языка в сравнении с кодом C++ C++ Компилируемый 1:1 Visual Basic Компилируемый 1:1 C# Компилируемый 1:1 Java Байт-код 1,5:1 PHP Интерпретируемый >100:1 Python Интерпретируемый >100:1 Как видите, в плане быстродействия языки C++, Visual Basic и C# примерно одина- ковы. Код на Java выполняется несколько медленнее. PHP и Python — интерпрети- руемые языки, и код, написанный на них, обычно выполняется в 100 и более раз медленнее, чем написанный на C++, Visual Basic, C# или Java. Однако к общим ре- зультатам, указанным в этой таблице, следует относиться с осторожностью. Отно- сительная эффективность C++, Visual Basic, C#, Java и других языков во многом за- висит от конкретного кода (читая главу 26, вы сами в этом убедитесь). 586 ЧАСТЬ V Усовершенствование кода Ошибки Наконец, еще одним источником проблем с производительностью яв- ляются некоторые виды ошибок. Какие? Вы можете оставить в итоговой версии про- граммы отладочный код (например, записывающий трассировочную информацию в файл), забыть про освобождение памяти, неграмотно спроектировать таблицы БД, опрашивать несуществующие устройства до истечения лимита времени и т. д. При работе над первой версией одного приложения мы столкнулись с операци- ей, выполнявшейся гораздо медленнее других похожих операций. Сделав массу попыток объяснить этот факт, мы выпустили версию 1.0, так и не поняв полнос- тью, в чем дело. Однако, работая над версией 1.1, я обнаружил, что таблица БД, используемая в этой операции, не была проиндексирована! Простая индексация таблицы повысила скорость некоторых операций в 30 раз. Определение индекса для часто используемой таблицы нельзя считать оптимизацией — это просто хорошая практика программирования. Относительное быстродействие распространенных операций Хотя нельзя с полной уверенностью утверждать, что одни операции медленнее других, не оценив их, определенные операции все же обычно дороже. Отыскивая патоку в своей программе, используйте табл. 25-2, которая поможет вам выдвинуть первоначальные предположения о том, какие фрагменты кода неэффективны. Табл. 25-2. Быстрота выполнения часто используемых операций Относительное время выполнения Операция Пример C++ Java Исходный показатель i = j 1 1 (целочисленное присваивание) Вызовы методов Вызов метода без параметров foo() 1 — Вызов закрытого метода this.foo() 1 0,5 без параметров Вызов закрытого метода this.foo( i ) 1,5 0,5 с одним параметром Вызов закрытого метода this.foo( i, j ) 2 0,5 с двумя параметрами Вызов метода объекта bar.foo() 2 1 Вызов метода производ- derivedBar.foo() 2 1 ного объекта Вызов полиморфного метода abstractBar.foo() 2,5 2 Обращения к объектам Обращение к объекту i = obj.num 1 1 1-го уровня Обращение к объекту i = obj1.obj2. num 1 1 2-го уровня Стоимость каждого i = obj1.obj2.obj3... неизмеряема неизмеряема дополнительного уровня ГЛАВА 25 Стратегии оптимизации кода 587 Табл. 25-2. (продолжение) Относительное время выполнения Операция Пример C++ Java Операции над целочислен- ными переменными Целочисленное присваивание i = j 1 1 (локальная операция) Целочисленное присваивание i = j 1 1 (унаследованная операция) Сложение i = j + k 1 1 Вычитание i = j - k 1 1 Умножение i = j * k 1 1 Деление i = j \ k 5 1,5 Операции над переменными с плавающей запятой Присваивание x = y 1 1 Сложение x = y + z 1 1 Вычитание x = y - z 1 1 Умножение x = y * z 1 1 Деление x = y / z 4 1 Трансцендентные функции Извлечение квадратного корня x = sqrt( y ) 15 4 из числа с плавающей запятой Вычисление синуса числа x = sin( y ) 25 20 с плавающей запятой Вычисление логарифма числа x = log( y ) 25 20 с плавающей запятой Вычисление экспоненты числа x = exp( y ) 50 20 с плавающей запятой Операции над массивами Обращение к массиву целых чи- i = a[ 5 ] 1 1 сел с использованием константы Обращение к массиву целых чисел i = a[ j ] 1 1 с использованием переменной Обращение к двумерному i = a[ 3, 5 ] 1 1 массиву целых чисел с исполь- зованием констант Обращение к двумерному i = a[ j, k ] 1 1 массиву целых чисел с исполь- зованием переменных Обращение к массиву чисел x = z[ 5 ] 1 1 с плавающей запятой с исполь- зованием константы Обращение к массиву чисел x = z[ j ] 1 1 с плавающей запятой с исполь- зованием целочисленной переменной ( см. след. стр.) 588 ЧАСТЬ V Усовершенствование кода Табл. 25-2. (окончание) Относительное время выполнения Операция Пример C++ Java Обращение к двумерному x = z[ 3, 5 ] 1 1 массиву чисел с плавающей запятой с использованием констант Обращение к двумерному x = z[ j, k ] 1 1 массиву чисел с плавающей запятой с использованием целочисленных переменных Примечание: показатели, приведенные здесь, сильно зависят от локальной среды, компилятора и выполняемых компилятором видов оптимизации. Результаты, указанные для языков C++ и Java, нельзя сравнивать непосредственно. С момента выхода первого издания этой книги относительное быстродействие отмеченных операций значительно изменилось, так что, если вы все еще подхо- дите к оптимизации кода, опираясь на идеи 10-летней давности, пересмотрите свои взгляды. Большинство частых операций — в том числе вызовы методов, присваивание, ариф- метические операции над целыми числами и числами с плавающей запятой — имеет примерно одинаковую цену. Трансцендентные математические функции очень дороги. Вызовы полиморфных методов чуть дороже вызовов других методов. Табл. 25-2 или похожая таблица, которую вы можете создать сами, — ключ, от- крывающий все двери в мир быстрого кода, описанные в главе 26. В каждом слу- чае повышение быстродействия исходит из замены дорогой операции на более дешевую (см. главу 26). 25.4. Оценка производительности На небольшие фрагменты программы обычно приходится непропорционально большая доля времени ее выполнения, поэтому перед оптимизацией кода вам следует оценить его и найти в нем горячие точки. Обнаружив горячие точки и оптимизировав их, снова оцените код, чтобы узнать, насколько вы его улучшили. Многие аспекты производительности противоречат интуиции. Выше я уже при- вел один пример этого, когда 10 строк кода оказались в итоге значительно быст- рее и компактнее, чем одна строка. Опыт также не особо полезен при оптимизации. Опыт может быть ос- нован на использовании старого компьютера, языка или компилятора, но когда что-либо из этого изменяется, все начинается сначала. Невоз- можно точно сказать, каковы результаты оптимизации, не оценив их. Много лет назад я написал программу, суммирующую элементы матрицы. Перво- начальный код выглядел примерно так: ГЛАВА 25 Стратегии оптимизации кода 589 Пример простого кода, суммирующего элементы матрицы (C++) sum = 0; for ( row = 0; row < rowCount; row++ ) { for ( column = 0; column < columnCount; column++ ) { sum = sum + matrix[ row ][ column ]; } } Как видите, код был прост, но суммирование элементов матрицы должно было выполняться как можно быстрее, а я знал, что все обращения к массиву и проверки условий цикла довольно дороги. Я знал, что при каждом обращении к двумерному масси- ву выполняются дорогие операции умножения и сложения. Так, обработка мат- рицы размером 100 на 100 требовала 10 000 умножений и сложений, что допол- нялось еще и затратами, связанными с управлением циклами. Использовав указа- тели, рассудил я, я смогу просто увеличивать указатель, заменив 10 000 дорогих умножений на 10 000 относительно дешевых операций инкремента. Я тщательно преобразовал код и получил: Пример попытки оптимизации кода, суммирующего элементы матрицы (C++) sum = 0; elementPointer = matrix; lastElementPointer = matrix[ rowCount - 1 ][ columnCount - 1 ] + 1; while ( elementPointer < lastElementPointer ) { sum = sum + *elementPointer++; } Хотя код стал менее удобочитаемым, особенно для программистов, не являющихся экспертами в C++, я был очень доволен собой. Оно и понятно: все-таки я изба- вился от 10 000 умножений и многих операций, связанных с управлением цикла- ми! Я был так доволен, что решил подкрепить свои чувства конкретными цифра- ми и оценить повышение скорости, хотя в то время я выполнял это не всегда. Знаете, что я обнаружил? Никакого улучшения. Ни для мат- риц размером 100 на 100. Ни для матриц размером 10 на 10. Ни для каких-либо других матриц. Я был так разочаро- ван, что погрузился в ассемблерный код, сгенерированный компилятором, чтобы понять, почему моя оптимизация не сработала. К моему удивлению, оказалось, что я был не пер- вым, кому понадобилось перебирать элементы массива: ком- пилятор сам преобразовывал обращения к массиву в опе- рации над указателями. Я понял, что единственным резуль- татом оптимизации, в котором можно быть полностью уверенным без измерения производительности, является затруднение чтения кода. Если оценка эффектив- ности не оправдывает себя, не стоит приносить понятность кода в жертву сомни- тельному повышению производительности. Дополнительные сведения Джон Бентли описывает похожий слу- чай, когда переписывание кода с использованием указателей снизило производительность примерно на 10%. В другой си- туации этот же подход повысил производительность более чем на 50%. См. «Software Explora- torium: Writing Efficient C Prog- rams» (Bentley, 1991). Ни один программист никогда не мог предсказать или обнару- жить узкие места, не обладая данными. Что бы вы ни дума- ли, реальность окажется совер- шенно другой. Джозеф М. Ньюкамер (Joseph M. Newcomer) 590 ЧАСТЬ V Усовершенствование кода Оценка должна быть точной Оценка производительности должна быть точной. Измере- ние времени выполнения программы с помощью секундо- мера или путем подсчета «один слон, два слона, три слона» точным не является. Используйте инструменты профилиро- вания или системный таймер и методы, регистрирующие истекшее время выполнения операций. Используете ли вы инструмент, написанный другим программистом, или пишете для оценки производительности программы собственный код, убедитесь, что из- меряете время выполнения только того оптимизируемого кода. Опирайтесь на число тактов процессора, выделенных вашей программе, а не на время суток. Иначе при переключении системы с вашей программы на другую программу один из ваших методов будет оштрафован на время, выделенное другой программе. Кро- ме того, попытайтесь исключить влияние процесса оценки кода и запуска про- граммы на первоначальный и оптимизированный код. 25.5. Итерация Обнаружив в коде узкое место и попробовав его устранить, вы удивитесь, насколько можно повысить производительность кода путем его оптимизации. Единственная методика редко приводит к десятикратному улучшению, но методики можно эф- фективно комбинировать, поэтому даже после обнаружения одного удачного вида оптимизации продолжайте пробовать другие виды. Однажды я написал программную реализацию алгоритма Data Encryption Standard (DES). Ну, на самом деле я писал ее не один раз, а около тридцати. При шифрова- нии по алгоритму DES цифровые данные кодируются так, что их нельзя расшиф- ровать без правильного пароля. Этот алгоритм шифрования так хитер, что иног- да кажется, что он сам зашифрован. Моя цель состояла в том, чтобы файл объе- мом 18 кб шифровался на IBM PC за 37 секунд. Первая реализация алгоритма вы- полнялась 21 минуту 40 секунд, так что мне предстояла долгая работа. Хотя большинство отдельных видов оптимизации было незначительно, в сумме они привели к впечатляющим результатам. Никакие три или даже четыре вида оптимизации не позволили бы мне достичь цели, однако итоговая их комбина- ция оказалась эффективной. Мораль: если копать достаточно глубоко, можно до- биться подчас неожиданных результатов. Оптимизация алгоритма DES — самая агрессивная оптими- зация, которую я когда-либо проделывал. В то же время я никогда не создавал более непонятного и трудного в сопро- вождении кода. Первоначальный алгоритм был сложен. Код, получившийся в результате трансформаций высокоуровневого кода, оказался практически нечитаемым. После преобразования кода на ассемблер я получил один метод из 500 строк, на который боюсь даже смотреть. Это отношение между оп- тимизацией кода и его качеством справедливо почти всегда. Вот таблица, отра- жающая историю оптимизации: Перекрестная ссылка Методи- ки, указанные в этой таблице, обсуждаются в главе 26. Перекрестная ссылка Об инст- рументах профилирования см. подраздел «Оптимизация кода» раздела 30.3. |