hang		e
			C				E
		X
	-							d
	F								t
	D								i
									r
P						NOW!			o
					BUY
				to
w Click								284m
w
	w								o
	.							.c
		p					g
			df			n		e
				-xcha

				hang		e
			C				E
		X
	-							d
	F								t
	D								i
									r
P						NOW!			o
					BUY
				to
Глава 11. Жажда скоростиClick										m
w									o
	w
w								.c
	.
		p					g
			df			n		e
				-x cha

Но лучше, если найдется алгоритм, у которого каждая итерация длится 7 мс, но зато их требуется повторить всего 100 раз. Тогда вы сэкономите 4,5 секунды, что существенно лучше.

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

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

Структуры данных

Структуры данных тесно связаны с выбором алгоритмов; некото% рые алгоритмы требуют определенных структур данных, и наобо% рот. Если программа требует слишком много памяти, изменение формата хранения данных может поправить дело, хотя часто это от% рицательно сказывается на скорости выполнения. Если нужно бы% стро провести поиск в списке из 1000 элементов, не храните их в ли% нейном массиве со скоростью поиска O(n) – воспользуйтесь бинар% ным деревом (которое больше) и поиском за O(log n).

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

Модификация кода

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

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

1Она включает в себя сложный анализ кода с целью выявления возможных

способов ускорения работы и выбора наиболее подходящих из них.

				hang		e
			C				E
		X
	-							d
	F								t
	D								i
									r
P						NOW!			o
					BUY
				to
w Click								Методыm		оптимизации
w
	w								o
	.							.c
		p					g
			df			n		e
				-xcha

				hang		e
			C				E
		X
	-							d
	F								t
	D								i
									r
P						NOW!			o
					BUY
				to
285Click										m
w									o
	w
w								.c
	.
		p					g
			df			n		e
				-x cha

Многие компиляторы позволяют определить цель оптимизации – уско% рение работы или уменьшение размера кода.

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

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

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

Развертывание циклов может быть частичным, что бывает оправда% но для больших циклов. Можно выполнить в каждой итерации че% тыре операции и каждый раз увеличивать счетчик цикла на четы% ре. Однако такой прием оказывается затруднителен, если количест% во итераций цикла не кратно количеству развернутых операций.

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

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

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

Затруднительно встраивание обращений к рекурсивным функциям – как узнать, когда нужно остановиться? Попытайтесь заменить ре% курсию другими алгоритмами.

Встраивание часто открывает возможность дальнейшей оптимиза% ции на уровне кода (ранее невозможной внутри границ функции).

				hang		e
			C				E
		X
	-							d
	F								t
	D								i
									r
P						NOW!			o
					BUY
				to
w Click								286m
w
	w								o
	.							.c
		p					g
			df			n		e
				-xcha

				hang		e
			C				E
		X
	-							d
	F								t
	D								i
									r
P						NOW!			o
					BUY
				to
Глава 11. Жажда скоростиClick										m
w									o
	w
w								.c
	.
		p					g
			df			n		e
				-x cha

Свертывание констант

Вычисления с использованием констант можно проводить во время компиляции, что сокращает объем действий, проводимых на этапе выполнения. Простое выражение типа return 6+4; можно свести к return 10;. В результате упорядочения членов большого выражения можно свести вместе две константы, что позволит сократить выра% жение.

Обычно программисты не пишут таких очевидных вещей, как return 6+4;. Однако такого рода выражения часто встречаются по% сле расширений макросов.

Перенос действий в этап компиляции

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

Понижение прочности

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

Вложенные выражения

Устранение одинаковых вложенных выражений позволяет избе% жать повторного вычисления выражений, значения которых не из% менились. В коде

int first = (a * b) + 10; int second = (a * b) / c;

выражение (a * b) вычисляется два раза. Достаточно одного. Можно выделить общее выражение и заменить его на

int temp = a * b; int first = temp + 10; int second = temp / c;

Удаление «мертвого» кода

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

Это были весьма неприятные типы оптимизации, но те, что приводят% ся ниже, более приемлемы. Они нацелены на ускорение работы про% граммы.

				hang		e
			C				E
		X
	-							d
	F								t
	D								i
									r
P						NOW!			o
					BUY
				to
w Click								Методыm		оптимизации
w
	w								o
	.							.c
		p					g
			df			n		e
				-xcha

				hang		e
			C				E
		X
	-							d
	F								t
	D								i
									r
P						NOW!			o
					BUY
				to
287Click										m
w									o
	w
w								.c
	.
		p					g
			df			n		e
				-x cha

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

•Перепишите эту функцию, выбрав другой язык. Например, перепи% шите критическую Java%функцию на C, воспользовавшись интер% фейсом Java Native Interface (JNI). Обычные компиляторы все еще превосходят JIT%интерпретаторы по скорости.

Не будьте наивны, думая, что один язык быстрее другого – многих программистов удивило, сколь малую выгоду приносит использо% вание JNI. Часто утверждают, что OO%языки гораздо медленнее со% ответствующих процедурных. Это неправда. Плохой OO%код может быть таким же медленным, как и плохой процедурный код. Если вы станете писать код в OO%стиле на C, то он, скорее всего, будет ра% ботать медленнее, чем код, правильно написанный на C++; компи% лятор C++ сгенерирует более эффективный код для вызова мето% дов, чем вы сможете сделать это вручную.

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

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

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

Выведите вычисления, дающие неизменный результат, за рамки цикла. Самый незаметный источник этой проблемы встречается в условии цикла. Если вы напишете for (int n = 0; n < tree.apple Count(); ++n), но appleCount() пересчитывает 1000 объектов при каж% дом обращении, цикл окажется очень медленным. Выполните под% счет до входа в цикл:

int appleCount = tree.appleCount(); for (int n = 0; n < appleCount; ++n)

{

... какие то действия ...

}

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

				hang		e
			C				E
		X
	-							d
	F								t
	D								i
									r
P						NOW!			o
					BUY
				to
w Click								288m
w
	w								o
	.							.c
		p					g
			df			n		e
				-xcha

				hang		e
			C				E
		X
	-							d
	F								t
	D								i
									r
P						NOW!			o
					BUY
				to
Глава 11. Жажда скоростиClick										m
w									o
	w
w								.c
	.
		p					g
			df			n		e
				-x cha

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

•Пользуйтесь справочными таблицами (lookup tables) для сложных вычислений, экономя время за счет памяти. Например, вместо того чтобы писать тригонометрические функции и вычислять потом их значения, выполните вычисления заранее и поместите в массив. Отобразите входные значения в индексы этого массива.

•Пользуйтесь укороченными вычислениями (short#circuit evaluation). Размещайте проверки, отрицательный результат которых наиболее вероятен, в самом начале, чтобы сэкономить время. Если вы пишете условное выражение if (condition_one && condition_two), то сделайте так, чтобы условие condition_one с большей вероятностью оказыва% лось невыполненным, чем condition_two (если только condition_one не выступает в качестве защиты для верности condition_two).

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

Оптимизация на уровне кода с целью сокращения объема памяти мо% жет осуществляться такими способами:

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

•Выделение стандартного кода в общую функцию и устранение дуб% лирования кода.

•Перенесение редко используемых функций в другое место. Помес% тите их в динамически загружаемую библиотеку или в отдельную программу.

Разумеется, предельная оптимизация может быть достигнута, если вы перепишете не удовлетворяющий вас участок кода на ассемблере – тут вы получите полный контроль над процессором и возможность любых действий (включая самоубийственные). Это последнее средство, в ко% тором практически никогда нет необходимости. Современные компи% ляторы производят вполне приемлемый код, и время, потраченное на написание, отладку и сопровождение «оптимизированных» разделов кода, не окупается достигаемым ростом эффективности.

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

с диска.