28

我正在用 Rust 编写一个线性代数库。

我有一个函数可以在给定的行和列中获取对矩阵单元的引用。此函数以行和列在界限内的一对断言开始：

#[inline(always)]
pub fn get(&self, row: usize, col: usize) -> &T {
    assert!(col < self.num_cols.as_nat());
    assert!(row < self.num_rows.as_nat());
    unsafe {
        self.get_unchecked(row, col)
    }
}

在紧密循环中，我认为跳过边界检查可能会更快，所以我提供了一个get_unchecked方法：

#[inline(always)]
pub unsafe fn get_unchecked(&self, row: usize, col: usize) -> &T {
    self.data.get_unchecked(self.row_col_index(row, col))
}

奇怪的是，当我使用这些方法来实现矩阵乘法（通过行和列迭代器）时，我的基准测试表明，当我检查边界时，它实际上快了大约 33%。为什么会这样？

我在两台不同的计算机上试过这个，一台运行 Linux，另一台运行 OSX，都显示了效果。

完整代码在 github 上。相关文件是lib.rs。感兴趣的函数是：

  • get在第 68 行
  • get_unchecked在第 81 行
  • next在第 551 行
  • mul在第 796 行
  • matrix_mul（基准）在第 1038 行

请注意，我使用类型级别的数字来参数化我的矩阵（也可以通过虚拟标记类型选择动态大小），因此基准是两个 100x100 矩阵相乘。

更新：

我已经大大简化了代码，删除了基准测试中没有直接使用的东西并删除了通用参数。我还编写了一个不使用迭代器的乘法实现，并且该版本不会产生相同的效果。有关此版本的代码，请参见此处。克隆minimal-performance分支并运行cargo bench将对乘法的两种不同实现进行基准测试（请注意，断言在该分支开始时已被注释掉）。

另外值得注意的是，如果我更改get*函数以返回数据的副本而不是引用（f64而不是&f64），效果就会消失（但代码会稍微慢一点）。

4

1 回答 1

2

这不是一个完整的答案，因为我没有测试我的说法，但这可能会解释它。无论哪种方式，唯一确定的方法是生成 LLVM IR 和汇编器输出。如果您需要 LLVM IR 手册，可以在此处找到：http: //llvm.org/docs/LangRef.html。

无论如何，足够了。假设您有以下代码：

#[inline(always)]
pub unsafe fn get_unchecked(&self, row: usize, col: usize) -> &T {
    self.data.get_unchecked(self.row_col_index(row, col))
}

此处的编译器将其更改为间接加载，这可能会在紧密循环中进行优化。有趣的是，每次加载都有可能出错：如果您的数据不可用，则会触发越界。

在边界检查与紧密循环相结合的情况下，LLVM 做了一个小技巧。因为负载处于紧密循环（矩阵乘法）中，并且由于边界检查的结果取决于循环的边界，所以它将从循环中删除边界检查并将其放在循环周围。换句话说，循环本身将保持完全相同，但有一个额外的边界检查。

换句话说，代码完全相同，只是有一些细微的差别。

那么发生了什么变化？两件事情：

  1. 如果我们有额外的边界检查，则不再有可能出现越界加载。这可能会触发以前不可能的优化。不过，考虑到这些检查通常是如何实施的，这不是我的猜测。

  2. 要考虑的另一件事是“不安全”这个词可能会触发一些行为，例如附加条件、固定数据或禁用 GC 等。我不确定 Rust 中的这种确切行为；找出这些细节的唯一方法是查看 LLVM IR。

于 2017-01-19T09:16:50.277 回答