如何以非线性方式在 C++ 中保存矩阵
How to save a matrix in C++ in a non-linear way
我必须为 Levenshtein 距离问题编写一个优化的多线程实现。它可以使用矩阵的动态规划来计算，wikipedia page on Levenshtein distance 足以涵盖这一点。
现在，我可以同时计算对角线元素了。没关系。
我现在的问题是缓存。 C++ 中的矩阵通常逐行保存在内存中，对吗？好吧，这对我不利，因为我需要前一行的 2 个元素和当前行的 1 个元素来计算我的结果，这在缓存方面很糟糕。缓存将保存当前行（或其中的一部分），然后我请求它可能不再保存的前一行。
然后对于另一个，我需要对角线的不同部分，所以再一次，我要求完全不同的行，缓存不会为我准备好那些。
因此，我想将我的矩阵以块或对角线的形式保存到内存中。这将导致更少的 cachce 未命中并再次使我的实现更快。
你是怎么做到的？我试着在互联网上搜索，但我找不到任何能给我指路的东西。是否可以告诉 c++ 如何在内存中排序该类型？
编辑：你们中的一些人似乎对我的问题的性质感到困惑。我想以自定义方式将矩阵（无论我将其设为二维数组还是任何其他方式）保存到 MEMORY 中。通常，二维数组会逐行保存，我需要使用对角线，因此缓存会在我将要处理的巨大矩阵（可能有数百万行和列）上遗漏很多。
我不是很确定，但我认为矩阵存储为一行接一行的长数组，并使用指针算法映射到矩阵，因此您总是引用相同的地址并计算距离在你的值所在的内存中
否则你可以很容易地实现它作为这种类型并为你的矩阵实现 operator[int, int]
相信您可能对(CPU) 缓存存在误解。
确实 CPU 缓存是线性的 - 也就是说，如果您访问内存中的地址，它会将一些先前和一些连续的内存位置带入缓存 - 这就像 "guessing"随后的访问将涉及 1-dimensional-close 元素。但是，在微观层面上确实如此。 CPU 的缓存由大量小 "lines" 组成（在最近的 Intel CPU 中，所有缓存级别均为 64 字节）。地域限行；不同的缓存行可以来自内存中完全不同的位置。
因此，如果您 "need two elements of the previous row and one element of the current row" 您的矩阵，那么缓存应该非常适合您：一些缓存将保存前一行的元素，一些将保存当前行的元素。当您前进到下一个元素时，整个缓存通常会包含您需要访问的矩阵元素。只需确保您的迭代顺序与缓存行中的进展顺序一致。
此外，在某些情况下，由于从主内存到缓存的映射，您可能会遇到不同的线程正在抖动相同的缓存行的情况。无需详细说明， 是 您需要考虑的事情（但同样，与 2D 和 1D 数据无关）。
编辑： 正如 geza 指出的那样，如果矩阵的行很长，您仍然会使用直接的方法读取每个内存位置两次：一次作为当前行，然后再次作为上一行，因为每个值在用作上一行值之前都会从缓存中逐出。如果您想避免这种情况，您可以遍历矩阵的 tiles，其大小（长度 x 宽度 x sizeof(element)）适合 L1 缓存（以及任何其他需要在那里）。您还可以考虑 将数据存储 在磁贴中，但我认为这不会太有用。
初评："Levenshtein distance"为编辑距离（一般定义下）。这是一个很常见的问题；您可能甚至不需要费心自己编写解决方案。查找现有代码。
现在，最后，为了一个正确的答案......你实际上根本不需要一个矩阵，你当然不需要 "save" 它：只保留一个 "front" 你的动态规划矩阵而不是整个事情。
但是"front"你会选择什么，如何推进呢？我建议你使用反对角线作为你的前沿，并给定每个反对角线，同时计算下一个反对角线。因此它将是 {(0,0)}，然后是 {(0,1),(1,0)}，然后是 {(0,2),(1,1),(2,0)} 等等在。每个反对角线最多需要两个较早的反对角线 - 如果我们将每个反对角线的值连续保存在内存中，那么下一个反对角线的访问模式是沿着前一个反对角线的线性进展 -这对缓存很有用（见我的）。
因此，您将 "concurrentize" 计算给每个线程一组连续的反对角元素来计算；这应该够了吧。并且在任何时候你只会在内存中保留 3 个反对角线：你正在处理的一个和之前的两个。您可以在三个这样的缓冲区之间循环，这样您就不会一直重新分配内存（但要确保预先分配具有最大对角线长度的缓冲区）。
对于非正方形的情况，整个过程应该基本相同。
我必须为 Levenshtein 距离问题编写一个优化的多线程实现。它可以使用矩阵的动态规划来计算，wikipedia page on Levenshtein distance 足以涵盖这一点。
现在，我可以同时计算对角线元素了。没关系。
我现在的问题是缓存。 C++ 中的矩阵通常逐行保存在内存中，对吗？好吧，这对我不利，因为我需要前一行的 2 个元素和当前行的 1 个元素来计算我的结果，这在缓存方面很糟糕。缓存将保存当前行（或其中的一部分），然后我请求它可能不再保存的前一行。 然后对于另一个，我需要对角线的不同部分，所以再一次，我要求完全不同的行，缓存不会为我准备好那些。
因此，我想将我的矩阵以块或对角线的形式保存到内存中。这将导致更少的 cachce 未命中并再次使我的实现更快。
你是怎么做到的？我试着在互联网上搜索，但我找不到任何能给我指路的东西。是否可以告诉 c++ 如何在内存中排序该类型？
编辑：你们中的一些人似乎对我的问题的性质感到困惑。我想以自定义方式将矩阵（无论我将其设为二维数组还是任何其他方式）保存到 MEMORY 中。通常，二维数组会逐行保存，我需要使用对角线，因此缓存会在我将要处理的巨大矩阵（可能有数百万行和列）上遗漏很多。
我不是很确定，但我认为矩阵存储为一行接一行的长数组，并使用指针算法映射到矩阵，因此您总是引用相同的地址并计算距离在你的值所在的内存中
否则你可以很容易地实现它作为这种类型并为你的矩阵实现 operator[int, int]
相信您可能对(CPU) 缓存存在误解。
确实 CPU 缓存是线性的 - 也就是说，如果您访问内存中的地址，它会将一些先前和一些连续的内存位置带入缓存 - 这就像 "guessing"随后的访问将涉及 1-dimensional-close 元素。但是，在微观层面上确实如此。 CPU 的缓存由大量小 "lines" 组成（在最近的 Intel CPU 中，所有缓存级别均为 64 字节）。地域限行；不同的缓存行可以来自内存中完全不同的位置。
因此，如果您 "need two elements of the previous row and one element of the current row" 您的矩阵，那么缓存应该非常适合您：一些缓存将保存前一行的元素，一些将保存当前行的元素。当您前进到下一个元素时，整个缓存通常会包含您需要访问的矩阵元素。只需确保您的迭代顺序与缓存行中的进展顺序一致。
此外，在某些情况下，由于从主内存到缓存的映射，您可能会遇到不同的线程正在抖动相同的缓存行的情况。无需详细说明， 是 您需要考虑的事情（但同样，与 2D 和 1D 数据无关）。
编辑： 正如 geza 指出的那样，如果矩阵的行很长，您仍然会使用直接的方法读取每个内存位置两次：一次作为当前行，然后再次作为上一行，因为每个值在用作上一行值之前都会从缓存中逐出。如果您想避免这种情况，您可以遍历矩阵的 tiles，其大小（长度 x 宽度 x sizeof(element)）适合 L1 缓存（以及任何其他需要在那里）。您还可以考虑 将数据存储 在磁贴中，但我认为这不会太有用。
初评："Levenshtein distance"为编辑距离（一般定义下）。这是一个很常见的问题；您可能甚至不需要费心自己编写解决方案。查找现有代码。
现在，最后，为了一个正确的答案......你实际上根本不需要一个矩阵，你当然不需要 "save" 它：只保留一个 "front" 你的动态规划矩阵而不是整个事情。
但是"front"你会选择什么，如何推进呢？我建议你使用反对角线作为你的前沿，并给定每个反对角线，同时计算下一个反对角线。因此它将是 {(0,0)}，然后是 {(0,1),(1,0)}，然后是 {(0,2),(1,1),(2,0)} 等等在。每个反对角线最多需要两个较早的反对角线 - 如果我们将每个反对角线的值连续保存在内存中，那么下一个反对角线的访问模式是沿着前一个反对角线的线性进展 -这对缓存很有用（见我的
因此，您将 "concurrentize" 计算给每个线程一组连续的反对角元素来计算；这应该够了吧。并且在任何时候你只会在内存中保留 3 个反对角线：你正在处理的一个和之前的两个。您可以在三个这样的缓冲区之间循环，这样您就不会一直重新分配内存（但要确保预先分配具有最大对角线长度的缓冲区）。
对于非正方形的情况，整个过程应该基本相同。