koanse 13 апр в 12:59

Проверка отсутствия деградации бенчмарков для двух версий статистическими методами

4 мин

1.1K

Тестирование IT-систем*Статистика в ITКачество кода*

Кейс

Привет, Хабр! Часто при тестировании идет сравнение производительности двух версий, например, master ветки и feature ветки. Допустим, идет сравнение по бенчмаркам, т.е. сравнивается время выполнения запросов для некоторого количества кейсов. Понятно, что если, например, в feature ветке есть улучшение производительности (и ветка создавалась как раз для улучшения производительности), это улучшение на целевых кейсах можно проверить даже вручную. Однако, осталось проверить, нет ли ухудшения производительности в остальных кейсах. Относительно точное вычисление производительности в смысле среднего времени выполнения запроса в конкретном кейсе требует нескольких прогонов кейса и может занять некоторое время, поэтому полная проверка всех кейсов (с десятками прогонов каждого кейса для получения более точного среднего результата) может занять, например, дни.

Однако, часто требуется лишь проверить лишь наличие деградации в feature ветке по сравнению с master, а не знать относительно точное время выполнения каждого запроса в feature ветке, это зачастую актуально для PR. Например, в feature ветке в одном кейсе два запроса выполняются за 300 и 300 секунд, а в master ветке для этого кейса за 12, 11, 10 секунд, нужно ли проводить несколько запусков кейса в feature ветке, или и так понятно, что есть деградация? Методы математической статистики позволяет формально ответить на этот вопрос с заданной вероятностью, например, 0.95, чтобы можно было принять решение формально, а не интуитивно. Интересующимся статистическими методами проверки отсутствия деградации — добро пожаловать под кат :)

Математическая статистика предоставляет целый набор критериев для решения этой задачи, одним из подходящих можно считать критерий Кохрена-Кокса. В этой статье рассматривается этот простой и более общий критерий и случай только одного фактора и не рассматривается многофакторный дисперсионный анализ ANOVA, который может учесть, например, зависимость бенчмарков от условно ресурсов CPU, RAM и т.д.

Таким образом, для проверки гипотезы о том, что среднее одной выборки меньше среднего другой выборки (т.е. среднее время выполнения одного бенчмарка в одной версии меньше среднего времени выполнения этого бенчмарка в другой версии), используется критерий Кохрена-Кокса и односторонний тест.

Алгоритм применения критерия Кохрена-Кокса

Формулирование гипотез

Будем считать, что сравнивается производительность одного кейса для выборки (время выполнения кейса на master ветке) и выборки (время выполнения того же кейса на feature ветке с возможными улучшениями).

Нулевая гипотеза $H_0:\mu_X \geq \mu_Y$ (среднее первой выборки не меньше среднего второй выборки), т.е. на master работает дольше и нет деградации.
Альтернативная гипотеза $H_A:\mu_X < \mu_Y$ (среднее первой выборки меньше среднего второй выборки), т.е. на master работало быстрее и есть деградация в feature ветке.

Алгоритм применения критерия Кохрена-Кокса

Даны две независимые выборки:
$X_1, X_2, ..., X_{n_1} \quad$ (размер $\ n_1$ )
$Y_1, Y_2, ..., Y_{n_2} \quad$ (размер $\ n_2$ )
Вычисляем выборочные средние:
$\bar{X} = \frac{1}{n_1} \sum_{i=1}^{n_1} X_i, \quad \bar{Y} = \frac{1}{n_2} \sum_{j=1}^{n_2} Y_j$
Вычисляем исправленные выборочные дисперсии (в знаменателе размер выборки минус 1):
$S_X^2 = \frac{1}{n_1 - 1} \sum_{i=1}^{n_1} (X_i - \bar{X})^2$
$S_Y^2 = \frac{1}{n_2 - 1} \sum_{j=1}^{n_2} (Y_j - \bar{Y})^2$
Находим -статистику Кохрена-Кокса:
$t = \frac{\bar{X} - \bar{Y}}{\sqrt{\frac{S_X^2}{n_1} + \frac{S_Y^2}{n_2}}}$
Определяем число степеней свободы по формуле Уэлча, причем округляем $\nu$ до ближайшего целого числа:
$\nu = \frac{\left(\frac{S_X^2}{n_1} + \frac{S_Y^2}{n_2}\right)^2} {\frac{\left(\frac{S_X^2}{n_1}\right)^2}{n_1 - 1} + \frac{\left(\frac{S_Y^2}{n_2}\right)^2}{n_2 - 1}}$
Определяем критическое значение $t_{\alpha, \nu}$ из таблицы распределения Стьюдента для одностороннего теста с уровнем значимости $\alpha$ .
Принимаем или отвергаем :
- Если $t < -t_{\alpha, \nu}$ , отвергаем в пользу , т.е. среднее первой выборки значимо меньше среднего второй выборки.
- Если $t \geq -t_{\alpha, \nu}$ , нет оснований отвергать , т.е. разница между средними не является статистически значимой.

Таким образом, критерий Кохрена-Кокса позволяет проверить гипотезу о том, что одно среднее меньше другого, даже если выборки разного размера и имеют разные дисперсии. Это делает его более гибким, чем стандартный -критерий Стьюдента.

Пример деградации в feature ветке

Проведем сравнение для двух выборок, первая выборка (т.е. результаты master ветки) содержит результаты выполнения в секундах для одного кейса: 12, 11, 10 секунд. Вторая выборка (т.е. результаты feature ветки) содержит два значения времени выполнения запроса для того же кейса: 300 и 300 секунд.

Проведем тест Кохрена-Кокса для проверки гипотезы:

$H_0: \mu_X \geq \mu_Y$

$H_A: \mu_X < \mu_Y$

где первая выборка $X = \{12, 11, 10\}$ , n_1 = 3 и вторая выборка $Y = \{300, 300\}$ , n_2 = 2 .

Результаты вычислений:

-статистика:
Число степеней свободы: $\nu = 2$
Критическое значение: $t_{0.05, 2} = -2.92$

Поскольку t=−500.56 меньше критического значения -2.92 , мы отвергаем нулевую гипотезу. Это означает, что среднее первой выборки значимо меньше среднего второй выборки, значит, уже есть деградация в feature ветке по сравнению с master и дальнейшие прогоны этого кейса и исследование feature ветки для этого кейса не требуется.

Как видно, можно сравнить две выборки с разными размерами, что, например, позволяет не запускать кейс с 300 секундами в третий раз на feature ветке и сэкономить условно 5 минут.

Пример улучшения в feature ветке

Проведем сравнение одного кейса для результатов выполнения одного кейса в master: 12, 11, 14, 11, 12 секунд и результатов выполнения того же кейса в feature: 5, 6, 8, 12, 8 секунд.

У нас теперь две выборки одинакового размера, каждая содержит по 5 значений, первая выборка: $X = \{12, 11, 14, 11, 12\}$ , вторая выборка: $Y = \{5, 6, 8, 12, 8\}$ , размеры выборок n_1 = n_2 = 5 .

Найдем выборочные средние и выборочные дисперсии, рассчитаем -статистику:

$t = \frac{12 - 7.8}{\sqrt{\frac{1.5}{5} + \frac{6.7}{5}}} \approx 3.28$

Рассчитаем число степеней свободы по формуле Уэлча:

$\nu = \frac{(0.3 + 1.34)^2}{\frac{0.3^2}{4} + \frac{1.34^2}{4}} \approx 5.7 \Rightarrow \nu \approx 6$

Критическое значение для уровня значимости и одностороннего теста равно .

Т.к. t = 3.28 > 1.943 и мы проверяем гипотезу $H_0: \mu_X \geq \mu_Y$ против $H_A: \mu_X < \mu_Y$ ,
то нулевая гипотеза не отвергается, т.е. среднее не меньше, чем среднее , более того — оно значительно больше.

Зачем все это нужно? Теперь видно, что если в feature ветке в одном кейсе результат двух измерений производительности равен условно 300 и 300 секунд, а в master ветке 12, 11, 10 секунд, то с вероятностью 0.95 (и даже больше на самом деле) можно утверждать, что в этом кейсе в feature ветке есть деградация, и дальнейшие длительные выполнения запросов для этого кейса не требуются, что экономит время, причем такой вывод можно сделать формально и с заданной вероятностью, а не интуитивно.

Также, как было продемонстрировано, и для менее очевидного кейса для 12, 11, 14, 11, 12 секунд в master ветке и для 5, 6, 8, 12, 8 в feature нет деградации в feature ветке.

Таким образом, критерий Кохрена-Кокса позволяет сравнивать производительность одного кейса для двух версий (в частности, веток) динамически, выполнять по одному прогону кейса для каждой ветки и принимать решение, не требуя точного расчета среднего времени выполнения для каждого кейса каждой ветки на основе, например, 100 прогонов.

Описанный подход в общем случае не заменяет бенчмарки, но позволяет решить частную задачу сравнения производительности двух веток значительно быстрее, в некоторых случаях на порядки быстрее, что, например, актуально для анализа PR.

Успехов в тестировании и бенчмарках :)

Хабы:

Проверка отсутствия деградации бенчмарков для двух версий статистическими методами

Алгоритм применения критерия Кохрена-Кокса

Формулирование гипотез

Алгоритм применения критерия Кохрена-Кокса

Пример деградации в feature ветке

Пример улучшения в feature ветке

Рассчитаем число степеней свободы по формуле Уэлча:

Критическое значение для уровня значимости и одностороннего теста равно .

Публикации

Работа

Ближайшие события