一维或二维阵列，哪个更快？

我需要表示一个2D 字段(轴 x，y) ，我面临一个问题: 我应该使用1D 数组还是2D 数组？

I can imagine, that recalculating indices for 1D arrays (y + x*n) could be slower than using 2D array (x, y) but I could image that 1D could be in CPU cache..

我做了一些谷歌，但只找到了关于静态数组的页面(并声明1D 和2D 基本上是相同的)。但是我的数组必须是动态的。

那么，什么是

  1. 更快,
  2. 较小(RAM)

动态一维阵列还是动态二维阵列？

57160 次浏览
小开

一维和二维静态阵列

  • 大小: 两者都需要相同的内存量。

  • 速度: 您可以假设没有速度差异，因为这两个数组的内存都应该是连续的(The 整个2D 数组应该显示为内存中的一个块，而不是一个 这可能是编译器 但须视乎情况而定。)

一维和二维动态数组

  • 大小: 2D 数组将需要比1D 数组多一点内存，因为2D 数组中需要指向所分配的1D 数组集的指针。(当我们讨论真正大的数组时，这一点点只是很小的。对于小数组来说，相对来说，这个小比特可能相当大。)

  • 速度: 一维数组可能比二维数组快，因为二维数组的内存不是连续的，所以缓存丢失将成为一个问题。

使用看起来最符合逻辑的工具，如果遇到速度问题，那么重构。

小开

除非 讨论的是静态数组，否则 1D 更快。

下面是一维数组(std::vector<T>)的内存布局:

+---+---+---+---+---+---+---+---+---+
|   |   |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+---+

对于动态2D 数组(std::vector<std::vector<T>>)也是如此:

+---+---+---+
| * | * | * |
+-|-+-|-+-|-+
|   |   V
|   | +---+---+---+
|   | |   |   |   |
|   | +---+---+---+
|   V
| +---+---+---+
| |   |   |   |
| +---+---+---+
V
+---+---+---+
|   |   |   |
+---+---+---+

显然，2D 用例丢失了缓存区域，并且使用了更多的内存。它还引入了一个额外的间接指针(因此后面还有一个额外的指针) ，但是第一个数组有计算索引的开销，所以这些索引或多或少都会出错。

小开

这实际上取决于如何实现2D 数组。

考虑以下守则:

int a[200], b[10][20], *c[10], *d[10];
for (ii = 0; ii < 10; ++ii)
{
c[ii] = &b[ii][0];
d[ii] = (int*) malloc(20 * sizeof(int));    // The cast for C++ only.
}

这里有3个实现: b、 c 和 d

访问 b[x][y]或 a[x*20 + y]不会有很大的差别，因为一个是您执行计算，另一个是编译器为您执行计算。c[x][y]和 d[x][y]比较慢，因为机器必须找到 c[x]指向的地址，然后从那里访问 yth 元素。这不是一个简单的计算。在一些机器上(例如 AS400，它有36个字节(非位)指针) ，指针访问非常缓慢。这完全取决于所使用的架构。在 x86类型的体系结构中，a 和 b 的速度相同，c 和 d 的速度比 b 慢。

小开
最佳答案

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]; }

VisualStudio2015RC 为这些函数(打开了优化)生成的(非内联的)程序集是:

?get_1d@@YAHPAHII@Z 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


?get_2d@@YAHPAPAHII@Z 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)和 lea(1d)。 前者的延迟为3个周期，最大吞吐量为每个周期2个，而后者的延迟为2个周期，最大吞吐量为每个周期3个。(根据 指令表-阿格纳雾 由于差异很小，我认为指数重新计算不会产生很大的业绩差异。我认为这种差异本身不太可能成为任何程序的瓶颈。

这就把我们带到了下一点(也是更有趣的一点) :

... 但我可以想象1D 可能在 CPU 缓存..。

没错，但是2d 也可能在 CPU 缓存中。请参阅 缺点: 内存位置了解为什么1d 仍然更好。

长的答案，或者为什么动态二维数据存储(指针到指针或向量向量)是“坏”的 很简单/小矩阵。

注意: 这是关于动态数组/分配方案[ malloc/new/Vector etc ]。静态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;
}

不好的方面

内存位置

对于这个“矩阵”，您分配四个指针的一个块和四个整数的四个块。因此可以导致任意内存位置。

下面的图片将给你一个想法，如何记忆可能看起来像。

对于 真正的二维情况:

  • 紫色正方形是职务本身的内存。
  • 绿色正方形将存储区域 p指向(4 x int*)。
  • 4个相邻蓝色方块的4个区域是绿色区域的每个 int*所指向的区域

对于 二维映射到一维情况:

  • 绿色正方形是唯一需要的指针 int *
  • 蓝色正方形集合了所有矩阵元素(16 x int)的存储区域。

Real 2d vs mapped 2d memory layout

这意味着(在使用左侧布局时)您可能会观察到比连续存储模式(如右侧所示)更差的性能，这是由于缓存等原因造成的。

假设一条缓存线路是“一次传输到缓存中的数据量”，让我们想象一个程序一个接一个地访问整个矩阵。

如果你有一个正确对齐的4乘4矩阵的32位值，一个64字节缓存线(典型值)的处理器能够“一次性”处理数据(4 * 4 * 4 = 64字节)。 如果您开始处理，而数据还没有在缓存中，您将面临缓存丢失，数据将从主存中提取。这个负载可以立即获取整个矩阵，因为它适合一个缓存行，当且仅当它是连续存储的(并且正确对齐)。 在处理这些数据时，可能不会再有任何遗漏。

对于一个动态的、“真正的二维”系统，其中每一行/每一列的位置不相关，处理器需要分别加载每一个内存位置。 即使只需要64字节，为4个不相关的内存位置加载4条缓存线路——在最坏的情况下——实际上传输256字节，浪费75% 的吞吐量带宽。 如果您使用2d 方案处理数据，您将再次(如果还没有缓存)面临第一个元素的缓存丢失。 但是现在，在从主内存第一次加载之后，只有第一行/列会在缓存中，因为所有其他行都位于内存中的其他位置，而不是与第一行相邻。 一旦到达一个新的行/列，将再次出现缓存丢失，并执行来自主内存的下一次加载。

长话短说: 由于数据的局部性，2d 模式缓存失败的几率更高，而1d 模式提供了更好的性能潜力。

频密分配/调迁

  • 为了创建所需的 NxM (4 × 4)矩阵，需要多达 N + 1(4 + 1 = 5)的分配(使用 new、 malloc、 allocator: : distribution 或其他方法)。
  • 还必须应用相同数量的适当的、各自的释放操作。

因此，与单个分配方案相比，创建/复制这样的矩阵的成本更高。

随着行数的增加，这种情况变得更加糟糕。

内存消耗开销

我假设 int 的大小为32位，指针的大小为32位(注意: 系统依赖性)

让我们记住: 我们想要存储一个4 × 4 int 矩阵，这意味着64字节。

对于 NxM 矩阵，与我们使用的指针到指针方案一起存储

  • 实际蓝色数据
  • [绿色指针] +
  • 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字节，而不是4x4int 的64字节。

此外，根据所使用的分配器，每个单独的分配可能(而且很可能)还有另外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 数据存储情况下，它们只会增加代码的复杂性，降低程序的性能和内存效率。

另一种选择

您应该使用一个连续的内存块，并将您的行映射到该块。

“ C + + 方法”可能是编写一个类来管理内存，同时考虑一些重要的事情，比如

例子

为了说明这样的类是什么样子的，这里有一个简单的例子，它有一些基本的特性:

  • 2d 大小可建造
  • 2D 大小
  • operator(size_t, size_t)用于2d 行主要元素访问
  • at(size_t, size_t)用于检查的2d 行主要元素访问
  • 满足 集装箱的概念要求

来源:

#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 处理)或者
  • 这些行没有相同数量的列(也就是说，如果除了另一个二维结构之外根本没有矩阵)。
小开

1D 和2D 数组的另一个区别出现在内存分配上。我们不能确定二维数组的成员是连续的。

小开

现有的答案都只是将1-D 数组与指针数组进行比较。

在 C (但不是 C + +)中有第三个选项; 你可以有一个连续的2-D 数组，它是动态分配的，并且有运行时维度:

int (*p)[num_columns] = malloc(num_rows * sizeof *p);

这就像 p[row_index][col_index]一样。

我希望它的性能与1-D 数组非常相似，但是它为访问单元格提供了更好的语法。

在 C + + 中，您可以通过定义一个类来实现类似的功能，该类在内部维护一个1-D 数组，但是可以使用重载操作符通过2-D 数组访问语法公开它。同样，我希望它与普通的1-D 数组具有相似或相同的性能。

小开

我喜欢 像素化学家提供的全面的答案。这种解决方案的简单版本如下所示。首先，声明尺寸:

constexpr int M = 16; // rows
constexpr int N = 16; // columns
constexpr int P = 16; // planes

接下来，创建一个别名以及 get 和 set 方法:

template<typename T>
using Vector = std::vector<T>;


template<typename T>
inline T& set_elem(vector<T>& m_, size_t i_, size_t j_, size_t k_)
{
// check indexes here...
return m_[i_*N*P + j_*P + k_];
}


template<typename T>
inline const T& get_elem(const vector<T>& m_, size_t i_, size_t j_, size_t k_)
{
// check indexes here...
return m_[i_*N*P + j_*P + k_];
}

最后，可以创建一个向量，并按以下方式编制索引:

Vector array3d(M*N*P, 0);            // create 3-d array containing M*N*P zero ints
set_elem(array3d, 0, 0, 1) = 5;      // array3d[0][0][1] = 5
auto n = get_elem(array3d, 0, 0, 1); // n = 5

在初始化时定义向量大小提供了 最佳性能。此解决方案是从 这个答案修改的。这些函数可能被重载，以支持单个向量的不同维度。这种解决方案的缺点是将 M、 N、 P 参数隐式地传递给 get 和 set 函数。这可以通过在类中实现解决方案来解决，就像 像素化学家所做的那样。


提交答案