Введение
Так уж сложилось, что моя работа тесно связана с математическим моделированием физических процессов. Математическое моделирование — это совершенно особенная область программирования. Расчет даже относительно простого физического процесса может занимать несколько дней и даже недель. Поэтому на первый план выходит производительность программы, пускай даже в ущерб удобству написания и чтения кода. Однако до недавнего времени быстродействие моих программ меня мало заботило: вполне хватало грубых сеток, для которых расчеты занимали что-то около суток. Но постепенно сетки становились все подробнее, и время работы программ неуклонно росло. Тогда я стал искать узкие места в своей программе. Сначала в алгоритмах. Потом дело дошло до структур данных. И тут меня очень заинтересовал вопрос «а что же лучше использовать для хранения векторов: массивы или контейнеры?»
В математическом моделировании операции с векторами и матрицами большой размерности, в частности итерационные методы решения СЛАУ, занимают одну из ключевых позиций. Теоретически, работа с массивами должна быть более быстрой, но работа с контейнерами более удобна. Весь вопрос в том как перевести это «более» в язык цифр? Стоит ли удобство таких затрат? Поиск по интернету внятных ответов так и не дал. Встречались либо расплывчатые формулировки из категории «более-менее», «существенно-несущественно» либо, в лучшем случае, простейшие тесты на многократное повторение одних и тех же действий над элементами вектора. Но тесты это одно, а боевая действительность — совсем другое. Тем более, проведя кое-какие из таких тестов самостоятельно, я с удивлением обнаружил, что на разных тестах преимущество имеют разные структуры данных. Тогда в качестве теста я решил использовать реальную физическую задачу.
Задача
В качестве теста я взял известную в теплофизике задачу о конвективном течении в бесконечно протяженной трубе квадратного сечения заполненной жидкостью и подогреваемой сбоку. Поскольку труба имеет бесконечную протяженность (для определенности — вдоль координаты z) и краевые условия не зависят от z, то задачу можно рассматривать как двумерную. Левая и правая стенки поддерживаются при постоянных, но разных, температурах. Верхняя и нижняя стенки тплоизолированы. На всех стенках заданы условия непротекания и прилипания, т.е. равенство нулю всех компонент скорости. Конвективный теплообмен в жидкости описывается системой уравнений энергии, Навье-Стокса и неразрывности в координатах температура-вихрь-функция тока:
Задача решалась методом конечных элементов на треугольной сетке с линейными базисными функциями. Размер секи 100х100 узлов. В качестве решателя СЛАУ использовался ЛОС с LU предобуславливанием.
Исходные коды
Исходные коды программ можно взять
здесь.
Результаты тестирования
Итак. Собственно то, для чего все и затевалось. Было написано три программных реализации решения вышеописанной задачи. В качестве языка программирования использовался c++. В первой программе для хранения матриц и векторов использовались динамические массивы, во второй — контейнеры std::vector, в третьей — контейнеры QVector. Времена работы программы (в тиках) предствлены в таблице:
Release |
|
1 |
2 |
3 |
4 |
5 |
Среднее |
Потери времени |
Массивы |
21820000 |
21760000 |
21730000 |
21660000 |
21850000 |
21764000 |
0% |
std::vector |
26680000 |
26660000 |
26900000 |
26870000 |
26790000 |
26780000 |
23% |
QVector |
43760000 |
43770000 |
43820000 |
43840000 |
43770000 |
43792000 |
101% |
Debug |
|
1 |
2 |
3 |
4 |
5 |
Среднее |
Потери времени |
Массивы |
50290000 |
50630000 |
50760000 |
- |
- |
50560000 |
0% |
std::vector |
118830000 |
119560000 |
118240000 |
- |
- |
118877000 |
135% |
QVector |
306800000 |
297400000 |
294400000 |
- |
- |
299530000 |
492% |
Выводы
Итак, основной вывод по результатам тестирования можно сделать следующий: использование контейнеров недопустимо при решении задач матмоделирования. Никакое удобство написание кода, никакая безопасность кода не могут оправдать падение производительности в 23%. Скажу честно, я не ожидал такого заметного падения. Тем более нериятным сюрпризом для меня стали результаты тестирования QVector'а, ведь имнно его я использовал в своей программе. Такое серьезное отставание по всей видимости объясняется использованием концепции SharedMemory. Экономя на копировании, мы проигроваем на доступе к элементам контейнера, ведь при изменении каждого! элемента происходит дополнительная проверка на необходимость выполнения отложенного копирования.
Бонус: Результаты математического моделирования
Температура:
|
Функция тока:
|
Вихрь:
|
Vx:
|
Vy:
|