c ++-1D或2D数组,更快些?

我需要表示一个2D字段(轴x,y),并且遇到一个问题:我应该使用一维数组还是二维数组?

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

我做了一些谷歌搜索,但只找到了有关静态数组的页面(并指出1D和2D基本相同)。 但是我的数组必须动态。

有啥

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

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

谢谢 :)

graywolf asked 2019-10-15T20:33:23Z
7个解决方案
173 votes

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

注意:在不填充书本的情况下比较动态1d或动态2d存储模式时,无法深入研究影响性能的细节,因为代码的性能取决于很多参数。 如果可能的话进行配置。

1.什么更快?

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

2.较小的是?

与2D方法相比,Dynamic-1D消耗的内存更少。 后者还需要更多分配。

备注

我出于以下几个原因提出了一个很长的答案,但我想首先对您的假设做一些评论。

我可以想象,重新计算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

区别是operator()(2d)与std::vector(1d)。前者的延迟为3个周期,最大吞吐量为每个周期2个,而后者的延迟为2个周期,最大吞吐量为每个周期3个。 (根据说明表-Agner Fog由于差异很小,我认为索引重新计算不会产生很大的性能差异。 我希望几乎不可能将这种差异本身确定为任何程序的瓶颈。

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

...但是我可以想象一维可能在CPU缓存中...

是的,但是2d也可能在CPU缓存中。 有关为什么1d仍然更好的说明,请参见缺点:内存局部性。

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

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

  • 紫色正方形是operator()本身占据的存储位置。
  • 绿色方块将存储区域operator()指向(4 x std::vector)。
  • 4个连续的蓝色正方形的4个区域分别是绿色区域中的每个operator()指向的区域

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

  • 绿色方块是唯一需要的指针operator()
  • 蓝色方块组合了所有矩阵元素的存储区域(16 x operator())。

Real 2d vs mapped 2d memory layout

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

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

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

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

长话短说:2d模式具有较高的高速缓存未命中率,而1d方案由于数据的局部性而具有更好的性能潜力。

频繁分配/取消分配

  • 创建所需的NxM(4×4)矩阵需要多达operator()(4 + 1 = 5)个分配(使用new,malloc,allocator :: allocate或其他方法)。
  • 也必须应用相同数量的适当的各自的重新分配操作。

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

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

内存消耗开销

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

让我们记住:我们要存储一个4×4 int矩阵,表示64个字节。

对于NxM矩阵,使用提出的指针到指针方案存储,我们消耗了

  • operator() [实际的蓝色数据] +
  • operator() [绿色指针] +
  • operator() [violet变量p]字节。

在本示例的情况下,这将产生operator()字节,而在使用std::vector时会变得更糟。它将需要new + N * sizeof(vector<int>) + sizeof(vector<vector<int>>)字节,即总共4*4*4 + 4*16 + 16 = 144字节,对于4 x 4 int,整数为64字节。

另外-根据所使用的分配器-每个单个分配可能会(而且很可能会)有另外16个字节的内存开销。 (一些“信息字节”用于存储已分配的字节数,以进行适当的重新分配。)

这意味着最坏的情况是:

operator()
std::vector

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

内存泄漏的风险

一堆分配需要适当的异常处理,以防止如果其中一个分配失败将导致内存泄漏!您需要跟踪分配的内存块,并且在释放内存时一定不要忘记它们。

如果operator()的内存不足并且无法分配下一行(特别是在矩阵很大时),则new将抛出std::vector

例:

在上面提到的new / delete示例中,如果要避免在operator()异常的情况下泄漏,我们将面临更多代码。

  // 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 ++方法”可能是编写一个类来管理您的内存,同时考虑诸如

  • 什么是三法则?
  • 资源获取是什么意思初始化(RAII)?
  • C ++概念:容器(在cppreference.com上)

为了提供这样一个类的外观的想法,下面是一个具有一些基本功能的简单示例:

  • 二维尺寸可构造
  • 2d可调整大小
  • operator()用于2d行主要元素访问
  • operator()用于检查的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);
  }

}

请注意以下几点:

  • operator()需要满足使用的std::vector成员功能的要求
  • operator()不执行任何“范围”检查
  • 无需自己管理数据
  • 不需要析构函数,复制构造函数或赋值运算符

因此,您不必费心为每个应用程序进行适当的内存处理,而只需为编写的类一次即可。

限制条件

在某些情况下,动态“真实”二维结构是有利的。 例如,如果

  • 矩阵非常大且稀疏(如果甚至不需要分配任何行,但可以使用nullptr对其进行处理),或者
  • 这些行没有相同数量的列(也就是说,如果您根本没有矩阵,而只有另一个二维结构)。
Pixelchemist answered 2019-10-15T20:42:10Z
17 votes

除非您在谈论静态数组,否则一维速度会更快。

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

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

这与动态2D数组(std::vector<std::vector<T>>)相同:

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

显然,二维情况会丢失缓存局部性并使用更多内存。 它还引入了一个额外的间接寻址(并因此引入了额外的指针),但是第一个数组具有计算索引的开销,因此这些索引或多或少地均匀。

Konrad Rudolph answered 2019-10-15T20:42:55Z
8 votes

一维和二维静态数组

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

  • 速度:您可以假设不会有速度差异,因为这两个阵列的内存应该是连续的(整个2D数组在内存中应显示为一个块,而不是一个一堆大块散布在内存中)。 (这可能是编译器但是取决于。)

一维和二维动态阵列

  • 大小:2D数组比1D数组需要更多的内存,这是因为2D数组中需要使用指向所分配的1D数组的指针。 (当我们谈论真正的大阵列时,这一点很小。对于小型阵列,相对而言,这点可能很大。)

  • 速度:1D阵列可能比2D阵列快,因为2D阵列的内存不是连续的,因此高速缓存未命中将成为问题。


使用可行的方法,并且看起来最合乎逻辑,如果遇到速度问题,请进行重构。

Mohamad Ali Baydoun answered 2019-10-15T20:44:00Z
5 votes

现有答案仅将一维数组与指针数组进行比较。

在C语言中(而不是C ++语言),有第三个选择; 您可以拥有一个连续分配的二维数组,该数组可以动态分配并具有运行时维度:

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

就像p[row_index][col_index]一样访问。

我希望它的性能与一维数组的情况非常相似,但是它为您提供了访问单元格的更好语法。

在C ++中,您可以通过定义一个在内部维护一维数组但可以使用重载运算符通过二维数组访问语法公开的类来实现类似的目的。 同样,我希望它具有与普通一维阵列相似或相同的性能。

M.M answered 2019-10-15T20:44:52Z
4 votes

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

Polymorphism answered 2019-10-15T20:45:17Z
1 votes

这实际上取决于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元素。 这不是一个直接的计算。 在某些计算机上(例如,具有36个字节(非位)指针的AS400),指针访问非常慢。 这完全取决于所使用的体系结构。 在x86类型的体系结构上,a和b的速度相同,c和d的速度慢于b。

cup answered 2019-10-15T20:45:50Z
0 votes

我喜欢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

在初始化时定义向量大小可提供最佳性能。 此解决方案是从此答案修改而来的。 函数可以重载以通过单个向量支持变化的尺寸。 该解决方案的缺点是M,N,P参数被隐式传递给get和set函数。 可以通过在类中实施解决方案来解决此问题,就像Pixelchemist所做的那样。

Adam Erickson answered 2019-10-15T20:46:36Z
translate from https://stackoverflow.com:/questions/17259877/1d-or-2d-array-whats-faster