内存布局:2D N * M数据作为指向N * M缓冲区的指针或作为指向数组的N指针数组

我对如何组织2D数据的内存布局犹豫不决。 基本上,我想要的是N * M 2D doublearrays,其中N~M是数千(并且来自用户提供的数据)

我看到它的方式,我有两个选择:

 double *data = new double[N*M]; 

要么

 double **data = new double*[N]; for (size_t i = 0; i < N; ++i) data[i] = new double[M]; 

第一个选择是我倾向于。 我看到的主要优点是更短的新/删除语法,如果我正确安排访问,连续内存布局意味着在运行时相邻内存访问,并且可能更好地实现矢量化代码(自动矢量化或使用矢量库,如vDSP或vecLib)

另一方面,在我看来,与分配一堆较小的连续内存相比,分配大量连续内存可能会失败/花费更多时间。 并且第二种方法还具有与data[i*M+j]相比较短的语法data[i][j]的优点

最常见/更好的方法是什么,主要是如果我尝试从性能角度来看它(尽管那些将是小改进,我很好奇看哪哪个会更好)。

在前两个选项之间,对于MN合理值,我几乎肯定会选择1.您跳过指针取消引用,如果以正确的顺序访问数据,则可以获得良好的缓存。

就您对尺寸的担忧而言,我们可以做一些背后的计算。

由于MN是数千,因此假设每个都是10000作为上限。 然后你消耗的总内存是

  10000 * 10000 * sizeof(double) = 8 * 10^8 

这大约是800 MB,虽然很大,但考虑到现代机器中的内存大小,这是非常合理的。

如果NM是常量,最好只是静态地声明你需要的内存作为二维数组。 或者,您可以使用std::array

 std::array, N> data; 

如果只有M是常量,则可以使用std::vector作为std::array

 std::vector> data(N); 

如果M不是常数,则需要执行一些动态分配。 但是, std::vector可以用来为你管理那个内存,所以你可以创建一个简单的包装器。 下面的包装器返回一个row中间对象,以允许第二个[]运算符实际计算vector的偏移vector

 template  class matrix { const size_t N; const size_t M; std::vector v_; struct row { matrix &m_; const size_t r_; row (matrix &m, size_t r) : m_(m), r_(r) {} T & operator [] (size_t c) { return m_.v_[r_ * m_.M + c]; } T operator [] (size_t c) const { return m_.v_[r_ * m_.M + c]; } }; public: matrix (size_t n, size_t m) : N(n), M(m), v_(N*M) {} row operator [] (size_t r) { return row(*this, r); } const row & operator [] (size_t r) const { return row(*this, r); } }; matrix data(10,20); data[1][2] = .5; std::cout << data[1][2] << '\n'; 

解决您对性能的特殊关注:您希望单个内存访问的理由是正确的。 你应该想避免做new并自己delete (这是这个包装器提供的东西),如果数据更自然地被解释为多维,那么在代码中显示代码也会使代码更容易阅读。

你的第二种技术中显示的多次分配是次要的,因为它需要更多的时间,但它的优点是,如果你的系统是碎片的,它可能会更频繁地成功(免费记忆由较小的洞组成,你没有一个免费的大块内存足够大以满足单个分配请求)。 但是多个分配还有另一个缺点,即需要更多内存来为每行指针分配空间。

我的建议提供单一分配技术,无需显式调用newdelete ,因为内存由vector管理。 同时,它允许使用二维语法[x][y]来寻址数据。 因此,只要您有足够的内存来满足分配请求,它就可以提供单个分配的所有好处以及多分配的所有好处。

考虑使用以下内容:

 // array of pointers to doubles to point the beginning of rows double ** data = new double*[N]; // allocate so many doubles to the first row, that it is long enough to feed them all data[0] = new double[N * M]; // distribute pointers to individual rows as well for (size_t i = 1; i < N; i++) data[i] = data[0] + i * M; 

我不确定这是否是一般的做法,我只是想出了这个。 一些下降仍然适用于这种方法,但我认为它消除了大多数,如能够访问像data[i][j]等所有的双重双打。