Честный замер: прогрев, повторы и разброс

Если ты знаешь, зачем прогрев, почему сравнивают медианы с разбросом, а не средние и не один прогон, и как не обмануться повторами, листай до «Теперь сам».

Как думаешь, какое число записать

Функция создаёт список из миллиона чисел и суммирует его. Двенадцать прогонов подряд на машине этого сайта:

import time


def rabota():
    a = list(range(1_000_000))
    return sum(a)


zamery = []
for popytka in range(12):
    t = time.perf_counter()
    rabota()
    zamery.append(round((time.perf_counter() - t) * 1000, 1))
print("прогоны 1-6, мс: ", zamery[:6])
print("прогоны 7-12, мс:", zamery[6:])

прогоны 1-6, мс:  [81.4, 77.6, 66.2, 68.2, 66.1, 66.4]
прогоны 7-12, мс: [68.3, 67.7, 66.8, 72.6, 66.6, 66.4]

Сколько стоит функция? Первый прогон - 81 мс, лучший - 66, среднее - около 69. Какое из этих чисел - «время работы»?

Ответь себе до чтения. Правильный ответ - «зависит от вопроса», и урок о том, какой вопрос какому числу соответствует.

На что это похоже

Напольные весы в ванной. Встал - 72,4. Сошёл, встал - 72,1. С утра после душа - 71,8. Ни одно число не «вес»: вес - это то, вокруг чего они дрожат, и дрожь не меньше десятой доли. Если вчера было 72,3, а сегодня 72,1, нельзя сказать «похудел на 200 граммов» - весы так не умеют. А первое взвешивание после того, как весы долго стояли выключенными, вообще лучше выбросить.

Механизм: откуда шум и что с ним делать

Прогрев. Первые прогоны платят за то, что потом бесплатно: память под миллион ссылок впервые берётся у операционной системы, и каждая новая страница стоит прерывания; кеши и предсказатель ветвлений ещё не знают кода и данных. В замере выше это первые два прогона - на 22 и 16% дольше медианы остальных (66,7 мс).

Помехи. Соседние процессы (на этой машине работает сайт и база), смена частоты процессора, сборщик мусора Python, прерывания. Чаще всего они ДОБАВЛЯЮТ время (частота и кеш иногда сдвигают и вниз, но слабее), поэтому шум несимметричен: редкие выбросы вверх (72,6 в седьмой-двенадцатой попытках), а вниз дорогу ограничивает сама работа.

Что делать.

• Отбросить прогрев: первые прогоны не считать или сделать перед замером пустой прогон.
• Повторить много раз: 7, 15, 30 - смотря какой разброс.
• Выбрать статистику под вопрос. Минимум - «сколько стоит код, когда ничто не мешает»: удобно сравнивать микрооптимизации. Медиана с квартилями - «сколько он обычно стоит и насколько дрожит»: для решения, какой вариант лучше. Квартили - числа, ниже которых лежит четверть (q1) и три четверти (q3) отсортированных замеров; между ними - средняя половина.
• Чередовать варианты A и B, чтобы медленный дрейф машины (нагрев, фоновая задача) достался обоим поровну.

Тот же принцип - весь разброс, а не лучший случай, - уже был в главе о локальном поиске, где качество эвристик сравнивали по многим зёрнам; здесь он применяется ко времени.

timeit.repeat даёт для этого сырьё: прогоняет код number раз в каждом из repeat замеров и на время замера выключает сборщик мусора. Прогрев, чередование и статистику делаешь сам.

Правило

Замер - распределение. Отбрось прогрев, повтори, сравнивай медианы вместе с разбросом (квартили), а не средние и не одиночные прогоны. Если средние половины двух вариантов перекрываются - «не различить». Минимум годится для вопроса «сколько стоит код без помех», медиана - для «что будет обычно». Это грубое правило для десятка-другого замеров: на сотнях замеров или при сравнении по парам различие можно доказать и при перекрытии - этим занимаются статистические критерии (знаков, Манна - Уитни), здесь хватит грубого.

Разбор: два одинаковых варианта

sorted(a) внутри делает то же, что «копия, потом a.sort()»: разницы быть не должно. Пятнадцать прогонов каждого на 200 000 случайных чисел, поочерёдно, на этой машине; посчитаем, что сказал бы каждый способ сравнения.

# два ряда замеров одной машины, мс: sorted(a) и «копия + a.sort()»
# на 200 000 случайных чисел, прогоны поочерёдно (замер dva_ryada.py)
ryad_a = [52.3, 47.2, 47.9, 46.0, 46.4, 46.1, 51.2, 48.0,
          53.2, 48.3, 56.8, 46.2, 46.3, 51.8, 46.2]
ryad_b = [49.4, 49.0, 46.8, 48.3, 46.7, 46.1, 48.7, 47.6,
          47.2, 45.9, 46.6, 45.6, 46.1, 45.6, 45.7]

def svodka(r):
    # q1, медиана, q3: четверть, половина и три четверти замеров
    # не больше этих чисел
    s = sorted(r)
    n = len(s)
    return [s[n // 4], s[n // 2], s[3 * n // 4]]

def vyvod(ra, rb):
    a = svodka(ra)
    b = svodka(rb)
    if a[2] < b[0]:
        return "A быстрее"
    if b[2] < a[0]:
        return "B быстрее"
    return "не различить"

print("первые прогоны:", ryad_a[0], ryad_b[0])
print("средние:", round(sum(ryad_a) / 15, 1), round(sum(ryad_b) / 15, 1))
print("A: q1, медиана, q3 =", svodka(ryad_a))
print("B: q1, медиана, q3 =", svodka(ryad_b))
print("вывод:", vyvod(ryad_a, ryad_b))
# что сказал бы один прогон: сравниваем пары по номеру попытки
a_luchshe = 0
b_luchshe = 0
for i in range(15):
    if ryad_a[i] < ryad_b[i]:
        a_luchshe = a_luchshe + 1
    elif ryad_b[i] < ryad_a[i]:
        b_luchshe = b_luchshe + 1
print("пары: «быстрее» A -", a_luchshe, ", B -", b_luchshe,
      ", ничьих -", 15 - a_luchshe - b_luchshe)

первые прогоны: 52.3 49.4
средние: 48.9 47.0
A: q1, медиана, q3 = [46.2, 47.9, 51.8]
B: q1, медиана, q3 = [45.9, 46.7, 48.3]
вывод: не различить
пары: «быстрее» A - 3 , B - 11 , ничьих - 1

Первый прогон «доказывает», что B быстрее на 6%. Средние - что на 4%. По парам - B выиграл 11 раз против 3 и одна ничья: выглядит как приговор. Квартили говорят другое: средние половины - от 46,2 до 51,8 и от 45,9 до 48,3 - сильно перекрываются: интервал B почти целиком лежит внутри интервала A. Средние сдвинуты выбросами (56,8 и 53,2 у A), а медиана к ним устойчива.

Разбор: пятнадцать пар тоже врут

Счёт 11 : 3 настораживает: неужели всё-таки разница есть? Проверка простая - повторить опыт. Сорок пар, трижды:

import random
import time

random.seed(1)
a = [random.random() for _ in range(200_000)]


def var_a():
    return sorted(a)


def var_b():
    b = a[:]
    b.sort()
    return b


def zamer(f):
    t = time.perf_counter()
    f()
    return time.perf_counter() - t


for opyt in range(1, 4):
    a_luchshe = 0
    for para in range(40):
        ta = zamer(var_a)
        tb = zamer(var_b)
        if ta < tb:
            a_luchshe += 1
    print("опыт", opyt, "- A быстрее в", a_luchshe, "парах из 40")

опыт 1 - A быстрее в 20 парах из 40
опыт 2 - A быстрее в 22 парах из 40
опыт 3 - A быстрее в 19 парах из 40

20, 22, 19 из 40 - монетка. Счёт 11 : 3 совместим со случайностью: если варианты равны, такой или более однобокий результат в 14 парах без ничьих выпадает примерно в 6% серий (2 · (1 + 14 + 91 + 364) / 2¹⁴), а бенчмарки гоняют часто. Маленькую настоящую разницу повторные серии не исключают - они лишь не видят никакой. Граница правила «много повторов - и ты прав»: один опыт с повторами - тоже один опыт. Неожиданный вывод проверяют новой серией, лучше в другое время.

Что ломается без этого

Оптимизация, которой нет. «Переписал - стало на 5% быстрее» по одному прогону каждого варианта. В половине таких случаев разница - шум, и через месяц кто-то «оптимизирует» обратно.

Регрессия, которую пропустили. Медиана выросла на 30%, но сравнили минимумы - а минимум у нового кода случайно совпал со старым.

Замер вместе с подготовкой. Создание входных данных, импорт модуля, первое обращение к диску попали в засечку - и сравнивается не алгоритм, а import.

Зачем это в работе

Решение «брать ли этот вариант» стоит недель работы, а замер - минут. Минимальный честный протокол: одни и те же данные, прогрев, 7-30 повторов, чередование вариантов, медиана и квартили в отчёте, повторная серия при неожиданном результате. Для Python готовый инструмент - pyperf: он сам калибрует число повторов, запускает замеры в отдельных процессах и печатает среднее с разбросом. В системах непрерывной интеграции так же устроены проверки на регрессии производительности: сигнал - сдвиг распределения, а не одного числа.

Теперь сам

1. Ряд замеров, мс: [9.1, 7.2, 7.0, 7.4, 7.1, 12.8, 7.0, 7.3]. Что выбросить, какую медиану записать?
2. У A средняя половина замеров - от 30 до 34 мс, у B - от 35 до 39 мс. Что можно сказать?
3. Почему средним значением сравнивать хуже, чем медианой?