Pull to refresh

Почему юнит-тесты не работают в научных приложениях

Reading time 7 min
Views 8.1K
В этой статье я хочу поделиться своим опытом разработки научных приложений, и рассказать, почему Test-Driven Development и юнит-тесты не являются панацеей, как принято считать в последнее время, по крайней мере с точки зрения нахождения программных ошибок. Почему же?

Статья будет состоять из нескольких разделов:
  1. «Введение», в котором я расскажу, почему решил написать ее
  2. «Иллюстрационный алгоритм». Здесь будет кратко описана научная проблема и алгоритм, который будет иллюстрировать дальнейшее изложение
  3. «Недостатки юнит-тестов» Здесь будут приведены аргументы, объясняющие недостатки юнит-тестов для научных приложений
  4. Заключение

Сразу замечу, что я не рассматриваю пользу от TDD как от способа разработки архитектуры, а исключительно с точки зрения тестирования программы.

Введение


Во время недели воздухоплавания на хабре на главной оказалась статья Цифровые самолеты [1], и занятный комментарий к ней [2] о том, что 20 лет назад не было юнит-тестов и вообще нормальных методов разработки, поэтому распространенной была схема «triple-triple redundant architecture», в частности, написание одной и той же программы тремя разными командами на разных языках с целью исключения программных ошибок.

Тем не менее, по свидетельствам очевидцев ([3], кстати, это еще одна прекрасная книга прекрасного ученого Ричарда Фейнмана, обретшего вторую жизнь на хабре) если и не Test Driven Development (TDD далее), то ручное тестирование было очень важным этапом разработки.
Именно поэтому у меня появилось желание проанализировать подход к разработке научных приложений и поделиться мыслями по этому поводу, в частности, рассказать, что TDD—это вовсе не silver bullet для поиска ошибок, как можно подумать сперва.

Иллюстрационный алгоритм


В последние 20 лет развивался необычный метод для моделирования гидродинамики: Lattice-Boltzmann Method (далее — LBM) [4], [5]. Я принимал участие в реализации этого алгоритма на C++ для института Макса Планка в Германии.

Во избежание неизбежных вопросов: да, уже существуют коммерческие и открытые пакеты, использующие этот метод [6]; но изначально планировалось использование модификации метода, которая должна была давать выигрыш в производительности и потребляемой памяти; тем не менее, от нее мы последовательно отказались (сначала для массопереноса, потом для теплопереноса). К тому времени было написано много кода, и мы решили продолжить собственную реализацию.

Гидродинамика, как известно, описывается уравнением Навье-Стокса. При его моделировании можно использовать, например, Finite Element Method [7]. К сожалению, у него есть недостатки — относительная сложность распараллеливания, невозможность моделирования многофазных потоков, трудности моделирования потоков в пористых средах. Этих недостатков лишен LBM.

Для разреженных газов справедливо уравнение Больцмана [8], которое описывает, как меняется плотность распределения частиц по скоростям в каждой точке пространства со временем. Макроскопически это уравнение эквивалентно уравнению Навье-Стокса (то есть после перехода к макроскопическим величинам — плотности и скорости).

Теперь следите за руками: несмотря на то, что для плотных жидкостей уравнение Больцмана не применимо, если мы научимся его моделировать, то сможем моделировать и уравнение Навье-Стокса для этих жидкостей. То есть мы тем самым заменяем нижележащий уровень абстракций (микроскопическое уравнение для плотных жидкостей) физически неправильной реализацией (микроскопическое уравнение для разреженных газов), но так, что верхний уровень (макроскопическое уравнение Навье-Стокса) описывается верно.

Следующий этап — это дискретизация уравнения Больцмана: по времени, по пространственным координатам (получаем пространственные узлы для моделирования) и по возможным направлениям частиц в каждом пространственном узле. Направления выбираются специальным образом, и всегда указывают в некоторые соседние узлы.

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

Недостатки юнит-тестов


Наконец, перейдем к тому, почему юнит-тесты не могут полностью покрыть сложное научное приложение.
Основная идея раздела заключается в том, что сложные алгоритмы препятствуют тестированию… себя.

Отсутствие простых тестов

Для сложных алгоритмов и методов тяжело придумать простые тесты.

Это, в общем-то, очевидно. Часто сложно подобрать простые входные параметры формулы так, чтобы на выходе получить простое и понятно число. То есть вы, конечно, отдельно на листочке или в Матлабе можете посчитать, какие параметры надо подать на вход, чтобы на выходе тестируемого метода получить единицу; но и входные параметры, и единица на выходе будут скорее магическими числами. Пример — это распределение Максвелла [9]. В алгоритме LBM оно используется в несколько измененном виде.

Малая область покрытия

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

Действительно, иногда простой и легко читаемый тест можно придумать: например, если вы тестируете, как написали матрицы поворота в вашем 3D движке (думаю, немало жителей хабра баловались этим), то поворот на нулевые углы по всем осям должен возвращать единичную матрицу. Тем не менее, часто эти тесты не обнаруживают большинства ошибок. Например, если вы вместо синуса угла поворота (в элементах матрицы поворота) станете использовать тангенс, то такой простой тест пройдет.

Еще пример: вам необходимо реализовать граничные условия для алгоритма LBM. Эти условия должны дополнять состояние узла, когда последний не полностью окружен «жидкими» соседями (например, он находится у стенки). Можно придумать и простой тест — если все соседи находятся в равновесных состояниях (то есть скорости распределены по Максвелловскому закону), то после итерации граничный узел тоже будет в равновесном состоянии. Тем не менее, оказалось, что этот тест пропускает большую часть ошибок…

Можно возразить — в бизнес-приложениях тесты тоже не призваны покрывать все возможные входные параметры. Тем не менее, отличие научных приложений в том, что они обычно оперируют с множествами другой мощности [10]. Бизнес-приложения в основном работают с конечными или счетными множествами (конечной мощности или мощности алеф-нуль: булевские переменные, строки, целые числа), а научные — с несчетными множествами (действительные или комплексные числа).

Малая скорость возрастания ошибок

Из-за того, что типичные множества несчетны, тяжело сразу обнаружить ошибку.

Дело в том, что если вы в методе, использующем только булевские переменные, перепутаете «или» и «и», то вы сразу на его выходе получите что-то не то. А если вы в формуле, работающей при малых значениях входных параметров, перепутаете плюс с минусом, то ошибку вполне можете и не обнаружить после одного вызова метода с этой формулой. Необходимо будет вызывать этот метод несколько сот тысяч раз, чтобы обнаружить расхождение. Стоит также помнить, что в тесте, работающем с действительными числами, надо думать о том, как избежать ложных срабатываний.

Пример: в одном из важных циклов алгоритма LBM был перепутал continue с break. Тем не менее, все тесты проходили. Обнаружилась ошибка только после ручной проверки алгоритма на простой системе — потоке Пуазейля [11], когда после 100000 итераций, или 5 минут(!) моделирования системы 32х64 узла (начиная со стационарного состояния) распределение скоростей оказалось несколько асимметричным (максимальная относительная ошибка — порядка 1e-10).

Отсутствие модульности

Для многих методов невозможно создать модульные тесты.

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

Например, чтобы протестировать типичный шаг алгоритма LBM или типичные граничные условия в двухмерном пространстве, необходима система как минимум 3х3 узла. В них нужно задать плотности, скорости, температуры, провести предварительные расчеты, задать контекст моделирования (типа различных провайдеров физических свойств и моделей) и т. д. В итоге, модульность теста постепенно скрывается в дымке интеграционности.

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

Большие фасады

Если алгоритм нетривиальный, то за одним public методом класса, реализующего этот алгоритм, может скрываться 10-15 методов и 300-400 строк сложного кода [12].

Даже так: 300-400 строк сурового, беспощадного, не поддающегося анализу кода. В этом классе могут быть 5 переменных типа a, b, gamma, вызовы методов библиотек LAPACK [13], BLAS, генерация случайных чисел и кто знает что еще. И вы можете всей душой желать назвать переменную «a» как-то нормально, потому что знаете, что при разработке корпоративного приложения вас бы долго ругали за такое имя, но не можете, потому что так она называется в оригинальной статье, и потому что она не несет никакого явного смысла. Лучшее, что вы можете сделать, это указать ссылку на статью в начале класса.

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

После столкновения с такой ситуацией лучшим решением оказалось переписать этот алгоритм на MATLAB и сравнивать вычисления построчно.

Заключение


Надеюсь, мне удалось привести достаточно веские аргументы и убедить читателей хабра, что зачастую написание одной и той же программы на разных языках разными командами — это прекрасное и (в случае жизненно важных систем) неизбежное дополнение для модульного тестирования, TDD, Interface Driven Development, Agile и прочих современных методик.

Спасибо за прочтение!

Ссылки


[1] Цифровые самолеты
[2] Комментарий к статье Цифровые самолеты
[3] Какое тебе дело до того, что о тебе думают другие, глава «Многострадальное приложение»
[4] Lattice Boltzmann method
[5] Книги по LBM. Некоторые доступны через google books
[6] Parallel Lattice Boltzmann Solver
[7] Finite element method
[8] Boltzmann equation
[9] Maxwell-Boltzmann distribution
[10] Cardinality
[11] Поток Пуазейля
[12] Паттерн Фасад
[13] LAPACK

P.S. Я догадываюсь, что для большинства читателей сайта алгоритм несколько экзотичен, тем не менее, думаю, это лучшая иллюстрация. В конце концов, куда ж без научных алгоритмов в статье о них самых.

P.P.S. Ссылки на научные статьи я не привожу, потому что все они доступны только по подписке.

P.P.S. Спасибо пользователю SychevIgor за инвайт!

UPD


После прочтения комментариев думаю, что надо избавляться от фобии магических чисел и писать для всех модулей (типа BoltzmannDistributionProvider) табличные тесты для сравнения с расчетами из Matlaba или расчетами работающего состояния приложения. А также добавить аналогичные системные тесты (например, просчитать динамику системы 5х5 узлов единожды, записать в файл, и сравнивать с этим файлом результаты прогона каждый раз). Всем спасибо за советы!
Tags:
Hubs:
+63
Comments 60
Comments Comments 60

Articles