Стресс-тестирование

Общие концепции

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

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

smart.cpp. Ваше решение, которое по какой-то причине не проходит тесты.
stupid.cpp. Тупое решение. Чаще всего за большую асимптотику. Очень важно, чтобы это решение было максимально тупым, и вы были уверены, что в нем нет никаких ошибок.
gen.cpp. Генератор тестов. Чаще всего тесты генерируются случайные, при этом они должны быть не очень большие, чтобы тупое решение тоже могло быстро на них работать, а также, чтобы вы могли потом найти ошибку в своем коде, используя этот тест. Когда вы нашли неработающий тест, попытайтесь максимально его минимизировать. Уменьшить константу в генераторе и так далее. Чем проще тест, тем легче вам будет исправлять ошибку.
stress.sh. Скрипт, который будет повторять следующий процесс: сгенерировать тест, запустить на нем умное решение, запустить на нем тупое решение, сравнить ответы. Если ответы равны, нужно повторить процесс, а если не равны, выдать тот тест, на котором ваше решение работает неправильно, и завершиться.
checker.cpp. Пункт, который редко будет вам нужен, но все же может понадобиться, — это чекер. Не всегда в задаче существует единственный правильный ответ на каждый тест. К примеру, если задача заключается в том, чтобы разложить число на два множителя, то разных ответов может быть несколько, и каждый из них при этом верный. Поэтому вам может понадобиться написать программу, которая проверяет правильность вашего ответа, учитывая ответ тупого решения. Также бывает так, что тупого решения написать нет возможности, потому что любое тупое решение по сложности сопоставимо с вашим умным решением. В этом случае вам может помочь некоторая промежуточная мера, когда у вас есть только чекер. Этот чекер может сделать некоторые проверки ответа на адекватность (к примеру, проверить, что в задаче о разложении на два множителя, произведение этих множителей равно входному числу). Эта проверка может не покрывать все случаи, когда ваше решение работает некорректно, но все равно может помочь вам найти нужный тест.

smart.cpp у вас уже есть, потому что это ваше решение. Чтобы написать stupid.cpp, надо просто представить, что ограничения в задаче маленькие, и написать другое решение. Как уже было сказано ранее, очень важно писать максимально простой код, чтобы не допускать ошибок. checker.cpp принимает на вход три файла: входной файл, правильный ответ и ваш ответ, и проверяет по ним корректность вашего ответа.

Теперь осталось разобраться, как правильно писать gen.cpp и stress.sh.

Замечание: Обратите внимание, что здесь речь идет про shell стрессы в linux. В других случаях могут отличаться детали, однако пока мы говорим больше про общие концепции. Конкретные несоответствия будут освещены в соответствующих секциях позже.

Генератор должен создавать случайный тест (небольшого размера). Рекомендуется использовать фиксированный сид рандома, чтобы тесты были воспроизводимы. При этом мы хотим запускать генератор много раз и получать разные тесты. Давайте для этого передавать сид рандома в аргументах командной строки. Функция main может принимать два параметра: agrc и argv. argc — это количество аргументов командной строки, а argv — это массив аргументов размера argc. К примеру, если вы скомпилировали ваш код в файл main и запускаете его командой ./main aba 123 8, то argc будет равен $4$, а в argv будут храниться ./main, aba, 123 и 8.

Нам нужно передавать всего один параметр, который будет храниться в argv[1]. Правда, он там будет храниться в типе char* (строки из C), а нам нужно число. Для перевода можно воспользоваться функцией atoi.

Кроме того, стоит помнить о том, что пользоваться стоит не функцией rand, а генератором mt_19937.

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

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());

Подробнее про генерацию случайных чисел можно прочитать в соответствующей статье.

Вооружившись всеми этими знаниями, давайте напишем генератор для задачи «A+B».

#include <iostream>
#include <random>
#include <cstdlib>

using namespace std;

int main(int argc, char* argv[]) {
    int seed = atoi(argv[1]);
    mt19937 rnd(seed);

    int a = rnd() % 1000;
    int b = rnd() % 1000;

    cout << a << ' ' << b << endl;
    return 0;
}

Теперь наша задача заключается в том, чтобы по очереди запускать gen, записывать его результат в файл, запускать два решения и сравнивать их ответы. Рассмотрим разные варианты того, как это можно делать.

Linux: Shell стрессы

Если вы пользуетесь linux, macos и т.п., то вам подойдет этот вариант. Если вы пользуетесь Windows, то для вас есть следующая секция.

Мы напишем shell скрипт, который будет делать то, что нам нужно. Для этого нужно создать файл с расширением .sh, в котором можно писать команды как в консоли, а также использовать циклы и т.п.

Для начала нужно скомпилировать все наши файлы (smart, stupid, gen и, возможно, checker). Рекомендуется при стресс-тестировании максимально приближаться к компиляции программ в тестирующей системе и использовать соответствующую оптимизацию (скорее всего, это -O2).

Далее мы запускаем цикл, в котором выполняем программы (компилируем мы один раз, а выполняем потом сколько угодно) и сравниваем результаты их работы.

Пример стресса:

g++ -std=c++17 -O2 smart.cpp -o smart
g++ -std=c++17 -O2 stupid.cpp -o stupid
g++ -std=c++17 -O2 gen.cpp -o gen

for t in $(seq 1 100000); do
    echo "Running test $t"
    ./gen $t > input
    ./smart < input > smart_output
    ./stupid < input > stupid_output
    diff smart_output stupid_output || exit
done

В первых трех строчках мы компилируем наши программы. Рассмотрим, к примеру, первую строчку. Здесь g++ — это компилятор c++, -std=c++17 устанавливает версию c++, под которой мы хотим компилировать программу, -O2 устанавливает нужный уровень оптимизаций, а -o smart говорит о том, что мы хотим скомпилировать программу в файл под названием smart (обратите внимание, что в данном случае у него нет никакого расширения). Остальные две компиляции аналогичны.

Далее на 5 строке представлен код цикла, который перебирает переменную t от $1$ до $100000$. Обратите внимание, что цикл завершается словом done в конце скрипта. После чего при помощи команды echo мы выводим на экран номер теста, чтобы можно было отслеживать прогресс.

Затем запускаются программы. Здесь ./gen означает запуск программы gen, $t означает, что мы передаем число t как параметр. Знак больше перенаправляет вывод программы. Таким образом, наш генератор будет писать тест не в консоль, а в файл под названием input. Затем мы аналогично запускаем два решения. Они пишут в файлы smart_output и stupid_output. При этом в этих строчках есть еще знак меньше, который наоборот означает то, откуда мы читаем входные данные. То, какой знак нужно использовать для чего, легко понять по направлению стрелочки. У знака > стрелочка указывает внутрь файла, то есть в этот файл мы выводим информацию, а у знака < стрелочка указывает наружу, то есть из этого файла мы достаем информацию.

После того, как программы отработали, настало время проверить совпадение ответов. Для этого мы воспользуемся консольной утилитой diff, которая сравнивает файлы на совпадение. Стоит обратить внимание, что если мы не пишем чекер и пользуемся diff‘ом, то формат вывода у обеих программ должен совпадать с точностью до пробелов. Утилита diff возвращает $1$, если файлы равны, и $0$, если файлы не равны. Далее мы используем оператор ||, который, как и в c++, означает «или». Если diff вернул $1$, то результат «или» уже равен единице и второй аргумент не вычисляется. Если же было возвращено значение $0$, то выполняется вторая команда exit, которая завершает наш скрипт. Кроме того, diff в этом случае выведет на экран места, в которых различаются файлы. Далее можно уже зайти в файл input, посмотреть, какой там тест, и пользоваться им для отладки программы. Если же неправильный тест не находится, то либо вы допустили ошибку при написании стресса, либо ваше решение верное, либо ошибка просто не ловится вашим стрессом (возможно, она проявляется только на больших тестах).

Чтобы запустить этот скрипт, нужно просто написать в консоль ./stress.sh, если вы сохранили его в соответствующий файл. Однако, вероятно, вам выдадут строчку примерно такого содержания:

permition denied: ./stress.sh

Дело в том, что по умолчанию у файлов нет прав на исполнение. Так что нужно их добавить. Это можно сделать при помощи следующей команды:

chmod +x stress.sh

И затем попытаться запустить скрипт заново.

Теперь поговорим об улучшениях, которые можно сделать к нашему стрессу. Во-первых, может возникнуть ситуация, в которой какая-то из запускаемых программ упадет с ошибкой выполнения. Наш стресс это просто проигнорирует. Давайте это обработаем. Для этого просто добавим || exit в конец запусков наших программ аналогично строке с diff:

g++ -std=c++17 -O2 smart.cpp -o smart
g++ -std=c++17 -O2 stupid.cpp -o stupid
g++ -std=c++17 -O2 gen.cpp -o gen

for t in $(seq 1 100000); do
    echo "Running test $t"
    ./gen $t > input || exit
    ./smart < input > smart_output || exit
    ./stupid < input > stupid_output || exit
    diff smart_output stupid_output || exit
done

Теперь наша программа завершится, если какая-то из программ упала. Однако мы не знаем, какая. Мы можем попытаться запустить их по очереди и проверить. Либо можно добавить описание причины ошибки:

g++ -std=c++17 -O2 smart.cpp -o smart
g++ -std=c++17 -O2 stupid.cpp -o stupid
g++ -std=c++17 -O2 gen.cpp -o gen

for t in $(seq 1 100000); do
    echo "Running test $t"
    ./gen $t > input || { echo "gen failed"; exit; }
    ./smart < input > smart_output || { echo "smart failed"; exit; }
    ./stupid < input > stupid_output || { echo "stupid failed"; exit; }
    diff smart_output stupid_output || { echo "outputs aren't equal"; exit; }
done

Windows: Bat стрессы

Аналогичный пример с bat скриптами в Windows:

g++ -std=c++17 -O2 smart.cpp -o smart.exe
g++ -std=c++17 -O2 stupid.cpp -o stupid.exe
g++ -std=c++17 -O2 gen.cpp -o gen.exe

:beg
gen.exe > input || exit
smart.exe < input > smart_output
stupid.exe < input > stupid_output
fc smart_output stupid_output
if errorlevel 1 goto bug
goto beg
:bug
echo found!

Компиляция аналогична варианту с linux. Далее мы используем goto как циклы, бесконечно запуская тесты (здесь представлена вариация без входных параметров, то есть в коде должен использоваться часто меняющийся рандом). Далее используется команда fc, аналогичная diff в linux.

Python стрессы

В данном подходе мы используем вместо shell или bat скрипта более высокоуровневый вариант — питон. Из него мы можем запускать все те же консольные команды, но кроме того можем, к примеру, написать прямо там без труда свой собственный чекер или генератор (или не писать). Особых отличий от скриптовых вариантов больше нет, рекомендуется изучить код:

import os, sys

for i in range(1, 100000):
    print('Running test', i)
    os.popen('./gen > input')
    smart_ans = os.popen('./smart < input').readlines()
    stupid_ans = os.popen('./stupid < input').readlines()
    if smart_ans != stupid_ans:
        print('Outputs are not equal')
        print('Input:')
        print(*(open('input').readlines()))
        print('stupid answer:')
        print(*stupid_ans)
        print('smart answer:')
        print(*smart_ans)
        sys.exit()
print('All tests passed')

Здесь os.popen выполняет консольную команду, а readlines сохраняет вывод программы.

Плюсом этого подхода является платформонезависимость.

In-Code стрессы

Наверное, самый простой вариант — сделать все в одной программе. Здесь smart, stupid, gen и checker будут не отдельными программами, а функциями. Вероятно также, что ввод-вывод в этом случае тестироваться не будут. Только смысловая часть программы. Если вы заранее не писали код в формате блоков: отдельная функция для ввода, отдельная функция для решения, отдельная функция для вывода, то вам придется немного поменять свое решение.

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

Если два решения используют функции или переменные с одинаковыми названиями, можно просто заключить оба решения в два разных пространства имен: NamespaceSmart и NamespaceStupid.

Пример такого стресса для задачи поиска квадрата числа можно посмотреть по ссылке.