c++ - 分配/访问二维数组，使得二维子块是连续的

我有一个二维数组 SomeData* data[4096][4096] 。这里数据沿最后一个坐标是连续的，因此由于内存局部性，迭代 y 坐标比迭代 x 坐标更快。但是，我的访问模式是查看一个条目，然后查看两个坐标中的附近邻居，即 data[x][y] 和 data[x-1][y-1], data[x +1][y+1] 等。

如果我可以分配这个数组，使得小的 2d 子块在内存中是连续的，那将会加快速度。

我说分配，但我怀疑这里的解决方案是正常分配一个二维数组，然后对索引做一些技巧，这样我就可以连续访问二维块。换句话说，我想要一些转换坐标的查找函数，但我无法立即看到它应该是什么。

SomeData* data[4096][4096];

SomeData* lookup(size_t x, size_t y) {
    //??? Some logic to translate x,y such that 2d blocks are accessed contiguously.
}

数据数组保证两个维度都是 2 的幂。

最佳答案

假设我们有一个 nxm-grid。我们想将网格 segmentation 为 bxb 块。 n%b=0 和 m%b=0 是必要的。

让我们调用整体索引 I=0,...,n-1 和 J=0,...,m-1 以及块中的索引 i=0,...,b-1 和 j=0， ...,b-1。

我试图勾 Canvas 局 here 。

给定 I，块的列索引是 (I/b) 并且块内索引 i=I%b。块的行索引是 (J/b) 并且块内索引 j=J%b。

每个完整块都包含 b*b 元素。因此，整行块包含 (n/b)bb = n*b 元素。

将元素 (I,J) 的所有线性索引放在一起是:

(I%b) [块中元素前的列]

+(J%b) * b [元素前块中的行]

+(I/b) * b*b [元素块之前的块列]

+(J/b) * n*b [元素块之前的块行]

运行时大小的阻塞网格类的粗略草图:

template <typename T>
class Block_Grid
{
public:
  Block_Grid(std::size_t n, std::size_t m, std::size_t b)
  : _n(n), _m(m), _b(b), _elements(n * m)
  {
    assert(n % b == 0);
    assert(m % b == 0);
  }

  T & operator()(std::size_t i, std::size_t j)
  {
    return _elements[index(i, j)];
  }

protected:
private:
  std::size_t index(int i, int j) const
  {
    return (i % b)
           + (j % b) * b
           + (i / b) * b * b
           + (j / b) * n * b;
  }

  std::size_t _n;
  std::size_t _m;
  std::size_t _b;
  std::vector<T> _elements;
};

或编译时大小的类

template <typename T, std::size_t N, std::size_t M, std::size_t B>
class Block_Grid
{
  static_assert(N % B == 0);
  static_assert(M % B == 0);
public:
  Block_Grid() = default;

  T & operator()(std::size_t i, std::size_t j)
  {
    return _elements[index(i, j)];
  }

protected:
private:
  std::size_t index(std::size_t i, std::size_t j) const
  {
    return (i % B) + (j % B) * B + (i / B) * B * B + (j / B) * N * B;
  }

  std::array<T, N * M> _elements;
};

关于c++ - 分配/访问二维数组，使得二维子块是连续的，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/58709314/