Методики оптимизации кода

Оптимизация кода уже давно привлекает пристальное внимание программистов. Если вы решили повысить производительность и хотите сделать это на уровне кода, то можете использовать целый ряд методик.

Производительность обычно охватывает и быстродействие, и объем кода, но при необходимости сокращения объема кода обычно лучше прибегнуть к перепроектированию классов и данных, а не к оптимизации кода. Последняя подразумевает небольшие изменения, а не изменения более крупномасштабных аспектов проектирования. Я просто хочу проиллюстрировать ряд видов оптимизации кода, которые вы сможете приспособить к своей ситуации.

Виды оптимизации, описываемые в этой главе, могут показаться похожими на виды рефакторинга, однако помните, что рефакторинг направлен на улучшение внутренней структуры программы (Fowler, 1999). То, о чем мы будем говорить, возможно, лучше называть «антирефакторингом». Эти изменения ухудшают внутреннуюю структуру программы ради повышения ее производительности. Это верно по определению. Если бы изменения не ухудшали внутреннюю структуру, мы не считали бы их видами оптимизации — мы использовали бы их по умолчанию и считали стандартными методиками кодирования.

Некоторые авторы характеризуют методики оптимизации кода как «практические правила» или приводят данные, говорящие о том, что определенный вид оптимизации непременно обеспечит желательный результат. Однако, как вы скоро увидите, концепция «практических правил» плохо описывает оптимизацию кода. Единственным надежным практическим правилом является оценка результатов каждого вида оптимизации в конкретной среде. Так что в этой главе представлен каталог «вещей, которые стоит попробовать»: многие из них в вашей среде пользы не принесут, но некоторые на самом деле окажутся очень эффективными.

Логика

Многие задачи программирования связаны с манипулированием логикой программы. В этом разделе мы рассмотрим эффективное использование логических выражений.

Прекращение проверки сразу же после получения ответа

Допустим, у вас есть выражение:

if ( 5 < x ) and ( x < 10 ) then ...

Как только вы определили, что x больше 5, вторую часть проверки выполнять не нужно.

Некоторые языки поддерживают так называемую «сокращенную оценку выражений», при которой компилятор генерирует код, автоматически прекращающий проверку после получения ответа. Сокращенная оценка выполняется, например, для стандартных операторов C++ и «условных» операторов Java.

Если ваш язык не поддерживает сокращенную оценку, избегайте операторов and иor, используя вместо них дополнительную логику. Для сокращенной оценки наш код следовало бы изменить так:

Принцип прекращения проверки сразу по получении ответа уместен и в других случаях. В качестве примера можно привести цикл поиска. Если вы сканируете массив введенных чисел и вам нужно только узнать, присутствует ли в массиве отрицательное значение, вы могли бы проверять значения по очереди, устанавливая при обнаружении отрицательного числа флаг negativeFound. Вот как выглядел бы такой цикл поиска:

Пример, в котором цикл продолжает выполняться даже после получения ответа (C++)

Лучше было бы прекращать просмотр массива сразу по обнаружении отрицательного значения. Любой из следующих советов привел бы к решению проблемы.

— Включите в код оператор break после строки negativeInputFound = true.

— Если язык не поддерживает оператор break, имитируйте его при помощи оператора goto, передающего управление первой команде, расположенной после цикла.

— Измените цикл for на цикл while и проверяйте значение negativeInputFound вместе с проверкой того, не превысил ли счетчик цикла значениеcount.

— Измените цикл for на цикл while, поместите сигнальное значение в первый элемент массива, расположенный после последнего исходного значения, а в условии цикла while просто проверяйте, не отрицательно ли значение. По завершении цикла узнайте, относится ли индекс обнаруженного отрицательного значения к исходному массиву или превышает на 1 индекс верхней границы массива. Подробнее о сигнальных значениях см. ниже.

Вот результаты использования ключевого слова break в коде C++ и Java:

Примечания:
(1) Временные показатели в этой и следующих таблицах данной главы указываются в секундах, а их сравнение имеет смысл только в пределах конкретных строк каждой из таблиц. Действительные показатели будут зависеть от компилятора, параметров компилятора и среды, в которой выполняется тестирование.

(2) Большинство результатов сравнительного тестирования основано на выполнении фрагментов кода от нескольких тысяч до многих миллионов раз, что призвано устранить колебания результатов.

(3) Конкретные марки и версии компиляторов не указываются. Показатели производительности во многом зависят от марки и версии компилятора.

(4) Сравнение результатов тестирования фрагментов, написанных на разных языках, имеет смысл не всегда, поскольку компиляторы разных языков не всегда позволяют задать одинаковые параметры генерирования кода.

(5) Фрагменты, написанные на интерпретируемых языках (PHP и Python), в большинстве случаев тестировались с использованием более чем в 100 раз меньшего числа тестов, чем фрагменты, написанные на других языках.

(6) Некоторые из показателей «экономии времени» не совсем точны из-за округления «времени выполнения кода до оптимизации» и «времени выполнения оптимизированного кода».

Результаты этого вида оптимизации во многом зависят от числа проверяемых значений и вероятности обнаружения отрицательного значения. В данном тесте число значений в среднем было равным 100, а отрицательные значения составляли половину всех значений.

Упорядочение тестов по частоте

Упорядочивайте тесты так, чтобы самый быстрый и чаще всего оказывающийся истинным тест выполнялся первым. Нормальные случаи следует обрабатывать первыми, а вероятность выполнения неэффективного кода должна быть низкой. Этот принцип относится к блокам case и цепочкам операторов if-then-else.

Рассмотрим, например, оператор Select-Case, обрабатывающий символы, вводимые с клавиатуры:

Пример плохо упорядоченного логического теста (Visual Basic)

Порядок обработки символов в этом фрагменте близок к порядку сортировки ASCII. Однако блоки case во многом похожи на большой набор операторов if-then-else, так что если первым введенным символом будет «a», данный фрагмент проверит, является ли символ математическим символом, числом, знаком пунктуации или пробелом, и только потом определит, что это алфавитно-цифровой символ. Зная примерную вероятность ввода тех или иных символов, вы можете разместить самые вероятные случаи первыми. Вот переупорядоченные блоки case:

Пример хорошо упорядоченного логического теста (Visual Basic)

Теперь наиболее вероятные символы обрабатываются первыми, что снижает общее число выполняемых тестов. При типичной смеси вводимых символов результаты этого вида оптимизации таковы:

С Visual Basic все ясно, а вот результаты тестирования кода Java и C# довольно неожиданны. Очевидно, это объясняется способом структурирования операторов switch-case в языках C# и Java: из-за необходимости перечисления всех значений по отдельности, а не в форме диапазонов, код C# и Java не выигрывает от этого вида оптимизации в отличие от кода Visual Basic. Это доказывает, что никакой из видов оптимизации не следует применять слепо: результаты будут во многом зависеть от реализации конкретных компиляторов.

Вы могли бы предположить, что для аналогичного набора операторов if-then-else компилятор Visual Basic сгенерирует похожий код. Взгляните на результаты:

Совершенно иная картина. Те же тесты на Visual Basic теперь выполняются медленнее в пять раз без оптимизации и в четыре — в случае оптимизированного кода. Это говорит о том, что для блоков case и операторов if-then-else компилятор генерирует разный код.

Результаты оптимизации операторов if-then-else более согласованны, но общая ситуация от этого не проясняется. Обе версии кода C# и Visual Basic, основанного на блокахcase, выполняются быстрее, чем обе версии кода, написанного на основе if-then-else, тогда как в случае Java все наоборот. Это различие результатов наводит на мысль о третьем виде оптимизации, описанном чуть ниже.

Сравнение быстродействия похожих структур логики

Описанное выше тестирование можно выполнить и для блоков case, и для операторов if-then-else. В зависимости от среды любой из подходов может оказаться более выгодным. Ниже данные из двух предыдущих таблиц представлены в форме, облегчающей сравнение быстродействия оптимизированного кода, написанного с применением обоих подходов:

Эти результаты не имеют логического объяснения. В одном из языков case гораздо лучше, чем if-then-else, а в другом наоборот. В третьем языке различие относительно невелико. Можно было бы предположить, что из-за похожего синтаксисаcase в C# и Java результаты тестирования этих языков также будут похожими, но на самом деле имеет место обратное.

Этот пример ясно показывает, что оптимизация кода не подчиняется ни «практическим правилам», ни «логике». Так что без оценки результатов вам не обойтись.

Замена сложных выражений на обращение к таблице

Иногда просмотр таблицы может оказаться более быстрым, чем выполнение сложной логической цепи. Суть сложной цепи обычно сводится к категоризации чего-то и выполнении того или иного действия, основанного на конкретной категории. Допустим, вы хотите присвоить чему-то номер категории на основе принадлежности этого чего-то к группам A, B и C:

Вот как эта задача решается при помощи сложной логической цепи:

Пример сложной логической цепи (C++)

Вместо этого теста вы можете использовать более модифицируемый и быстродействующий подход, основанный на просмотре табличных данных:

Пример использования таблицы вместо сложной логики (C++)

Определение этой таблицы кажется запутанным, но, если она хорошо документирована, читать ее будет не труднее, чем код сложной логической цепи. Кроме того, изменить таблицу будет гораздо легче, чем более раннюю логику. Вот результаты сравнения быстродействия обоих подходов:

Отложенные вычисления

Один из моих бывших соседей любил все откладывать на потом. В оправдание своей лени он говорил, что многое из того, что люди порываются сделать, делать просто не нужно. Если подождать достаточно долго, утверждал он, неважные дела канут в Лету, и он не будет тратить на них свое время.

Методика отложенных вычислений основана на принципе моего соседа: программа делает что-то, только когда это действительно нужно. Отложенное вычисление похоже на стратегию решения задач «по требованию», при которой работа выполняется максимально близко к тому месту, где нужны ее результаты.

Допустим, ваша программа работает с таблицей из 5000 значений, полностью генерируя ее при запуске и затем обращайтесь к ней по мере выполнения. Если программа использует только небольшую часть элементов таблицы, возможно, есть смысл вычислять их по мере надобности, а не все сразу. После вычисления элемента его можно сохранить на будущее (это называется «кэшированием»).

Циклы

Так как циклы выполняются многократно, горячие точки часто следует искать именно внутри циклов. Методики, описываемые в этом разделе, помогают ускорить выполнение циклов.

Размыкание цикла

Замыканием (switching) цикла называют принятие решения внутри цикла при каждой его итерации. Если во время выполнения цикла решение не изменяется, вы можете разомкнуть (unswitch) цикл, приняв решение вне цикла. Обычно для этого нужно вывернуть цикл наизнанку, т. е. поместить циклы в условный оператор, а не условный оператор внутрь цикла. Вот пример цикла до размыкания:

Пример замкнутого цикла (C++)

В этом фрагменте проверка if ( sumType == SUMTYPE_NET ) выполняется при каждой итерации, хотя ее результат остается постоянным. Вы можете ускорить выполнение этого кода, переписав его так:

Пример разомкнутого цикла (C++)

Этот фрагмент нарушает несколько правил хорошего программирования. Удобочитаемость и удобство сопровождения кода обычно важнее его быстродействия или размера, но целью является производительность, а для ее повышения часто нужно поступиться другими целями.

Размыкание этого цикла позволяет ускорить его выполнение примерно на 20%:

К сожалению, после размыкания цикла вам придется сопровождать оба цикла параллельно. Так, если переменную count потребуется заменить на clientCount, нужно будет изменить два фрагмента, что будет раздражать и вас, и всех других программистов, которым придется работать с вашим кодом.

Этот пример также иллюстрирует главную проблему оптимизации кода: результат любого отдельного вида оптимизации непредсказуем. Размыкание цикла оказалось выгодным для трех языков из четырех, но не для Visual Basic. В случае этой конкретной версии Visual Basic размыкание цикла только затруднило сопровождение кода, ничего не дав взамен. Урок очевиден: чтобы с уверенностью говорить о результатах любого вида оптимизации, вы должны их оценить. Никаких исключений.

Объединение циклов

Если два цикла работают с одним набором элементов, можно выполнить их объединение (jamming). Выгода здесь объясняется устранением затрат, связанных с выполнением дополнительного цикла. Например, на объединение претендуют следующие циклы:

Пример отдельных циклов, которые можно объединить (Visual Basic)

Объединение циклов обычно требует, чтобы условия циклов были одинаковы. В нашем примере оба цикла выполняются от 0 доemployeeCount % 1, поэтому мы можем их объединить:

Пример объединенного цикла (Visual Basic)

Результаты объединения циклов таковы:

Как и прежде, все зависит от конкретного языка.

С объединением циклов связаны два главных фактора риска. Во-первых, индексы двух объединенных циклов могут позднее измениться, утратив совместимость. Во-вторых, объединить циклы иногда трудно. Прежде чем объединять циклы, убедитесь, что это не нарушит работу остальных частей кода.

Развертывание цикла

Целью развертывания (unrolling) цикла является сокращение затрат, связанных с его выполнением. Если помните, после полного развертывания цикла из трех строк в главе 25 оказалось, что 10 отдельных обращений к массиву выполняются быстрее.

Полное развертывание цикла — быстрое решение, эффективное при малом числе элементов, но оно непрактично, если элементов много или вы не знаете заранее, с каким числом элементов вы будете иметь дело. Вот пример обычного цикла:

Пример цикла, допускающего развертывание (Java)

После частичного развертывания цикла при каждой его итерации обрабатывается не один случай, а два или более. Это ухудшает удобочитаемость, но не нарушает общность цикла. Вот цикл, развернутый один раз:

Пример однократного развертывания цикла (Java)

Как видите, мы заменили первоначальную строку a[ i ] = i на две строки и увеличиваем счетчик цикла на 2, а не на 1. Дополнительный код после циклаwhile нужен на случай нечетных значений переменнойcount, при которых цикл завершается, так и не обработав один элемент массива.

Конечно, девять строк хитрого кода труднее читать и сопровождать, чем пять строк простого. Что греха таить: после развертывания цикла качество кода ухудшилось. Однако любой подход к проектированию предполагает поиск компромиссных решений, и, даже если конкретная методика обычно плоха, в определенных обстоятельствах она может стать оптимальной.

Вот результаты развертывания цикла:

Возможность ускорения кода на 16–43% заслуживает внимания, хотя, как показывает тест кода, написанного на Python, тут тоже не все однозначно. Главная опасность при развертывании цикла — ошибка завышения или занижения на единицу в коде, обрабатывающем последнюю итерацию.

Что, если мы продолжим развертывание цикла? Принесет ли дополнительную выгоду двойное развертывание?

Пример двукратного развертывания цикла (Java)

Развертывание цикла во второй раз привело к таким результатам:

Итак, дальнейшее развертывание цикла может принести дополнительную пользу, а может и не принести, как показывает случай языка Java. В то же время сложность кода быстро возрастает. Если предыдущий фрагмент не кажется вам таким уж сложным, вспомните, что в самом начале он был циклом из пяти строк, и сами оцените компромисс между производительностью и удобочитаемостью.

Минимизация объема работы, выполняемой внутри циклов

Одной из методик повышения эффективности циклов является минимизация объема работы, выполняемой внутри цикла. Если вы можете вычислить выражение или его часть вне цикла и использовать внутри цикла результат вычисления, сделайте это. Это хорошая методика программирования, которая иногда улучшает удобочитаемость кода.

Допустим, у вас есть цикл, включающий сложное выражение с указателями:

Пример цикла, включающего сложное выражение с указателями (C++)

Присвоив результат выражения удачно названной переменной, вы улучшите удобочитаемость кода, а может, и ускорите его выполнение:

Пример упрощения сложного выражения с указателями (C++)

Дополнительная переменная quantityDiscount (оптовая скидка) ясно показывает, что элементы массиваbaseRate умножаются на показатель скидки. В первом фрагменте это совсем не было очевидно. Кроме того, вынесение сложного выражения за пределы цикла устраняет три разыменования указателей при каждой итерации, что приводит к таким результатам:

За исключением компилятора Java экономия времени не так уж и велика, поэтому при первоначальном кодировании вы можете применить любую методику, улучшающую удобочитаемость кода, и отложить работу над быстродействием на потом.

Сигнальные значения

Если цикл включает проверку сложного условия, время его выполнения часто можно сократить, упростив проверку. В случае циклов поиска это можно сделать, использовав сигнальное значение (sentinel value) — значение, которое располагается сразу после окончания диапазона поиска и непременно завершает поиск.

Классический пример сложной проверки, которую можно упростить с помощью сигнального значения, — условие цикла поиска, включающее проверки обнаружения нужной переменной и выхода за пределы диапазона поиска. Вот код такого цикла:

Пример проверки сложного условия цикла (C#)

При каждой итерации этого цикла проверяются два условия: !found и i < count. Проверка !found служит для определения того, найден ли нужный элемент. Проверка i < count нужна для предотвращения выхода за пределы массива. Кроме того, внутри цикла проверяются отдельные значения массива item[], так что на самом деле при каждой итерации цикла выполняются три проверки.

Этот вид циклов поиска позволяет объединить три проверки и выполнять при каждой итерации только одну проверку: для этого нужно поместить в конце диапазона поиска «сигнальное значение», завершающее цикл. В нашем случае можно просто присвоить искомое значение элементу, располагающемуся сразу после окончания диапазона поиска (объявляя массив, не забудьте выделить место для этого элемента). Далее вы проверяете по очереди каждый элемент: если вы достигаете сигнального значения, значит, нужного вам значения в массиве нет. Вот соответствующий код:

Пример использования сигнального значения для ускорения цикла (C#)

Если item содержит целые числа, выгода может быть весьма существенной:

Результаты, полученные для Visual Basic, особенно впечатляют, но и остальные тоже очень неплохи. Однако при изменении типа массива результаты также изменяются. Если item включает числа с плавающей запятой, результаты таковы:

Как обычно, многое зависит от языка.

Сигнальное значение можно использовать почти в любой ситуации, требующей выполнения линейного поиска, причем не только в массивах, но и в связных списках. Вы только должны тщательно выбирать сигнальные значения и с осторожностью включать их в структуры данных.

Вложение более ресурсоемкого цикла в менее ресурсоемкий

Если вы имеете дело с вложенными циклами, подумайте, какой из них должен быть внешним, а какой внутренним. Вот пример вложенного цикла, который можно улучшить:

Пример вложенного цикла, который можно улучшить (Java)

Ключ к улучшению цикла в том, что внешний цикл состоит из гораздо большего числа итераций, чем внутренний. С выполнением любого цикла связаны накладные расходы: в начале цикла индекс должен быть инициализирован, а при каждой итерации — увеличен и проверен. Общее число итераций равно 100 для внешнего цикла и 100 * 5 = 500 для внутреннего цикла, что дает в сумме 600 итераций. Просто поменяв местами внешний и внутренний циклы, вы можете снизить число итераций внешнего цикла до 5, тогда как число итераций внутреннего цикла останется тем же. В итоге вместо 600 итераций будут выполнены только 505. Можно ожидать, что перемена циклов местами приведет примерно к 16%-ому улучшению: (600 – 505) / 600 = 16%. На самом деле результаты таковы:

Значительные различия в очередной раз доказывают, что по поводу следствий оптимизации нельзя сказать ничего определенного, не оценив их в конкретной среде.

Снижение стоимости операций

Под снижением стоимости (strength reduction) понимают замену дорогой операции на более дешевую, например, умножения на сложение. Иногда внутри цикла выполняется умножение индекса на какие-то другие значения. Сложение обычно выполняется быстрее, чем умножение, и, если вы можете вычислить то же число, заменив умножение на прибавление значения при каждой итерации цикла, это скорее всего приведет к ускорению выполнения кода. Вот пример кода, основанного на умножении:

Пример умножения с использованием индекса цикла (Visual Basic)

Этот код прост, но дорог. В то же время цикл можно переписать так, чтобы при каждой итерации выполнялось более дешевое сложение:

Пример замены умножения на сложение (Visual Basic)

Этот вид изменения похож на купон, предоставляющий скидку со стоимости цикла. В первоначальном коде при каждой итерации выполнялось умножение выражения revenue * baseCommission * discount на счетчик цикла, увеличенный на единицу: сначала на 1, затем на 2, затем на 3 и т. д. В оптимизированном коде значение выражения revenue * baseCommission * discount присваивается переменной incrementalCommission. После этого при каждой итерации цикла значение incrementalCommission прибавляется к cumulativeCommission. При первой итерации оно прибавляется один раз, при второй — два, при третьей — три и т. д. Эффект тот же, что и при умножении incrementalCommission на 1, на 2, на 3 и т. д., но оптимизированный вариант дешевле.

Чтобы этот вид оптимизации оказался возможным, первоначальное умножение должно зависеть от индекса цикла. В данном примере индекс цикла был единственной изменяющейся частью выражения, поэтому мы и смогли сделать выражение более эффективным. Вот к чему это привело:

Изменения типов данных

Изменение типов данных может быть эффективным способом сокращения кода и повышения его быстродействия. Проектирование структур данных в этой кни# ге не рассматривается, но умеренные изменения реализации отдельных типов данных также могут повышать производительность. Ниже описано несколько способов оптимизации типов данных.

Использование целых чисел вместо чисел с плавающей запятой

Сложение и умножение целых чисел, как правило, выполняются быстрее, чем аналогичные операции над числами с плавающей запятой. Например, циклы выполняются быстрее, если индекс имеет целочисленный тип.

Пример неэффективного цикла с индексом с плавающей запятой (Visual Basic)

Сравните этот код с аналогичным циклом, в котором явно используется целочисленный индекс:

Пример эффективного цикла с целочисленным индексом (Visual Basic)

Насколько выгоден этот вид оптимизации? Вот результаты выполнения указанных фрагментов кода Visual Basic и аналогичных циклов, написанных на C++ и PHP:

Использование массивов с минимальным числом измерений

Использовать массивы, имеющие несколько измерений, накладно. Если вы сможете структурировать данные так, чтобы их можно было хранить в одномерном, а не двумерном или трехмерном массиве, вы скорее всего ускорите выполнение программы. Допустим, у вас есть подобный код инициализации массива:

Пример стандартной инициализации двумерного массива (Java)

При инициализации массива из 50 строк и 20 столбцов этот код выполняется вдвое дольше, чем код инициализации аналогичного одномерного массива, сгенерированный тем же компилятором Java. Вот как выглядел бы исправленный код:

Пример одномерного представления массива (Java)

А вот результаты тестирования этого кода и похожего кода, написанного на не# скольких других языках:

Примечание: временные показатели, указанные для Python и PHP, получены в результате более чем в 100 раз меньшего числа итераций, чем показатели, приведенные для других языков, поэтому их непосредственное сравнение недопустимо.

Результаты этого вида оптимизации прекрасны для Visual Basic и Java, хороши для PHP и Python, но довольно заурядны для C++ и C#. Правда, время выполнения неоптимизированного кода C# было лучшим, так что на это едва ли можно жаловаться. Широкий разброс результатов лишь подтверждает недальновидность слепого следования любым советам по оптимизации. Не испытав методику в конкретных обстоятельствах, ни в чем нельзя быть уверенным.

Минимизация числа обращений к массивам

Кроме минимизации числа обращений к двумерным или трехмерным массивам часто выгодно минимизировать число обращений к массивам вообще. Подходящий кандидат для применения этой методики — цикл, в котором повторно используется один и тот же элемент массива. Вот пример необязательного обращения к массиву:

Пример необязательного обращения к массиву внутри цикла (C++)

При изменении индекса discountLevel по мере выполнения внутреннего цикла обращение к массиву discount[ discountType ] остается все тем же. Вы можете вынести его за пределы внутреннего цикла, и тогда у вас будет одно обращение к массиву на одну итерацию внешнего, а не внутреннего цикла. Вот оптимизированный код:

Пример вынесения обращения к массиву за пределы цикла (C++)

Как обычно, результаты зависят от конкретного компилятора.

Использование дополнительных индексов

Использование дополнительного индекса предполагает добавление данных, связанных с основным типом данных и повышающих эффективность обращений к нему. Связанные данные можно добавить к основному типу или хранить в параллельной структуре.

Индекс длины строки

Примером использования дополнительного индекса может служить одна из форм представления строк. В языке C строки заканчиваются нулевым байтом. Что касается строк Visual Basic, то их длина хранится в начальном байте. Чтобы определить длину строки C, нужно начать с начала строки и продвигаться по ней, подсчитывая байты, до достижения нулевого байта. Для определения длины строки Visual Basic, нужно просто прочитать байт длины. Байт длины строки Visual Basic — наглядный пример дополнения типа данных индексом, ускоряющим выполнение определенных операций, таких как вычисление длины строки. Идею индексации длины можно приспособить к любому типу данных переменной длины. Слежение за длиной структуры часто — более эффективный подход, чем вычисление длины каждый раз, когда она требуется.

Независимая параллельная структура индексации

Иногда выгоднее работать с индексом типа данных, а не с самим типом данных. Если элементы типа данных велики или их накладно перемещать (скажем, на диск), сортировка и поиск по индексам будут выполняться быстрее, чем непосредственные операции над данными. Если каждый элемент данных велик, вы можете создать вспомогательную структуру, состоящую из ключевых значений и указателей на подробную информацию. Если различие размеров элемента структуры данных и элемента вспомогательной структуры достаточно велико, элемент-ключ можно хранить в памяти, а сами данные — на внешнем носителе. Все операции поиска и сортировки будут выполняться в памяти, а к диску можно будет обращаться только после определения точного расположения нужного вам элемента.

Кэширование

Кэширование — это такой способ хранения нескольких значений, при котором значения, используемые чаще всего, получить легче, чем значения, используемые реже. Так, если программа случайным образом читает записи с диска, метод может хранить в кэше записи, считываемые наиболее часто. Получив запрос записи, метод проверяет, имеется ли запись в кэше. Если да, запись возвращается непосредственно из памяти, а не считывается с диска.

Кэширование можно применять и в других областях. В программе обработки шрифтов Microsoft Windows узким местом было получение ширины символа при его отображении на экране. Кэширование ширины символа, использованного последним, позволило примерно вдвое ускорить отображение.

Вы можете кэшировать и результаты ресурсоемких вычислений, особенно если их параметры просты. Пусть, например, вам нужно найти длину гипотенузы прямоугольного треугольника по длинам двух катетов. Простая реализация этого метода была бы примерно такой:

Пример метода, напрашивающегося на кэширование (Java)

Если вы знаете, что те же значения скорее всего будут переданы в метод повторно, их можно кэшировать:

Пример кэширования для предотвращения дорогих вычислений (Java)

Вторая версия метода сложнее и объемнее первой, поэтому она должна обосновать свое право на жизнь быстродействием. Многие схемы кэширования предполагают кэширование более одного элемента, и с ними связаны еще большие затраты. Вот быстродействие двух версий метода:

Польза кэширования зависит от относительной стоимости обращения к кэшированному элементу, создания некэшированного элемента и сохранения нового элемента в кэше. Она также зависит от числа запросов кэшированной информации. Иногда она может зависеть и от аппаратного кэширования. В целом чем дороже генерирование нового элемента и чем чаще запрашивается та же самая информация, тем выгоднее кэширование. Чем дешевле обращение к кэшированному элементу и сохранение новых элементов в кэше, тем выгоднее кэширование. Как и другие методики оптимизации, кэширование усложняет код и часто оказывается источником ошибок.

Выражения

Многие задачи программирования требуют применения математических и логических выражений. Сложные выражения обычно дороги, и в этом разделе мы рассмотрим способы их удешевления. Алгебраические тождества Алгебраические тождества иногда позволяют заменить дорогие операции на более дешевые. Так, следующие выражения логически эквивалентны:
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(), можно ожидать, что это приведет к огромной экономии. Так и есть:

Снижение стоимости операций

Как уже было сказано, снижение стоимости операций подразумевает замену дорогой операции более дешевой. Вот некоторые возможные варианты:
— замена умножения сложением;
— замена возведения в степень умножением;
— замена тригонометрических функций их эквивалентами;
— замена типа longlong на long или int (следите при этом за аспектами производительности, связанными с применением целых чисел естественной и неестественной длины);
— замена чисел с плавающей запятой числами с фиксированной точкой или целые числа;
— замена чисел с плавающей запятой с удвоенной точностью числами с одинарной точностью;
— замена умножения и деления целых чисел на два операциями сдвига.

Допустим, вам нужно вычислить многочлен. Если вы забыли, что такое многочлены, напомню, что это выражения вида Ax² + Bx + C. Буквы A, B и C — это коэффициенты, а x — переменная. Обычный код вычисления значения многочлена n-ной степени выглядит так:

Пример вычисления многочлена (Visual Basic)

Если вы подумаете о снижении стоимости операций, то поймете, что оператор возведения в степень — не самое эффективное решение в этом случае. Возведение в степень можно заменить на умножение, выполняемое при каждой итерации цикла, что во многом похоже на снижение стоимости, выполненное нами ранее, когда умножение было заменено на сложение. Вот как выглядел бы код, снижающий стоимость вычисления многочлена:

Пример снижения стоимости вычисления многочлена (Visual Basic)

Если вы имеете дело с многочленами второй или более высокой степени, выгода может быть очень приличной:

Если вы действительно серьезно отнесетесь к снижению стоимости операций, то позаботитесь и о двух умножениях чисел с плавающей запятой. Стоимость операций, выполняемых в цикле, можно сделать еще меньшей, если постепенно возводить в нужную степень сразу несколько компонентов выражения, а не находить нужную степень при каждой итерации путем умножения:

Пример дальнейшего снижения стоимости вычисления многочлена (Visual Basic)

В этой версии метода отсутствует переменная powerOfX, а вместо двух умножений при каждой итерации выполняется одно. Результаты таковы:

Это хороший пример расхождения теории и практики. Код, имеющий сниженную стоимость, казалось бы, должен работать быстрее, но на деле это не так. Возможно, в Visual Basic снижение производительности объясняется декрементом счетчика цикла на 1 вместо инкремента, но чтобы говорить об этом с уверенностью, эту гипотезу нужно оценить.

Инициализация во время компиляции

Если вы вызываете метод, передавая ему в качестве единственного аргумента именованную константу или магическое число, попробуйте предварительно вычислить нужное значение, присвоить его константе и избежать вызова метода. Это же справедливо для умножения, деления, сложения и других операций.
Однажды мне понадобилось вычислять значение двоичного логарифма целого числа, округленное до ближайшего целого числа. Система не предоставляла метод вычисления двоичного логарифма, поэтому я написал собственный. Быстрый и легкий подход был основан на формуле:

log(x)base = log(x) / log(base)

Опираясь на это тождество, я написал такой метод:
Пример метода, вычисляющего двоичный логарифм с использованием системных методов (C++)

Этот метод был очень медленным, а так как значение log(2) измениться не может, я заменил вызов метода log(2) на действительное значение, равное 0.69314718:

Пример метода, вычисляющего двоичный логарифм с использованием системного метода и константы (C++)

Вызов метода log() довольно дорог — гораздо дороже преобразования типа или деления, и поэтому резонно предположить, что уменьшение числа вызовов метода log() вдвое должно примерно в два раза ускорить выполнение метода. Вот результаты измерений:

Обоснованное предположение оказалось довольно близким к действительности. Если учесть невысокую предсказуемость результатов, приводимых в этой главе, точность моего прогноза в этом случае доказывает только то, что даже слепые белки иногда наталкиваются на орехи.

Недостатки системных методов

Системные методы дороги и часто обеспечивают избыточную точность. Например, большинство системных математических методов написаны с тем расчетом, чтобы космонавт, отправившийся на Луну, прилунился с точностью ±2 фута. Если вам не нужна такая точность, нет смысла тратить на нее время.

В предыдущем примере метод Log2() возвращал целое число, но использовал для его вычисления метод log(), возвращающий число с плавающей запятой. Я не нуждался в такой точности, так что после своей первой попытки я написал ряд целочисленных проверок, которые прекрасно вычисляли целое значение двоичного логарифма:

Пример метода, возвращающего примерное значение двоичного логарифма (C++)

Этот метод использует целочисленные операции, никогда не преобразовывает целые числа в числа с плавающей запятой и значительно превосходит по быстродействию оба метода, работающих с числами с плавающей запятой:

Большинство так называемых «трансцендентных» функций разработано для наихудшего случая, т. е. внутри себя они даже целочисленный аргумент преобразуют в число с плавающей запятой с удвоенной точностью. Обнаружив вызов такой функции в проблемном фрагменте кода, уделите ей самое пристальное внимание, если, конечно, вам не нужна подобная точность.

Но вернемся к нашему методу. Еще один вариант его оптимизации основан на том факте, что деление на 2 аналогично операции сдвига вправо. Двоичный логарифм числа равен количеству операций деления на 2, которое можно выполнить над этим числом до получения нулевого значения. Вот как выглядит соответствующий код:

Пример альтернативного метода, определяющего примерное значение двоичного логарифма с использованием оператора сдвига вправо (C++)

Читать этот код трудно, особенно программистам, не работавшим с C++. Сложное выражение в условии цикла while — прекрасный пример того, что следует использовать только в крайних случаях. Этот метод выполняется примерно на 350% дольше, чем более длинная предыдущая версия (2,4 и 0,66 секунды соответственно), но он быстрее, чем первый оптимизированный метод, и легко адаптируется к 32-, 64-разрядным и другим средам.

Этот пример ясно показывает, насколько полезно продолжать поиск после нахождения первого успешного вида оптимизации. Первый вид оптимизации привел к приличному повышению быстродействия на 30–40%, но это не идет ни в какое сравнение с результатами второго и третьего видов оптимизации.

Использование констант корректного типа

Используйте именованные константы и литералы, имеющие тот же тип, что и переменные, которым они присваиваются. Если константа и соответствующая ей переменная имеют разные типы, перед присвоением константы переменной компилятор должен будет выполнить преобразование типа. Хорошие компиляторы преобразуют типы во время компиляции, чтобы не снижалась производительность в период выполнения программы. Однако менее эффективные компиляторы или интерпретаторы генерируют код, преобразующий типы в период выполнения. Чуть ниже указаны различия во времени инициализации переменной с плавающей точкой x и целочисленной переменной i в двух случаях. В первом случае инициализация выглядит так:
x = 5
i = 3.14

и требует преобразований типов. Во втором случае преобразования типов не нужны:

x = 3.14
i = 5
Результаты в очередной раз указывают на большие различия между компиляторами:

Предварительное вычисление результатов

При низкоуровневом проектировании часто приходится решать, вычислять ли результаты по ходу дела или лучше вычислить их один раз, сохранить и извлекать по мере надобности. Если результаты используются много раз, второй вариант часто предпочтительнее.

Этот выбор проявляется несколькими способами. На самом простом уровне вы можете вычислить часть выражения вне цикла вместо того, чтобы вычислять его внутри. Пример этого я приводил выше. На более сложном уровне вы можете вычислить табличные данные один раз при запуске программы и использовать их позднее; вы также можете сохранить результаты в файле данных или встроить их в программу.

Например, работая над игрой «звездные войны», программисты сначала вычисляли коэффициенты гравитации для разных расстояний от Солнца. Эти вычисления были ресурсоемкими и снижали производительность программы. Однако число разных расстояний, используемых в игре, было небольшим, поэтому разработчики в итоге вычислили коэффициенты гравитации предварительно и сохранили их в массиве из 10 элементов. Получение коэффициентов из массива оказалось гораздо более быстрым, чем их вычисление.

Допустим, у вас есть метод, вычисляющий сумму, которую нужно уплатить при погашении ссуды на покупку автомобиля. Код подобного метода мог бы выглядеть так:

Пример сложного выражения, которое можно вычислить предварительно (Java)

Формула вычисления платежей по ссуде сложна и довольно дорога. Помещение информации в таблицу, наверное, сделало бы вычисление более дешевым. Насколько крупной была бы эта таблица? Переменной с наибольшим диапазоном является переменная loanAmount. Переменная interestRate может принимать значения от 5% до 20% с шагом 0,25%, что дает нам 61 значение. Переменная months может иметь значение от 12 до 72, или 61 значение. Значение переменной loanAmount, вероятно, может находиться в пределах от 1000 до 100 000 долларов, и вам едва ли удастся сохранить все эти значения в таблице. Однако большая часть выражения не зависит от loanAmount, поэтому параметры действительно отвратительной части (знаменатель более крупного выражения) можно сохранить в таблице, индексируемой значениями interestRate и months. Значение loanAmount нужно будет вычислять:

Пример предварительного вычисления сложного выражения (Java)

Итак, сложное вычисление мы заменили вычислением индекса массива и одним обращением к массиву. К чему же это привело?

В зависимости от обстоятельств вы должны были бы предварительно вычислять массив loanDivisor при инициализации программы или читать его из файла. Вы также могли бы инициализировать массив нулями, вычислять каждый элемент при его первом запросе, сохранять его, а впоследствии просто извлекать из массива. Это было бы одной из форм кэширования, которое обсуждалось выше.

Предварительное вычисление выражения не обязывает вас создавать таблицу — возможен и иной вариант. Допустим, у вас есть код, вычисляющий взносы, которые нужно уплатить при погашении ссуд на разную сумму:

Пример второго сложного выражения, которое можно вычислить предварительно (Java)

Даже без таблицы, вы можете предварительно вычислить сложную часть выражения вне цикла и использовать найденное значение внутри цикла:

Пример предварительного вычисления второго сложного выражения (Java)

Этот вид оптимизации похож на уже рассмотренные нами методики, предполагающие вынесение обращений к массиву и разыменований указателей за пределы цикла. Результаты оптимизации кода Java в данном случае сравнимы с результатами предыдущего вида оптимизации, основанного на предварительном вычислении табличных данных:

В отличие от первой попытки оптимизации быстродействие кода Python сейчас также выросло. Это происходит довольно часто: если один вид оптимизации не приводит к желаемым результатам, другой, казалось бы, аналогичный вид оказывается очень эффективным.

Оптимизация программы путем предварительного вычисления выражений имеет несколько вариантов:
— вычисление результатов до выполнения программы и связывание их с константами во время компиляции;
— вычисление результатов до выполнения программы и присвоение их переменным, используемым в период выполнения;
— вычисление результатов до выполнения программы и сохранение их в файле, загружаемом в период выполнения;
— однократное вычисление результатов при запуске программы и их использование во всех последующих случаях;
— вычисление как можно большего числа значений до начала цикла, позволяющее свести к минимуму объем работы, выполняемой внутри цикла;
— вычисление результатов при возникновении первой потребности в них и их сохранение, позволяющее получить результаты, когда они понадобятся снова.

Устранение часто используемых подвыражений

Если какое-то выражение повторяется в коде несколько раз, присвойте его значение переменной и используйте переменную вместо вычисления выражения в нескольких местах. Подвыражение, которое можно устранить, уже встречалось нам в предыдущем подразделе:

Пример часто используемого подвыражения (Java)

Вместо двукратного вычисления выражения interestRate/12.0 вы можете присвоить его переменной и обратиться к ней два раза. Если вы присвоите переменной удачное имя, этот вид оптимизации не только повысит производительность кода, но и улучшит его удобочитаемость. Вот оптимизированный код:

Пример устранения часто используемого подвыражения (Java)

Результаты не впечатляют:

По-видимому, метод Math.pow() настолько дорог, что он перекрывает выгоду устранения подвыражения. Возможно также, что подвыражение уже было устранено компилятором. Если бы подвыражение составляло не такую малую часть стоимости всего выражения или если бы оптимизатор компилятора был менее эффективен, этот вид оптимизации, наверное, оказал бы большее влияние на производительность.

Методы

Одним из самых эффективных способов оптимизации кода является грамотная декомпозиция программы на методы. Небольшие, хорошо определенные методы делают программу компактнее, устраняя повторяющиеся фрагменты кода. Они упрощают оптимизацию, потому что рефакторинг одного метода улучшает все методы, которые его вызывают. Небольшие методы относительно легко переписать на низкоуровневом языке. Объемные хитроумные методы понять сложно, а после переписывания их на низкоуровневом языке вроде ассемблера это вообще невыполнимо.

Встраивание методов

На заре программирования вызывать методы на некоторых компьютерах было крайне дорого. Вызов метода означал, что ОС должна выгрузить программу, загрузить каталог методов, загрузить конкретный метод, выполнить метод, выгрузить метод и снова загрузить вызвавший метод. Все это потребляло много ресурсов и замедляло программу. Современные компьютеры облагают вызовы методов гораздо меньшей пошлиной. Например, встраивание метода копирования строк приводит к таким результатам:

В некоторых случаях вы можете сэкономить несколько наносекунд, встроив код метода в программу, используя ключевое слово inline языка C++ или аналогичную возможность. Если ваш язык не поддерживает inline непосредственно, но имеет препроцессор макросов, вы можете встраивать код при помощи макроса, включая и выключая встраивание по требованию. Однако современные компьютеры (под «современными» я понимаю любые машины, с которыми вы можете столкнуться в своей работе), при вызове метода почти не тратят дополнительных ресурсов. Как показывает пример, встроив код, вы можете как улучшить производительность, так и ухудшить ее.

Переписывание кода на низкоуровневом языке

Давняя мудрость, которую не стоит оставлять без внимания, гласит, что при низком быстродействии код следует переписать на языке низкого уровня. Если вы пишете на C++, языком низкого уровня может быть ассемблер, если на Python — C. Переписывание кода на низкоуровневом языке обычно положительно влияет и на быстродействие кода, и на его объем. Типичный подход к оптимизации при помощи низкоуровневого языка таков.

1.Напишите все приложение на высокоуровневом языке.
2. Выполните полное тестирование приложения и проверьте его корректность. 3. Если производительность недостаточна, выполните профилирование приложения с целью выявления горячих точек. Так как около 50% времени выполнения программы обычно приходится примерно на 5% кода, горячими точками обычно будут небольшие фрагменты программы.
4. Перепишите несколько небольших фрагментов на низкоуровневом языке для повышения общей производительности программы.

Последуете ли вы по этому проторенному пути, зависит от того, насколько хорошо вы программируете на низкоуровневых языках, насколько хорошо проблема подходит для решения на низкоуровневом языке, а также от степени вашего отчаяния. Сам я впервые применил эту методику при реализации алгоритма Data Encryption Standard. Я перепробовал все виды опти# мизации, о которых когда-либо слышал, но программа все равно работала вдвое медленнее, чем нужно. Мне ничего не оставалось делать, кроме как переписать часть программы на ассемблере. Не имея особого опыта программирования на ассемблере, я по сути ограничился простым переводом кода с высокоуровневого языка на ассемблер, но даже этот примитивный подход ускорил выполнение программы на 50%. Рассмотрим переписывание на ассемблере метода, преобразующего двоичные данные в символы ASCII верхнего регистра. В следующем примере показан соответствующий код Delphi:

Пример кода на Delphi, который лучше переписать на ассемблере

Трудно увидеть жир в этом коде, однако он содержит много манипуляций с битами, что не является сильной стороной Delphi. А вот ассемблер подходит для этого как нельзя лучше, так что этот код является хорошим кандидатом на переписывание. Вот что получается в итоге:

Пример метода, переписанного на ассемблере

Переписывание этого кода на ассемблере привело к уменьшению времени выполнения на 41%. Логично предположить, что код, написанный на языке, более подходящем для операций над битами, (скажем, на C++), менее восприимчив к этому виду оптимизации, чем код Delphi. Проверим:

Второй столбец этой таблицы отражает эффективность двух языков в отношении операций над битами. После оптимизации время выполнения стало почти одинаковым — перевод кода на ассемблер свел к минимуму первоначальные различия между Delphi и C++.

Полученный нами метод показывает, что результатом переписывания кода на ассемблере не всегда является огромный и уродливый метод. Итоговый код часто оказывается довольно компактным. Иногда ассемблерный код почти так же компактен, как его высокоуровневый эквивалент.

Существует одна относительно легкая и эффективная стратегия переписывания кода на ассемблере. В самом начале воспользуйтесь компилятором, генерирующем ассемблерные листинги во время компиляции. Извлеките ассемблерный код метода, который вам нужно оптимизировать, и сохраните его в отдельном исходном файле. Используя этот код как основу, выполните оптимизацию вручную, проверяя корректность кода и оценивая улучшения на каждом этапе. Некоторые компиляторы вставляют в ассемблерный код высокоуровневые операторы в форме комментариев. Если ваш компилятор на это способен, можете сохранить первоначальные операторы в ассемблерном коде в качестве документации.