1D或2D阵列，什么更快？

问题描述 投票：56回答：7

我需要表示一个2D场（轴x，y），我遇到一个问题：我应该使用一维数组还是二维数组？

我可以想象，重新计算1D数组的索引（y + x * n）可能比使用2D数组（x，y）慢，但我可以想象1D可能在CPU缓存中。

我做了一些谷歌搜索，但只找到关于静态数组的页面（并说明1D和2D基本相同）。但我的阵列必须是动态的。

有啥

  1. 快点，
  2. 较小的（RAM）

动态1D阵列还是动态2D阵列？

谢谢 ：）

c++ c arrays
7个回答
176
投票

tl;dr : You should probably use a one-dimensional approach.

注意：在比较动态1d或动态2d存储模式而不填充书籍时，人们无法深入研究影响性能的细节，因为代码的性能取决于非常多的参数。如果可能的话。

1. What's faster?

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

2. What's smaller?

Dynamic-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为这些函数生成的（非内联）程序集（启用了优化）是：

?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的说法，由于差异较小，我认为不应该因索引重新计算而产生很大的性能差异。我预计这种差异本身不太可能成为任何程序的瓶颈。

这将我们带到下一个（也是更有趣的）点：

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

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

The long answer, or why dynamic 2 dimensional data storage (pointer-to-pointer or vector-of-vector) is "bad" for simple / small matrices.

注意：这是关于动态数组/分配方案[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;
}

缺点

Memory locality

对于这个“矩阵”，你分配一个四个指针的块和四个四个整数的块。所有分配都是不相关的，因此可能导致任意的内存位置。

下图将让您了解内存的外观。

对于真正的2d案例：

  • 紫色方块是p本身占据的记忆位置。
  • 绿色方块组装内存区域p指向（4 x int*）。
  • 4个连续蓝色方块的4个区域是绿色区域的每个int*所指向的区域

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

  • 绿色方块是唯一需要的指针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方案由于数据的局部性而提供更好的性能潜力。

Frequent Allocation / Deallocation

  • 只需N + 1（4 + 1 = 5）分配（使用new，malloc，allocator :: allocate或其他）就可以创建所需的NxM（4×4）矩阵。
  • 还必须应用相同数量的适当的相应解除分配操作。

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

行数越来越多，情况越来越糟。

Memory consumption overhead

我假设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字节，对于4 x 4 int，为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%_

随着矩阵大小的增加，开销的份额将减少但仍将存在。

Risk of memory leaks

一堆分配需要适当的异常处理，以避免内存泄漏，如果其中一个分配失败！您需要跟踪已分配的内存块，并且在释放内存时不能忘记它们。

如果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数据存储情况下，它们只会增加代码的复杂性并降低性能和你的程序的内存效率。

Alternative

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

这样做的“C ++方式”可能是编写一个管理你的记忆的类，同时考虑重要的事情

例

为了提供这样一个类的外观，这里有一个简单的例子，它带有一些基本特征：

  • 2D-尺寸constructible
  • 2D-可调整大小
  • operator(size_t, size_t)用于第二行主要元素访问
  • 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()不做任何“范围”检查
  • 无需自行管理数据
  • 不需要析构函数，复制构造函数或赋值运算符

因此，您不必为每个应用程序处理正确的内存处理，而只需为您编写的类处理一次。

Restrictions

可能存在动态“真实”二维结构有利的情况。例如，如果是这种情况

  • 矩阵非常大且稀疏（如果任何行甚至不需要分配但可以使用nullptr处理）或者如果
  • 行没有相同的列数（即如果除了另一个二维构造之外根本没有矩阵）。
17
投票

除非你在讨论静态数组，否则1D会更快。

这是一维数组（std::vector<T>）的内存布局：

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

对于动态2D数组（std::vector<std::vector<T>>），这是相同的：

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

显然，2D情况会丢失缓存局部性并使用更多内存。它还引入了一个额外的间接（因此是一个额外的指针），但第一个数组有计算索引的开销，所以这些指数或多或少都有。

8
投票

1D and 2D Static Arrays

  • 大小：两者都需要相同的内存量。
  • 速度：您可以假设没有速度差异，因为这两个阵列的内存应该是连续的（整个2D阵列应该在内存中显示为一个块而不是一堆遍布内存的块）。 （但这可能是编译器依赖的。）

1D and 2D Dynamic Arrays

  • 大小：2D阵列比1D阵列需要更多的内存，因为2D阵列中需要指针指向分配的1D阵列集。 （当我们谈论真正的大型阵列时，这一点很小。对于小型阵列，相对而言，这一点可能相当大。）
  • 速度：1D阵列可能比2D阵列更快，因为2D阵列的内存不是连续的，因此缓存未命中将成为问题。

使用什么有效，似乎最合乎逻辑，如果你遇到速度问题，那么重构。

5
投票

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

在C（但不是C ++）中有第三种选择;您可以拥有一个动态分配并具有运行时维度的连续二维数组：

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

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

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

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

4
投票

1D和2D阵列的另一个区别出现在内存分配中。我们不能确定2D阵列的成员是否是序列的。

1
投票

这实际上取决于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]或[x * 20 + y]不会有很多差异，因为一个是你在做计算而另一个是编译器为你做这件事。 c [x] [y]和d [x] [y]较慢，因为机器必须找到c [x]指向的地址，然后从那里访问第y个元素。这不是一个直接的计算。在某些机器上（例如AS400有36个字节（非位）指针），指针访问速度极慢。它完全取决于使用的架构。在x86类型的体系结构中，a和b的速度相同，c和d比b慢。

0
投票

我喜欢Pixelchemist提供的全面答案。该解决方案的更简单版本可以如下。首先，声明尺寸：

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

接下来，创建一个别名，并获取和设置方法：

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

在初始化时定义矢量大小提供了optimal performance。该解决方案由this answer修改。可以使用单个向量来重载函数以支持不同的维度。该解决方案的缺点是M，N，P参数被隐式传递给get和set函数。这可以通过在类中实现解决方案来解决，如Pixelchemist所做。

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.