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
279Click										m
w									o
	w
w								.c
	.
		p					g
			df			n		e
				-x cha

Вот несколько очень важных советов, касающихся проведения заме% ров времени:

•Используйте одни и те же входные данные в тестах, проводимых до и после оптимизации. В противном случае ваши тесты окажутся бессмысленными; вы будете сравнивать хрен с апельсином. Лучше всего воспользоваться автоматизированным контрольным приме% ром (см. «Руками не трогать!» на стр. 203) – с такого же рода реаль% ными репрезентативными данными, как при профилировании.

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

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

Оптимизация кода

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

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

После оптимизации

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

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

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

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

				hang		e
			C				E
		X
	-							d
	F								t
	D								i
									r
P						NOW!			o
					BUY
				to
w Click								280m
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

Существуют различные виды оптимизации. Какой из них подойдет в вашем случае, зависит от конкретной проблемы, вашей цели (напри% мер, увеличить скорость или уменьшить размер кода) и требуемой сте% пени оптимизации.

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

Чаще всего возникает задача повысить скорость выполнения. Для по% вышения скорости предлагаются следующие пути:

•Заменить медленный код быстрым

•Реже обращаться к медленному коду

•Откладывать выполнение медленного кода до того момента, когда оно реально потребуется

Другие распространенные задачи оптимизации – уменьшение требуе% мой памяти (в основном путем изменения представления данных, мо% дификации схемы работы с памятью или сокращения объема данных, одновременно находящихся в памяти) или уменьшение размера вы% полняемого модуля (путем сокращения функциональности или удале% ния повторяющегося кода). Как будет продемонстрировано, эти зада% чи часто противоречат одна другой: рост скорости часто происходит за счет увеличения потребления памяти, и наоборот.

Конструктивные изменения

Имеются в виду макрооптимизации – крупные изменения, направ% ленные на улучшение внутренней конструкции вашего программного продукта. Исправлять плохой проект тяжело. Чем ближе срок завер% шения проекта, тем менее вероятно, что вы станете вносить конструк% тивные изменения; это слишком рискованно.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
281Click										m
w									o
	w
w								.c
	.
		p					g
			df			n		e
				-x cha

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

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

Точность связана не только с типами данных; эту тактику можно развить гораздо глубже, выбирая те или иные алгоритмы или каче% ство представления результирующих данных. Можно также оста% вить решение на усмотрение пользователя – выбрать режим мед# ленной, но точной работы или быстрой, но приближенной.

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

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

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

•Не злоупотреблять исключениями (exceptions). Они могут поме% шать компилятору выполнить оптимизацию1 и нанести ущерб бы% стродействию, если применяются слишком часто.

•Отказаться от определенных средств языка, если это поможет сократить объем кода. Некоторые компиляторы C++ позволяют

1Как и функции, блоки try/catch представляют собой препятствие для опти% мизатора. Через них не видно, есть ли возможность оптимизации, поэтому

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

				hang		e
			C				E
		X
	-							d
	F								t
	D								i
									r
P						NOW!			o
					BUY
				to
w Click								282m
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

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

•Ограничить функциональность: самый быстрый код тот, который во% обще не выполняется. Функция будет работать медленно, если она делает много вещей, которые не нужны. Уберите все лишнее. Перене% сите его в какое%нибудь другое место. Откладывайте выполнение вся% кой работы до того времени, когда она действительно понадобится.

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

Обозначения для сложности

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

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

Алгоритмическая сложность обозначается с помощью «О боль% шого» – системы, придуманной немецким специалистом по тео% рии чисел Эдмундом Ландау. Задача с размером входных дан% ных n может иметь сложность:

O(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
283Click										m
w									o
	w
w								.c
	.
		p					g
			df			n		e
				-x cha

O(n): порядка n

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

O(n2): порядка n в квадрате

В этом случае дело с производительностью гораздо хуже: сложность растет быстрее, чем объем входных данных. Алго% ритм с квадратичным временем может быть совсем не плох, когда объем входных данных для него невелик, но для боль% ших наборов данных он может выполняться очень долго. Ал% горитм пузырьковой сортировки имеет сложность O(n2).

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

Обозначения в виде «О большого» не содержат констант или чле% нов более низкого порядка. Вы едва ли встретите сложность типа O(2n+6). Когда n достаточно велико, эти константы и члены более низкого порядка становятся несущественны.

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

Алгоритмы

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

Рассмотрим конкретный пример. Пусть некоторый алгоритм вы% полняет цикл 1000 раз. Каждый проход тела цикла занимает 5 мил% лисекунд. Вся операция, таким образом, длится около 5 секунд. До% пустим, модифицировав код внутри цикла, вы сократите каждую итерацию на 1 мс; это даст вам выигрыш в 1 секунду. Неплохо.