Allocating/accessing 一个二维数组,使得二维子块是连续的
Allocating/accessing a 2d array such that 2d sub-blocks are contiguous
我有一个二维数组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。我们想将网格细分为 bxb 块。必须 n%b=0 和 m%b=0.
让我们调用整体索引 I=0,...,n-1 和 J=0,...,m-1 以及块中的索引 i=0,...,b-1并且 j=0,...,b-1.
我已经尝试绘制布局草图 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 [元素块之前的块行]
运行时大小的块状网格的粗略草图-class:
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;
};
或编译时大小的 class
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;
};
我有一个二维数组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。我们想将网格细分为 bxb 块。必须 n%b=0 和 m%b=0.
让我们调用整体索引 I=0,...,n-1 和 J=0,...,m-1 以及块中的索引 i=0,...,b-1并且 j=0,...,b-1.
我已经尝试绘制布局草图 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 [元素块之前的块行]
运行时大小的块状网格的粗略草图-class:
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;
};
或编译时大小的 class
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;
};