Описывая очень длинную матрицу вектором векторов, какое измерение должно быть наибольшим?

Question

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

using namespace std;
vector< vector< userclass > > matrix = vector<vector<userclass> >(sizeX, vector<userclass>(sizeY));

Этот класс, который также может быть структурой, будет содержать несколько встроенных функций, таких как float и указатели.Итак, вот в чем дело: допустим, матрица будет иметь размер 2000 в одном направлении, но только размер 20 в другом, но у меня есть полная свобода выбора.Для лучшей производительности, какую из них я должен сделать наибольшим, sizeX или sizeY?

Другими словами: что быстрее, маленький вектор больших векторов или большой вектор маленьких векторов?Есть ли разница вообще?

Оптимизация производительности должна быть направлена ​​на единичный случайный доступ.

Answer 1

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

---

Конечно, это зависит от того, как вы собираетесь их использовать. Если вы можете, попробуйте получить доступ к вектору как можно дольше - vec[i][j] намного лучше, чем vec[j][i]. Если вам нужно сделать vec[j][i], то увеличение sizeX может иметь лучшую производительность или использование 1 непрерывного массива.

Самая быстрая итерация, где sizeX> sizeY:

for(int i...)
for(int j...) {
  vec[i][j];
}

Answer 2

Здесь нужно учитывать разные вещи. Во-первых, вам, вероятно, лучше определить собственный тип matrix, который содержит один вектор данных размером sizeX*sizeY вместе с операторами, которые отображают координаты в месте расположения элемента в векторе. Преимущество этого подхода состоит в том, что объем памяти будет более компактным (меньше используемой памяти ¹ ) и память будет смежной.

Что касается того, как должно выполняться это сопоставление, и, главным образом, с точки зрения производительности, это зависит от использования данных. Если вы собираетесь выполнять итерацию в определенном направлении, вы хотите, чтобы последовательные элементы в этом направлении занимали смежные позиции в памяти (т. Е. Если вы собираетесь выполнять итерацию с внешним циклом по Y и внутренним циклом по X, тогда формула должно быть pos = y * sizeX + x.

¹ Если предположить, что тип занимает 10 байтов, вектор из 2000 векторов из 20 элементов займет (2000+1)*sizeof(vector) + 2000*20*10 байтов, вектор из 20 векторов из 2000 элементов займет приблизительно (20+1)*sizeof(vector) + 2000*20*10 байтов, и один вектор из 2000*20 элементов занимает sizeof(vector)+2000*20*10 байт. Примерно в 64-битной платформе в выпуске без дополнительной отладочной информации, sizeof(vector<X>) ~ 3*8 (т.е. 24 байта), и итоговые значения будут: 448024, 400504 и 400024 байты. Это может не иметь большого значения, но в первом случае используется дополнительная память на 10% по сравнению с оптимальным случаем.