Скорость контейнеров STL против массивов

Я только начал работать над научным проектом, где скорость действительно имеет значение (HPC). В настоящее время я разрабатываю структуры данных. Ядром проекта является 3D-сетка двойных значений для решения уравнения в частных производных.

Поскольку скорость здесь, вероятно, больше беспокоит, чем простоту кода, я хотел бы знать, как работает STL по сравнению с обычными массивами в стиле C. В моем случае, поскольку это 3D-сетка, я думал о: а) одномерном векторе с линейной индексацией, б) векторе с 3 векторами или в) одномерном массиве в стиле с, или г) трехмерном стиле в, массив.

Я посмотрел старые вопросы, но нашел только вопросы, связанные со строительством / разрушением (что здесь не важно, так как структуры данных создаются только один раз при запуске программы — важны быстрая индексация и вычисления на ней) или сравнение различных контейнеров STL.

Спасибо за помощь

4

Решение

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

Кроме того, в зависимости от машины и реализации библиотеки,
используя std::vector для этого плоского вектора может быть больше
дороже, чем использование простого указателя на память (или это может
не будь — ты не можешь знать заранее). Я бы все еще пошел на
сначала вектор, аккуратно оберните все в контрольном классе,
и, если проблемы с производительностью не устранены, переключитесь на
указатель.

7

Другие решения

Расположение памяти для 1D и 3D массивов будет таким же, и похоже на расположение памяти линейного std::vector, Я бы выбрал такой подход: одномерный вектор и встроенную функцию для сопоставления с соответствующим местоположением.

Вектор векторов, с другой стороны, имеет совершенно иную компоновку, поскольку данные в векторе не хранятся внутри объекта, а динамически распределяются и на них ссылаются. Это означает, что две разные строки в std::vector<std::vector<int>> может быть в совершенно не связанных местах в памяти.

3

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

Например, один вектор должен работать так же, как одномерный c-массив, а вектор векторов должен работать примерно так же, как если бы вы использовали необработанный массив указателей, каждый элемент которого указывает на массив.

Однако, если 3d-массив имеет одинаковые размеры (то есть не рваные массивы), то векторы платят дополнительную плату за индивидуальное управление своими размерами (например, они должны хранить свои размеры индивидуально). Если какой-либо из размеров измерения известен во время компиляции, вам лучше использовать std :: array контейнера ‘STL’, because it won't have that unnecessary overhead. You can even have multi-dimentionalстанд :: arrays`:

template<typename T, int Planes, int Rows, Cols>
using Matrix = std::array<std::array<std::array<T,Cols>,Rows>,Planes>;

Хотя это и не обязательно, оно должно быть таким же, как T arr[Planes][Rows][Cols];, но без проблем сырых c-массивов.

2

Широко используемый в HPC динамически размещаемый статический (с точки зрения неизменяемых измерений после выделения) массив объектов представляет собой комбинацию плоского массива и допингового вектора. По сути, идея состоит в том, чтобы выделить большой плоский кусок памяти, а затем встроить в него дерево указателей. Для двумерных массивов дерево представляет собой простой линейный список указателей на начало каждой строки. Для трехмерных массивов дерево имеет два уровня, и каждый из элементов второго уровня указывает на строку из 2D-среза, которая соответствует первому уровню. Размещение дерева допинг-векторов в начале выделенной памяти позволяет напрямую применить [] оператор индексации, например A[i][j][k], но некоторая осторожность должна быть принята как &A[i] не будет началом i2-й 2D-срез.

Одной из проблем этого подхода является то, что дерево допинговых векторов может стать очень большим по размеру. Например, размер этой структуры данных для массива 1000x1000x1000 на 64-разрядной машине составляет 1000x1000x8 байт или почти 8 МБ. Это может занять драгоценное место в кеше для определенных шаблонов доступа к данным.

0
По вопросам рекламы [email protected]