c++ - 一维或二维数组，哪个更快？

Question

我需要表示一个二维字段(x、y 轴)，但我面临一个问题:我应该使用一维数组还是二维数组？
我可以想象，重新计算一维数组 (y + x*n) 的索引可能比使用二维数组 (x, y) 慢，但我可以想象一维可能在 CPU 缓存中。
我做了一些谷歌搜索，但只找到了关于静态数组的页面(并说明一维和二维基本相同)。但是我的数组必须是动态的。
有啥

更快，

更小 (RAM)

动态一维数组还是动态二维数组？

Answer 1

tl;dr :您可能应该使用一维方法。

注意:在比较动态 1d 或动态 2d 存储模式时，无法深入研究影响性能的细节而无需填写书籍，因为代码的性能取决于大量参数。如果可能，配置文件。

1. 什么更快？

对于密集矩阵，一维方法可能更快，因为它提供更好的内存局部性和更少的分配和释放开销。

2. 什么更小？

动态一维比二维方法消耗更少的内存。后者也需要更多的分配。

评论

我在下面列出了一个很长的答案，原因有几个，但我想先对你的假设发表一些评论。

I can imagine, that recalculating indices for 1D arrays (y + x*n) could be slower than using 2D array (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 为这些函数(打开优化)生成的(非内联)程序集是:

?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个。 (根据 Instruction tables - Agner Fog
由于差异很小，我认为应该不会因为索引重新计算而产生很大的性能差异。我预计这种差异本身不太可能成为任何程序中的瓶颈。

这将我们带到下一个(也是更有趣的)点:

... but I could image that 1D could be in CPU cache ...

没错，但 2d 也可以在 CPU 缓存中。有关为什么 1d 仍然更好的解释，请参阅 The Downsides: Memory locality。

长答案，或者为什么动态二维数据存储(指针到指针或 vector vector )对于简单/小矩阵“不好”。

注意:这是关于动态数组/分配方案 [malloc/new/vector 等]。静态二维数组是一个连续的内存块，因此不受我将在此处介绍的缺点的影响。

问题

为了能够理解为什么动态数组的动态数组或 vector 的 vector 很可能不是首选的数据存储模式，您需要了解此类结构的内存布局。

使用指向指针语法的指针的示例案例

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 x int*)。

4个连续蓝色方块的4个区域是绿色区域

的每个 int*所指向的区域

对于映射在 1d 情况下的 2d:

绿色方块是唯一需要的指针 int *

蓝色方块集合了所有矩阵元素的内存区域 (16 x int )。

这意味着(当使用左侧布局时)您可能会观察到比连续存储模式(如右侧所示)更糟糕的性能，例如由于缓存。

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

如果您有一个正确对齐的 32 位值的 4 乘 4 矩阵，则具有 64 字节缓存线(典型值)的处理器能够“一次性”处理数据(4*4*4 = 64 字节)。
如果您开始处理并且数据不在缓存中，您将面临缓存未命中，数据将从主内存中获取。此加载可以一次获取整个矩阵，因为它适合缓存行，当且仅当它连续存储(并正确对齐)时。
处理该数据时可能不会再有任何遗漏。

在动态的、“真正的二维”系统中，每行/列的位置都不相关，处理器需要单独加载每个内存位置。
尽管只需要 64 个字节，但为 4 个不相关的内存位置加载 4 个缓存行 - 在最坏的情况下 - 实际上会传输 256 个字节并浪费 75% 的吞吐量带宽。
如果您使用 2d-scheme 处理数据，您将再次(如果尚未缓存)在第一个元素上遇到缓存未命中。
但是现在，在第一次从主内存加载后，只有第一行/列会在缓存中，因为所有其他行都位于内存中的其他位置，而不是与第一行相邻。
一旦到达新的行/列，就会再次发生缓存未命中，并执行从主内存的下一次加载。

长话短说:2d 模式有更高的缓存未命中机会，1d 方案由于数据的局部性提供了更好的性能潜力。

频繁分配/解除分配

多达 N + 1 (4 + 1 = 5) 次分配(使用 new、malloc、allocator::allocate 或其他)是创建所需的 NxM (4×4) 矩阵所必需的。

还必须应用相同数量的适当的相应解除分配操作。

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

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

内存消耗开销

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

让我们记住:我们想要存储一个 4×4 int 矩阵，这意味着 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 整数。

此外——取决于使用的分配器——每个单独的分配很可能(并且很可能会)有另外 16 字节的内存开销。 (一些“信息字节”存储分配的字节数，以便正确释放。)

这意味着最坏的情况是:

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 抛出。

示例:

在上面提到的新建/删除示例中，如果我们想在 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++ 方式”可能是编写一个类来管理您的内存，同时考虑诸如

What is The Rule of Three?

What is meant by Resource Acquisition is Initialization (RAII)?

C++ concept: Container (on cppreference.com)

例子

为了让您了解此类类的外观，这里有一个具有一些基本功能的简单示例:

2d 尺寸可构造

二维可调整大小

operator(size_t, size_t) 用于二维行主要元素访问

at(size_t, size_t) 用于检查二维行主要元素访问

满足容器

的概念要求

来源:

#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 处理)或者如果

行的列数不同(也就是说，如果您根本没有矩阵，只有另一个二维结构)。