Rust 中的自定义缓存对齐

Question

如何针对大量行优化 Rust 中的 RowMatrix 结构的性能？

我使用 Rust 中的结构以 RowMajor 形式定义了一个矩阵，如下所示：

pub struct RowMatrix
{
    data: Vec<[usize; 8]>,
    width: usize,
}

每一行被分解为一个由 8 个元素组成的数组，并在

data

向量中逐个堆叠。例如，如果宽度为 64，则向量中的前 8 个元素代表第一行，接下来的 8 个元素代表第二行，依此类推。

我需要对属于该矩阵的同一索引处的两个单独行的各个数组执行操作。例如，如果我想对第 1 行和第 10 行的第 2 个数组段执行操作，我将分别从数据向量中选取第 2 个和第 74 个元素。数组元素将始终来自同一数组段。

此操作使用不同的行对执行多次，并且当矩阵中的行数较小时，我没有看到任何性能问题。然而，当行数很大时，我发现性能显着下降，我将其归因于频繁的缓存未命中。

有没有一种方法可以在不更改结构定义的情况下沿着缓存行自定义对齐结构以减少缓存未命中？我想以细粒度级别控制内存中元素的布局，例如在缓存中保留 8 个元素相距的元素（如果矩阵的宽度为 64）。

我使用

repr(align(x))

属性来指定结构体的对齐方式，但我认为它没有帮助，因为我认为它以顺序方式保持数组元素，并且在大矩阵的情况下，各个元素可能不在缓存中.

Answer 1

#[repr(align)]

只能影响存储在结构体中的项目（

Vec

指针、长度和容量加上你的

width

），但由于

Vec

只不过是一个指向数据的指针，它背后的布局完全是由它的实现决定，您无法直接影响它。因此，“在不更改结构定义的情况下”不可能更改布局。但是，您可以创建类似自定义的

Vec

或直接在

RowMatrix

中自行管理内存

Answer 2

您的术语有点令人困惑，但听起来您在矩阵上执行的操作实际上更适合列主矩阵？

据我了解，您执行的操作对每个（？）行的第n数组元素（这是正确的术语，而不是“段”）进行操作 - 或者更确切地说，跨第n列。但是，由于您使用的是行主序，这些元素/列单元位于内存中物理上较远的不同子数组中。如果您使用列优先顺序，则所有第 n 列元素将位于单个数组中。

另外，数据结构需要可修改吗？我想这取决于应用程序，但我习惯使用的大多数矩阵往往是固定大小的。在这种情况下，它使实现变得“更加容易”，并消除了与使用 Vector 作为内部数据结构相关的开销。 （如果您在构造过程中需要灵活性，您可以创建一个单独的构建器类型。）至于大小调整方面的通用灵活性，您可以使用 const generics 来调整结构体内部数组的大小。 类似：

struct ColMatrix<T: Sized, const NUM_ROWS: usize, const NUM_COLS: usize> {
  data: [[T; NUM_ROWS]; NUM_COLS],
  //width is now implied by the type parameters
}

与相同的概念相比，但按行主序排列，正如您目前所拥有的：

struct RowMatrix<T: Sized, const NUM_ROWS: usize, const NUM_COLS: usize> {
  data: [[T; NUM_COLS]; NUM_ROWS],
}

将同一列的所有元素放置在同一内存段中应该会大大降低缓存未命中率，因为 CPU 需要在缓存中拥有的内存（以操作同一列的所有元素）现在将是单个内存，连续线段，因而闭合。在 8 个 

usize

元素的情况下，根据您的示例，它将适合单个缓存行（64 字节），这将使其

非常

快。 如果您需要通过添加更多行来修改矩阵

在您开始执行该操作之后

，那么麻烦当然会随之而来，因为必须向所有内部数组插入额外的元素有点尴尬......就像，非常慢。但是，如果矩阵的大小在构造后是固定的，如上所述，您可以创建一个单独的构建器类型来协助构造（然后可以按行主序使用 Vec 来轻松灵活地添加行添加，然后在构造实际对象时翻转顺序即可）。