Числа, которые стоит знать
Также: Latency numbers · Latency numbers every programmer should know · Numbers everyone should know · задержки памяти, диска и сети · если наносекунда — секунда · прикидка на салфетке · back-of-the-envelope
Сложение — треть наносекунды, чтение из памяти — сотня наносекунд, пакет через океан — полторы сотни миллисекунд. Растяните время в миллиард раз, и это будет треть секунды, пара минут и почти пять лет. Здесь эти числа измерены на сервере сайта и в вашем браузере, а тренажёр учит прикидывать по ним время настоящих задач.
Сколько стоит одна операция? Сложение двух чисел — треть наносекунды. Чтение из памяти, если нужного числа нет в кэше, — около сотни наносекунд. Пакет через океан и обратно — полторы сотни миллисекунд. Между первым и последним девять порядков, и на таких расстояниях интуиция не работает. Растянем время в миллиард раз: наносекунда станет секундой, а остальное — минутами, днями и годами.
Строки про память измерены на сервере этого сайта. Строку «запрос к серверу» ваш браузер меряет прямо сейчас: это дорога до сервера и обратно вместе с его работой — лучший из пяти запросов. Кнопка измерит память вашего устройства тем же способом, что и на сервере. Остальное — типичные порядки: у вашего SSD своё число, но оно ближе к десяткам микросекунд, чем к единицам или к тысячам.
Идея
Для прикидки не нужны точные значения — нужны порядки и то, что соседние ступени лестницы различаются в десятки и сотни раз. Кэш — наносекунды, память — сотня наносекунд, SSD — десятки микросекунд, сеть внутри дата-центра — доли миллисекунды, жёсткий диск — миллисекунды, сеть через океан — сотня миллисекунд. Прикидка — это сумма слагаемых «сколько раз × сколько стоит», и почти всегда одно слагаемое больше всех остальных вместе. Найти его — значит понять, что ускорять, а что можно не трогать.
Таблицы таких чисел давно ходят среди программистов. Одну Питер Норвиг приводит к своему эссе «Научитесь программировать за десять лет», другую Джефф Дин показывал в докладах о больших распределённых системах в конце 2000-х под заголовком «Числа, которые должен знать каждый». С тех пор процессоры стали быстрее, жёсткие диски уступили место SSD, но чтение из памяти так и осталось около сотни наносекунд, а свет быстрее не стал: в оптоволокне он проходит около 200 километров за миллисекунду, и путь в 10 000 километров туда и обратно не займёт меньше 100 мс, как ни ускоряй серверы. Порядки держатся десятилетиями. Как устроены кэши и почему лестница именно такая — в главе курса «Близко и далеко»; здесь — как этими числами пользоваться.
Шпаргалка
| Операция | Время | Если 1 нс = 1 с |
|---|---|---|
| Такт процессора на 3 ГГц | 0,3 нс | 0,3 с |
| Чтение из кэша первого уровня | 1–2 нс | 1–2 с |
| Чтение из оперативной памяти мимо кэша | 100 нс | почти 2 мин |
| Прочитать 1 МБ из памяти подряд | 50–100 мкс | 14–28 ч |
| Случайное чтение 4 КБ с SSD | 20–100 мкс | 6–28 ч |
| Туда и обратно внутри дата-центра | 0,1–0,5 мс | 1–6 дней |
| Прочитать 1 МБ с SSD подряд | 0,2–1 мс | 2–12 дней |
| Прочитать 1 МБ с жёсткого диска подряд | 5 мс | 2 мес. |
| Случайное чтение с жёсткого диска | 5–10 мс | 2–4 мес. |
| Передать 1 МБ по сети 1 Гбит/с | 8 мс | 3 мес. |
| Туда и обратно через океан | 100–200 мс | 3–6 лет |
Обратите внимание на пары «случайно» и «подряд». Задержка — сколько ждать первого байта, пропускная способность — сколько байт в секунду потом. Случайное чтение с SSD — 50 мкс на 4 КБ, около 80 МБ/с, если читать по одному, а подряд тот же SSD отдаёт гигабайты в секунду — в десятки раз больше. С памятью то же самое, и это видно на замере.
Лестница памяти на сервере сайта
Почему в таблице чтение из памяти одно, а в сцене их три? Потому что цена чтения зависит от того, сколько памяти программа трогает. Программа ниже бегает по массиву в случайном порядке, и каждое следующее чтение зависит от предыдущего: адрес следующего шага лежит в текущей ячейке. Процессор не может ни угадать адрес, ни прочитать наперёд, и время шага — это задержка той ступени, куда помещается массив. Второй ряд — те же числа, прочитанные подряд.
На Go — переключатель над графиком — ступеньки видны отчётливо. Пока массив помещается в кэш первого уровня, шаг стоит пару наносекунд, в следующих кэшах — несколько, а когда массив перестаёт помещаться в кэш совсем — около сотни. Подряд — четверть наносекунды на число при любом размере: процессор замечает, что адреса идут подряд, и подкачивает строки памяти заранее, а одна строка кэша — это 16 чисел. На 64 мегабайтах разница — в сотни раз при одинаковом числе чтений и одинаковом O(n). Это и есть разница между обходом массива и связного списка, узлы которого разбросаны по памяти.
На Python оба ряда почти совпадают и почти плоские: каждый шаг цикла стоит интерпретатору около 40 нс, и ступеньки кэшей в этой цене тонут. Только на самом большом массиве чтение вразброс становится заметно дороже — задержка памяти дорастает до цены интерпретатора.
Прикиньте сами
Десять задач. Поставьте оценку на шкале от микросекунды до суток, потом посмотрите ответ и то, как он получился из таблицы. Ошибиться в два-три раза для прикидки нормально. Ошибка в сто раз — это уже другое решение: другое хранилище, другой алгоритм, другая архитектура.
Задачи идут парами, и пары важнее ответов: подряд и вразброс, память и диск, SSD и жёсткий диск, база рядом и за океаном. Почти в каждой паре число операций одинаковое, а время различается в сотни и тысячи раз. O-большое этой разницы не видит: оно считает шаги, а не их цену. Последняя задача объясняет, почему базы данных хранят индексы не в двоичных деревьях, а в B-деревьях: на диске важно не число сравнений, а число чтений.
Код
Прикидку полезно записывать маленькой программой: таблица цен и слагаемые «сколько раз × сколько стоит». Вот отчёт по 10 000 заказов, которому для каждого заказа нужна карточка клиента из базы в том же дата-центре.
Первый вариант тратит 90 % времени на дорогу до базы и обратно, а не на работу: ускорять базу бесполезно. Один запрос на все карточки делает главным слагаемым чтение с диска — 0,6 с вместо 5,6. Карточки, которые уже лежат в памяти сервиса, достаются за 2 мс. Каждый шаг меняет главное слагаемое, и прикидка подсказывает, что делать дальше.
А это замер, по которому построена лестница: погоня за указателями. Массив превращён в одно кольцо перестановкой Саттоло — в ней каждый элемент указывает на следующий так, что проход из нулевой ячейки обходит весь массив, а не застревает в маленьком цикле. Обычное случайное перемешивание дало бы несколько колец, и замер мог бы бегать по короткому, которое целиком сидит в кэше.
Насколько верить этим числам
Это порядки, а не константы. Ноутбук и сервер отвечают из памяти по-разному, на сервере с двумя процессорами чтение из памяти соседнего процессора ещё дольше, SSD различаются между собой в разы, а сеть внутри дата-центров стала быстрее, чем в старых таблицах. Поэтому:
- Запоминайте отношения. Память в сотню раз медленнее кэша, случайное чтение с SSD — в сотни раз медленнее памяти, жёсткий диск — в сотни раз медленнее SSD. Отношения меняются медленнее самих чисел.
- Ошибка в два раза — хорошая прикидка. Ошибка в сто раз значит, что пропущено слагаемое: лишний запрос по сети, промах кэша на каждом шаге, чтение с диска вместо памяти. Ищите его.
- Одновременность меняет картину. SSD и сеть обслуживают много запросов сразу, и тысяча запросов одновременно — не тысяча задержек подряд. Прикидка «по одному» — оценка сверху.
- Когда решение зависит от точного числа — измерьте. Как сделать это честно, рассказано в статье «Как честно измерить скорость».
Задачи
Задача — о том, куда уходит время при загрузке страницы. Ресурсы находятся друг в друге: шрифт — в стиле, данные — в скрипте. С каждым новым сервером браузер сначала здоровается, и эти приветствия стоят по несколько путей туда и обратно. В разборе видно, что на странице из примера они занимают больше половины времени загрузки.
Водопад загрузки