matrix - 高效地从向量中提取任意切片

Question

这与我的帖子有点相关here .

我正在尝试在 Rust 中实现矩阵乘法，我认为为了有效地执行此操作，我需要能够从矩阵中获取列数据。这很困难，因为我以行优先格式存储我的矩阵。

我正在使用展开的点积实现，在上面 link 中有详细说明还有我之前的 question .我希望能够为该方法提供一个矩阵的行和另一个矩阵的列。

如何有效地从矩阵中选择列数据？更一般地说:我如何选择任意数据模式(如在 R、matlab、numpy 等中)？

我试过:

1. 使用跨步 View 并收集迭代器 - 这似乎太慢了。
2. 使用标准的 for 循环迭代，但这似乎没有被 Rust 编译器矢量化。

Answer 1

如果您使用更聪明的 for 循环，您就会得到问题的答案。我的意思是，如果您重新排序 for 循环，则不必从矩阵中抽出一列。这样，您就可以让 CPU 缓存保持温暖。

如果您当前的算法如下所示:

// traditional multiplication
for i in 0..a_rows {
    for j in 0..b_cols {
        for k in 0..a_cols {
            c[i][j] += a[i][k] * b[k][j];
        } 
    }
}

由于 b[k][j] 不按顺序访问您的数据，因此您会产生大量缓存未命中。

for i in 0..a_rows {
    for k in 0..a_cols {
        // Note, that j iterates over a column of B
        for j in 0..b_cols {
            c[i][j] += a[i][k] * b[k][j];
        } 
    }
}

如果您交换两个内部循环，您将按顺序迭代 B 的列并利用您的缓存。首先，您将访问 b[k][0]，然后是 b[k][1] 等等。如果一个元素是 4 字节，您可以直接从缓存中访问下一个 12 元素(因为 64 字节是最常见的 L1 缓存行大小)。传统方法不能如此有效地使用缓存。