Какие критерии обсуждать с тестировщиками при оптимизации алгоритма

Что проверяют

Умеете ли вы договориться о том, как доказать, что оптимизация сработала и ничего не сломала. Интервьюеру важно, что вы приходите к тестировщикам с измеримой целью, а не с «стало быстрее». Следом обычно спрашивают, как вы будете мерить производительность на JVM.

Как отвечать

Постройте ответ вокруг двух вопросов: что должно остаться прежним и что должно измениться, причём на сколько.

• функциональная эквивалентность: новая реализация даёт тот же результат, что старая. Удобно прогнать обе версии на одних данных и сравнить вывод, плюс property-based тесты на инварианты (jqwik);
• граничные случаи: пустой вход, один элемент, дубликаты, null, переполнение int, очень большие коллекции. Оптимизации чаще всего ломаются именно здесь;
• целевая метрика: время ответа по перцентилям p95 и p99, пропускная способность, память. Цель формулируется числом и на конкретном профиле данных;
• методика замера: микробенчмарки через JMH с прогревом, нагрузочные прогоны в Gatling или JMeter на стенде с данными, похожими на продовые;
• память и GC: аллокации, паузы сборщика, размер heap. Кэш или предвычисление часто меняют время на память, и это надо согласовать заранее;
• конкурентность: если алгоритм стал многопоточным, нужны тесты на гонки и на стабильность под параллельной нагрузкой;
• регресс и откат: какой набор регрессионных тестов гоняем, стоит ли новая версия за фиче-флагом, по каким метрикам мониторинга заметим проблему на проде.

Закончите тем, что критерии фиксируются до начала работ: без базового замера «до» сравнивать не с чем.

Где спотыкаются

Говорят только про асимптотику. O(n log n) против O(n²) не скажет тестировщику, укладываемся ли мы в SLA на реальных объёмах, где константы и кэш процессора решают больше.

Меряют через System.currentTimeMillis() в цикле без прогрева. На JVM такой замер показывает работу интерпретатора и JIT-компилятора, а не алгоритма, поэтому нужен JMH и System.nanoTime() хотя бы для грубых оценок.

Не договариваются о данных. Бенчмарк на отсортированном массиве из тысячи элементов и прод с миллионом неупорядоченных записей приведут к разным выводам.