c++ - 缓存友好矩阵，用于访问相邻单元格

Question

当前设计

在我的程序中，我有一个很大的2-D 网格(1000 x 1000，或更多)，每个单元格包含一个小信息。 为了表示这个概念，选择非常简单:矩阵数据结构。

相应的代码(在 C++ 中)是这样的:

int w_size_grid = 1000;
int h_size_grid = 1000;
int* matrix = new int[w_size_grid * h_size_grid];

如您所见，我使用了 vector ，但原理是相同的。

为了访问网格的元素，我们需要一个函数来给定网格中的一个单元格(由 (x,y) 标识)，它返回存储在该单元格中的值。

数学上: f(x,y) -> Z 明显地: f: Z^2 -> Z 其中 Z 是 integer numbers 的集合.

这可以通过线性函数 轻松实现。这是一个 C++ 代码表示:

int get_value(int x, int y) {
  return matrix[y*w_size_grid + x];
}

其他实现说明

实际上，设计概念需要一种“圆形连续网格”:单元格的访问索引可以超出网格本身的限制。 p>

这意味着，例如，特定情况:get_value(-1, -1); 仍然有效。该函数将返回与 get_value(w_size_grid - 1, h_size_grid -1); 相同的值。

其实这在实现上是没有问题的:

int get_value(int x, int y) {
  adjust_xy(&x, &y);  // modify x and y in accordance with that rule.
  return matrix[y*w_size_grid + x];
}

无论如何，这只是为了使场景更清晰的附加说明。

---

问题是什么？

上面提出的问题非常简单，易于设计和实现。

我的问题是矩阵更新频率很高。矩阵中的每个单元格都被读取并可能更新为新值。

显然，根据缓存友好设计，矩阵的解析是通过两个循环完成的:

for (int y = 0; y < h_size_grid; ++y) {
  for (int x = 0; x < w_size_grid; ++x) {
    int value = get_value(x, y);
  }
}

内部循环是 x 因为 [x-1] [x] [x+1] 是连续存储的。事实上，那个循环利用了 principle of locality .

现在问题来了，因为实际上为了更新单元格中的值，它取决于相邻单元格中的值。

每个单元格恰好有八个邻居，即水平、垂直或对角相邻的单元格。

(-1,-1) | (0,-1) | (1,-1)
-------------------------
(-1,0)  | (0,0)  | (0, 1)
-------------------------
(-1,1)  | (0,1)  | (1,1)

所以代码很直观:

for (int y = 0; y < h_size_grid; ++y) {
  for (int x = 0; x < w_size_grid; ++x) {
    int value = get_value(x, y);
    auto values = get_value_all_neighbours(x, y);  // values are 8 integer
  }
}

函数get_value_all_neighbours(x,y) 将访问矩阵中相对于y 向上一行和向下一行。 由于矩阵中的一行非常大，它涉及缓存未命中并弄脏缓存本身。

问题

我终于向您展示了场景和问题，我的问题是如何“解决”问题。

使用一些额外的数据结构，或重新组织数据是否有办法利用缓存并避免所有这些遗漏？

一些个人考虑

我的感受引导我走向战略数据结构。

我考虑过重新实现值在 vector 中的存储顺序，试图将相邻的单元格存储在连续的索引中。

这意味着 no-more-linear 函数用于 get_value。 经过一番思考，我认为不可能找到这个非线性函数。

我还想过一些额外的数据结构，例如哈希表来存储每个单元格的相邻值，但我认为这在空间上甚至在 CPU 周期上也是一种矫枉过正。

Answer 1

假设您确实遇到了无法轻易避免的缓存未命中问题(请参阅此处的其他答案)。

你可以使用 space filling curve以缓存友好的方式组织数据。本质上，空间填充曲线将体积或平面(例如您的矩阵)映射到线性表示，这样空间中靠得很近的值(大部分)在线性表示中靠得很近。实际上，如果您将矩阵存储在按 z 顺序排列的数组中，则相邻元素很可能位于同一内存页上。

最好的邻近映射可通过希尔伯特曲线获得，但计算成本很高。更好的选择可能是 z-curve (莫顿秩序)。它提供了良好的接近度并且计算速度很快。

Z 曲线:从本质上讲，要获得排序，您必须将 x 和 y 坐标的位交错为一个值，称为“z 值”。此 z 值确定矩阵值列表中的位置(如果使用数组，甚至可以简单地确定数组中的索引)。对于完全填充的矩阵(使用每个单元格)，z 值是连续的。相反，您可以取消交错列表中的位置(=数组索引)并取回您的 x/y 坐标。

交织两个值的位非常快，甚至有专门的 CPU 指令可以用很少的周期来做到这一点。如果你找不到这些(我现在找不到)，你可以简单地使用一些 bit twiddling tricks .