Ответ 1
tl; dr: Вероятно, вы должны использовать одномерный подход.
Примечание. Невозможно разобраться в деталях, влияющих на производительность при сравнении динамических 1d или динамических шаблонов хранения 2d без заполнения книг, поскольку производительность кода зависит от очень большого числа параметров. Профиль, если это возможно.
1. Что быстрее?
Для плотных матриц 1D-подход, вероятно, будет более быстрым, поскольку он предлагает лучшую локальность памяти и меньшие затраты на распределение и освобождение.
2. Что меньше?
Динамический-1D потребляет меньше памяти, чем 2D-подход. Последнее также требует больше ассигнований.
Примечания
Я изложил довольно длинный ответ ниже по нескольким причинам, но сначала хочу сделать некоторые замечания о ваших предположениях.
Я могу себе представить, что пересчет индексов для 1D массивов (y + x * n) может быть медленнее, чем использование 2D-массива (x, y)
Сравним эти две функции:
int get_2d (int **p, int r, int c) { return p[r][c]; }
int get_1d (int *p, int r, int c) { return p[c + C*r]; }
Сборка (не встроенная), сгенерированная Visual Studio 2015 RC для этих функций (с включенными оптимизациями):
[email protected]@[email protected] PROC
push ebp
mov ebp, esp
mov eax, DWORD PTR _c$[ebp]
lea eax, DWORD PTR [eax+edx*4]
mov eax, DWORD PTR [ecx+eax*4]
pop ebp
ret 0
[email protected]@[email protected] PROC
push ebp
mov ebp, esp
mov ecx, DWORD PTR [ecx+edx*4]
mov eax, DWORD PTR _c$[ebp]
mov eax, DWORD PTR [ecx+eax*4]
pop ebp
ret 0
Разница заключается в mov (2d) vs. lea (1d).
Первый имеет задержку в 3 цикла и максимальную пропускную способность 2 за цикл, в то время как последний имеет латентность в 2 цикла и максимальную пропускную способность 3 за цикл. (Согласно Таблицы инструкций - Agner Fog
Поскольку различия незначительны, я думаю, что не должно быть большой разницы в производительности, связанной с пересчетом индекса. Я ожидаю, что очень маловероятно, чтобы эта разница сама по себе была узким местом в любой программе.
Это приводит нас к следующей (и более интересной) точке:
... но я мог бы представить, что 1D может быть в кэше CPU...
Правда, но 2d также может быть в кэше CPU. См. The Downsides: Местоположение памяти для объяснения, почему 1d все еще лучше.
Длинный ответ или почему динамическое 2-мерное хранилище данных (указатель на указатель или вектор-вектор) является "плохим" для простых/малых матриц.
Примечание. Это касается динамических массивов/схем распределения [malloc/new/vector и т.д.]. Статический 2d-массив является непрерывным блоком памяти и поэтому не подвержен минусам, которые я собираюсь представить здесь.
Проблема
Чтобы понять, почему динамический массив динамических массивов или вектор векторов, скорее всего, не является шаблоном хранения данных по выбору, вам необходимо понять расположение памяти таких структур.
Пример с использованием указателя на синтаксис указателя
int main (void)
{
// allocate memory for 4x4 integers; quick & dirty
int ** p = new int*[4];
for (size_t i=0; i<4; ++i) p[i] = new int[4];
// do some stuff here, using p[x][y]
// deallocate memory
for (size_t i=0; i<4; ++i) delete[] p[i];
delete[] p;
}
Недостатки
Местоположение памяти
Для этой "матрицы" вы выделяете один блок из четырех указателей и четыре блока из четырех целых чисел. Все распределения не связаны друг с другом и поэтому могут привести к произвольной позиции памяти.
Следующее изображение даст вам представление о том, как может выглядеть память.
Для реального 2d случая:
- Фиолетовый квадрат - это позиция памяти, занятая самой
p. - Зеленые квадраты собирают область памяти
pуказывает на (4 xint*). - 4 области из 4 смежных синих квадратов - это те, на которые указывают каждая
int*зеленой области
Для 2d, нанесенного на 1-й случай:
- Зеленый квадрат является единственным обязательным указателем
int * - Синие квадраты объединяют область памяти для всех матричных элементов (16 x
int).
Это означает, что (при использовании левого макета) вы, вероятно, заметите худшую производительность, чем для непрерывного шаблона хранилища (как видно справа) из-за кэширования, например.
Предположим, что строка кэша - это "объем данных, передаваемых в кеш за один раз", и представьте себе, что программа обращается ко всей матрице за одним элементом за другим.
Если у вас правильно выровненная 4-кратная 4-разрядная матрица из 32-битных значений, процессор с 64-байтной строкой кэша (типичное значение) способен "одноразово" данных (4 * 4 * 4 = 64 байта), Если вы начнете обработку, а данные еще не находятся в кеше, вы столкнетесь с пропуском кеша, и данные будут извлечены из основной памяти. Эта загрузка может извлекать всю матрицу сразу, поскольку она вписывается в строку кэша, если и только если она смежно хранится (и правильно выровнена). Вероятно, не будет больше промахов при обработке этих данных.
В случае динамической, "реальной двумерной" системы с несвязанными расположениями каждой строки/столбца, процессор должен загружать каждую ячейку памяти отдельно. Несмотря на то, что требуется только 64 байта, загрузка 4 строк кэша для 4 несвязанных позиций памяти будет в худшем случае - фактически передать 256 байтов и потратить 75% пропускной способности. Если вы обрабатываете данные с помощью 2d-схемы, вы снова (если не кэшированы) сталкиваетесь с пропуском кеша на первый элемент. Но теперь только первая строка /colum будет в кеше после первого загрузки из основной памяти, потому что все остальные строки расположены где-то еще в памяти, а не рядом с первым. Как только вы достигнете новой строки/столбца, снова будет пропущен кеш, и выполняется следующая загрузка из основной памяти.
Короче говоря: у 2d-шаблона более высокая вероятность промаха в кэше с 1-й схемой, предлагающей лучший потенциал для производительности из-за локальности данных.
Частное распределение/освобождение
- Для создания нужной матрицы NxM (4 × 4) необходимы целые числа, такие как
N + 1(4 + 1 = 5) распределения (с использованием либо new, malloc, allocator:: allocate, либо любой другой). - Необходимо также использовать такое же количество правильных, соответствующих операций освобождения.
Следовательно, создание или копирование таких матриц более выгодно, в отличие от одной схемы распределения.
Это становится все хуже с ростом числа строк.
Накладные расходы на память
Я напишу размер 32 бита для int и 32 бит для указателей. (Примечание: системная зависимость.)
Помните: мы хотим сохранить матрицу 4 × 4, что означает 64 байта.
Для матрицы NxM, сохраненной с представленной схемой указателя на указатель, мы потребляем
-
N*M*sizeof(int)[фактические синие данные] + -
N*sizeof(int*)[зеленые указатели] + -
sizeof(int**)[фиолетовая переменная p] байт.
Это делает 4*4*4 + 4*4 + 4 = 84 байты в случае данного примера, и при использовании std::vector<std::vector<int>> становится еще хуже.
Для этого потребуется N * M * sizeof(int) + N * sizeof(vector<int>) + sizeof(vector<vector<int>>) байтов, т.е. 4*4*4 + 4*16 + 16 = 144 байтов, всего 64 байта для 4 x 4 int.
Кроме того, в зависимости от используемого распределителя - каждое отдельное распределение может хорошо (и, скорее всего, будет) иметь еще 16 байт служебных данных памяти. (Некоторые "Infobytes", которые хранят количество выделенных байтов для надлежащего освобождения.)
Это самый худший случай:
N*(16+M*sizeof(int)) + 16+N*sizeof(int*) + sizeof(int**)= 4*(16+4*4) + 16+4*4 + 4 = 164 bytes ! _Overhead: 156%_
Доля служебных данных будет уменьшаться по мере роста размера матрицы, но все равно будет присутствовать.
Опасность утечки памяти
Связка распределений требует соответствующей обработки исключений, чтобы избежать утечек памяти, если одно из распределений не удастся! Вам нужно отслеживать выделенные блоки памяти, и вы не должны забывать их при освобождении памяти.
Если new пробегает память, а следующая строка не может быть выделена (особенно вероятно, когда матрица очень велика), std::bad_alloc вызывается new.
Пример:
В приведенном выше примере new/delete мы рассмотрим еще один код, если мы хотим избежать утечек в случае bad_alloc исключений.
// allocate memory for 4x4 integers; quick & dirty
size_t const N = 4;
// we don't need try for this allocation
// if it fails there is no leak
int ** p = new int*[N];
size_t allocs(0U);
try
{ // try block doing further allocations
for (size_t i=0; i<N; ++i)
{
p[i] = new int[4]; // allocate
++allocs; // advance counter if no exception occured
}
}
catch (std::bad_alloc & be)
{ // if an exception occurs we need to free out memory
for (size_t i=0; i<allocs; ++i) delete[] p[i]; // free all alloced p[i]s
delete[] p; // free p
throw; // rethrow bad_alloc
}
/*
do some stuff here, using p[x][y]
*/
// deallocate memory accoding to the number of allocations
for (size_t i=0; i<allocs; ++i) delete[] p[i];
delete[] p;
Резюме
Есть случаи, когда "реальные 2d" макеты памяти подходят и имеют смысл (т.е. если количество столбцов на строку не является константой), но в самых простых и распространенных случаях хранения данных 2D они просто раздувают сложность вашего кода и снизить производительность и эффективность памяти вашей программы.
Alternative
Вы должны использовать непрерывный блок памяти и сопоставить свои строки на этом блоке.
"С++-путь" для этого - это, вероятно, написать класс, который управляет вашей памятью при рассмотрении важных вещей, таких как
- Что такое правило трех?
- Что подразумевается под инициализацией ресурсов (RAII)?
- Концепция С++: Контейнер (на cppreference.com)
Пример
Чтобы представить себе, как выглядит такой класс, вот простой пример с некоторыми основными функциями:
- 2d-размер-построимо
- 2d-изменяемая
-
operator(size_t, size_t)для доступа к главному элементу с двумя строками -
at(size_t, size_t)для проверки доступа к главному элементу с 2-го ряда - Выполняет концептуальные требования для контейнера
Источник:
#include <vector>
#include <algorithm>
#include <iterator>
#include <utility>
namespace matrices
{
template<class T>
class simple
{
public:
// misc types
using data_type = std::vector<T>;
using value_type = typename std::vector<T>::value_type;
using size_type = typename std::vector<T>::size_type;
// ref
using reference = typename std::vector<T>::reference;
using const_reference = typename std::vector<T>::const_reference;
// iter
using iterator = typename std::vector<T>::iterator;
using const_iterator = typename std::vector<T>::const_iterator;
// reverse iter
using reverse_iterator = typename std::vector<T>::reverse_iterator;
using const_reverse_iterator = typename std::vector<T>::const_reverse_iterator;
// empty construction
simple() = default;
// default-insert rows*cols values
simple(size_type rows, size_type cols)
: m_rows(rows), m_cols(cols), m_data(rows*cols)
{}
// copy initialized matrix rows*cols
simple(size_type rows, size_type cols, const_reference val)
: m_rows(rows), m_cols(cols), m_data(rows*cols, val)
{}
// 1d-iterators
iterator begin() { return m_data.begin(); }
iterator end() { return m_data.end(); }
const_iterator begin() const { return m_data.begin(); }
const_iterator end() const { return m_data.end(); }
const_iterator cbegin() const { return m_data.cbegin(); }
const_iterator cend() const { return m_data.cend(); }
reverse_iterator rbegin() { return m_data.rbegin(); }
reverse_iterator rend() { return m_data.rend(); }
const_reverse_iterator rbegin() const { return m_data.rbegin(); }
const_reverse_iterator rend() const { return m_data.rend(); }
const_reverse_iterator crbegin() const { return m_data.crbegin(); }
const_reverse_iterator crend() const { return m_data.crend(); }
// element access (row major indexation)
reference operator() (size_type const row,
size_type const column)
{
return m_data[m_cols*row + column];
}
const_reference operator() (size_type const row,
size_type const column) const
{
return m_data[m_cols*row + column];
}
reference at() (size_type const row, size_type const column)
{
return m_data.at(m_cols*row + column);
}
const_reference at() (size_type const row, size_type const column) const
{
return m_data.at(m_cols*row + column);
}
// resizing
void resize(size_type new_rows, size_type new_cols)
{
// new matrix new_rows times new_cols
simple tmp(new_rows, new_cols);
// select smaller row and col size
auto mc = std::min(m_cols, new_cols);
auto mr = std::min(m_rows, new_rows);
for (size_type i(0U); i < mr; ++i)
{
// iterators to begin of rows
auto row = begin() + i*m_cols;
auto tmp_row = tmp.begin() + i*new_cols;
// move mc elements to tmp
std::move(row, row + mc, tmp_row);
}
// move assignment to this
*this = std::move(tmp);
}
// size and capacity
size_type size() const { return m_data.size(); }
size_type max_size() const { return m_data.max_size(); }
bool empty() const { return m_data.empty(); }
// dimensionality
size_type rows() const { return m_rows; }
size_type cols() const { return m_cols; }
// data swapping
void swap(simple &rhs)
{
using std::swap;
m_data.swap(rhs.m_data);
swap(m_rows, rhs.m_rows);
swap(m_cols, rhs.m_cols);
}
private:
// content
size_type m_rows{ 0u };
size_type m_cols{ 0u };
data_type m_data{};
};
template<class T>
void swap(simple<T> & lhs, simple<T> & rhs)
{
lhs.swap(rhs);
}
template<class T>
bool operator== (simple<T> const &a, simple<T> const &b)
{
if (a.rows() != b.rows() || a.cols() != b.cols())
{
return false;
}
return std::equal(a.begin(), a.end(), b.begin(), b.end());
}
template<class T>
bool operator!= (simple<T> const &a, simple<T> const &b)
{
return !(a == b);
}
}
Обратите внимание на несколько вещей здесь:
-
Tдолжен удовлетворять требованиям используемых функций-членовstd::vector -
operator()не выполняет никаких проверок "диапазона" - Вам не нужно управлять данными самостоятельно
- Не требуется деструктор, конструктор копирования или оператор присваивания
Поэтому вам не нужно беспокоиться о правильной обработке памяти для каждого приложения, но только один раз для класса, который вы пишете.
Ограничения
Бывают случаи, когда динамическая "реальная" двумерная структура благоприятна. Это, например, случай, если
- матрица очень большая и разреженная (если какая-либо из строк даже не требуется выделять, но может обрабатываться с помощью nullptr), или если
- строки не имеют одинакового количества столбцов (т.е. если у вас нет матрицы вообще, кроме другой двумерной конструкции).