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

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

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

С какими сбоями системы сборки вы сталкивались и как вы смогли ис править или даже предотвратить их?

В число обычных ошибок сборки входят:

•Неправильный сбор информации о зависимостях.

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

•Проблемы с контролем версий: некорректное слияние или выбор неправильных версий кода.

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

•Неумение программистов пользоваться системой сборки и соверше% ние ими глупых ошибок.

Если что%то пошло неожиданным путем, отчасти проблема вызвана системой сборки.

Глава 11. Жажда скорости

Вопросы для размышления

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

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

•Количество функций в противовес размеру кода

•Скорость программы в противовес расходу памяти

•Хранение и кэширование в противовес вычислению по требованию

•Защищенный подход в противовес незащищенному; оптимистич% ный в противовес пессимистичному

•Приближенные вычисления в противовес точным вычислениям

•Встроенные функции в противовес вызову функций; монолитность в противовес модульности

•Индексирование массива в противовес поиску в списке

				hang		e
			C				E
		X
	-							d
	F								t
	D								i
									r
P						NOW!			o
					BUY
				to
w Click								634m
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
Ответы и обсуждениеClick										m
w									o
	w
w								.c
	.
		p					g
			df			n		e
				-x cha

•Передача параметра по ссылке или адресу в противовес передаче копии

•Аппаратная реализация в противовес программной

•Жесткий, прямой доступ в противовес косвенному доступу

•Предопределенное, фиксированное значение в противовес перемен% ному и настраиваемому

•Выполнение во время компиляции в противовес выполнению на этапе исполнения

•Локальная функция в противовес удаленному вызову

•Отложенные вычисления в противовес немедленным вычислениям

•«Умный» алгоритм в противовес понятному коду

2.Посмотрите на альтернативы оптимизации, перечисленные в разделе «Доводы против оптимизации» на стр. 271. Допускаются ли при этом компромиссы, и если да, то какие?

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

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

3.Объясните значение следующих терминов и связь между ними:

•Производительность (Performance)

•Эффективность (Efficiency)

•Оптимизированность (Optimized)

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

4.Какие наиболее вероятные узкие места могут быть в медленно рабо тающей программе?

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

•Интенсивный обмен между оперативной памятью и файлом под%

качки на жестком диске.

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

5.Как устранить необходимость в оптимизации? Какие методы позволя ют избежать появления неэффективного кода?

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

Хорошо продумав архитектуру, пишите разумный код. Нужно знать, какие конструкции в выбранном вами языке наиболее эффективны, и избегать использования неэффективных. Например, в C++ лучше пе% редавать ссылки const, а не создавать дорогостоящие временные копии.1

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

6. Как влияет на оптимизацию наличие нескольких потоков?

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

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

7.Почему мы пишем неэффективный код? Главное, что мешает нам сразу воспользоваться высокопроизводительными алгоритмами?

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

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

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

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

				hang		e
			C				E
		X
	-							d
	F								t
	D								i
									r
P						NOW!			o
					BUY
				to
w Click								636m
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
Ответы и обсуждениеClick										m
w									o
	w
w								.c
	.
		p					g
			df			n		e
				-x cha

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

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

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

8.Тип данных List реализован с помощью массива. Какова будет алго ритмическая сложность следующих методов List в худшем случае?

a.Конструктор

b.append – добавление нового элемента в конец списка

c.insert – вставка нового элемента в заданном месте между двумя су ществующими элементами

d.isEmpty – возвращает true, если в списке нет элементов

e.contains – возвращает true, если в списке есть указанный элемент

f.get – возвращает элемент с указанным индексом

Оценки для худшего случая будут такими:

a.Сложность конструктора будет O(1), поскольку ему нужно лишь создать массив; вначале список пуст. Однако следует учесть, что размер этого массива влияет на сложность конструктора – в боль% шинстве языков массивы при создании полностью заполняются объектами, даже если вы не сразу собираетесь ими пользоваться. Если конструкторы этих объектов нетривиальны, выполнение кон% структора List займет некоторое время.

Размер массива может не фиксироваться – конструктор примет еще один параметр, который определит этот размер (фактически задав максимальный размер списка). Тогда сложность метода становится

O(n).

b.В среднем операция append имеет сложность O(1): она должна просто записать элемент массива и обновить размер списка. Но если мас% сив полон, придется выделять новую память, копировать и освобо% ждать память – в худшем случае сложность не меньше O(n) (зависит от производительности менеджера памяти).

1Выглядит глупо, но в эту ловушку легко попадают.