koanse Apr 27 at 15:14

BI в тестировании — сравнение результатов бенчмарков двух веток с помощью однофакторного ANOVA (критерий Кохрена-Кокса)

5 min

1.1K

Statistics in ITIT systems testing*Perfect code*

Case

Business Intelligence (BI) находит применение в самых разных сферах, в том числе, например, при анализе результатов бенчмарков. Часто возникает задача сравнения производительности двух версий приложения на основе результатов бенчмарков (время выполнения тестов для нескольких прогонов и нескольких тестов), например, сравнение master ветки и feature ветки. Улучшение производительности в feature ветке (особенно, если она для улучшения производительности и создавалась) проверить можно условно и вручную, но также важно проверить, что нет деградации в других кейсах бенчмарков для feature ветки по сравнению с master веткой. Это можно решить статистическими методами, например, достаточно однофакторного дисперсионного анализа (ANOVA), здесь будет рассмотрен критерий Кохрена-Кокса, особенности его имплементации на PostgreSQL и возможные виды графиков для представления результатов. Интересующимся применением BI и ANOVA для сравнения производительности двух версий приложения на бенчмарках — добро пожаловать под кат :)

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

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

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

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

Даны две независимые выборки:
$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_{\alpha, \nu}$ положительно.
Принимаем или отвергаем :
- Если $t < -t_{\alpha, \nu}$ , отвергаем в пользу , т.е. среднее первой выборки значимо меньше среднего второй выборки.
- Если $t \geq -t_{\alpha, \nu}$ , нет оснований отвергать , т.е. разница между средними не является статистически значимой.

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

Пример расчета на тестовых данных в PostgreSQL

Рассмотрим пример на тестовых данных из таблицы benchmark_data: имя теста testname, продолжительность теста elapsed и имя ветки branch, для упрощения другую информацию (например, ошибки) не рассматриваем.

SQL с рассчитанным критерием для вывода тестов с подтвердившейся нулевой гипотезой о деградации с уровнем значимости $\alpha=0.05$ на dummy данных может выглядеть следующим образом:

SELECT testName AS testname,
       xAverage AS xAverage,
       yAverage AS yAverage
FROM (SELECT xTestName AS testName,
             xAverage  AS xAverage,
             yAverage  AS yAverage,
             tstat     AS tstat,
             CASE
                 WHEN nu <= 1 THEN 12.70
                 WHEN nu <= 2 THEN 4.303
                 WHEN nu <= 3 THEN 3.182
                 WHEN nu <= 4 THEN 2.776
                 WHEN nu <= 5 THEN 2.571
                 WHEN nu <= 6 THEN 2.447
                 WHEN nu <= 7 THEN 2.365
                 WHEN nu <= 8 THEN 2.306
                 WHEN nu <= 9 THEN 2.262
                 WHEN nu <= 10 THEN 2.228
                 WHEN nu <= 20 THEN 2.086
                 WHEN nu <= 30 THEN 2.042
                 WHEN nu <= 40 THEN 2.021
                 WHEN nu <= 50 THEN 2.009
                 ELSE 1.967
                 END   AS ttheory
      FROM (SELECT xTestName,
                   xAverage                                                                   AS xAverage,
                   yAverage                                                                   AS yAverage,
                   (xAverage - yAverage) / SQRT(xVarianceDivideN + yVarianceDivideN)          AS tstat,
                   round((xVarianceDivideN + yVarianceDivideN) ^ 2 /
                         (xVarianceDivideN ^ 2 / (xn - 1) + yVarianceDivideN ^ 2 / (yn - 1))) AS nu
            FROM (SELECT benchmark_data.test_name                    AS xTestName,
                         VAR_SAMP(benchmark_data.elapsed)            AS xVariance,
                         AVG(benchmark_data.elapsed)                 AS xAverage,
                         COUNT(*)                                    AS xn,
                         VAR_SAMP(benchmark_data.elapsed) / COUNT(*) AS xVarianceDivideN
                  FROM benchmark_data
                  WHERE benchmark_data.branch = 'master'
                  GROUP BY benchmark_data.test_name) AS xQuery
                     INNER JOIN
                 (SELECT benchmark_data.branch                       AS yTestName,
                         VAR_SAMP(benchmark_data.elapsed)            AS yVariance,
                         AVG(benchmark_data.elapsed)                 AS yAverage,
                         COUNT(*)                                    AS yn,
                         VAR_SAMP(benchmark_data.elapsed) / COUNT(*) AS yVarianceDivideN
                  FROM benchmark_data
                  WHERE benchmark_data.branch = 'feature'
                  GROUP BY benchmark_data.branch) AS yQuery
                 ON xTestName = yTestName)
               AS stats)
         AS stats
WHERE tstat < - ttheory;

В PostgreSQL кроме, естественно, AVG для расчета среднего есть VAR_SAMP для расчета исправленной дисперсии (т.е. в знаменателе минус 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$ . Также для удобства в xVarianceDivideN и yVarianceDivideN рассчитываются отношения дисперсии к для удобства последующих расчетов.

Поскольку в PostgreSQL нет функции расчета теоретического значения критерия Стьюдента, использован относительно грубый расчет теоретических значений критерия Стьюдента (и только для уровня значимости $\alpha=0.05$ ), но его преимуществом является то, что не нужно, например, создавать новую таблицу со значением критерия или использовать дополнительные инструменты для расчетов.

CASE
                 WHEN nu <= 1 THEN 12.70
                 WHEN nu <= 2 THEN 4.303
                 WHEN nu <= 3 THEN 3.182
                 WHEN nu <= 4 THEN 2.776
                 WHEN nu <= 5 THEN 2.571
                 WHEN nu <= 6 THEN 2.447
                 WHEN nu <= 7 THEN 2.365
                 WHEN nu <= 8 THEN 2.306
                 WHEN nu <= 9 THEN 2.262
                 WHEN nu <= 10 THEN 2.228
                 WHEN nu <= 20 THEN 2.086
                 WHEN nu <= 30 THEN 2.042
                 WHEN nu <= 40 THEN 2.021
                 WHEN nu <= 50 THEN 2.009
                 ELSE 1.967
                 END   AS ttheory

Примеры графиков с результатами

В итоге на основе критерия Кохрена-Кокса с уровнем значимости $\alpha=0.05$ можно получить график с деградацией feature ветки по сравнению с master веткой по кейсам на основе dummy данных, деградация видна между двумя графиками средних и заполнена красным цветом.

График деградаций feature по сравнению с master веткой на уровне значимости 0.05 по кейсам. Вертикальная ось — время выполнения для master (нижний график) и feature (верхний график) в секундах, горизонтальная ось — название теста, залито красным — деградация feature ветки по сравнению с master — График деградаций *feature* по сравнению с *master* веткой на уровне значимости 0.05 по кейсам. Вертикальная ось — время выполнения для *master* (нижний график) и *feature* (верхний график) в секундах, горизонтальная ось — название теста, залито красным — деградация *feature* ветки по сравнению с *master*

График предназначен для дальнейшего детального анализа каждого кейса. Примечательно, что выводы сделаны на основе статистической значимости, а не интуиции. Для значительного количества наблюдений в каждом тесте (например, 1000 или больше) можно обойтись и без статистических гипотез и просто сравнить средние, однако при меньших объемах выборок (например, 10-100 значений) полагаться на интуицию при сравнении средних может быть не так эффективно и предпочтительнее использовать формальные инструменты, вы частности, рассмотренный критерий.

Также наглядным может быть open-close график с теми же данными.

Open-close график деградаций feature по сравнению с master веткой на уровне значимости 0.05 по кейсам. Вертикальная ось — время выполнения для master (нижняя часть прямоугольника) и feature (верхняя часть прямоугольника) в секундах, горизонтальная ось — название теста, прямоугольник — деградация feature ветки по сравнению с master — Open-close график деградаций *feature* по сравнению с *master* веткой на уровне значимости 0.05 по кейсам. Вертикальная ось — время выполнения для *master* (нижняя часть прямоугольника) и *feature* (верхняя часть прямоугольника) в секундах, горизонтальная ось — название теста, прямоугольник — деградация *feature* ветки по сравнению с *master*

Таким образом, с вероятностью получаем случаи деградации для дальнейшего анализа. Полученные кейсы деградации выбираются с учетом заданной статистической значимости (например, уровень значимости $\alpha=0.05$ ), т.е. с учетом, условно, количества наблюдений, а не интуитивно. Как бонус, после получения приемлемых результатов при текущих объемах выборок и (т.е. количестве прогонов тестов), критерий позволяет варьировать к и , чтобы получить условно те же результаты, «те же графики», но для меньшего количества прогонов, что может сэкономить время и не выполнять дополнительные прогоны тестов.

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

Hubs: