Изучите ограничения

(В оригинале - Know Your Limits)

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

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

Сложность определяется функцией O(f(n)), являющейся для n, равного размеру входных данных, приближенным значением требуемого объема памяти или времени по мере приближения n к бесконечности. Важные классы сложности включают ln(n), n, n ln(n), ne, and en

Графическое представление наглядно показывает, что по мере роста n O(ln(n)) значительно меньше, чем O(n) и O(n ln(n)), а n в свою очередь значительно меньше O(ne) и O(en). Для доступных значений n можно выделить три класса сложности – константная, линейная и бесконечная.

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

	access time	capacity
register	< 1 ns	64b
cache line		64B
L1 cache	1 ns	64 KB
L2 cache	4 ns	8 MB
RAM	20 ns	32 GB
disk	10 ms	10 TB
LAN	20 ms	> 1 PB
internet	100 ms	> 1 ZB

Заметьте, что объемы и быстродействие отличаются на несколько порядков. Кэширование используется практически на всех уровнях, чтобы скрыть эти различия, однако оно работает лишь для предсказуемого доступа. При частых «промахах кэша» система может замедлиться в разы. Например, чтобы в случайном порядке прочитать все байты жесткого диска, может понадобиться 32 года. А чтобы случайно просмотреть всю оперативную память – 11 минут. Случайный доступ непредсказуем. Исходя из этого, следует помнить, что повторный доступ к уже использовавшимся элементам и последовательный доступ практически всегда работают эффективно.

Алгоритмы и структуры данных значительно отличаются по эффективности использования кэша. Например:

• Линейный поиск выполняет последовательный перебор, но требует O(n) сравнений

• Бинарный поиск в отсортированном массиве требует лишь O(log(n)) сравнений

• Поиск по дереву van Emde Boas также требует O(log(n)) сравнений и при этом эффективно использует кэш (cache-oblivious)

Элементы	Время поиска (нс)
	линейный	бинарный	vEB
8	50	90	40
64	180	150	70
512	1200	230	100
4096	17000	320	160

И как же сделать выбор? Измеряя. В таблице показано время, требуемое для поиска 64-битного целого числа тремя методами в массивах различного размера. На моем компьютере линейный поиск наиболее выгоден для небольших массивов, однако существенно проигрывает при увеличении размера. Алгоритм van Emde Boas выигрывает всегда благодаря предсказуемому доступу к данным.

Автор оригинала - Greg Colvin