Как честно измерить скорость

Прежде чем сравнивать алгоритмы, нужно научиться мерить. Это кажется простым: засечь время до, засечь после, вычесть. Ниже — сортировка двадцати тысяч чисел, повторённая сто пятьдесят раз подряд на сервере, где исполняется код этого каталога. Код и данные не меняются, а время меняется. Вторая гистограмма — тот же замер с одной незаметной ошибкой: она показывает ускорение в десятки раз, которого нет.

Посмотрите на честную гистограмму: основная масса замеров лежит плотно, но есть хвост вправо — отдельные запуски в полтора, два, а то и в семь раз медленнее. Их никто не замедлял нарочно: в этот момент процессор отвлекался на другие процессы, ядро ОС переключало задачи, сборщик мусора наводил порядок. Нажмите «Замерить заново» — у вас получится похожая картина, но не та же самая.

Что на самом деле измеряет замер

Время работы программы — случайная величина. Один замер — одно её значение, и по нему ничего нельзя сказать: может, повезло, а может, нет. Нужно много повторов и взгляд на распределение — хотя бы на минимум и медиану.

Из чего складывается шум:

• Соседи. На машине работают другие процессы, и планировщик ОС делит между ними процессор. Наш сервер — общий для всех читателей, и ваш замер может совпасть с чужим.
• Частота процессора. Современные процессоры меняют частоту в зависимости от нагрузки и температуры, иногда за доли секунды.
• Кэши. Первый проход по данным читает их из памяти, следующие — из кэша процессора. Первые замеры часто медленнее остальных: это прогрев.
• Сборка мусора. В Python и Go память время от времени освобождается, и это попадает в чей-то замер.
• Точность часов. Часы тикают с конечным шагом. Операцию в несколько наносекунд одиночным замером не измерить — её нужно повторить миллион раз и поделить.

Минимум, медиана и среднее

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

Документация модуля timeit прямо советует смотреть на минимум: более высокие значения обычно вызваны не тем, что Python стал медленнее, а тем, что другие процессы мешали замеру. Среднее и стандартное отклонение здесь мало что дают — хвост тянет их вправо. Но если вы мерите не алгоритм, а сервис, где хвост переживают реальные люди, всё наоборот: смотрят на перцентили.

Ошибка, которая ускоряет в сорок раз

Вернитесь к второй гистограмме. Код почти тот же самый: сортировка на месте, xs.sort(). Только сортируется один и тот же список, и со второго повтора он уже отсортирован. Python сортирует алгоритмом Timsort, а Go — pdqsort, и оба замечают уже упорядоченные участки и проходят их за линейное время. В итоге «замер сортировки» на самом деле мерит проверку, что всё уже на месте.

Это частная история общей беды: замер должен работать на тех же данных, что и настоящая программа. Отсортированное вместо случайного, маленькое вместо большого, закэшированное вместо холодного — и цифры будут красивыми и бесполезными. Хорошая привычка — проверять результат внутри замера: если сортировка ничего не переставила, что-то не так.

Код

В Python для коротких замеров есть модуль timeit. Функция repeat делает несколько серий, в каждой — заданное число запусков, и возвращает время каждой серии. Берём лучшую серию и делим на число запусков. Код настройки (setup) выполняется вне замера.

В Go стандартный способ — бенчмарки пакета testing. Обычно их запускают командой go test -bench, но функцию testing.Benchmark можно вызвать и из обычной программы. Она сама подбирает число повторов b.N, чтобы замер длился около секунды, и возвращает среднее время на операцию. Цикл for b.Loop() (Go 1.24 и новее) заодно гарантирует, что компилятор не выбросит тело цикла, даже если его результат никому не нужен.

Обратите внимание на вторую строку вывода: копирование данных — тоже работа, и если копия попала внутрь замера, её стоимость надо знать. Здесь она в десятки раз меньше сортировки, и ею можно пренебречь. Бывает и наоборот.

А это программа, которая построила гистограммы выше: она печатает по строке JSON на каждый повтор, и страница рисует их на графике.

Правила честного замера

1. Повторяйте. Один замер ничего не значит. Делайте серии и смотрите на распределение.
2. Мерьте достаточно долго. Если операция короче микросекунды, повторяйте её в цикле, пока серия не займёт хотя бы десятую долю секунды, и делите.
3. Прогрейте. Первые запуски выбросьте или хотя бы посмотрите на них отдельно.
4. Те же данные, что в жизни. Размер, порядок, распределение значений.
5. Ничего лишнего внутри. Печать, чтение файла, генерация данных — снаружи замера, если вы мерите не их.
6. Сравнивайте на одной машине, вперемешку. Две версии кода мерьте по очереди несколько раз, а не одну утром, другую вечером.
7. Пишите, где мерили. Цифра без машины, языка и размера данных не значит ничего. Все замеры в этом каталоге подписаны.

Во что это обходится

Честный замер дорог: сотни повторов вместо одного. Но обычно это секунды, а цена ошибки — неделя оптимизации, которая на самом деле ничего не ускорила. Если замер сложно повторить, это повод упростить его, а не повод довериться одному числу. О том, как по нескольким замерам на разных размерах понять, как растёт время, — статья «Сложность по замерам»; о том, где именно программа тратит время, — профилировщики.

Задачи

Посчитайте по ряду замеров всё, о чём шла речь: минимум, медиану, среднее и среднее без выбросов.